[ 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 publications: [PUBLink] [PUBLink] [PUBLink])

This chapter has provided the basic mechanism to handle arbitrary structures for an agent's behavior plan, enabling us to treat open-world problems with a potentially infinite number of objects. Being embedded in the general constraint programming paradigm, the framework is not restricted to a certain way of exploring the search space, e.g., according to an increasing plan length.

Combining conventional constraint satisfaction with structural requirements enables us to formulate and solve combinatorial search problems without explicitly giving the solution's structure. The SCSP approach follows the declarative constraint programming paradigm by stating only requirements for the solution and without including information on solution generation. Productions can be deduced from the SCSP's embedding and extension graphs, which allow search to generate all potentially valid solutions. During search, the SCSP's structural constraints must be checked to ensure the graph's consistency.

SCSPs allow us to tackle a new class of problems by constraint programming techniques. An example for the need of structural alternatives is action planning, where it is not clear in advance how many and what kind of actions are needed and how they must be arranged. The same holds for configuration and design problems, where type and number of parts and the parts' relations must be determined as part of the search process.

The concept of structural constraint satisfaction contrasts with previous approaches that try to overcome the problem by considering maximal structures with deactivatable elements (e.g., [PUBLink] [PUBLink]). The use of maximal structures is useful in the case of only slightly variable structures and a known maximum. A formulation by an SCSP does not have these restrictions.

Composite CSPs [PUBLink] aim at a similar extension of the conventional constraint satisfaction paradigm as SCSPs. A composite CSP expresses subgraph alternatives in a hierarchical way. This allows optimized search guidance, but requires manual preprocessing to build the hierarchy. The creation of the hierarchy it is often problematic, as completeness and appropriate structure are not always obvious. This pre-structuring of the search space is similar to using a pre-defined static variable/value ordering within refinement search.

The combination of structural constraint satisfaction with the approach of global constraints for local search forms the basis for formulating and efficiently solving planning problems within the constraint programming framework.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek