UMDL Service Classifier Agent Demo:
Programmer's Interface

This document is intended for programmers who are developing agents which communicate with the UMDL Service Classifier Agent (SCA). We assume that the reader is already familiar with protocols for communicating between UMDL agents.

This document specifies the SCA's performative interface, and the languages for describing agent services. The performative interface includes functions to facilitate sending and receiving messages within the UMDL society of agents. The languages for describing services are very expressive, and are therefore relatively complex compared to performatives. They have a Lisp-like flavor, and use symbols from the UMDL ontology and the Loom description logic system. The languages for classifications and queries are similar, but distinct. Service descriptions fit into the :content field of the UMDL performatives used to request a classification or query.

Contents

Performative Interface
	Classification
	Queries

Service Description Languages
	Classification
		Loom Grammar
	Queries
		Loom Grammar
		SCA Predicates
		SCA Wrappers

Performative Interface

The SCA is considered part of the infrastructure of the UMDL. As such, its service label is fixed. The service label is ServiceClassifier.

The SCA is packaged with a library of interface functions. Include the header file sca.interface.H in source which sends or receives messages to/from the SCA, and link using the library libsca.interface.a.

Some developers may prefer to forego use of the convenient functions in the sca.interface library. Because the KQML philosophy calls for KQML to be a level of common language understood by all participating agents, we don't treat the interface library as an inviolable package. Instead, this document describes the internal KQML structure as well as the packaged interface functions.

Classification

Before advertising in a registry, use the SCA to classify a description of the service your agent provides. Then advertise in a registry using the SCA service label as the value of the :service-label performative field.

Sending

To prepare a performative to send to the SCA for a classification, call the following function to add information to the PerfArg pa.

void addSCAClassifyInfo (	const char* requested_label,
				const char* service_description,
		       		const char* reply_with,
	       			PerfArg &pa);

The requested-label will be the name the classifier associates with the service-description, except under either of these conditions:

The label has already been used for another service-description. In this case the SCA will generate a new label automatically, which typically will combine one of the concepts from the service-description with a numeric identifier.
If the service-description is equivalent to another agent service, then the previously existing label will be returned.

The reply_with identifier will be returned in the :reply-to field of the reply performative.

Then use send_tell() to send a performative to the SCA with the PerfArg pa as the argument.

Internal KQML. The :content field of the PerfArg should be a PerfArg with :name requested-label, and :description service-description.

Receiving

Successful classifications should be received with recv_reply(). To extract the recommended service label use:

PerfArgValue getSCAServiceLabel(const PerfArg& pa);

An empty PerfArgValue is returned if there is no label (which should never happen).

Use recv_error() for when the service description is not successfully classified. To extract an explanation of the error use:

PerfArgValue getSCAErrorMessage(const PerfArg& pa);

An empty PerfArgValue is returned if there is no message.

Internal KQML. The recommended service label, or the error message, is found in the :content field of the PerfArg.

Queries

To find an agent to provide a service, first query the SCA to identify labels associated with services that meet your requirements. Then use the labels to identify individual agent instances advertising in a registry.

Sending

To prepare a performative to send to the SCA for a query, call the following function to add information to the PerfArg pa.

void addSCAQueryInfo (	const char* variables,
		   	const char* service_description,
		  	const char* reply_with,
		  	PerfArg &pa);

The variables argument must be a list of variables referenced within the query service-description (see Service Description Language for Queries). The reply_with identifier will be returned in the :reply-to field of the reply performative. Then use send_ask_about() to send the performative to the SCA with pa as both arguments.

Internal KQML. The :content field of the PerfArg should be a PerfArg with :variables variables, and :description service-description.

Receiving

Successful queries should be received with recv_reply(). The classifier's response may include zero or more sets of bindings to the query variables, each of which is an alternative answer. Use the following function to determine how many answers there are to the query:

int getSCANumBindingSets(const PerfArg& pa);

Use the following function to extract a value bound to some variable in a particular answer (binding_set).

PerfArgValue getSCABinding (	const PerfArg& pa,
			   	int binding_set, 
			   	const char* variable);

Binding sets are indexed starting with 0. If the binding set or variable doesn't exist the function returns an empty PerfArgValue.

Internal KQML. An error message is found in the :content field of the PerfArg. For successful queries, the PerfArg's content field contains a PerfArg which is a list of PerfArgs, each one of which has a slot for each variable. For example, if two binding sets are returned, and the variable list was (?x ?y), the reply PerfArg would have the following structure:

Reply           Binding set
Perfarg label   PerfArg label   Variable label   Value
-------------   -------------   --------------   -----
:content        0               ?x               x1
                                ?y               y1
                1               ?x               x2
                                ?y               x3

Service Description Languages

Service descriptions are expressed using concepts and relations from the UMDL ontology, composed according to grammars defined by the Loom description logic system. The languages for classification and queries are similar, but different. This section provides informal descriptions and examples, and also the complete grammars as documented in the reference manual for Loom.

Classification

The classification request expresses the "meaning" of the service provided in the language of the UMDL ontology. Classification requests have two parts:

Requested-labels. These must be single tokens, with no embedded blanks. Special characters are limited to '-' and '_'. The classifier is not case sensitive. Requested labels which are already used in the UMDL or Loom ontologies will not cause an error, but will not be accepted either (the SCA will generate a new name based on the service description).
Examples:
task-planning-for-schools
BOOK_DELIVERY
Service-description. These are Lisp-like expressions which may be composed of multiple phrases in boolean combinations. Valid keywords, which are preceded by colons, are identified in Loom's concept expression grammar (see Loom Grammar for classification). All other symbols are concepts and relations from the UMDL Ontology. Service descriptions which include the :or keyword are accepted but strongly discouraged, because their cumulative effect would strongly degrade the classifier's overall performance.
The following example of a service description is typical. It is a conjunctive expression in which the first phrase identifies the kind of service that will be provided, and following phrases add detail by specifying the values of attributes associated with the service concept.
Example:
(:and recommend-dlcollection
(:all recommend-dlcollection.has.audience middle-school)
(:all recommend-dlcollection.has.topic science))

Loom retrieval operates on instances, not concepts. The SCA therefore asserts service descriptions to be instances as well as concepts. It also asserts that each role is filled by a "generic instance" of the value restriction. For example, the service defined just above is instantiated as an instance with an audience that is an instance of the middle-school concept. This permits retrieval of services for middle-schools. In short, for most purposes SCA clients do not need to worry about Loom's internal distinction between concepts and instances.

Loom Grammar

A full explanation of defining concepts in Loom is available on-line. The BNF for concept expressions is replicated here:

  concept-expr ::= 
      ConceptName | 
      ( {:AND | :OR} concept-expr+ ) | 
      ( :ONE-OF {Number+ | InstanceId+} ) | 
      ( :THROUGH Number Number ) | 
      ( {:AT-LEAST | :AT-MOST | :EXACTLY} Integer relation-expr ) | 
      ( {:ALL | :SOME | :THE} relation-expr ConceptName ) | 
      ( {:FILLED-BY | :NOT-FILLED-BY} relation-expr  
                                      {InstanceId | Constant}+ ) | 
      ( {:SAME-AS | :SUBSET} relation-expr relation-expr ) | 
      ( {< | > | <= | >= | = | <>} relation-expr  
                                   {relation-expr | Number} ) | 
      ( :RELATES relation-expr relation-expr 
                               {relation-expr | Constant} ) | 
      ( :SATISFIES ( ?Var ) query-expr ) | 
      set-expr ;

The concept-forming operators have the following semantics:

If C = (:and C1...Cn), an instance of C is an instance of each of the concepts C1...Cn.
If C = (:or C1...Cn), an instance of C is an instance of at least one of the concepts C1...Cn.
If C = (:at-least K R), an instance of C has at least K fillers of the role R.
If C = (:at-most K R), an instance of C has at most K fillers of the role R.
If C = (:exactly K R), an instance of C has exactly K fillers of the role R.
If C = (:all R C1), and I is an instance of C, all fillers of the role R on I are instances of concept C1.
If C = (:some R C1), and I is an instance of C, at least one filler of the role R on I is an instance of concept C1.
If C = (:the R C1), and I is an instance of C, the role R on I has exactly one filler, and that filler is an instance of concept C1.
If C = (:filled-by R V1...Vn), and I is an instance of C, the role R on I contains all of the fillers V1...Vn.
If C = (:not-filled-by R V1...Vn), and I is an instance of C, the role R on I does not contain any of the fillers V1...Vn.
If C = (:same-as R1 R2), an instance of C has the same set of fillers for role R1 as for role R2.
If C = (:subset R1 R2), and I is an instance of C, the fillers of role R1 on I are a subset of the fillers of role R2.
If C = (< R1 R2), and I is an instance of C having single-valued roles R1 and R2, the filler of R1 is numerically less than the filler of R2. The other arithmetic operators have corresponding semantics.
If C = (:relates R R1 R2), and I is an instance of C having single-valued roles R1 and R2, the relation R holds between the filler of R1 and the filler of R2.
If C = (:satisfies (?X) Q), and I is an instance of C, the the Loom query Q is satisfied when ?X is bound to I.

Queries

A query identifies those classified service descriptions which match the requirements of the request. The query answer consists of bindings of elements of the matched service descriptions to variables in the query request. Query requests have two parts:

Variables list. This is a list of variables that are included in the service description. Every variable must be in the service description, and no variable may be included in the service description which is not in the variable list. The list must be surround by parentheses, and each symbol must start with a question mark. The name of the variable is not syntactically important, but should be designed to clarify the meaning of the query to enhance system maintainability. Similarly, the order of the variables is not syntactically important, but the primary object of the query should be listed first.
Example:
(?service ?topic)
Service description. These are Lisp-like expressions which may be composed of multiple phrases in boolean combinations. Valid keywords, which are preceded by colons, are identified in Loom's query expression grammar (see Loom Grammar for queries). Symbols following the :predcall and :wrapper keywords identify functions supplied by the SCA to augment Loom's query language (see SCA Predicates and SCA Wrappers). All other symbols are concepts and relations from the UMDL Ontology. The meaning of non-trivial query expressions is derived from the use of multiple concepts and expressions which are chained together with variables.
Predicates are Lisp functions which are either true or false for every combination of bindings considered by the query. Wrappers, in comparison, are not invoked for every possible set of bindings, but are invoked only once for the entire query. In other words, whereas predicates are inside of Loom queries, wrappers are outside the Loom query. Thus, the :wrapper keyword can be used only once in a service description, and it must be the first element of the list. Since predicates and wrappers are functions, these symbols must be preceded by the Lisp prefix #'. Symbols in the remainder of :predcall phrases are arguments to the predicate or wrapper function, and so are defined by the syntax of the function. Typically they must be preceded by the Lisp quote symbol '.
```
Examples:

(:and 	(recommend-dlcollection ?service)
	(recommend-dlcollection.has.audience 
                   ?service middle-school)
	(recommend-dlcollection.has.topic ?service ?topic))

(:and 	(recommend-dlcollection ?service)
	(recommend-dlcollection.has.audience 
                   ?service middle-school)
	(:predcall #'same-filler-or-none 
	               ?service 
                       'recommend-dlcollection.has.topic 
		       'science))

(:wrapper #'most-specific
	'(:and 	(recommend-dlcollection ?service)
		(recommend-dlcollection.has.audience 
                           ?service ?audience)
		(school ?audience))
	'((middle-school ?audience)))
```
Loom Grammar
A full explanation of retrieval in Loom is available on-line. The BNF for query expressions is replicated here:
```
  query-expr ::= 
      ( {:AND | :OR} query-expr+ ) | 
      ( {:NOT | :FAIL} query-expr ) | 
      ( :IMPLIES query-expr query-expr ) | 
      ( {:FOR-SOME | :FOR-ALL} ( ?Var+ ) query-expr ) | 
      ( :COLLECT ( ?Var ) query-expr ) | 
      ( concept instance ) | 
      ( relation instance+ value ) | 
      ( :SAME-AS instance instance ) | 
      ( :SUBSET instance instance ) | 
      ( :PREDCALL LispPredicate value+ ) | 
      ( :ABOUT instance about-clause* )
```
```
  about-clause ::= 
      concept | 
      ( concept ) | 
      ( relation value ) | 
      ( :FILLED-BY relation value+ ) | 
      ( {:AT-LEAST | :AT-MOST | :EXACTLY} Integer relation ) | 
      ( {:ALL | :SOME | :THE} relation concept )
```
The query-expression operators have the following semantics:
- If Q = (:and Q1...Qn), Q is true if Q1...Qn are all true.
- If Q = (:or Q1...Qn), Q is true if at least one of Q1...Qn is true.
- If Q = (:not Q1), Q is true if Q1 is not true.
- If Q = (:fail Q1), Q is true if Loom cannot prove that Q1 is true.
- If Q = (:for-some (?X1...?Xn) Q1), Q is true if there are bindings for ?X1...?Xn that cause Q1 to be satisfied.
- If Q = (:for-all (?X1...?Xn) (:implies Q1 Q2)), Q is true if all bindings of ?X1...?Xn that satisfy Q1 also satisfy Q2.
- If Q = (:collect ?X Q1), Q returns the values V1...Vn such that Q1 is satisfied when ?X is bound to each Vi.
- If Q = (C I), Q is true if I is an instance of concept C.
- If Q = (R I V), Q is true if V is a filler of role R on instance I.
- If Q = (R I1...In), Q is true if the tuple <I1...In> is in the n-ary relation R
- If Q = (:same-as V1 V2), Q is true if values V1 and V2 are equivalent.
- If Q = (:subset V1 V2), Q is true if V1 and V2 evaluate to sets of values, and V1 is a subset of V2.
- If Q = (:predcall P V), Q is true if application of Lisp predicate P to value V returns true.
- If Q = (:about I C) or (:about I (C)), Q is true if I is an instance of concept C.
- If Q = (:about I (R V)), Q is true if the filler of role R on instance I is V.
- If Q = (:about I (:filled-by R V1...Vn)), Q is true if every value Vi is a filler of role R on instance I.
- If Q = (:about I (:at-least K R)), Q is true if instance I has at least K fillers of role R. The :at-most and :exactly operators have corresponding semantics.
- If Q = (:about I (:all R C)), Q is true if all fillers of role R on instance I are instances of concept C. The :some and :the operators have corresponding semantics.
A concept, relation, or instance may be either a symbol that names a Loom object, or a variable beginning with the character ?. An instance may also be a constant or a formula, where a formula is a list of the form (relation instance).

Query predicates
Predicates are Lisp functions which are either true or false for every combination of bindings considered by the query. The following special-purpose predicates are currently available:
1. same-filler-or-none (concept-instance slot-relation filler-value).
  Accepts a set of bindings if the slot-relation filler for the concept-instance is the same as filler-value, or if the slot is not filled with another value.
```
Example:

(:and (recommend-dlcollection ?service)
      (:predcall #'same-filler-or-none ?service 
                     'recommend-dlcollection.has.topic 'science))
```
  In this example the concept instance ?service is accepted if the recommend-dlcollection.has.topic slot is filled with the value science, or is not filled at all.
2. only-expected-fillers (concept-instance slot-relations-list).
  Accepts a set of bindings if concept-instance has no filler for any slot whose relation is not in slot-relations-list,
```
Example:

(:and (recommend-dlcollection ?service)
      (:predcall #'only-expected-fillers ?service 
                    '(recommend-dlcollection.has.topic
                      recommend-dlcollection.has.conceptual-level)))
```
  In this example the concept instance ?service is accepted if no slot besides recommend-dlcollection.has.topic is filled.
Query wrappers
Wrappers are invoked only once for the entire query. The :wrapper keyword can be used only once in a service description, and it must be the first element of the list.
Currently the following wrapper functions are available:
1. increasingly-general (start-from-service
  end-with-service)
  increasingly-specific
  (start-from-service)
  These wrapper functions return services that are increasingly general (subsume) or increasingly specific (subsumed by) the start-from-service. These are each bound to the first variable in the variables list. The returned list does not include the start-from-service. Subsumption is a partial order, and the relative location of services that do not subsume each other is undetermined. The end-with-service argument is the most general service that will be included in the list. If other services are equivalently general, they may be omitted.
  Example: (?service) (:wrapper #'increasingly-general 'tpa1 'recommend-dlcollection)
  define-inclusive-concept
  (list-of-services)
  This wrapper function returns a definition of a concept that would subsume each of the concepts included in list-of-services. If desired, this definition can then be classified. The new definition is for the least-common-subsuming concept subject to a language restriction. Since Loom's concept language includes OR, the unrestricted least-common-subsuming concept would be the (uninteresting) disjunction of the input concepts. Only elements of concept definitions that fit the following form are considered:
  { (and [direct superconcepts]* [(ALL relation value-restrictions)]* }
  
  We define the inclusive concept, which may be new, as having:
  1. The intersection of superconcepts.
  2. Only roles with relations shared by all.
  3. The intersection of role value restriction superconcepts.
  For an algorithm with a language bias that permits equality constraints, see Cohen and Hirsh in Machine Learning 17 (1994).
  Example: (?new-def) (:wrapper #'define-inclusive-concept '(tpa1 tpa2 tpa3))
  most-specific-subsuming (hard-constraints-query-expression
  soft-constraints-list
  &key
  priorities-list
  attenuation-factors-list)
  most-general-subsumed (hard-constraints-query-expression
  soft-constraints-list
  &key
  priorities-list
  attenuation-factors-list)
  These wrapper functions permit fine tuning to find increasingly general or specific services, in cases where the attributes of interest are known. They find sets of bindings that satisfy the hard-constraints-query-expression, and rank them according to how well they satisfy the list of soft constraints. Use a typical query expression as the hard constraint to identify any agent service that would be satisfactory. Then use the soft constraints to identify an agent service that would be ideal.
  Each element of soft-constraints-list must be of the form (concept variable). The set of bindings returned is that which is closest to satisfying the constraints. The semantic distance with respect to specificity or generality is measured by the path distance in the taxonomy between the preferred concept and the actual filler.
  If some soft constraints are more important than others, the priorities-list argument can be used to weight the relative impact of each soft constraint. The priorities-list should have the same length as the soft-constraints-list, and must contain numeric values. Only their relative value is important. The default priority weight for any soft constraint for which it is not specified is 1.
  Because some areas of the ontology may be more densely developed than others, it may be desirable to fine-tune the multiplicative factor with which concept generality/specificity is penalized for each step of inheritance in the ontology. The attenuation-factors-list should have the same length as the soft-constraints-list, and should contain numeric values in the interval (0, 1). The default attenuation factor for any soft constraint for which it is not specified is currently 0.7.
  Example: (?service ?audience ?topic) (:wrapper #'most-specific-subsuming '(:and (recommend-dlcollection ?service) (recommend-dlcollection.has.audience ?service ?audience) (school ?audience) (recommend-dlcollection.has.topic ?service ?topic) (science ?topic)) '((middle-school ?audience) (earth-science ?topic)) :priorities '(2 1) :attenuation-factors '(0.6 0.8))
  
  In this example the hard constraint query selects only recommend-dlcollection services for audiences which are schools, and whose topic is science. Then, candidates are ranked according to how specific their audience is to middle-school, and how specific their topic is to earth-science. The audience constraint is considered to be twice as important as the topic constraint (within the limits set by the hard constraint). Also, because (hypothetically) the ontology differentiates topics more densely than audiences, the topic constraint is penalized less for each required inheritance link than is the audience constraint.
Papers
Run-Time Classification of Agent Services, by Peter Weinstein and Bill Birmingham (available in postscript and rtf format)
Documentation
Service Classifier Agent Programmer's Interface
UMDL Ontology Concepts and Relations available to the Service Classifier Agent
Demo
SCA demo homepage
Classify a service description
Query a service description
History of the current SCA
People
Mail Peter Weinstein
Mail the UMDL architecture group
Mail the UMDL ontology group

UMDL Service Classifier Agent Demo:Programmer's Interface

Sending

Receiving

Sending

Receiving

UMDL Service Classifier Agent Demo:
Programmer's Interface