The Advertisement and Query Language
`LARKS`

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:

Advertisement of capabilities as a provider, and
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:

Provider agents provide their capabilities, e.g., information search services, retail electronic commerce for special products, etc., to their users and other agents;
Requester agents consume informations and services provided by provider agents available in the system;
Matchmaker agents mediate among both, requesters and providers, for some mutually beneficial cooperation. For this purpose each provider agent must first register himself at a matchmaker by advertising his capabilities by sending some appropriate specifications written in LARKS. With this information the matchmaker is able to match receiving requests with his actual set of capability descriptions or advertisements, thereby finding relevant providers for requester agents.

Each agent, as a requester or provider, creates and maintains a

Set of requests or advertisements written in LARKS, and a
Domain Ontology containing descriptions of concepts in the agent's local domain(s). Such an ontology can be defined, e.g.,
- as a terminology in a concept language such as CLASSIC, LOOM, KRIS or ITL.
- in a full-fledged first-order predicate logic such as the Knowledge Interchange Format KIF.
- in the Unified Modeling Language UML.

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):

Context. The context of the specification in the local domain of the agent.
Types.
Optional definition of the used data types. If not used all data types are assumed to be defined in the following slots for input and output variables.
Input and Output.
Input/output variables for required input/output knowledge to describe a capability of an agent: if the input given to an agent fits with the specified input declaration part, then the agent is able to process an output as specified in the output declaration part. Processing takes all specified constraints on the input and output variables into consideration.
InConstraints and OutConstraints.
Logical constraints on input/output variables in the input/output declaration part. The constraints are finite program clauses, e.g., Horn clauses.
ConcDescriptions.
Optional description of the meaning of words used in the specification. The description relies on concepts in a given local domain ontology. Attachement of a concept C to a word w in any of the slots above is done in the form: w*C. That means that the concept C is the ontological description of the word w. The concept C is included in the slot ConcDescription if it has not already been sent to the matchmaker.

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.

IntegerSort

Context: Sort

Types:

Input: xs: ListOf Integer;

Output: ys: ListOf Integer;

InConstraints: le(length(xs),100);

OutConstraints:

before(x,y,ys) <- ge(x,y);

before(x,y,ys) <- preceeds(x,y);

in(x,ys) <- in(x,xs);

ConcDescriptions:

GenericSort

Context: Sorting

Types:

Input: xs: ListOf Real|String;

Output: ys: ListOf Real|String;

InConstraints:

OutConstraints:

before(x,y,ys) <- ge(x,y);

before(x,y,ys) <- preceeds(x,y);

in(x,ys) <- in(x,xs);

ConcDescriptions:

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.

FindComputerInfo

Context: Computer^Computer;

Types:

Input:

brands: SetOf Brand^Brand;

areas: SetOf State;

processor: SetOf CPU^CPU;

priceLow^LowPrices: Integer;

priceHigh^HighPrices: Integer;

Output:

Info: ListOf(model: Model^ComputerModel, brand: Brand^Brand,
price: Price^Money, color: Color^Colors);

InConstraints:

OutConstraints: sorted(Info).

ConcDescriptions:

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;

Types:

Input:

symbol: StockSymbols;

yourMoney: Money^Money;

shares: Money^Money;

Output:

yourStock: StockSymbols;

yourShares: Money^Money;

yourChange: Money^Money;

InConstraints: yourMoney >= shares*currentPrice(symb);

OutConstraints:

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

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

`Context`:	Sorting
`Types`:
`Input`:	xs: ListOf Real\|String;
`Output`:	ys: ListOf Real\|String;
`InConstraints`:
`OutConstraints`:
	before(x,y,ys) <- ge(x,y);
	before(x,y,ys) <- preceeds(x,y);
	in(x,ys) <- in(x,xs);
`ConcDescriptions`:

`Context`:	Computer^Computer;
`Types`:
`Input`:
	brands: SetOf Brand^Brand;
	areas: SetOf State;
	processor: SetOf CPU^CPU;
	priceLow^LowPrices: Integer;
	priceHigh^HighPrices: Integer;
`Output`:
`Output`:	Info: ListOf(model: Model^ComputerModel, brand: Brand^Brand, price: Price^Money, color: Color^Colors);
`InConstraints`:
`OutConstraints`:	sorted(Info).
`ConcDescriptions`:
	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)))

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

The Advertisement and Query Language LARKS

Language for Advertisement and Request for Knowledge Sharing

Advertisements and Requests in LARKS

Examples for Specifications in LARKS

The Advertisement and Query Language
`LARKS`

Advertisements and Requests in `LARKS`

Examples for Specifications in `LARKS`