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 
© 2000 Foundation for Intelligent Physical Agents  http://www.fipa.org/
Geneva, Switzerland
Notice 
Use of the technologies described in this specification may infringe
patents, copyrights or other intellectual property rights of FIPA Members and
nonmembers. 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 agentbased
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
agentbased 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 agentbased 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 nonprofit 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.2 Constraint
Satisfaction Problem Definitions
1.2.1 Standard
Definition of Constraint Satisfaction Problems
1.2.2 Expressing Choices
and Choice Problems
1.2.3 Constraint
Satisfaction Problem Model Used in FIPA Constraint Choice Language
1.3.1 Search Termination
and Complexity
2 FIPA Constraint Choice Language Ontology
2.2.1 Give Constraints
for Information Gathering
2.2.2 Give Values for
Information Gathering
2.2.3 Solving to
Generate Solutions
2.2.4 Solving to
Generate a List of Solutions
2.3.4 Is a Constraint
Satisfaction Problem
4 Normative Annex A FIPACCL XML Based Concrete Syntax
5 Informative Annex B Language Usage
5.1.1 FIPA Constraint Choice
Language Constraint Representations
5.2 Step 2:
Information Gathering
5.2.1 Using Tags to
Separate Information from Different Sources
5.3 Step 3:
Information Fusion
5.3.1 Using Tags for
Information Fusion
5.3.2 Information Fusion
for Constraint Satisfaction Problems with Nonidentical Variable Sets
5.4.1 Simple Constraint
Satisfaction Problem Search Algorithm
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/
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.
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.
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.
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 nary constraints can be transformed into an equivalent
CSP using only binary (2ary) 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, greaterthan 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).
Given the CSP
representation in previous sections, the following sections make statements
about the formal properties of FIPA CCL.
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 NPcomplete. 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 NPcomplete: 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 1020 variables can be solved using very simple
search algorithms.
This section describes a set of frames, that represent the classes of objects in the domain of discourse within the framework of the FIPACCL 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 FIPAdefined constants that can assume values for this parameter.
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 cspref parameter is not empty, then the CSP referenced in this parameter is taken to be the object of the cspidentifier 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 FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
cspref 
This references a CSP object. 
Mandatory 
cspidentifier 

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 cspvariable 

relations 
Represent the relationships between the choices to
be made. 
Optional 
Set
of cspvariable 

exclusions 
Represents a list of unary relations on single
variables which exclude certain values from variable domains 
Optional 
Set of
cspvariable 

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 
cspsolution FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
cspref 
This references a CSP object that the solution is for. 
Mandatory 
cspidentifier 

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 CSPref slot, and, the assignment of these values
violates none of the constraints posted for the CSP in the cspref parameter.
That is, the variable assignment must be consistent. 
Mandatory 
Set of
cspvariableassignment 

This object captures the notion of a list of solutions to a choice problem.
Frame Ontology 
cspsolutionlist FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
cspref 
This references a CSP object that the list of solutions is for. 
Mandatory 
cspidentifier 

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
cspsolution 

This object represents the unique identifier of a CSP.
Frame Ontology 
cspidentifier FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
identifierbody 
This is the unique identifier of the CSP. 
Mandatory 
Symbol 

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


Parameter 
Description 
Presence 
Type 
Reserved Values 
range 
This defines complete domains such as ordered lists of number numbers, worldairports, etc., which must be part of a common ontology. 
Optional 
domainrange 

tuplerange 
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
domainrange 

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 
cspvalue FIPACCL 


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 domainterm 

tags 
This contains a list of symbols
that allow selective constraints. 
Optional 
Set of
Symbol 

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 
cspvaluelist FIPACCL 


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 

valuelist 
This gives a list of values: one for each of the elements in the tuple. 
Mandatory 
Set
of (Set of domainterm) 

tags 
This contains a list of symbols
that allow selective constraints. 
Optional 
Set of
Symbol 

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 
cspvariable FIPACCL 


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 domainvariabletype 

role 
This identifies the position of the variable within the problemsolving context. 
Optional 
Set
of domainroleterm 

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 
csprange 

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.
Frame Ontology 
cspvariableassignment FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
name 
This is the name of the variable having a value assigned to it. 
Mandatory 
cspvariablename 

value 
This is value being assigned
which must match with the type of the variable. 
Mandatory 
cspvalue 

This object represents the name of a variable in a CSP.
Frame Ontology 
cspvariablename FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
name 
This name of a variable (choice). 
Mandatory 
Symbol 

This
object represents a constraint on a single variable by specifying a set of
values that is explicitly disallowed for this variable.
This object represents a relation between two variables. Any variables named in the Relationbody must appear in the set of Variables of the relation. The indices parameter identifies which slots in a tuple valued variable are covered by the relation. For example, for an equality relation between two variables with 3 tuples as values (for example, (x, y, z)), setting the set of indices to ((2,2), (3,3)) indicates that only the 2nd and 3rd slot of the value tuples need ever be equal the constraint is not violated even if the values in the 1st slots are unequal.
Frame Ontology 
csprelation FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
variables 
This contains two variable names such that the named variables are defined in the current CSP[1]. 
Mandatory 
Set
of cspvariablename 

relationtype 
This is the type of the relation being applied. 
Mandatory 
String 
IntentionalEquality IntentionalInequality IntensionalGreaterThan IntensionalLessThan IntensionalGreaterThanEqual IntensionalLessThanEqual IntensionalEmpty 
indices 
This specifies what subfields of variable values the relation refers to. 
Mandatory 
Set
of indexpair 

tags 
This contains a list of
symbols that allow selective constraints. 
Optional 
Set of
Symbol 

Table 1 describes the allowed relations which can be specified in relationtype.
Relation Type 
Description 
IntentionalEquality 
This specifies that all the variables listed in the variables parameter of the relevant CSP object and must take equal values in any instantiation. 
IntentionalInequality 
This specifies that all the variables listed in the variables parameter of the relevant CSP object and must take strictly different values in any instantiation. 
IntensionalGreaterThan 
This specifies that the variables in the variables list of the relevant CSP object are related by a greater than relationship such that the order of the tuple defines the order in the relationship; the first variable in the list is strictly greater than the second, which is strictly greater than the third, etc. Note that this relation is only valid for variable types which have an ordering relation defined in the domain ontology (integers, for example). 
IntensionalLessThan 
This specifies that the variables in the variables list of the relevant CSP object are related by a less than relationship such that the order of the tuple defines the order in the relationship; the first variable in the list is strictly less than the second, which is strictly less than the third, etc. Note that this relation is only valid for variable types which have an ordering relation defined in the domain ontology (integers, for example). 
IntensionalGreaterThanEqual 
Similar to the IntensionalGreaterThan relation but using a greater than or equals relation. 
IntensionalLessThanEqual 
Similar to the IntensionalGreaterThan relation but using a less than or equals relation. 
IntensionalEmpty 
This specifies that there are no allowed combinations of values for these values. 
Table 1: Variable Relationship Types
Frame Ontology 
domainrange FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
domainrangebody 
This is a symbol defined in this
ontology. 
Mandatory 
String 

Frame Ontology 
domainroleterm FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
domainroletermbody 
This is a symbol defined in this
ontology. 
Mandatory 
String 

Frame Ontology 
domainterm FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
domaintermbody 
This is a symbol defined in this
ontology. 
Mandatory 
String 

Frame Ontology 
domainvariabletype FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
domainvariabletypebody 
This is a symbol defined in this
ontology. 
Mandatory 
String 

This object is used to identify particular instances of objects. Symbols should be unique in their context of use.
Frame Ontology 
Symbol FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
symbolbody 
This is a unique word that is used
to identify a particular instance of an object. 
Mandatory 
String 

This object is used in relations to reference the individual fields in tuples. Given two variables with tuple valued variables, the this object indicates a field in the first and a field in the second which are somehow related.
Frame Ontology 
index FIPACCL 


Parameter 
Description 
Presence 
Type 
Reserved Values 
indexbody 
This is a pair of numeric values
which are used to identify which two particular fields in a tuple are related 
Mandatory 
Set of Integer 

The following tables define usage and semantics of the functions that are
part of the FIPACCL ontology.
The following terms are used to describe the functions of the FIPACCL domain:
· Function. This is the symbol that identifies the function in the ontology.
· Ontology. This is the name of the ontology, whose domain of discourse includes the function described in the table.
· Description. This is a natural language description of the semantics of the function.
· Domain. This indicates the domain over which the function is defined. The arguments passed to the function must belong to the set identified by the domain.
· Range. This indicates the range to which the function maps the symbols of the domain. The result of the function is a symbol belonging to the set identified by the range.
· Arity. This indicates the number of arguments that a function takes. If a function can take an arbitrary number of arguments, then its arity is undefined.
This action is used to collect constraints on a given set of variables and domains (that is, those specified in the CSP_{T}). The information is captured in a new CSP CSP_{INF} which is a copy of CSP_{T} containing new constraints (and potentially new variables which are required for expressing these new constraints). The two CSPs (CSP_{T} and CSP_{INF}) could now be composed using one of the two main composition operations (conjunctive or disjunctive composition see Section 5.3.2, Information Fusion for Constraint Satisfaction Problems with Nonidentical Variable Sets). However it should be noted that this composition is not part of the cspgiveconstraints action.
· Using cspgiveconstraints followed by a conjunctive composition of CSP_{T} and CSP_{INF} creates a CSP whose solutions satisfy both the actors constraints and the constraints originally present in CSP_{T}.
· Using cspgiveconstraints followed by a disjunctive composition of CSP_{T} and CSP_{INF} creates a CSP whose solutions satisfy either the original constraints in CSP_{T} or the constraints of the actor or both.
An agent can perform the cspgiveconstraints iff it knows all variables v_{i} and all constraints c_{i} identifying the problem P to solve (either by understanding the CSP sent in the message or having access to the CSP referred to in the cspref reference).
Function 
cspgiveconstraints 

