EXCALIBUR
Adaptive Constraint-Based Agents in Artificial Environments

[GENERATION]   [Variables]   [Nonextensible Constraints]   [Extensible Constraints]   [Constraint Extensions]

[ 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. ]

Productions for Nonextensible Constraints

(Related publication: [PUBLink])

Addition

To guarantee that an extensible constraint cannot exceed its maximal configuration pmax, it must be ensured that edges to an extensible constraint with a nonempty pmax graph can only be added if the constraint's pmax graph is not exceeded. An addition production can include NACs with the involved constraints' pmax graphs to ensure that a maximal configuration is not already existent. This requires that

Requirement reqmax: If the pmax graph of an extensible constraint is nonempty, any derivation sequence of productions that is applied to the constraint's pbase graph cannot produce a graph that includes the pmax graph without producing the pmax graph before.

The pbase specification states the only consistent way to connect a nonextensible constraint with variables. Therefore, a whole pbase structure can be established by an addition production at once. Multiple similar nonextensible constraints between the same elements can be prohibited by an NAC for the addition production. This is not a vital structural constraint but saves from redundancy.

In conclusion, there must be one addition production per nonextensible constraint, which is constructed in the following way:

Construction Pnonextensiblea: The right-hand side of the addition production is equal to the constraint's embedding graph pbase. The left-hand side of the production contains the vertices of the right-hand side without the constraint itself, and an NAC that contains the right-hand side without the vertices that are connected to the constraint. In addition, the left-hand side includes an NAC for each included extensible constraint to prevent from exceeding this constraint's pmax graph. These NACs consist of a constraint's maximal embedding graph pmax such that the constraint is unified with the constraint of the left-hand side (NAC without the constraint itself).

Production PLessa in the figure below shows the addition production for the Less constraint.

The left-hand side of the addition production requires that the other vertices of pbase are already existent. To prevent from deadlocks, it must be possible to create the other vertices of pbase independently of the nonextensible constraint. This is enforced by

Requirement reqne: The occurrence of a nonextensible constraint is only allowed in its addition and deletion production.

This requirement also ensures that the pbase specification is always satisfied, as no production can connect or disconnect vertices from the constraint.

Deletion

To guarantee that an extensional constraint in the graph cannot be changed by productions below its minimal configuration pbase, it must be ensured that

Requirement reqmin: Edges to an extensible constraint can only be deleted (without deleting the constraint itself), if at least the constraint's pbase graph is preserved.

There must also be one deletion production per nonextensible constraint. It withdraws the addition of the corresponding Pnonextensiblea production:

Construction Pnonextensibled: The left-hand side of a deletion production is equal to the embedding graph pbase. The right-hand side of the production contains the vertices of the left-hand side without the constraint itself. In addition, the left-hand side includes a PAC for each included extensible constraint to prevent from falling below this constraint's pbase graph. These PACs consist of a constraint's embedding graph pbase such that the constraint is unified with the constraint of the left-hand side (PAC without the constraint itself).

Production PLessd in figure above shows the deletion production for the Less constraint.

reqd can be neglected for the deletion productions of nonextensible constraints, as no additional vertex can be connected to the constraint because of reqne. reqp is satisfied, as Pnonextensibled is the reversal of Pnonextensiblea without its NAC and as the PACs of Pnonextensibled cannot endanger the applicability as the existence of the pbase graphs is ensure by reqmin.


[GENERATION]   [Variables]   [Nonextensible Constraints]   [Extensible Constraints]   [Constraint Extensions]

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek