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

The presented combination of local search and constraint programming provides an important building block for EXCALIBUR's agents. Many other publications focus on problem-specific local search solutions. Improved efficiency is the main goal, generality often being disregarded. In contrast, our approach's modular structure of the constraints makes it easy to vary, reuse and extend problem descriptions.

Other authors have tackled the problem of combining local search with search frameworks on a more general level, too. This includes work on Boolean satisfiability problems like GSAT [PUBLink] [PUBLink] and Walksat [PUBLink], the processing of linear pseudo-Boolean constraint problems [PUBLink], and approaches for CSPs like coalition forming [PUBLink] and the well-known min-conflicts heuristic [PUBLink] with its extension and generalization by GENET [PUBLink]. The most important difference between our work and these approaches is the ability of the global constraints to exploit domain-specific information by including constraint-specific search control and representation knowledge. In contrast to low-level constraint programming approaches, which correspond rather to SAT- or OR-based approaches, the use of higher-level constraints is more in keeping with the basic intentions of constraint programming. Fine-grained constraints allow a wide application range, but the low-level problem decomposition also deprives the search process of most of the domain-specific knowledge.

The results of the presented case study indicate that the global constraint approach's revision of a current state on a more global level with an inclusion of domain-specific knowledge makes the search quite resistant to getting caught in local optima or on plateaus. Techniques to escape from local optima and plateaus, like randomization, random walks or tabu lists, had only a limited effect, and this for some decision points only. The advantage of these techniques further decreased with the inclusion of more domain knowledge.

The concept of global constraints was originally used for refinement search (e.g., by le Pape [PUBLink] and Puget and Leconte [PUBLink]). Transferring it to a local search context makes it possible to get an efficient and declarative handle on local search, while preserving features like reusability and maintenance.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek