A Tutorial On Planning Graph Based Reachability Heuristics

ArticlesA Tutorial onPlanning Graph–BasedReachability HeuristicsDaniel Bryce and Subbarao Kambhampati The primary revolution in automated planning inthe last decade has been the very impressive scaleup in planner performance. A large part of thecredit for this can be attributed squarely to theinvention and deployment of powerful reachability heuristics. Most, if not all, modern reachabilityheuristics are based on a remarkably extensibledata structure called the planning graph, whichmade its debut as a bit player in the success ofGraphPlan, but quickly grew in prominence tooccupy the center stage. Planning graphs are acheap means to obtain informative look-aheadheuristics for search and have become ubiquitousin state-of-the-art heuristic search planners. Wepresent the foundations of planning graph heuristics in classical planning and explain how theirflexibility lets them adapt to more expressive scenarios that consider action costs, goal utility,numeric resources, time, and uncertainty.Synthesizing plans capable of achieving anagent’s goals has always been a centralendeavor in AI. Considerable work hasbeen done in the last 40 years on modeling awide variety of plan-synthesis problems anddeveloping multiple search regimes for drivingthe synthesis itself. Despite this progress, theability to synthesize reasonable length plansunder even the most stringent restrictionsremained severely limited. This state of affairshas changed quite dramatically in the lastdecade, giving rise to planners that can routinely generate plans with hundreds of actions.This revolutionary shift in scalability can beattributed in large part to the use of sophisticated reachability heuristics to guide the planners’ search.Reachability heuristics aim to estimate thecost of a plan between the current search stateand the goal state. While reachability analysiscan be carried out in many different ways(Bonet and Geffner 1999, McDermott 1999,Ghallab and Laruelle 1994), one particularway—involving planning graphs—has provento be very effective and extensible. Planninggraphs were originally introduced as part of theGraphPlan algorithm (Blum and Furst 1995)but quickly grew in prominence once theirconnection to reachability analysis was recognized.Planning graphs provide inexpensive butinformative reachability heuristics by approximating the search tree rooted at a given state.They have also proven to be quite malleable inbeing adapted to a range of expressive planning problems. Planners using such heuristicshave come to dominate the state of the art inplan synthesis. Indeed, 12 out of 20 teams inthe 2004 International Planning Competitionand 15 out of 22 teams in the 2006 International Planning Competition used planninggraph–based heuristics. Lack of search controlfor domain-independent planners has, in thepast, made most planning applications be written with a knowledge-intensive planningapproach—such as hierarchical task networks.However, the effectiveness of reachabilityheuristics has started tilting the balance backand is giving rise to a set of applications basedon domain-independent planners (Ruml, Do,and Fromherz 2005; Boddy et al. 2005).This article1 aims to provide an accessibleintroduction to reachability heuristics in planning. While we will briefly describe the planning algorithms to set the context for theheuristics, our aim is not to provide a compre-Copyright 2007, Association for the Advancement of Artificial Intelligence. All rights reserved. ISSN 0738-4602SPRING 2007 47

ArticlesClassical Planning- Unit Cost Actions- Boolean-valued Variables- Atomic Time- Known State- Deterministic Actions- Fully Satisfy GoalsPlanning Under Uncertainty- Unit Cost Actions- Boolean-valued Variables- Atomic Time- Partially-Known State- Uncertain Actions- Fully Satisfy GoalsCost-Based Planning- Nonunit Cost Actions- Boolean-valued Variables- Atomic Time- Known State- Deterministic Actions- Fully Satisfy GoalsPartial Satisfaction Planning- Nonunit Cost Actions- Boolean-valued Variables- Atomic Time- Known State- Deterministic Actions- Partially Satisfy GoalsPlanning with Resources- Unit Cost Actions- Real-valued Variables- Atomic Time- Known State- Deterministic Actions- Fully Satisfy GoalsTemporal Planning- Unit Cost Actions- Boolean-valued Variables- Durative Time- Known State- Deterministic Actions- Fully Satisfy GoalsFigure 1. Taxonomy of Planning Models.hensive introduction to planning algorithms.Rather, we seek to complement existing sources(see, for example, Ghallab, Nau, and Traverso[2004]) by providing a complete introductionto reachability heuristics in planning.As outlined in figure 1, we discuss the classical planning model along with several extensions (in clockwise order). Naturally, as theplanning model becomes more expressive, theplanning graph representation and heuristicschange. We start with classical planning to layan intuitive foundation and then build uptechniques for handling additional problemfeatures. We concentrate on the following features independently, pointing out where theyhave been combined. Action costs are uniformin the classical model, but we later describenonuniform costs. Goal satisfaction is total inthe classical model but can be partial in general (that is, the cost of satisfying all goals canexceed the benefit). Resources are describedonly by Boolean variables in the classical model but can be integer or real-valued variables.Time is atomic in the classical model, but is48AI MAGAZINEdurative in general (that is, actions can havedifferent durations). Uncertainty is nonexistent in the classical model but can generallyresult through uncertain action effects and partial (or no) observability. While there are manyadditional ways to extend the classical model,we hold some features constant throughoutour discussion. The number of agents isrestricted to only one (the planning agent),execution takes place after plan synthesis, andwith the exception of temporal planning, plansare sequential (no actions execute concurrently).We will use variations on the following running example to illustrate how several planning models can address the same problem andhow we can derive heuristics for the models:Example 1 (Planetary Rover)Ground control needs to plan the daily activities for the rover Conquest. Conquest is currently at location alpha on Mars, with partial power reserves and some broken sensors. Themission scientists have objectives to obtain asoil sample from location alpha, a rock coresample from location beta, and a photo of the

