Planning parallel actions

AbstractThis paper presents an integrated view of a wide range of planning systems derived from different theoretical foundations. The work is motivated by the need to provide a clear foundation from which a systematic study of search and representation issues in planning can be conducted. An evolutionary path is identified which shows how the classical (state-based) planning strategy can be incrementally refined into strategies capable of generating parallel plans. This is achieved by considering a succession of planning strategies having a progressively deeper involvement with interval-based representations. Each strategy is defined in terms of a plan representation, truth criterion and an example plan generation procedure which maps out a clearly specified search graph. The capabilities and limitations of each strategy are compared. This approach enables much of the wisdom embedded in existing planners based on the specified strategies to be distilled and unified. The succession of planning strategies identified in this paper define a framework within which fundamental design issues can be considered such as the level of commitment a constraintposting planner should make during its search for a solution. The framework also highlights the need for practical planners to prevent synergistic interference between parallel actions in an efficient manner