Ontology 
FIPACCL 

Description 
The expected effect of this
function is the creation of a new CSP (CSP_{INF}) containing information the agent carrying
out the action (the actor) wishes
to express about the choice problem defined by the CSP given in target of the
action (CSP_{T}). CSP_{INF} consists of: ·
A complete copy of CSP_{T }, including: all the variables originally
present in CSP_{T} (with
their original roles and types), all the values in the variable domains of
these variables and all the constraints present in CSP_{T}. ·
New information in the form of
constraints between variables v_{i}
specified in CSP_{T, }i.e.:

Relations between variables v_{i}, 
Exclusions on variable domains of v_{i}. ·
CSP_{INF} may also
include new variables (with associated domain values) which are added as part
of the expression of constraints (when expressing ternary constraints in
their binary representation for example see Section 5, Informative Annex B Language Usage). 

Domain 
csp / cspidentifier 

Range 
If the action could be successfully
performed, then a CSP object representing the new CSP_{INF} is
generated. All new elements (those not present in CSP_{T}_{ }), including constraints, domain values and variables in CSP_{INF} must include a tag in their tags
field. This tag should be: the same for
each element (this identifies all added information as being the result
of a single information gathering action) and not present as a tag in the CSP_{T}_{ }(ensuring that the information does
not become mixed with existing information). If the cspgiveconstraints function
contains a cspidentifier referring to a CSP which the receiving agent has no
knowledge of, then cspunknown proposition is the result of the
function. 

Arity 
1 
This function is used to collect suitable options for a certain problem solving context. The CSP given as argument specifies a list of variables whose types, roles and relations identify the requested values. The two CSPs (CSP_{T} and CSP_{INF}) could now be composed using one of the two main composition operations (conjunctive or disjunctive composition see Section 5.3.2, Information Fusion for Constraint Satisfaction Problems with Nonidentical Variable Sets). However it should be noted that this composition is not part of the cspgiveconstraints function.
· Using cspgivevalues followed by a conjunctive composition of CSP_{T} and CSP_{INF} creates a CSP whose solutions only contain value assignments which are acceptable to both the actor and the agent(s) creating the original CSP_{T}.
· Using cspgivevalues followed by a disjunctive composition of CSP_{T} and CSP_{INF} creates a CSP which includes an extended set of options (and possibly solutions) beyond those available in the original CSP_{T} .
An agent can perform the cspgivevalues iff it knows all variables v_{i} and all constraints c_{i} identifying the problem P to solve.
Function 
cspgivevalues 

Ontology 
FIPACCL 

Description 
The expected effect of this
function is the creation of a new CSP (CSP_{INF})
containing information the agent carrying out the function (the actor) wishes to express about the
choice problem defined by the CSP given in target of the function (CSP_{T}). CSP_{INF} consists of: ·
A copy of all the variables v_{i} in CSP_{T} including
their original roles and types but not
including the values in their domains,
·
New information in the form of
values added to the domains of variables v_{i}
in CSP_{INF} :

If the actor knows of no suitable
values for the domain of a particular variable then the domain is left empty. ·
CSP_{INF} may also include new constraints
(exclusions and relations) between the variables since these new constraints
apply to the values being given as information by the execution of the
function. New variables may be added as part of the expression of these
constraints (when expressing ternary constraints for example). 

Domain 
csp / cspidentifier 

Range 
If the function could be
successfully performed, then a CSP object representing the new CSP_{INF} is generated. All new elements (those not
present in CSP_{T}_{ }),
including constraints, domain values
and variables in CSP_{INF} must include a tag in their tags
field. This tag should be: the same for
each element (this identifies all added information as being the result
of a single information gathering function) and not present as a tag in the
CSP_{T}_{ }(ensuring
that the information does not become mixed with existing information). If the cspgivevalues function
contains a cspidentifier referring to a CSP which the receiving agent has no
knowledge of, then cspunknown proposition is the result of the
function. 

Arity 
1 
This is the function of solving a CSP (the CSP specified as the subject parameter of the function). In order to perform this function an agent must be able to understand the CSP problem representation, that is, all of the variables and constraints.
Function 
cspsolve 

Ontology 
FIPACCL 

Description 
The expected effect of having
performed this function is to find an assignment of values to the variables v_{i}_{ } in the CSP specified as the target of the
function CSP_{T} such that none of the constraints c_{i}_{ }specified in CSP_{T}_{ }are violated. 

Domain 
csp / cspidentifier 

