The Advertisement and Query Language

Language for Advertisement and Request for Knowledge Sharing

Service matchmaking in a multiagent system requires a common agent capability description language (ACDL) for two main purposes:

  1. Advertisement of capabilities as a provider, and
  2. Requests for knowledge sharing in terms of information about capabilities of other provider agents.
We propose such an ACDL, called LARKS. In any scenario of service matchmaking there are the following different kinds of collaborating information agents: Each agent, as a requester or provider, creates and maintains a
  1. Set of requests or advertisements written in LARKS, and a
  2. Domain Ontology containing descriptions of concepts in the agent's local domain(s). Such an ontology can be defined, e.g.,
In our implementation of the matchmaking process we assume the ontology to be a terminology defined in the concept language ITL (Information Terminological Language). The concepts are described in ITL by the user, the agent's administrator, or are imported from other agents. The details of syntax and semantics of LARKS and the ITL as well as comprehensive examples of the matchmaking process can be found in (Sycara, Lu, Klusch, 1998).

Advertisements and Requests in LARKS

A specification in LARKS is a frame with the following structure:

Context: Context of specification
Types: Declaration of used variable types
Input: Declaration of input variables
Output: Declaration of output variables
InConstraints: Constraints on input variables
OutConstraints: Constraints on output variables
ConcDescfriptions: Ontological Descriptions of used words

The frame slot types have the following meaning (see examples below):

Every specification in LARKS can be interpreted as an advertisement as well as a request; this depends on the purpose an agent sends a specification to some matchmaker agent(s) for. Every Larks specification must be wrapped up in an appropriate KQML message by the sending agent indicating if the message content is to be treated as a request or an advertisement.

Examples for Specifications in LARKS

The following two examples show how to describe in LARKS the capability to sort a given list of items, and return the sorted list. Example 1 is the the specification of the capability to sort a list of at most 100 integer numbers, whereas in example 2 a more generic kind of sorting real numbers or strings is specified in LARKS.


Context: Sort
Input: xs: ListOf Integer;
Output: ys: ListOf Integer;
InConstraints: le(length(xs),100);
before(x,y,ys) <- ge(x,y);
before(x,y,ys) <- preceeds(x,y);
in(x,ys) <- in(x,xs);


Context: Sorting
Input: xs: ListOf Real|String;
Output: ys: ListOf Real|String;
before(x,y,ys) <- ge(x,y);
before(x,y,ys) <- preceeds(x,y);
in(x,ys) <- in(x,xs);

LARKS offers the option to use application domain knowledge in any advertisement or request. This is done by using a given local ontology for describing the meaning of a word in a LARKS specification. As mentioned before, local ontologies can be formally defined using, e.g., concept languages such as ITL, BACK, LOOM, CLASSIC or KRIS, or a full-fledged first order predicate logic, such as the knowledge interchange format (KIF).
The main benefit of that option for the user is that he can specify in a more detail of what he is requesting or advertising. The matchmaker agent is able to make automated inferences on such kind of additional semantic descriptions while matching LARKS specifications, thereby improving the overall quality of matching.
Any attachment of a concept in a given ontology to a used word W is done by the ^-operator in LARKS: W^C. The concept C must be defined in the local ontology of the agent or given by the user.
Please note that the attachment of concepts to words in a LARKS specification is an option. The process of matching two specifications with attachments is more complex in terms of time and computation than without.


