| EXCALIBUR Adaptive Constraint-Based Agents in Artificial Environments |
| [DOCUMENTATION] | [Preface] [Introduction] [Local] [SCSP] [Model] [Application] [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. ] |
(Related publications: [PUBLink] [PUBLink])
EXCALIBUR's agents need to adapt their behavior in real time to new situations. Conventional refinement-based constraint programming techniques are not suitable for these requirements. Thus, as discussed in Section [Introduction], our agents will be based on local search. This chapter presents a technique to combine local search with constraint programming.
The use of local search has become very popular in recent years as applications have begun to tackle complex real-world optimization problems for which complete (refinement) search methods are still not powerful enough.
Conventional ways of using local search are difficult to generalize. Increased efficiency is the only goal, generality often being disregarded. It is quite common to define highly sophisticated and problem-tailored representations with specialized neighborhoods and successor selection methods (see [PUBLink] for examples). From a software engineering point of view, this is not a good idea. Integrating complex, heterogeneous problems in a monolithic system hinders the system's reuse, extension and modification.
Other approaches take the general constraint programming framework as starting point and try to introduce local search methods for constraint satisfaction. Through the use of CSP formulations, local search acquires a general application-independent framework. CSP formulations used with local search approaches typically involve only very basic constraint types, e.g., linear inequalities or binary constraints. The problem with this kind of formulation is that the inherent problem structure is mostly lost by the necessary translation of the problem to this low-level formulation. Domain-specific knowledge about appropriate representations and search control is only available at a higher level and cannot be used. Consequently, these methods frequently fail because they have only a very limited view of the unknown search-space structure.
This work attempts to overcome the drawbacks of these two local search approaches - monolithic problem-tailored and general low-level - by using global constraints. The use of global constraints for local search allows us to revise a current state on a more global level with domain-specific knowledge, while preserving features like reusability and maintenance. The proposed strategy is demonstrated on a dynamic job-shop scheduling problem, which is a subproblem of EXCALIBUR's planning framework.
Local search techniques provide a solution at any time, the quality of the solution being subject to constant improvement. This anytime feature makes it worthwhile evaluating the whole solution process, not just the final result. To have a measure for the utility of intermediate states as well, we can extend the CSP formulation to weighted CSPs (WCSPs). In WCSPs, constraints have associated costs, which are dependent on the constraint variables' assignments. The goal is to minimize the total sum of costs, which provides us with a useful cost function for local search. A value of zero for the costs means total satisfaction. This graded consistency measure is essential for our approach, as we cannot expect to achieve an agent's total satisfaction because of the limited reasoning time.
| [DOCUMENTATION] | [Preface] [Introduction] [Local] [SCSP] [Model] [Application] [Conclusion] |
For questions, comments or suggestions, please contact us.
Last update:
May 19, 2001 by Alexander Nareyek