Range 
If a solution to the problem
identified by the cspsolve function (CSP_{T}) exists then it is
represented by a resulting cspsolution
object. If there exist no solutions to the
CSP identified of the cspsolve function, then a cspinsoluble proposition is the result of the function. If the cspsolve function
contains a cspidentifier referring to a CSP which the receiving agent has no
knowledge of, then a cspunknown proposition is the result of the
function. 

Arity 
1 
This function is similar to the cspsolve function but is defined as solving the CSP given in the subject parameter to return all of its solutions and collating these into a list of solutions.
Function 
cspsolvelist 

Ontology 
FIPACCL 

Description 
The expected effect of having
performed this function is to find one or several sets of assignments of
values to the variables v_{i}_{
} in the CSP specified as the
target of the function CSP_{T} such that none of the constraints c_{i}_{ }specified in CSP_{T}_{ }are violated. 

Domain 
csp / cspidentifier 

Range 
If a solution or set of solutions
to the problem identified by the cspsolve
function (CSP_{T}) exists
then it is represented by a resulting cspsolutionlist object. If there exist no solutions to the
CSP identified in the cspsolvelist function, then a cspinsoluble proposition is the result of the
function. If the cspsolvelist function
contains a cspidentifier referring to a CSP which the receiving agent has no
knowledge of, then a cspunknown proposition is the result of the
function. 

Arity 
1 
A proposition makes a statement about the truth or falsity of a property of a CSP object. Note that the definitions given in this section are effectively proposition schemas expressed as predicates. However, once the variables in the schemas are instantiated the ensemble is treated as a proposition.
This states that the CSP given in the subject parameter has no solutions.
Proposition 
cspinsoluble 

Ontology 
FIPACCL 

Description 
This
proposition is true iff ^{Ψ}$ X such that X is an assignment of values to the variables of the
given CSP consistent with the given
constraints. 

Domain 
csp / cspidentifier 
This states that the CSP given in the subject parameter has at least one solution.
Proposition 
cspsoluble 

Ontology 
FIPACCL 

Description 
This
proposition is true iff ^{ }$ at least an X such that X is an assignment of values to the
variables of the given CSP consistent with the given constraints. 

Domain 
csp / cspidentifier 
This states that the CSP referred to is unknown to an agent.
Proposition 
cspunknown 

Ontology 
FIPACCL 

Description 
This
proposition is true iff the referred CSP is unknown to
the agent making the statement. 

Domain 
cspidentifier 
This proposition can be used to wrap CSPs
in a proposition construct for general information passing. The semantic
meaning of the message containing such a proposition may be derived from the
conversation context.
Proposition 
iscsp 

Ontology 
FIPACCL 

Description 
This
proposition is true iff the object referred to is a
well formed CSP object. 

Domain 
csp / cspidentifier 
The cspaction value is not mandatory since in some cases it may be
unnecessary to repeat the specification of the action that led to the result
since the action is being referred to may be clear form the context.
Proposition 
isactionresult 

Ontology 
FIPACCL 

Description 
This
proposition is true iff the object referred to is the
result of an action which is either given in the optional cspaction value or is well defined in
the context of the agent conversation. 

Domain 
cclobject / cclproposition, cspaction 
To ensure that domain ontologies can be easily bound into the content language, FIPA CCL imposes some minimal restrictions on the form of an ontology that is used with it. In particular the ontologies must define items of the following types:
· Types of variables should correspond to the object defined in Section 2.1.16, Domain Variable Type. Variable types define the form of information which variables of that type can express, for example, times, dates, places, airlines, etc.
· Roles of variables should correspond to the object defined in Section 2.1.14, Domain Role Term. A variable role corresponds to the variables function in the current problem solving context, for example, 'flight', 'outbound', 'meeting location', etc. Agents can attach roles to variables to keep track of the semantic interpretation of the choice problem.
· Values are the available options for choices and correspond to the domainterm terminals defined in Section 2.1.15. This can be any usefully defined term in the domain ontology.
· Variable domain ranges should correspond the allowed range expressions in the domain, where a range is a well defined set or continuum of domain terms. Domain ranges correspond to the object defined Section 2.1.13, Domain Range. Since some variable domains are often best compactly expressed as ranges rather than enumerated, an ontology may define the legal types of ranges available. Examples include, ranges of time (workingday = 8.00am 5.00pm), ranges of sizes (shoe size = 3 12), etc. For some ontologies, domain ranges may be parameterised expressions, for example, a time ontology may include a expression for a range such as hours (start, end) indicating the range of hours between the start and end hours given.
Effectively these restrictions impose typing requirements on the domain ontology to be used with FIPA CCL. How the types are expressed in any particular ontology is application and ontology dependent and hence not addressed in this specification.
[Dechter92] Constraint Networks, Dechter, R. In:
Encyclopedia of Artificial Intelligence, Wiley, pages 276285, 1992.
[FIPA00061] FIPA ACL Message
Structure Specification. Foundation for Intelligent
Physical Agents, 2000. http://www.fipa.org/specs/fipa00061/
[Freuder82] A Sufficient Condition of BacktrackFree Search, Freuder, EC. In: Journal of the ACM, 29(1), pages 2432, January 1982.
[Mackworth77] Consistency in Networks of Constraints, Mackworth, A. In: Artificial Intelligence, Vol. 8, 1977.
[SamHaroud96] Consistency Techniques for Continuous Constraints, SamHaroud, D and Faltings, B. In: Constraints, 1(1), pages 85118, 1996.
[Tsang94] Foundations
of Constraint Satisfaction, Tsang, E. Academic Press, 1994.
[vanBeek97] Constraint Tightness and Looseness Versus
Local and Global Consistency, van Beek, P and Dechter, R. In: Journal of the
ACM, 44(4), pages 549566, July 1997.
[Waltz
75] Generating Semantic Descriptions
from Drawings of Scenes with Shadows, Waltz, D I. In: The Psychology of
Computer Vision, McGrawHill, 1975.
This annex gives a concrete syntax for the FIPA CCL language as an XML DTD. This syntax is the default syntax for FIPA CCL and the only one currently defined. Any agent sending an ACL message with the :content parameter set to FIPACCL is assumed to have used this syntax.
<?xml
version="1.0" encoding="UTF8"?>
<!=== DTD
of the Choice Content Language (CLL). This definition is based in the document
"A FIPA Content Language for Expressing Agent Choice: Constraint Choice
Language (FIPACCL)" ===>
<!ELEMENT
Expression (Object
 Action
 Proposition)>
