An LP-Based Heuristic For Optimal Planning

An LP-Based Heuristic for Optimal PlanningMenkes van den Briel1 , J. Benton2 , Subbarao Kambhampati2 ,and Thomas Vossen31Arizona State University, Department of Industrial Engineering,2Department of Computer Science and Engineering,Tempe AZ, 85287, USA{menkes,j.benton,rao}@asu.edu3University of Colorado, Leeds School of Business,Boulder CO, 80309, USAvossen@colorado.eduAbstract. One of the most successful approaches in automated planning is to use heuristic state-space search. A popular heuristic that is usedby a number of state-space planners is based on relaxing the planningtask by ignoring the delete effects of the actions. In several planning domains, however, this relaxation produces rather weak estimates to guidesearch effectively. We present a relaxation using (integer) linear programming that respects delete effects but ignores action ordering, which ina number of problems provides better distance estimates. Moreover, ourapproach can be used as an admissible heuristic for optimal planning.Keywords: Automated planning, improving admissible heuristics,optimal relaxed planning1IntroductionMany heuristics that are used to guide heuristic state-space search planners arebased on constructing a relaxation of the original planning problem that is easierto solve. The idea is to use the solution to the relaxed problem to guide searchfor the solution to the original problem. A popular relaxation that has beenimplemented by several planning systems, including UNPOP [17,18], HSP [4,5],and FF [15], involves using relaxed actions in which the delete effects of theoriginal actions are ignored.For example, FF estimates the distance between an intermediate state andthe goals by creating a planning graph [3] using relaxed actions. From this graph,FF extracts in polynomial time a relaxed plan whose corresponding plan lengthis used as an inadmissible, but effective, distance estimate. One can transformthis approach into an admissible heuristic by finding the optimal relaxed plan,also referred to as h [14], but computing such a plan is NP-Complete [8]. Inorder to extract the optimal relaxed plan one must extend the relaxed planninggraph to level off [3] so that all reachable actions can be considered.Although ignoring delete effects turns out to be quite effective for many planning domains, there are some obvious weaknesses with FF’s relaxed plan heuristic. For example, in a relaxed plan no atom changes more than once, if anC. Bessiere (Ed.): CP 2007, LNCS 4741, pp. 651–665, 2007.c Springer-Verlag Berlin Heidelberg 2007

652M. van den Briel et al.atom becomes true it remains true as it is never deleted. However, in a plancorresponding to the original problem an atom may be added and deleted several times. In order to improve the quality of the relaxed plan we consider arelaxation based on relaxed orderings.In particular, we view a planning problem as a set of interacting networkflow problems. Given a planning domain where states are defined in terms ofn boolean or multi-valued state variables (i.e. fluents), we view each fluent asa separate flow problem, where nodes correspond to the values of the fluent,and arcs correspond to the transitions between these values. While network flowproblems are computationally easy, what makes this flow problem hard is thatthe flows are “coupled” as actions can cause transitions in multiple fluents.We set up an IP formulation where the variables correspond to the numbertimes each action is executed in the solution plan. The objective is to minimizethe number of actions, and the constraints ensure that each pre-condition issupported. However, the constraints do not ensure that pre-conditions are supported in a correct ordering. Specifically, for pre-conditions that are deleted wesetup balance of flow constraints. That is, if there are m action instances inthe plan that cause a transition from value f of fluent c, then there must bem action instances in the plan that cause a transition to value f of c. Moreover, for pre-conditions that are not deleted we simply require that they mustbe supported.The relaxation that we pursue in this paper is that we are not concernedabout the specific positions of where the actions occur in the plan. This can,to some extent, be thought of as ignoring the ordering constraints that ensurethat the actions can be linearized into a feasible plan. An attractive aspect of ourformulation is that it is not dependent on the length of the plan. Previous integerprogramming-based formulations for planning, such as [7,9,21], use a step-basedencoding. In a step-based encoding the idea is to set up a formulation for a givenplan length and increment it if no solution can be found. The problem withsuch an encoding is that it may become impractically large, even for mediumsized planning tasks. In a step-based encoding, if l steps are needed to solve aplanning problem then l variables are introduced for each action, whereas in ourformulation we require only a single variable for each action.The estimate on the number of actions in the solution plan, as computed byour IP formulation, provides a lower bound on the optimal (minimum number ofactions) plan. However, since solving an IP formulation is known to be computationally intractable, we use the linear programming (LP) relaxation which canbe solved in polynomial time. We will see that this double relaxation is still competitive with other admissible heuristics after we add non-standard and strongvalid inequalities to the formulation. In particular, We show that the value ofour LP-relaxation with added inequalities, gives very good distance estimatesand in some problem instances even provides the optimal distance estimate.While the current paper focuses on admissible heuristics for optimal sequentialplanning, the flow-based formulation can be easily extended to deal with moregeneral planning problems, including cost-based planning and over-subscription

An LP-Based Heuristic for Optimal Planning653planning. In fact, a generalization of this heuristic leads to state-of-the-artperformance in oversubscription planning with non-uniform actions costs, goalutilities as well as dependencies between goal utilities [2].This paper is organized as follows. In Section 2 we describe our action selection formulation and describe a number of helpful constraints that exploitdomain structure. Section 3 reports some experimental results and related workis described in Section 4. In Section 5 we summarize our main conclusions anddescribe some avenues for future work.2Action Selection FormulationWe find it useful to do the development of our relaxation in terms of multi-valuedfluents (of which the boolean fluents are a special case). As such, we will use theSAS formalism [1] rather than the usual STRIPS/ADL one as the backgroundfor our development. SAS is a planning formalism that defines actions by theirprevail-conditions and effects. Prevail-conditions describe which variables mustpropagate a certain value during the execution of the action and effects describethe pre- and post-conditions of the action.To make the connection between planning and network flows more straightforward, we will restrict our attention to a subclass of SAS where each actionthat has an post-condition on a fluent also has a pre-condition on that fluent.We emphasize that this restriction is made for ease of exposition and can beeasily removed; indeed our work in [2] avoids making this restriction.2.1NotationWe define a SAS planning task as a tuple Π C, A, s0 , s , where– C {c1 , ., cn } is a finite set of state variables, where each state variable c C has an associated domain Vc and an implicitly defined extended domainVc Vc {u}, where u denotes the undefined value. For each state variablec C, s[c] denotes the value of c in state s. The value of c is said to be definedin state s if and only if s[c] u. The total state space S Vc1 . Vcnand the partial state space S Vc 1 . Vc n are implicitly defined.– A is a finite set of actions of the form pre, post, prev , where pre denotesthe pre-conditions, post denotes the post-conditions, and prev denotes theprevail-conditions. For each action a A, pre[c], post[c] and prev[c] denotesthe respective conditions on state variable c. The following two restrictionsare imposed on all actions: (1) Once the value of a state variable is defined,it can never become undefined. Hence, for all c C, if pre[c] u thenpre[c] post[c] u; (2) A prevail- and post-condition of an action cannever define a value on the same state variable. Hence, for all c C, eitherpost[c] u or prev[c] u or both.– s0 S denotes the initial state and s S denotes the goal state. We saythat state s is satisfied by state t if and only if for all c C we have s[c] uor s[c] t[c]. This implies that if s [c] u for state variable c, then anydefined value f Vc satisfies the goal for c.

654M. van den Briel et al.While SAS planning allows the initial state, the goal state and the pre-conditionsof an action to be partial, we assume that s0 is a total state and that all preconditions are defined for all state variables on which the action has post-conditions(i.e. pre[c] u if and only if post[c] u). The assumption that s0 is a total stateis common practice in automated planning. However, the assumption that all preconditions are defined is quite strong, therefore, we will briefly discuss a way torelax this second assumption in Section 5.An important construct that we use in our action selection formulation is theso-called domain transition graph [13]. A domain transition graph is a graphrepresentation of a state variable and shows the possible ways in which valuescan change. Specifically, the domain transition graph DT Gc of state variable cis a labeled directed graph with nodes for each value f Vc . DT Gc contains alabeled arc (f1 , f2 ) if and only if there exists an action a with pre[c] f1 andpost[c] f2 or pre[c] u and post[c] f2 . The arc is labeled by the set ofactions with corresponding pre- and post-conditions. For each arc (f1 , f2 ) withlabel a in DT Gc we say that there is a transition from f1 to f2 and that actiona has an effect in c.We use the following notation.DT Gc (Vc , Ec ): is a directed domain transition graph for every c CVc : is the set of possible values for each state variable c CEc : is the set of possible transitions for each state variable c CVca Vc represents the prevail condition of action a in cEca Ec represents the effect of action a in caAEc : {a A : Ec 0} represents the actions that have an effect in c,Eand Ac (e) represents the actions that have the effect e in c– AVc : {a A : Vca 0} represents the actions that have a prevail conditionin c, and AVc (f ) represents the actions that have the prevail condition f in c– Vc (f ): to denote the in-arcs of node f in the domain transition graph Gc ;– Vc (f ): to denote the out-arcs of node f in the domain transition graph Gc ;––––––Moreover, we define the composition of two state variables, which is relatedto the parallel composition of automata [10], as follows.Definition 1. (Composition) Given the domain transition graph of two statevariables c1 , c2 , the composition of DT Gc1 and DT Gc2 is the domain transitiongraph DT Gc1 c2 (Vc1 c2 , Ec1 c2 ) where– Vc1 c2 Vc1 Vc2– ((f1 , g1 ), (f2 , g2 )) Ec1 c2 if f1 , f2 Vc1 , g1 , g2 Vc2 and there exists anaction a A such that one of the following conditions hold. pre[c1 ] f1 , post[c1 ] f2 , and pre[c2 ] g1 , post[c2 ] g2 pre[c1 ] f1 , post[c1 ] f2 , and prev[c2 ] g1 , g1 g2 pre[c1 ] f1 , post[c1 ] f2 , and g1 g2We say that DT Gc1 c2 is the composed domain transition graph of DT Gc1 andDT Gc2 .