Adaptive Constraint-Based Agents in Artificial Environments

[APPLICATION]   [Orc Quest Revisited]   [Domain-Independent Planning]   [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 publication: [PUBLink])

This chapter has shown that a system based on the techniques described in the previous chapters can also be applied to handle domain-independent planning tasks, even though the underlying techniques are specifically designed to promote a search guided by domain-dependent knowledge. The very fast specialized solution for the Orc Quest example, as well as the promising results for domain-independent planning tasks, indicate the strength of the underlying technology.

A simple version of a State Resource Constraint featuring a symbolic state domain was presented. Much more complex SRCs will be necessary to tackle more sophisticated problems, e.g., SRCs with state domains of integer numbers, real numbers or even sets (as shown in this figure), SRCs with enhanced temporal projections like continuous change (see this figure), and SRCs with enhanced support of precondition checks like state-related or temporal ranges. These extensions are beyond the scope of this thesis and will be the subject of future research.

The system's approach of looking at the problem from a simplified perspective (of one constraint) to choose a heuristic to improve the overall problem is similar to the way in which some other powerful planning approaches proceed, e.g., the approach of Ephrati, Pollack and Milshtein [PUBLink], HSP [PUBLink] and Fast-Forward [PUBLink]. It has actually proved to be a good approach for solving numerous other problems (see also [PUBLink]).

The improvement heuristics developed for the constraints have a lot in common with those of the DCAPS/ASPEN/CASPER planning systems [PUBLink] [PUBLink] [PUBLink] and scheduling systems like GERRY [PUBLink] and OPIS [PUBLink]. The OPIS scheduler is probably the most advanced system with respect to its repair heuristics, as a more sophisticated conflict analysis of the schedules is applied. An integration and extension of these methods for planning tasks seems to be a promising direction for future improvements.

Our system's iterative improvement by local search makes it possible to easily interleave the planning process with sensing and execution. Only a few agent/planning system are able to do this (see also Section [Autonomous Agents]). The approach most similar to ours is the CASPER system [PUBLink], which also uses local search strategies to repair a plan. Slightly similar is also the repair strategy of O-Plan [PUBLink], tackling broken plans by a set of domain-dependent repair heuristics. A very different approach is applied in CPEF [PUBLink], which is based on hierarchical refinement planning and applies a dependency analysis to restart the planning process from the lowest possible hierarchy level.

[APPLICATION]   [Orc Quest Revisited]   [Domain-Independent Planning]   [Conclusion]

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek