Planning with complex actions.
Sheila A. McIlraith, Ronald Fadel · 2002
In this paper we address the problem of planning with complex actions. We are motivated by the problem of automated Web service composition, in which planning must be performed using pre-defined complex actions or services as the build-ing blocks of a plan. Planning with complex ac-tions is also compelling in primitive action plan-ning domains because it enables the exploitation of reusable subplans, potentially improving the efficiency of planning. This paper provides a formal, semantically-justified account of how to plan with complex actions using operator-based planning techniques. A key contribution of this work is the definition, characterization, and com-putation of preconditions and conditional effects for complex actions. While we use the situation calculus and Golog to formalize the task and our solution, the results in this paper are directly ap-plicable to most action theories and planning sys-tems. In particular, we have developed a PDDL-equivalent compiler that computes the precon-ditions and effects of complex actions, thus en-abling wide-spread use of these results. Finally we provide an approach to planning that enables us to exploit deductive plan synthesis or alterna-tively ADL planners to plan with complex ac-tions. Our approach to complex-action planning is sound and complete relative to the correspond-ing primitive action domain. 1