<!Definition
of an Object in FIPACCL>
<!ENTITY %
objects "CSP
 CSPsolution

CSPsolutionlist">
<!ELEMENT
Object (CSP
 CSPsolution
 CSPsolutionlist)>
<!ATTLIST
Object Name ( %objects; ) #REQUIRED>
<!== CSP
===>
<!ELEMENT
CSP (CSPvariable*, CSPrelation*, CSPexclusion*)>
<!ATTLIST
CSP CSPref ID #IMPLIED>
<!===
CSPsolution ===>
<!ELEMENT
CSPsolution (CSPvariableassignment*)>
<!ATTLIST
CSPsolution href CDATA #REQUIRED>
<!===
CSPsolutionlist ===>
<!ELEMENT
CSPsolutionlist (CSPsolution+)>
<!ATTLIST
CSPsolutionlist href CDATA #REQUIRED>
<!Definition
of an Action in FIPACCL>
<!ENTITY %
actions "CSPgiveconstraints
 CSPgivevalues
 CSPsolve
 CSPsolvelist">
<!ELEMENT
Action (CSPgiveconstraints
 CSPgivevalues
 CSPsolve
 CSPsolvelist)>
<!ATTLIST
Action Name (%actions;) #REQUIRED>
<!===
CSPgiveconstraints ===>
<!ELEMENT
CSPgiveconstraints (CSP

CSPidentifier)>
<!===
CSPgivevalues ===>
<!ELEMENT
CSPgivevalues (CSP
 CSPidentifier)>
<!===
CSPsolve ===>
<!ELEMENT
CSPsolve (CSP  CSPidentifier)>
<!ENTITY %
resultvalues "CSPsolution
 CSPinsoluble

CSPsolutionlist">
<!===
CSPsolvelist ===>
<!ELEMENT
CSPsolvelist (CSP
 CSPidentifier)>
<!Definition
of a Proposition in FIPACCL>
<!ENTITY %
propositions "CSPinsoluble
 CSPsoluble
 CSPunknown">
<!ELEMENT
Proposition (CSPinsoluble
 CSPsoluble
 CSPunknown)>
<!ATTLIST
Proposition Name ( %propositions; ) #REQUIRED>
<!===
CSPinsoluble ===>
<!ELEMENT
CSPinsoluble (CSP
 CSPidentifier)>
<!===
CSPsoluble ===>
<!ELEMENT
CSPsoluble (CSP
 CSPidentifier)>
<!===
CSPunknown ===>
<!ELEMENT
CSPunknown EMPTY>
<!ATTLIST
CSPunknown href CDATA #REQUIRED>
<!===
IScsp ===>
<!ELEMENT
IScsp (CSP
 CSPidentifier)>
<!===
ISactionresult ===>
<!ELEMENT
ISactionresult (Actionperformed?, Resultobtained)>
<!ELEMENT
Resultobtained (Object
 Proposition)>
