On the role of disjunctive representations and constraint propagation in refinement planning

Abstract

Most existing planners intertwine the refinement of a partial plan with search by pushing the individual refinements of a plan into different search branches. Although this approach reduces the cost of handling partial plans, it also often leads to search space explosion. In this paper, we consider the possibility of handling the refinements of a partial plan together (without splitting them into search space). This is facilitated by disjunctive partial plan representations that can compactly represent large sets of partial plans. Disjunctive representations have hitherto been shunned since they may increase the plan handling costs. We argue that performance improvements can be obtained despite these costs by the use of (a) constraint propagation techniques to simplify the disjunctive plans and (b) CSP/SAT techniques to extract solutions from them. We will support this view by showing that some recent promising refinement planners, such as the GRAPHPLAN algorithm [2], can be seen as deriving their power from disjunctive plan representations. We will also present a new planning algorithm, UCPOPD, which uses disjunctive representations over UCPOP [19] to improve performance. Finally, we will discuss the issues and tradeoffs involved in planning with disjunctive representations.