Context: Computer^Computer;
brands: SetOf Brand^Brand;
areas: SetOf State;
processor: SetOf CPU^CPU;
priceLow^LowPrices: Integer;
priceHigh^HighPrices: Integer;
Info: ListOf(model: Model^ComputerModel, brand: Brand^Brand,
price: Price^Money, color: Color^Colors);
OutConstraints: sorted(Info).
Product = (and (all is-manufactured-by Brand) (atleast 1 is-manufactured-by) (all has-price Price))
Computer = (and Product (exists has-processor CPU) (all has-memory Memory) (all is-model ComputerModel))
ComputerModel = aset(HP-Vectra,PowerPC-G3,Thinkpad380,Thinkpad770,Satellite315)
CPU = aset(Pentium,K6,PentiumII,G3,Merced)
Brand = (and Company (all is-located-in State))
State = (and (all part-of Country) aset(VA,PA,TX,OH,NY))
Company = aset(IBM,Toshiba,HP,Apple,DEC,Dell,Gateway)
Colors = aset(Blue,Green,Yellow,Red)
Money = (and Real (all in-currency aset(USD,DM,FF,Y,P)))
LowPrice = (and Price (<= 1800) (exists in-currency aset(USD)))
HighPrice = (and Price (<= 50000)(exists in-currency aset(USD)))

Most words in this specification have been attached with a name of concept in a given local ontology. In our current implementation we assume the underlying ontology to be written in the concept language ITL. A generic interface for using different kinds of ontologies in LARKS will be provided in near future.

Concept Languages for Knowledge Representation

The research area on concept languages in AI has its origins in the theoretical deficiencies of semantic networks in the late 70's. KL-ONE was the first concept language providing a well-founded semantic for a more native language-based description of knowledge. Since then different concept languages are intensively investigated; they are almost decidable fragments of first-order predicate logic. Several knowledge representation and inference systems, like CLASSIC, BACK, KRIS, TEWIS or CRACK, based on such languages are available.
Conceptual knowledge about a given application domain, or even common-sense, is defined by a set of concepts and roles as terms in the given language; each term as a definition of some concept C is a conjunction of logical constraints which are necessary for any object to be an instance of C. For example:

Product   <=
  (and (all is-manufactured-by Brand) (atleast 1 is-manufactured-by) (all has-price Price))

Computer   <=
  (and Product (exists has-processor CPU) (all has-memory Memory) (all is-model ComputerModel))

Notebook   <=
  (and Computer (all has-price (and (and (>= 1000) (<= 2999)) (all in-currency aset(USD)) )
  (all has-weight (and kg (<= 5)) (all is-manufactured-by Company))
  (all is-model aset(Thinkpad380,Thinkpad770,Satellite315))))

ComputerModel   <= aset(HP-Vectra,PowerPC-G3,Thinkpad380,Thinkpad770,Satellite315)

CPU   <= aset(Pentium,K6,PentiumII,G3,Merced)

The set of terminological definitions forms a terminology. Any undefined word in a terminology is assumed to be a primitive component, i.e., its semantic is known and consistently used across boundaries.
One of the main inferences on terminological knowledge bases is the so-called concept subsumption: A concept C subsumes another concept C' if the extension of C' is a subset of that of C, i.e., the logical constraints defined in the term of concept C' logically imply those of the more general concept C. Any concept language is decidable if it is for concept subsumption among two concepts defined in this language. The computation of subsumption relationships among all concepts in a terminology leads to a concept hierarchy.

The concept language ITL we use as a sublanguage of LARKS for describing the meaning of words in the input and output declarations or constraints (in an advertisement or request) is NP-complete decidable. The well-known trade-off between expressiveness and tractability of concept languages in practice is surrounded almost by subsumption algorithms which are sound but incomplete - so we do.

The next example is a specification of the capability to buy stocks in a stock market under some given constraints.

Selling stocks by a portfolio agent

Context: Stock^StockInMarket;
symbol: StockSymbols;
yourMoney: Money^Money;
shares: Money^Money;
yourStock: StockSymbols;
yourShares: Money^Money;
yourChange: Money^Money;
InConstraints: yourMoney >= shares*currentPrice(symb);
yourMoney = yourChange+shares*currentPrice(symb);
yourShares = shares; yourStock = symbol;
ConcDescriptions: [StockInMarket, Money]

[StockInMarket, Money] means that the definitions of the concepts StockInMarket and Money were already sent to the matchmaker agent.

Matchmaking RETSINA project