Adaptive Constraint-Based Agents in Artificial Environments

[SCSP]   [Grammars]   [Elements]   [Structural Constraints]   [SCSPs]   [Generation]   [Redundancy]   [Combination]   [Conclusion]

[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

Graph Elements for SCSPs

(Related publications: [PUBLink] [PUBLink] [PUBLink])

A variable of the CSP is represented by a vertex with the label Variable. It is graphically depicted by a circular vertex (see figure below).

Constraints could be represented by edges, but there are constraint types that allow a variable number of variables to be included. These constraint types will be called extensible constraints (Ce) in contrast to nonextensible constraints (Cn), such that Ce Cn = C. As the number of variables incorporated for extensible constraints may vary throughout the search, there must be a simple mechanism to include/exclude variables for constraints. Hence, a constraint is also represented by a vertex, new edges to variables being added in order to incorporate them. A constraint vertex's label corresponds to the type of the constraint. A constraint is graphically depicted by a rectangular vertex.

An SCSP allows the existence of so-called object constraints. These constraints do not restrict the variables' values, but provide structural context information. For example, for the job-shop scheduling example of the chapter's introduction, it must be known which two Start and Duration variables together form a SubTask object. Otherwise, a Machine constraint designed to check if the included SubTasks overlap might combine Start and Duration variables of different SubTasks for the check (see figure below). Object constraints act as a kind of structural broker between variables and conventional constraints. They are represented by a rectangular vertex with a dashed outline. Object constraints can be nonextensible as well as extensible, Oe On = O,   C O = Ø. Constraints of C can be connected to variables and object constraints, whereas object constraints can be connected to constraints of C as well.

Edges are used to connect vertex elements. The role/position of a variable (or constraint when speaking about objects) within a constraint is often very important. Thus, an edge's label and direction can be used to express its role/position. An edge's direction is indicated by an arrow and the label is displayed in the edge's middle (NoLabel if omitted).

The figure below shows an example graph with an extensible conventional constraint Machine, an extensible object constraint Task, two nonextensible object constraints SubTask, three extensible conventional constraints Sum and a nonextensible conventional constraint Less. The Machine constraint ensures that the Start and Duration variables of all connected SubTasks (via Tasks) do not produce an overlap. The Sum constraint restricts the sum of ()-connected variables to equal a ()-connected variable. The Less constraint restricts the ()-connected variable to be less than the ()-connected variable.

[SCSP]   [Grammars]   [Elements]   [Structural Constraints]   [SCSPs]   [Generation]   [Redundancy]   [Combination]   [Conclusion]

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek