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

For planning problems that involve resource constraints, some planning systems keep planning and resource allocation separate, e.g., the approach of Srivastava and Kambhampati [PUBLink] and the parcPLAN system [PUBLink]. The separation of planning and resource allocation prevents the systems from considering interactions between the decisions with respect to planning and resource assignment, which is a great disadvantage if resource-related properties are to be optimized. Consequently, the resources serve only as constraints for the planning problem and are not used as primary optimization goals. The same applies to resource-based planning systems that integrate planning and resource allocation, like O-Plan2 [PUBLink], IxTeT [PUBLink], the LPSAT engine's application to planning [PUBLink] and IPP's extension [PUBLink]. All of these focus primarily on optimization of the plan length, which is a rather curious approach as this property is usually irrelevant (see Section [Resources] for a discussion of decision-theoretic planning approaches).

Resource-based planning systems that are based entirely on general search frameworks like CP or OR require bounds for the plan length or the number of actions. If a correct plan cannot be found, these bounds can be expanded. Some examples here are the OR-based approach of Bockmayr and Dimopoulos [PUBLink], ILP-PLAN [PUBLink], CPlan [PUBLink] and the approach of Rintanen and Jungholt [PUBLink]. Again, these systems primarily optimize the plan-length property. An optimum with respect to resource-related optimization goals can only be found if the initial bound can be set such that the optimal solution is guaranteed to lie within this bound. This is a very hard task for specific problems and impossible at a general level. Besides, creating the maximal structures for the search space is much too costly for complex real-world problems.

The presented constraint-based planning model for the EXCALIBUR agents does not require any bounds for the plan length and allows us to integrate the planning and scheduling process and focus on resource-related optimization. The model is based on the SCSP approach and avoids the use of maximal structures by including the search for the structure as part of the satisfaction process.

The SCSP approach also allows us to tackle open-world problems in which an arbitrary number of objects can be involved. The past decade has seen the development of a few planning systems with this capability, e.g., XII [PUBLink] and PSIPLAN [PUBLink]. Satisfaction-based planners are very rare in this domain. The lack of satisfaction-based approaches to open-world planning can be explained by the massive explosion of the search space under consideration. Systems based on maximal structures cannot handle this.

The presented model involves a representation of incomplete knowledge. In contrast to contingent/MDP planning approaches, the representation here does not include alternative timelines with branching points. Only one timeline is considered, which has to be adapted in case of a failed prediction (see Section [A Single-Plan Approach]). Probabilities and incomplete knowledge about states are expressed by special values, annotations and continuous domain state resources. A limited handling of an agent's partial view of the world state can thus be realized, avoiding the combinatorial explosion of branching approaches.

The presented planning model borrows from typical constraint-based applications for resource allocation/optimization. The power of global constraints for constraint-specific representation and reasoning mechanisms for specific resource types was recognized here very early on and led to significant speed-ups in the solution process. General frameworks for planning and scheduling like Muscettola's HSTS [PUBLink] lack such specialized representation and reasoning capabilities.

Furthermore, the model uses a domain-independent representation. By contrast, constraint-based planning systems like parcPLAN and CPlan - besides their inability to search in a way that is not focused on the criterion of plan length - do not have a model for general planning, relying instead on domain-dependent encodings.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek