FOUNDATION FOR INTELLIGENT PHYSICAL AGENTS

FIPA CCL Content Language Specification

Document title	FIPA CCL Content Language Specification
Document number	XC00009A	Document source	FIPA TC C
Document status	Experimental	Date of this status	2000/08/22
Supersedes	None
Contact	fab@fipa.org
Change history
2000/08/22	Approved for Experimental

Geneva, Switzerland

Notice

Use of the technologies described in this specification may infringe patents, copyrights or other intellectual property rights of FIPA Members and non-members. Nothing in this specification should be construed as granting permission to use any of the technologies described. Anyone planning to make use of technology covered by the intellectual property rights of others should first obtain permission from the holder(s) of the rights. FIPA strongly encourages anyone implementing any part of this specification to determine first whether part(s) sought to be implemented are covered by the intellectual property of others, and, if so, to obtain appropriate licenses or other permission from the holder(s) of such intellectual property prior to implementation. This specification is subject to change without notice. Neither FIPA nor any of its Members accept any responsibility whatsoever for damages or liability, direct or consequential, which may result from the use of this specification.

Foreword

The Foundation for Intelligent Physical Agents (FIPA) is an international organization that is dedicated to promoting the industry of intelligent agents by openly developing specifications supporting interoperability among agents and agent-based applications. This occurs through open collaboration among its member organizations, which are companies and universities that are active in the field of agents. FIPA makes the results of its activities available to all interested parties and intends to contribute its results to the appropriate formal standards bodies.

The members of FIPA are individually and collectively committed to open competition in the development of agent-based applications, services and equipment. Membership in FIPA is open to any corporation and individual firm, partnership, governmental body or international organization without restriction. In particular, members are not bound to implement or use specific agent-based standards, recommendations and FIPA specifications by virtue of their participation in FIPA.

The FIPA specifications are developed through direct involvement of the FIPA membership. The status of a specification can be either Preliminary, Experimental, Standard, Deprecated or Obsolete. More detail about the process of specification may be found in the FIPA Procedures for Technical Work. A complete overview of the FIPA specifications and their current status may be found in the FIPA List of Specifications. A list of terms and abbreviations used in the FIPA specifications may be found in the FIPA Glossary.

FIPA is a non-profit association registered in Geneva, Switzerland. As of January 2000, the 56 members of FIPA represented 17 countries worldwide. Further information about FIPA as an organization, membership information, FIPA specifications and upcoming meetings may be found at http://www.fipa.org/.

Contents

1 Scope. 1

1.1 Semantic Underpinnings. 1

1.2 Constraint Satisfaction Problem Definitions. 1

1.2.1 Standard Definition of Constraint Satisfaction Problems. 1

1.2.2 Expressing Choices and Choice Problems. 2

1.2.3 Constraint Satisfaction Problem Model Used in FIPA Constraint Choice Language. 2

1.3 Language Properties. 3

1.3.1 Search Termination and Complexity. 3

2 FIPA Constraint Choice Language Ontology. 4

2.1 Object Descriptions. 4

2.1.1 Choice Problem.. 4

2.1.2 Solution. 4

2.1.3 Solution List 5

2.1.9 Variable Assignments. 7

2.1.10 Variable Name. 7

2.1.11 Exclusion. 8

2.1.12 Relation. 8

2.1.13 Domain Range. 9

2.1.14 Domain Role Term.. 9

2.1.15 Domain Term.. 9

2.1.16 Domain Variable Type. 10

2.1.17 Symbol 10

2.1.18 Index Pair 10

2.2 Function Descriptions. 10

2.2.1 Give Constraints for Information Gathering. 11

2.2.2 Give Values for Information Gathering. 11

2.2.3 Solving to Generate Solutions. 13

2.2.4 Solving to Generate a List of Solutions. 13

2.3.4 Is a Constraint Satisfaction Problem.. 14

2.3.5 Is an Action Result 15

2.4 Ontology Requirements. 15

3 References. 16

4 Normative Annex A — FIPA-CCL XML Based Concrete Syntax. 17

4.1 XML DTD. 17

5 Informative Annex B — Language Usage. 20

5.1 Step 1: Problem Modelling. 20

5.1.1 FIPA Constraint Choice Language Constraint Representations. 20

5.2 Step 2: Information Gathering. 22

5.2.1 Using Tags to Separate Information from Different Sources. 22

5.3 Step 3: Information Fusion. 22

5.3.1 Using Tags for Information Fusion. 22

5.3.2 Information Fusion for Constraint Satisfaction Problems with Non-identical Variable Sets. 24

5.4 Step 4: Problem Solving. 25

5.4.1 Simple Constraint Satisfaction Problem Search Algorithm.. 26

5.5 References. 26

1 Scope

This document gives the specification of the Constraint Choice Language (CCL) which is designed as a language to be used for agent communication, and more specifically as a content language to be used with FIPA ACL (see [FIPA00061]).

The language is primarily intended to enable agent communication for applications that involve exchanges about multiple interrelated choices. FIPA CCL is based on the representation of choice problems as Constraint Satisfaction Problems (CSPs) and supports:

· Problem representation,

· Information gathering,

· Information fusion, and,

· Access to problem solution techniques.

Further information and additional resources concerning the use of FIPA CCL are available at:

http://liawww.epfl.ch/CCL/

1.1 Semantic Underpinnings

As already indicated, the FIPA CCL language is based on the representation of choice problems as CSPs. The CSP formalisms can therefore be used as a framework for defining the properties of the language and as a support for defining its semantics.

1.2 Constraint Satisfaction Problem Definitions

1.2.1 Standard Definition of Constraint Satisfaction Problems

Constraint Satisfaction Problems have been an intensive area study for some 30 years now and the basic definition of a CSP has remained unchanged since the early 1970s (see [Waltz75] for example). A finite binary discrete CSP is defined by:

· A finite set of variables V,

· A finite domain D_i of possible discrete values for each variable v_iÎ V, and,

· A finite set of constraints C between any pairs of variables in V.

A solution to the CSP is defined as:

An assignment of values to variables such that: each variable v_iÎ V is assigned a value d Î D_i, and none of the constraints c Î C are violated.

A solution therefore consists of finding consistent legal to assignment of values to each variable such that all the constraints posted for the problem are respected. More formal definitions can be found in [Mackworth77] and [Dechter92] amongst others. The basic definition has previously been extended in many ways, for example:

· Allowing dynamic sets of variables,

· Allowing dynamic, continuous or infinite variable domains, and,

· Allowing constraints of up to arity N where N = |V|.

These extensions are in general well defined and each has its own body of literature discussing appropriate solution techniques and application areas.

1.2.2 Expressing Choices and Choice Problems

Having defined CSPs, a choice problem can be defined as a CSP in the following way:

· Variables are choices to be made, such as which brand of shampoo to use or how many roses to buy for a date. The set of variables V is the set of interrelated choices which all need to be made to have a complete solution to the current problem.

· Domains are the available options for each choice (variable). Thus the number of roses may be anywhere between 1 and 30 and the brands of shampoo one of X, Y and Z. The assignment of one of the values from a domain D_i to a variable v_i corresponds to making a choice for v_i. The set of all possible combinations of assignments of domain values to variables define the problem search space.

· Finally Constraints are relationships between choices which express valid or invalid combinations. The set of constraints C therefore restricts the set of all possible combinations of choices to a smaller set of desirable assignments which meet the requirements of a solution to the choice problem.

The aim of the FIPA CCL language is therefore to leverage this formulation of a choice problem for use in agent communication. CSP techniques have been successfully applied to domains as diverse as configuration, planning, scheduling, design, diagnosis, truth maintenance, spatial reasoning logic programming and resource allocation. Using such a flexible problem representation as the basis for FIPA CCL will hopefully make it useful for a wide range of agent applications. Section 5, Informative Annex B — Language Usage gives a more detailed guide to how FIPA CCL can be used to model, communicate about and solve choice problems.

1.2.3 Constraint Satisfaction Problem Model Used in FIPA Constraint Choice Language

The CSP model which underlies FIPA CCL has three restrictions imposed which have been made to make the model minimal and more suitable for a communication language:

1. Binary Constraints. All constraints expressed must have an arity of no more than 2 (i.e. constraints are only ever between two variables. This restriction is often made in the CSP field, since most powerful solving techniques only apply to CSPs with arity 2 constraints. Furthermore, for discrete CSPs, any CSP represented in a form using n-ary constraints can be transformed into an equivalent CSP using only binary (2-ary) constraints. The language therefore looses none of its expressive power with this restriction.

2. Discrete Variable Domains. CSPs with only discrete sets of values in each variable domain are by far the best understood in the literature. Solving CSPs with ranges of continuous real values for value domains requires specialised solving techniques, therefore they are excluded in this version of the language. In practice, CSPs requiring continuous values are often be formulated by discretizing the continuous domain (so that discrete CSP solving techniques can be applied, see [SamHaroud96]).

3. Intensional Relations. There are two main ways of representing constraints for CSPs – as extensional relations (consisting of a list of the valid combinations of values for a pair or tuple of variables) and as intensional relations (consisting of relations such as equals, greater-than etc. which do not rely on an explicit list). FIPA CCL excludes the use of extensional relations – this makes CSPs expressed in FIPA CCL much easier to compose (merge) when fusing information from several sources. Once again, no expressive power is lost since it can be shown that for discrete CSPs every formulation using extensional constraints has an equivalent formulation using only intensional constraints.

There are also several implicit constraints which arise out of the fact that that CSPs represented in FIPA CCL must be contained in a single message:

· The number of variables must be finite (since they must be encapsulated in a single message), and,

· The number of constraints must be finite (since they must be encapsulated in a single message).

1.3 Language Properties

Given the CSP representation in previous sections, the following sections make statements about the formal properties of FIPA CCL.

1.3.1 Search Termination and Complexity

The basic underlying representation used in FIPA CCL is that of a CSP. In a sense most messages in FIPA CCL will define a problem (a CSP) which acts as an, as yet, unexplored solution space. This allows us to make definitive statements about when these problems have solutions, when a search is guaranteed to terminate and how long the search might take.

Questions of termination depend upon the type of CSP represented and on the state of the variable domains as follows:

· If all variable domains are discrete (as they must be given the restrictions in Section 0) and finite, then the solution and search spaces are both finite and search is guaranteed to terminate.

· Although the search for a solution can be shown to terminate, solving the problem is in general NP-complete. This is to be expected since the choice problems agents using FIPA CCL are trying solve are by their very nature combinatorially explosive.

· It has been shown that for some restricted types of CSP problem the complexity of finding a solution may be less than NP-complete: linear or polynomial for example (for example, see [Freuder82] and [vanBeek97]).

An important advantage gained by using the underlying CSP representation is that problem solving can leverage the powerful techniques which have been developed for CSP solving (there is extensive literature on this subject and [Tsang94] provides a good starting point). Techniques exist which routinely solve problems of over 1000 variables and most problems of 10-20 variables can be solved using very simple search algorithms.

2 FIPA Constraint Choice Language Ontology

2.1 Object Descriptions

This section describes a set of frames, that represent the classes of objects in the domain of discourse within the framework of the FIPA-CCL ontology.

The following terms are used to describe the objects of the domain:

· Frame. This is the mandatory name of this entity, that must be used to represent each instance of this class.

· Ontology. This is the name of the ontology, whose domain of discourse includes the parameters described in the table.

· Parameter. This is the mandatory name of a parameter of this frame.

· Description. This is a natural language description of the semantics of each parameter.

· Presence. This indicates whether each parameter is mandatory or optional.

· Type. This is the type of the values of the parameter: Integer, Word, String, URL, Term, Set or Sequence.

· Reserved Values. This is a list of FIPA-defined constants that can assume values for this parameter.

2.1.1 Choice Problem

This object represents a choice problem. For a CSP object to be well defined, the items in the exclusion and relations parameters must only refer to variables which are present in the Variables parameters. If the csp-ref parameter is not empty, then the CSP referenced in this parameter is taken to be the object of the csp-identifier object and the items in the variables, relations and exclusions fields are ignored. A CSP object which contains no variables, relations or exclusions (directly or by reference) is known as a null CSP.

Frame Ontology	csp FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
csp-ref	This references a CSP object.	Mandatory	csp-identifier
variables	Represents the choices which need to be taken in the choice problem. The variables listed in this parameter must all have unique names. The Variables listed in this parameter should have unique Role/Type combinations.	Optional	Set of csp-variable
relations	Represent the relationships between the choices to be made.	Optional	Set of csp-variable
exclusions	Represents a list of unary relations on single variables which exclude certain values from variable domains	Optional	Set of csp-variable

2.1.2 Solution

This object captures the notion of a solution to a choice problem. Here all the choices are assigned an appropriate value (one of the options) and the assignment violates none of the posted constraints.

Frame Ontology	csp-solution FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
csp-ref	This references a CSP object that the solution is for.	Mandatory	csp-identifier
assignments	A list of variable assignments such that the list contains one and only one assignment for each and every variable defined in the CSP reference in the CSP-ref slot, and, the assignment of these values violates none of the constraints posted for the CSP in the csp-ref parameter. That is, the variable assignment must be consistent.	Mandatory	Set of csp-variable-assignment

2.1.3 Solution List

This object captures the notion of a list of solutions to a choice problem.

Frame Ontology	csp-solution-list FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
csp-ref	This references a CSP object that the list of solutions is for.	Mandatory	csp-identifier
solutions	This is a list of possible solutions to the choice problem. The list must contain at least one such solution and may contain any subset of the whole set of solutions for the CSP.	Mandatory	Set of csp-solution

2.1.4 Identifier

This object represents the unique identifier of a CSP.

Frame

Ontology

csp-identifier

FIPA-CCL

Parameter

Description

Presence

Type

Reserved Values

identifier-body

This is the unique identifier of the CSP.

Mandatory

Symbol

2.1.5 Range

This object represents a complete domain, to be used when explicit enumeration of values would be too inefficient. The two items range and tuple-range are optional however one or the other must be present.

Frame Ontology	csp-range FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
range	This defines complete domains such as ordered lists of number numbers, world-airports, etc., which must be part of a common ontology.	Optional	domain-range
tuple-range	This defines a combination of all the legal values in a tuple. A range is given for each slot in the tuple and this parameter specifies that all combinations of values from the given ranges in each slot in the tuple are legal.	Optional	Set of domain-range

2.1.6 Value

This object represents an option. In general this can be a tuple and hence, the variable is an ordered list of domain terms.

Frame Ontology	csp-value FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
npart	This identifies the number of elements of the tuple value which must be identical to the number of items in the elements parameter.	Mandatory	Number
elements	This gives a list of values: one for each of the elements in the tuple.	Mandatory	Set of domain-term
tags	This contains a list of symbols that allow selective constraints.	Optional	Set of Symbol

2.1.7 Value List

This object represents a list of options. Each option is a tuple and each of the values in the list must have the same number of elements in the tuple; the number of elements must in turn be equal to the value of the npart parameter.

Frame Ontology	csp-value-list FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
npart	This identifies the number of elements of the tuple value which must be identical to the number of items in the elements parameter.	Mandatory	Number
value-list	This gives a list of values: one for each of the elements in the tuple.	Mandatory	Set of (Set of domain-term)
tags	This contains a list of symbols that allow selective constraints.	Optional	Set of Symbol

2.1.8 Variable

This object represents a single choice to be made, along with a set of possible options for that choice. The type and role parameters enable this object to be situated within the problem solving context.

Frame Ontology	csp-variable FIPA-CCL
Parameter	Description	Presence	Type	Reserved Values
name	This gives a unique symbol that is used to make references to the variable within the context of a single CSP.	Mandatory	Symbol
type	This specifies the type of values that the variable takes which includes granularity. An ordered list is used since the variable might take tuple values. In this case, the first type refers to the type of the first element in the tuple, etc.	Mandatory	Set of domain-variable-type
role	This identifies the position of the variable within the problem-solving context.	Optional	Set of domain-role-term
domain	This lists the possible values this variable object may take, that is, the available options. These options must be consistent with the types of values given in the type parameter.	Optional	csp-range \| Set of csp-value

2.1.9 Variable Assignments

This object represents the assignment of a variable with a value. The variable named in the name parameter is assigned the value given in the value parameter. This represents a variable instantiation, that is, a choice being made.