<!ELEMENT
Actionperformed (Action)>
<!Apart
from the three main types of items listed above (Actions, Objects and
Propositions) there are also other constructs in the CL which form part of the
main objects but cannot form valid sentences by themselves.>
<!===
CSPidentifier ===>
<!ELEMENT
CSPIdentifier EMPTY>
<!ATTLIST
CSPIdentifier href CDATA #REQUIRED>
<!===
CSPdomain ===>
<!ELEMENT
CSPdomain (Tags*)>
<!ATTLIST
CSPdomain Range CDATA #REQUIRED>
<!ELEMENT
Tags EMPTY>
<!ATTLIST
Tags Name CDATA #REQUIRED>
<!===
CSPvalue ===>
<!ELEMENT
CSPvalue (Elements+, Tags*)>
<!ATTLIST
CSPvalue Npart CDATA #REQUIRED>
<!ELEMENT
Elements EMPTY>
<!ATTLIST
Elements Value CDATA #REQUIRED>
<!===
CSPvariable ===>
<!ELEMENT
CSPvariable (Role*, Domain*)>
<!ATTLIST
CSPvariable Name CDATA #REQUIRED
Type CDATA
#REQUIRED>
<!ELEMENT Role
(#PCDATA)>
<!ELEMENT
Domain (CSPrange
 CSPvalue+
 CSPvaluelist)>
<!===
CSPrange ===>
<!ELEMENT
CSPrange (Tuplerange) >
<!ATTLIST
CSPrange Range CDATA #REQUIRED>
<!ELEMENT
Tuplerange EMPTY>
<!ATTLIST
Tuplerange Values CDATA #REQUIRED>
<!===
CSPvariableassignment ===>
<!ELEMENT
CSPvariableassignment (CSPvalue)>
<!ATTLIST
CSPvariableassignment Name CDATA #REQUIRED>
<!===
CSPvaluelist===>
<!ELEMENT
CSPvaluelist (Listvalues, Tags*) >
<!ATTLIST
CSPvaluelist Npart CDATA #REQUIRED>
<!ELEMENT
Listvalues EMPTY>
<!ATTLIST
Listvalues Values CDATA #REQUIRED>
<!Constraint
Related Items>
<!===
CSPexclusion ===>
<!ELEMENT
CSPexclusion (ExcludedValues+, Tags*)>
<!ATTLIST
CSPexclusion Variablename CDATA #REQUIRED>
<!ELEMENT
ExcludedValues (CSPvalue)>
<!===
CSPrelation ===>
<!ENTITY %
relation "intentionalEquality
 intentionalInequality
 IntensionalGreatherThan
 IntensionalLessThan

IntensionalGreatherThanEqual
 IntensionalLessThanEqual

IntensionalEmpty">
<!ELEMENT
CSPrelation (Tags*)>
<!ATTLIST
CSPrelation Variables CDATA #REQUIRED
Relationtype (%relation;)
#REQUIRED
Indices CDATA #REQUIRED>
FIPA CCL is primarily intended for information gathering and problem solving for tasks involving multiple interrelated choices. In general information gathering and problem solving tasks can be broken down into four steps[2]:
2. Information gathering,
3. Information fusion, and,
4. Problem solution.
This section gives a brief overview of using FIPA CCL in each of these
steps.
Modelling
a choice problem in the FIPA CCL language requires the problem to be formulated
as a CSP:
·
Identifying what the choices are which become the variables
in the problem formulation,
·
Identifying which options are available for each of the
choice which generates the domains of values for each of the variables, and,
·
Specifying how choices are related which generates the
constraints (relations and exclusions) which apply to problem solutions.
This
process is exactly what would be required when formulating problems so that
they can be expressed in FIPA CCL messages. The process is in general
intuitive, although there may also exist multiple formulations of a particular
problem all of which are equivalent in the solution space they describe
(although they may be easier or harder to solve depending upon the solution
techniques applied).
FIPA CCL uses a particular style of representation for constraints which allows only two types of constraints:
· Exclusions which act on a single variable and are specified as a nogood list, that is, a list of values which this variable may not take.
· Binary intensional relations which act on two variables and are restricted to a closed set of eight general types of relations, that is, the set {=, Ή, <, >, £, ³, ^, null}.
The use of tuplevalued variables allows the language to handle arbitrary nary constraints by introducing variables whose values represent the tuples allowed by the constraint and then linking the n variables involved in the nary constraints to the tuple valued variable using binary relations. The advantage of this implementation is that solving or consistency engines can be restricted to unary and binary constraints.
As an example of representing nary constraints in terms of binary constraints consider a ternary constraint over three variables (Hotel, City and RoomType):
· Variable: Hotel, Values: {Marriott, Intercontinental, HyattRegency}.
· Variable: City, Values: {New York, Washington, Chicago}.
· Variable: RoomType, Values: {standard, suite}.
· Constraint: Goodlist: {( Hotel: Marriott, City: New York, RoomType: suite), (Hotel: Intercontinental, City: Washington, RoomType: standard)}.
This can be converted into the following binary CSP by adding a tuple valued variable which represents the goodlist:
· Variable: Hotel, Values: {Marriott, Intercontinental, HyattRegency}.
· Variable: City, Values: {New York, Washington, Chicago}.
· Variable: RoomType, Values: {standard, suite}.
· Variable: Constraint1, Values: {(Marriott, NewYork, suite), (Intercontinental, Washington, standard)}.
· Constraint: (IntensionalEquality, Variable 1: Hotel, Variable 2: Constraint1, Indices: {(1, 1)}).
· Constraint: (IntensionalEquality, Variable 1: City, Variable 2: Constraint1, Indices: {(1, 2)}).
· Constraint: (IntensionalEquality, Variable 1: RoomType, Variable 2: Constraint1, Indices: {(1, 3)}).
The same mechanism of using a tuplevalued variable can be used to express constraints which might normally be expressed using an extensional constraint, such as a good list or nogood list, that is, lists of allowed or excluded combinations.
Giving a list of all the allowed combinations of values between a set of variables defines an extensional relation, such as for clothing for example:
· Variable: Hat, Values: {green, red, brown, black}.
· Variable: Shirt, Values: {white, red, pink}.
· Constraint: Goodlist: {(Hat: green, Shirt: white), (Hat: red, Shirt: white), (Hat: black, Shirt: red)}.
This relates the two variables Hat and Shirt by giving a list of the allowed combinations. The same type of representation could be used to express combinations which are not allowed and resulting in a nogood list. In FIPA CCL this would be expressed using three variables, using only intensional relations:
·
Variable:
Hat, Values: {green, red, brown,
black}.
·
Variable:
Shirt, Values: {white, red, pink}.
·
Variable:
ConstraintHatShirt, Values: {(green, white), (red,
white), (black, red)}.
·
Constraint:
ConstraintHat: (IntensionalEquality, Variable 1: Hat, Variable 2: ConstraintHatShirt, Indices: {(1, 1)}).
·
Constraint:
ConstraintShirt: (IntensionalEquality, Variable 1: Shirt, Variable 2: ConstraintHatShirt, Indices: {(1, 2)}).
The two intensional constraints therefore link the Hat and Shirt variables to a new third variable which contains the list of allowed tuples. This removes any need for lists of valid combinations to be represented as constraints.
Once a choice problem had been modelled as a CSP, problem information can be added to the CSP representation to constrain or expand the range of options available. This information can be obtained from other agents by sending requests for cspgiveconstraints and cspgivevalues:
· Requesting cspgiveconstraints results in a CSP with more constraints (exclusions or relations) posted on the set of possible combinations, and,
· Requesting cspgivevalues results in a CSP with more possible options being added to the CSP variables (choices).
The results of both these actions is a new CSP which can be composed with the original CSP to create a new CSP with more information about the problem being solved. An agent may request information from several sources by:
· Sending the complete CSP to several agents and asking for constraints or values. This case would be most useful if the agents being queried have similar roles in the scenario e.g. they are all airline flight databases but for different companies. The agent trying to solve the choice problem would receive several sets of information for the same problem.
· Dividing up the whole problem into smaller pieces (each containing a not necessarily disjoint  subset of variables and constraints) and sending requests about each piece to different information agents. This would be most useful when communicating with agents which have different specialties, that is, one hotel database agent, one airline agent and one ticket booking agent. In each communication the interaction concerns only the part of the problem related to the queried agents specialty.
Once information has been gathered the agent solving the problem can pass on to the information fusion step.
FIPA CCL includes a way of tagging values and constraints uniquely which allows problems to include a representation of where information came from. In the results of both the cspgiveconstraints and cspgivevalues functions the domain values and constraints returned can be grouped together using a tag (a unique symbol). The tags are given in the tags parameter of the cspvalue, cspexclusion and csprelation items.
There are two ways of combining CSPs which contain identical sets of variables:
· So that the resulting solution space is the intersection of the solutions of each of the participant CSPs. Hence all solutions to the new CSP satisfy all the participant CSPs. In this document this is referred to as a conjunctive combination.
· So that the resulting solution space is the union of the solutions of each participant CSPs. Here each solution to the new CSP satisfies at least one of the participant CSPs. In this document this is referred to as a disjunctive combination.
These are the basic operations required for compositions. Both operations can be carried out by straightforward algorithms as long as CSPs have the same variables, but may be require transformations to the participant CSPs beforehand.
The mechanism for combining relations relies on the use of tags to achieve the correct semantics. This is best understood by considering an example. In Figure 1, variables X1 and X2 are linked with an equality constraint and tag T1, the solution space is therefore ((a, a), (b, b)).
Figure 1: Constraint Problem 1
In Figure 2, the same variables are connected by a ³ constraint[3], but with a different tag T2. Its solution space is ((b, b), (c, b), (c, c)).
Figure 2: Constraint Problem 2
Hence the tags define two sets of information for the two variables X1 and X2. The information associated with Tag T1 gives on set of possibilities for the variable domains and a constraint. The information associated with Tag T2 gives a second set of domains and a different constraint. Some information (such as the value b in both domains) is common to both information sets.
Exclusions are handled in the same manner simply by treating them as constraints on a single variable. It should also be noted that when relations have the same tags, they can be combined directly by combining their types, that is, £ and ³ combined give =.
Given the two example CSPs in the previous section we can now consider forming the intersection of the two solution spaces described by tags T1 and T2. This intersection would give only the solution ((b, b)) as valid. To do this, we need to intersect the domains for each variable. We then make sure that both constraints apply to the remaining values simultaneously by letting the tags of the remaining values be the union of the tags they had in the original problems, thus making all their constraints applicable (see Figure 3).
Figure 3: Constraint Problem 3
For the same example we can also form the union of the two solution spaces: a new CSP that has the solution space ((a, a), (b, b), (c, b), (c, c)). To do this, we need take the union of the domains for each variable. We also take the union of the constraints but constraints only apply to the values which have the appropriate tags that is, constraints only apply to the values they applied to in the original problems (see Figure 4).
Figure 4: Constraint Problem 4
If two CSPs to be composed do not have exactly the same variables, the two composition operations need to be extended.
This composition is a straightforward extension of the conjunctive composition for the case where variable sets were identical. when composing two CSPs CSP_{1} and CSP_{2} (to form CSP_{Result}):
· All constraints from both CSP_{1} and CSP_{2} hold in CSP_{Result} (as defined for the standard composition operation),
· All variables from both CSP_{1} and CSP_{2 }are present in CSP_{Result}, and,
· All variables in CSP_{Result} must be instantiated s.t. both participant CSPs are satisfied by any solution to the whole CSP_{Result}.
The disjunctive case is a little more complex. When composing two CSPs CSP_{1 }and CSP_{2} (to form CSP_{Result}), variables are treated as follows:
· Variables in the intersection CSP_{1} CSP_{2} (set I): for the variables which exist in both CSPs the required disjunctive composition operation can be directly applied and all variables and constraints between them appear in CSP_{Result}.
· Variables outside the intersection CSP_{1} CSP_{2} (set NI): these variables exist in only one of the participant CSPs. All these variables are also added to CSP_{Result} but are modified in the process by adding a special value * to each of their domains, where * stands for unused.
To add the variables in CSP_{1 }which do not appear in CSP_{1} (I.e. are in the intersection of CSP_{1} and NI call this set NI_{1}):
The same process is performed for the variables in CSP_{2} and not in CSP_{1} (set IN_{2}) but with a different tag generated in step 1 of the algorithm.
Finally, all the * values are considered compatible with any relation, this makes it possible to distinguish solutions to the problem which assign a value to the variable in question and those that do not. The algorithm uses the tag mechanism to distinguish the new variables and relations from the existing ones: since the * value is compatible with any relation, the set of solutions of the revised CSP is exactly the solutions of the original CSP with the * value added for the new variable. Furthermore, the unique tag ensures that this same property continues to hold when the new CSP is combined with another one.
Once a problem has been modelled, information gathered and composed to form a single choice problem, then this can be solved. The semantic meaning behind the variables and constraints in the task model can be stripped away during the solution process and the problem can be solved as a generic CSP. This allows powerful CSP problem solving algorithms to be applied.
In the context of the FIPA CCL language there are two main ways to solve a constructed CSP problem:
· Implementation of one (or several) solution algorithms in the problem solving agent. Solution algorithms range from very simple compact approaches to elaborate specialised techniques. The next section gives an example of a simple search algorithm which would suffice for most small CSP problems. More advanced algorithms can be found in, among others; [Tsang94], the proceedings of major AI conferences and the proceedings of specialist constraints conferences such as Constraint Programming.
· Usage of a dedicated CSP solving agent which implements a suite of algorithms for solving algorithms for generic CSPs. Such solver agents can be requested to solve choice problems using the FIPA CCL language actions cspsolve and cspsolvelist.
This section gives a basic solution algorithm for CSP problems to provide the minimum for problem solving using FIPA CCL. The backtracking search algorithm given here instantiates variables in some fixed order and is perhaps the most commonly used CSP search techniques (many advanced methods are derived from it). The following gives the general idea:
The procedure also terminates if it backtracks to step 2 and the first variable in the sequence has no remaining possible values in its domain. This indicates that all value combinations are invalid and the CSP has no solution.
This procedure is sound and complete since the backtracking procedure essentially explores the search tree of possible variable assignment combinations. Constraints are checked at each step (ensuring a nonvalid combination is never allowed) and the backtracking step is eventually forced to explore the whole search tree.
[Dechter92] Constraint Networks, Dechter, R. Encyclopaedia of Artificial Intelligence, Wiley, pages 276285, 1992.
[Tsang94] Foundations
of Constraint Satisfaction, Tsang, E. Academic Press, 1994.