Fast Planning Through Planning Gra ph Analys is∗Avrim L. BlumSchool of Computer ScienceCarnegie Mellon UniversityPittsburgh PA [email protected] L. FurstSchool of Computer ScienceCarnegie Mellon UniversityPittsburgh PA [email protected](Final version in Artificial In telligence, 90:281–300, 1997)AbstractWe introduce a new approach to planning in STRIPS-like domains based on con-structing and analyzing a compact structure we call a Planning Graph. We describe anew pla nner, Graphplan, that uses this paradigm. Graphplan always returns a shortest-possible partial-order plan, or states that no valid plan exists.We provide empirical e vidence in favor of this approach, showing that Graphplanoutperforms the total-order planner, Prodigy, and the partial-order planner, UCPOP,on a variety of interesting natural and artificial planning problems. We also give empir-ical e vidence that the plans produced by Graphplan are quite sensible. Since searchesmade by this approach are fundamentally different from the searches of other commonplanning methods , they provide a new perspective on the planning problem.Keywords: General Pur pose Planning, STRIPS Planning, Graph Algorithms, PlanningGraph Analysis.1 IntroductionIn this paper we introd uce a new planner, Graphplan, which plans in STRIPS-like domains.The algorithm is based on a paradigm we call Planning Graph Analysis. In this appr oach,rather than immediately embarking upon a s earch as in standard planning methods, thealgorithm instead begins by explicitly constructing a compact structure we call a PlanningGraph. A Planning Graph encodes the planning problem in such a way that many usefulconstraints in herent in the problem become explicitly available to reduce the amount ofsearch needed. Furthermore, P lanning Graphs can be constructed quickly: they have poly-nomial size and can be built in polynomial time. It is worth pointing out that a Planning∗This research is sponsored in part by the Wright Laboratory, Aeronautical Systems Center, Air ForceMateriel Command, USAF, and the Advanced R esearch Projects Agency (ARPA) under grant numberF33615-93-1-1330. The first author is also supported in part by NSF National Young Investigator grantCCR-9357793 and a Sloan Foundation Research Fellowship. The second author is supported in part by NSFgrant CCR-9119319. Views and conclusions contained in this document are those of the authors and sh ouldnot be interpreted as n ecessarily representing official policies or endorsements, either expressed or implied,of Wright Laboratory or the United St ates Government.1Graph is not the state-space graph, which of course could be huge. In fact, unlike th estate-space graph in which a plan is a path through the graph, in a Planning Graph a planis essentially a flow in the network flow sense. Planning Graphs are closer in spirit to theProblem Space Graphs (PSGs) of Etzioni[1990], though unlike PSGs, Planning Graphs arebased n ot only on domain information, but also th e goals and initial conditions of a pr oblemand an explicit notion of time.Planning Graphs offer a means of organizing and maintaining search information thatis reminiscent of the efficient solutions to Dynamic Programming problems. PlanningGraph Analysis appears to have significant practical value in solving planning problemseven though the inherent complexity of STRI PS plannin g, which is at least PSPACE-hard(e.g., see Bylander[1994]), is much greater than the complexity of standard Dynamic Pro-gramming problems. We provide empirical evidence on a variety of “natural” an d artificialdomains showing that Planning Graph Analysis is able to provide a quite substantial im-provement in running time.The Graphplan planner uses the Planning Graph that it creates to guide its search fora plan. The search that it performs combines aspects of both total-order and partial-orderplanners. Like traditional total-order planners, Graphplan makes strong commitments inits search. When it considers an action, it considers it at a specific point in time: forinstance, it might consider placing the action ‘move Rocke t1 from London to Paris’ ina plan at exactly time-step 2. On the other hand, like partial-order planners[Chapman,1987][McAllester and R osenblitt, 1991][Barrett and Weld, 1994][Weld, 1994], Graphplangenerates partially ordered plans. For instance, in Veloso’s rocket problem (Figure 1), theplan that Graphpla n finds is of the form: “In time-step 1, appr op riately load all the objectsinto the rockets, in time-step 2 move the rockets, and in time-step 3, unload the rockets.”The semantics of such a plan is that the actions in a given time step may be performedin any desired order. Conceptually this is a kin d of “parallel” plan[Knoblock, 1994], sinceone could imagine executing the actions in three time steps if one had as many workers asneeded to load and u nload and fly the rockets.One valuable feature of our algorithm is that it guarantees it will find the shortest planamong those in which independent actions may take place at the same time. Empiricallyand su bjectively these sorts of plans seem p articularly sensible. For example, in StuartRussell’s “flat-tire world” (the goal is to fix a flat tire and then return all the tools backto where they came from; see the UCPOP domains list), the plan produced by Graphplanopens the boot (trunk) in step 1, fetches all the tools and the spare tire in step 2, inflatesthe spare and loosens the nuts in step 3, and so forth until it finally closes the boot in step12. (See Figure 4.) Another significant feature of our algorithm is that it is not particularlysensitive to the order of the goals in a planning task, unlike traditional approaches. Morediscussion of this issue is given in Section 3.2. In Section 4 of this paper we present empiricalresults that demonstrate th e effectiveness of Graphplan on a variety of interesting “natural”and artificial domains.An extended abstract of this work appears in[Blum and Furst, 1995].1.1 Definitions and NotationPlanning Graph Analysis applies to STRIPS-like planning domains[Fikes and Nilsson,1971]. In these domains, operators have preconditions, add-effects, and delete-effects, all of2The rocket domain (introduced by Veloso[1989]) has three operators: Load,Unload, and Move. A p iece of cargo can be loaded into a rocket if the rocketand cargo are in the same location. A r ocket may move if it has fuel, butperforming the move