Total Order Planning Is More Efficient than We Thought

Abstract

In this paper, we present VVPLAN, a planner based on a classical state space search algorithm. The language used for domain and problem representation is ADL (Pednault 1989). We have compared VVPLAN to UCPOP (Penberthy and Weld 1992)(Weld 1994), a planner that admits the same representation language. Our experiments prove that such an algorithm is often more efficient than a planner based on a search in the space of partial plans. This result is achieved as soon as we introduce in VVPLAN’s algorithm a loop test relating to previously visited states. In particular domains, VVPLAN can also outperform IPP (Koehler et al. 1997), which makes a planning graph analysis as GRAPHPLAN. We present here the details of our comparison with UCPOP, the results we obtain and our conclusions.