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. ] |
(Related publication: [PUBLink])
To guarantee that an extensible constraint cannot exceed its maximal configuration p_{max}, it must be ensured that edges to an extensible constraint with a nonempty p_{max} graph can only be added if the constraint's p_{max} graph is not exceeded. An addition production can include NACs with the involved constraints' p_{max} graphs to ensure that a maximal configuration is not already existent. This requires that
Requirement req_{max}: If the p_{max} graph of an extensible constraint is nonempty, any derivation sequence of productions that is applied to the constraint's p_{base} graph cannot produce a graph that includes the p_{max} graph without producing the p_{max} graph before.
The p_{base} specification states the only consistent way to connect a nonextensible constraint with variables. Therefore, a whole p_{base} 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 P_{nonextensiblea}: The right-hand side of the addition production is equal to the constraint's embedding graph p_{base}. 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 p_{max} graph. These NACs consist of a constraint's maximal embedding graph p_{max} such that the constraint is unified with the constraint of the left-hand side (NAC without the constraint itself).
Production P_{Lessa} 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 p_{base} are already existent. To prevent from deadlocks, it must be possible to create the other vertices of p_{base} independently of the nonextensible constraint. This is enforced by
Requirement req_{ne}: The occurrence of a nonextensible constraint is only allowed in its addition and deletion production.
This requirement also ensures that the p_{base} specification is always satisfied, as no production can connect or disconnect vertices from the constraint.
To guarantee that an extensional constraint in the graph cannot be changed by productions below its minimal configuration p_{base}, it must be ensured that
Requirement req_{min}: Edges to an extensible constraint can only be deleted (without deleting the constraint itself), if at least the constraint's p_{base} graph is preserved.
There must also be one deletion production per nonextensible constraint. It withdraws the addition of the corresponding P_{nonextensiblea} production:
Construction P_{nonextensibled}: The left-hand side of a deletion production is equal to the embedding graph p_{base}. 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 p_{base} graph. These PACs consist of a constraint's embedding graph p_{base} such that the constraint is unified with the constraint of the left-hand side (PAC without the constraint itself).
Production P_{Lessd} in figure above shows the deletion production for the Less constraint.
req_{d} can be neglected for the deletion productions of nonextensible constraints, as no additional vertex can be connected to the constraint because of req_{ne}. req_{p} is satisfied, as P_{nonextensibled} is the reversal of P_{nonextensiblea} without its NAC and as the PACs of P_{nonextensibled} cannot endanger the applicability as the existence of the p_{base} graphs is ensure by req_{min}.
[GENERATION] | [Variables] [Nonextensible Constraints] [Extensible Constraints] [Constraint Extensions] |
For questions, comments or suggestions, please contact us.
Last update:
May 20, 2001 by Alexander Nareyek