Articleslander from the hilltop location gamma—eachobjective having a different utility. The rovermust communicate any data it collects to havethe objectives satisfied. The driving time andcost from one location to another vary depending on the terrain and distance between locations. Actions to collect soil, rock, and imagedata incur different costs and take varioustimes. Mission scientists may not know whichlocations will have the data they need, and therover’s actions may fail, leading to potentialsources of uncertainty.History of Reachability andPlanning Graph HeuristicsGiven the current popularity of heuristicsearch planners, it is somewhat surprising tonote that the interest in the reachability heuristics in AI planning is a relatively new development. Ghallab and his colleagues were the firstto report on a reachability heuristic in IxTeT(Ghallab and Laruelle 1994) for doing actionselection in a partial-order planner. Howeverthe effectiveness of their heuristic was not adequately established. Subsequently the idea ofreachability heuristics was independently(re)discovered by Drew McDermott (1996,1999) in the context of his UNPOP planner.UNPOP was one of the first domain-independent planners to synthesize plans containingup to 40 actions. A second independent rediscovery of the idea of using reachability heuristics in planning was made by Blai Bonet andHector Geffner (1999). Each rediscovery is theresult of attempts to speed up plan synthesiswithin a different search substrate (partialorder planning, regression, and progression).The most widely accepted approach to computing reachability information is embodiedby GraphPlan. The original GraphPlan planner(Blum and Furst 1995) used a specialized combinatorial algorithm to search for subgraphs ofthe planning graph structure that correspondto valid plans. It is interesting to note thatalmost 75 percent of the original GraphPlanpaper was devoted to the specifics of this combinatorial search. Subsequent interpretationsof GraphPlan recognized the role of the planning graph in capturing reachability information. Subbarao Kambhampati, Eric Lambrecht,and Eric Parker (1997) explicitly characterizedthe planning graph as an envelope approximation of the progression search tree (see figure 3of his work and the associated discussion).Bonet and Geffner (1999) interpreted GraphPlan as an IDA* search with the heuristicencoded in the planning graph. XuanLongNguyen and Subbarao Kambhampati (2000)described methods for directly extractingheuristics from the planning graph. That sameyear, FF (Hoffmann and Nebel 2001), a plannerusing planning graph heuristics placed first inthe International Planning Competition. Sincethen there has been a steady stream of developments that increased both the effectivenessand the coverage of planning graph heuristics.Classical PlanningIn this section we start with a brief backgroundon how the classical planning problem is represented and why the problem is difficult. Wefollow with an introduction to planning graphheuristics for state-based progression search(extending plan prefixes). In the Heuristics inAlternative Planning Strategies section, we cover issues involved with using planning graphheuristics for state-based regression and planspace search.BackgroundThe classical planning problem is defined as atuple P, A, SI, G , where P is a set of propositions, A is a set of actions, SI is an initial state,and G is a set of goal propositions. Throughoutthis article we will use many representationalassumptions (described later) consistent withthe STRIPS language (Fikes and Nilsson 1971).While STRIPS is only one of many choices foraction representation, it is very simple, andmost other action languages can be compileddown to STRIPS (Nebel 2000). In STRIPS a states is a proper subset of the propositions P, whereevery proposition p s is said to be true (or tohold) in the state s. Any proposition p s isfalse in s. The initial state is specified by a set ofpropositions I P known to be true (the falsepropositions are inferred by the closed-worldassumption), and the goal is a set of propositions G P that must be made true in a state sfor s to be a goal state. Each action a A isdescribed by a set of propositions pre(a) forexecution preconditions, a set of propositionsthat it causes to become true eff (a), and a setof propositions it causes to become false eff–(a).An action a is applicable appl(a, s) to a state s ifeach precondition proposition holds in thestate, pre(a) s. The successor state s is theresult of executing an applicable action a instate s, where s exec(a, s) s\ eff– (a) eff (a).A sequence of actions {a1, an}, executed instate s, results in a state s , where s exec(an,exec(an–1, exec(a1, s) )) and each action isexecutable in the appropriate state. A validplan is a sequence of actions that can be executed from sI and results in a goal state. Fornow we assume that actions have unit cost,making the cost of a plan equivalent to thenumber of actions.We use the planning domain descriptionSPRING 2007 49