Integrating Constraint Models for Sequential and Partial-Order Planning

Classical planning deals with finding a (shortest) sequence of actions transferring the world from its initial state to a state satisfying the goal condition. Traditional planning systems explore either paths in the state space (state-space planning) or partial plans (plan-space planning). In this paper we show how the ideas from plan-space (partial order) planning can be integrated into state-space (sequential) planning by combining constraint models describing both types of planning. In particular, we extend our existing constraint model for sequential planning by constraints describing satisfaction of open goals. We demonstrate experimentally that this extension pays-off especially when the planning problems become harder.