# On the Completeness of Pruning Techniques for Planning with Conditional Effects

Authors: Dunbo Cai; Sheng Xu; Tongzhou Zhao; Yanduo Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Pruning techniques and heuristics are two keys to the heuristic search-based planning. Thehelpful actions pruning (HAP) strategy and relaxed-plan-based heuristics are two representatives among those methods and are still popular in the state-of-the-art planners. Here, we present new analyses on the properties of HAP. Specifically, we show new reasons for which HAP can cause incompleteness of a search procedure. We prove that, in general, HAP is incomplete for planning with conditional effects if factored expansions of actions are used. To preserve completeness, we propose a pruning strategy that is based on relevance analysis and confrontation. We will show that both relevance analysis and confrontation are necessary. We call it the confrontation and goal relevant actions  pruning (CGRAP) strategy. However, CGRAP is computationally hard to be exactly computed. Therefore, we suggest practical approximations from the literature.


---

## Body

## 1. Introduction

The research of AI planning has advanced to a new level. Pioneers from the AI planning community have developed various practical methods that can solve much larger problems than those toy problems in early days. Two such well known methods are SAT-based planning [1], and heuristic search-based planning [2]. SAT-based planning translates planning problems into propositional satisfiability problems or more general constraint satisfaction problems (CSPs) [3]. An obvious advantage of the method is that it can exploit the power of fast algorithms from the CSP literature [4–6]. On the other hand, the “planning as search” community has been pursuing more informative heuristics to make the search fast [7, 8]. While recent studies show that planning specific heuristics can make SAT-based planning methods more competitive [9, 10], the planning as search method has shown its potential in many kinds of planning problems including classical planning [11, 12], conformant planning [13], contingent planning [14], and probabilistic planning [15]. Recent International Planning Competitions (IPCs) http://ipc.icaps-conference.org/ have witnessed the success of heuristic search-based planners, since the winners: Fast-Forward (FF) [11], LPG [16], SGPlan [17], and Fast Downward [12] and its successors—LAMA [18] all employ heuristic search. Two enabling techniques underlying heuristic search-based planning are heuristic functions and pruning techniques. A heuristic function measures the distances to goal of states, while pruning techniques eliminate branches that are safe to ignore. Here, we focus on the pruning techniques.HAP is a pruning strategy developed in FF with the idea of making the search process goal directed [19].Though, initially, it was a byproduct of the relaxed-plan heuristic, its notion has been popular and important in the design of top performance planners, such as Fast Downward [12]. However, the HAP strategy does not guarantee completeness; that is, it may cut branches that can reach the goal. Some of these cases were explained by  Hoffmann and Nebel  [11]. Nevertheless, here, we uncover a new case in which HAP can cause incompleteness. We study the conditions under which the new case will occur, the way to remedy the HAP strategy, and the cost of doing that. Based on our work, one can gain more insights into why Fast Downward, which employs the helpful transitions strategy, is powerful.The rest of the paper is organized as follows. In the next section, we introduce some background. Then, we show the incompleteness of HAP and extend it to a more general one called goal relevant actions pruning (GRAP), which is complete only for STRIPS planning. In Section4, we propose our confrontation and goal relevant actions pruning (CGRAP), which is complete for both STRIPS planning and actions with conditional effects. In Section 5, we discuss some pruning techniques in the literature that can be seen as approximations of CGRAP. Finally, we conclude the paper and discuss some future work.


## 2. Background

We will first introduce notations from the state space search-based planning, then methods for handling conditional effects, and finally the heuristic function and the HAP strategy in FF.A planning task is a quadtupleT=(P,A,I,G), where P is the set of atoms, A is the set of actions, I⊆P is a set of atoms called the initial state, and G⊆P is the goal condition that each goal state must fulfill. States are denoted by sets of atoms. We adopted the “closed world” assumption; that is, an atom that is not in a state is false in the state. So, if P={p,q,r} and a state s={p,q}, then s is logically equal to p∧q∧¬r. An action a is a pair 〈pre(a),E(a)〉, where pre(a) is a set of atoms denoting the preconditions of a and E(a) is the set of conditional effects of a. Each conditional effect e∈E(a) has the form 〈con(e),add(e),del(e)〉, where con(e), add(e), and del(e) are conditions, add effects, and delete effects of e, respectively. For an action a and a state s, if pre(a)⊆s, then we say a is applicable in s. We use App(s)={a∣pre(a)⊆s} to denote all the actions that are applicable in s. The execution of a on s, denoted by a(s), results in a state s′, where s′=s-⋃e:con(e)⊆s‍del(e)+⋃e:con(e)⊆s‍add(e) if a is applicable in s, and s′=s otherwise. A state s is called a goal state if G⊆s. A plan for a planning task is an action sequence π=〈a0,a1,…,an-1〉 that transforms the initial state I into a goal state. We use |π| to denote its length, which is the number of actions in it. Here, we assume that a plan does not have redundant actions; that is, when some action is removed from π, it will no longer be a plan.Actions with conditional effects were introduced in the planning problem description language “Action description language” (ADL) [20]. And there are mainly three ways for handling conditional effects. Conditional effects of actions are expressed with the keyword “when”. Figure 1 (left) shows an action with two conditional effects: the first effect q will happen with no condition and the second effect ¬t will happen if r∧s holds in the state where the action is executed. The three ways for handling conditional effects are, full expansion [21], IPP's method [22] and factored expansion [23]. Here, we focus on IPP's method, which is used in FF. The method will translate the action in Figure 1 (left) into the form shown in Figure 1 (right). From now on, we will call planning with actions with conditional effects ADL planning.An action with conditional effects (a) and its compiling result by IPP (b).
(a)
(b)FF employs a forward state space search framework. Three key techniques of FF are the relaxed-plan-based heuristic (RP), HAP, and the enforced hill-climbing (EHC) algorithm. Here, we focus on RP and HAP. A relaxed plan is extracted from a relaxed version of a planning task where the delete effects of actions are ignored. Specifically, the relaxed version of a planning taskT=(P,A,I,G) is T′=(P,A′,I,G), where A′={〈pre(a),E′(a)〉∣a∈A} and E′(a)={〈con(e),add(e),∅〉∣〈con(e),add(e),del(e)〉∈E(a)}. An action sequence π=〈a0,a1,…,an-1〉 is called a relaxed plan for T if it is a plan for T′. For a state s, its heuristic value is the length of a relaxed plan for the planning task Ts=(P,A,s,G). Note that the relaxed plan for Ts is not unique and FF finds one using the Graphplan [24] algorithm. During the process of computing a relaxed plan, FF keeps track of the subgoals generated in the second propositional level of a planning graph, which is saved in a set G1(s). Helpful actions are the set of actions H(s)={a∣pre(a)⊆s∧∃e∈E(a):(con(e)⊆s)∧(add(e)∩G1(s)≠∅)}. For a state s, the EHC algorithm only considers actions in H(s) and ignores others. This search strategy is called helpful actions pruning. We say that a strategy is complete if using it does not make a complete algorithm eliminate search branches that are directions to goal states. As shown in [11], HAP is incomplete for STRIPS planinng.


## 3. Complete Pruning Strategy for STRIPS

In this section, we will extend HAP to a complete strategy for STRIPS that we callgoal relevant actions pruning (GRAP). We will then prove the completeness of GRAP for STRIPS and show that GRAP is incomplete for ADL planning. As a result, we will extend GRAP to a complete strategy for ADL planning in the next section.


### 3.1. Goal Relevant Actions

Helpful actions for a states are actions in App(s) that is relevant for adding the subgoals in G1(s). To obtain completeness, our goal relevant actions for s are actions in App(s) that is relevant for adding every (sub)goal generated by the GraphPlan algorithm.Definition 1 (Dependency among Facts).
For two factsl,g∈P and a set of actions A, l is dependent ong with respect to A (denoted as l⊲Ag) if(1)
l=g,(2)
∃a∈A:∃e∈E(a):(l∈add(e)∧g∈(pre(a)∪con(e))),(3)
∃h∈P:(l⊲Ah∧h⊲Ag).Definition 2 (Dependency between Facts and Actions).
For an atoml∈P and an action a∈A, l is dependent ona with respect to A (denoted as l⊲Aa) if(1)
∃a∈A:∃e∈E(a):l∈add(e),(2)
∃g∈P:l⊲Ag∧g⊲Aa.We note that Definitions1 and 2 capture the relevant facts and actions to a goal. Specifically, if we are going to reach a goal g, then the actions on which g is dependent are relevant, and further, actions that adds facts on which g is dependent are also relevant. Note that in the previous definitions we use “dependent,” instead of “relevant,” to indicate a directional relation.Now, we are ready to introduce the notion of goal relevant actions. The actions are those a search algorithm could explore for reaching some goal state. Actions that are not relevant are to be ignored.Definition 3 (Goal Relevant Actions, GRA).
Given a planning taskT=(P,A,I,G), actions that are relevant to l∈P are DEP⊲A(l)={a∣a∈Aandl⊲Aa}, actions that are relevant to G⊆P are DEP⊲A(G)=⋃l∈G‍DEP⊲A(l). Given a state s, the “goal relevant actions” for s is RELG,⊲A(s)=DEP⊲A(G)∩App(s).We propose the following pruning strategy based on GRA. For any search algorithm and any states, we only consider actions in RELG,⊲A(s)  and ignore those in App(s)-RELG,⊲A(s). We call the strategy GRA pruning (GRAP). We will prove that GRAP is a generalization of HAP and is complete for STRIPS planning.Proposition 4.
For a planning taskT=(P,A,I,G) and any state s of T, H(s)⊆RELG,⊲A(s).As the directional relation⊲A is transitive, the correctness of Proposition 4 is straightforward in that G1(s)⊆DEP⊲A(G).Next, we will prove that GRAP is complete for STRIPS planning.Proposition 5.
GRAP is a complete pruning strategy for STRIPS planning.Proof.
LetT=(P,A,s,G) be a STRIPS planning task, and let π=〈a0,a1,…,an-1〉 be one of the plans for s. Note that π is not redundant. As we restrict to STRIPS planning, each action a∈A has only one conditional effect, which is denoted by e(a). We will prove that a0∈RELG,⊲A(s). We will compute DEP⊲A(G) with k=n-1,…,0. Initially, DEP⊲A(G)=G. For the action an-1, if its effect e(an-1) does not add a fact in G then π with an-1 removed will still be a plan. This contradicts the assumption that π is not redundant. Following Definition 1, DEP⊲A(G)=DEP⊲A(G)∪pre(an-1). Similarly, for ak(0<k<n-1), ak must add a fact in DEP⊲A(G)∪pre(an-1)∪⋯∪pre(ak+1); otherwise, π with ak removed is still a plan, which contradicts the assumption that π is not redundant. Therefore, DEP⊲A(G)=DEP⊲A(G)∪pre(an-1)∪⋯∪pre(ak+1). For a0, as π is not redundant, it must hold that e(a0)∩(G∪pre(an-1)∪⋯∪pre(a1))≠∅. Following Definition 2, a0 is in DEP⊲A(G). And according to Definition 3, a0∈RELG,⊲A(s) holds. As π is an arbitrary plan, we finish the proof.Note that the above proof cannot be adapted to prove the completeness of HAP, as helpful actions are defined with respect to a specific relaxed plan. In other words, the arbitrariness of plans is not guaranteed.


### 3.2. GRAP is Incomplete for ADL Planning

Hoffmann and Nebel [11] pointed out that HAP is incomplete as the GraphPlan algorithm is greedy in computing shorter relaxed plans. Therefore, the source of this incompleteness could be eliminated if we use other algorithms to compute relaxed plans, other than GraphPlan. The method proposed by Hoffmann and Nebel [11] works in the following way: for a state s and a relaxed planning task T′=(P,A′,s,G), they expand the planning graph to the level |A′| and collect subgoals backward from the level |A′| to level  1. Specifically, let Gi′ be the subgoals at level i, then
(1)G|A′|′=G,Gi′=Gi+1′∪⋃a∈Ai∧(∃e∈E(a):add(e)∩Gi+1≠∅)‍pre(e)∪con(e).Following the method,G1′ is the union of subgoals of every relaxed plan for T′ at level  1. We call actions in {a∣a∈App(s),∃e∈E(a):add(e)∩G1′≠∅} “full helpful actions” (FHAs). Intuitively, an FHA is equivalent to our definition RELG,⊲A(s). However, the former is more procedural, and ours is more formal. We will use our definition to develop a new pruning strategy for ADL planning. Before that, we will show, by example, that both the FHA pruning (FHAP) strategy and GRAP are generally incomplete for ADL planning.Example 6.
Given a planning taskT′′, where P′′={p,q,r,s,m}, I′′={p,q,r}, G′′={r,m}, and A′′={a1,a2} where a1 is ({p},{(∅,{m},∅),({q},{m},{r})}) and a2 is (q,(∅,∅,{q})). The meaning of a1 is as follows: its preconditions are {q} and it has two conditional effects—the first is (∅,{m},∅) (denoted as e0) and the second is ({q},{m},{r}) (denoted as e1). The action a2 has one condition q, and has a conditional effect (∅,∅,{q}) that falsifies q.Next, let us consider the plan for Example6. The difference between G′′ and I′′ is that the atom m is not true in I′′. To make m true, we would use action a1. However, executing a1 on I′′ will result in a state s′′={p,q,m} where atom r does not hold. After that, there is no action that can transform s′′ into a goal state. One could notice that this dead end is due to the fact that e0 and e1 both happened and e1 destroyed r. If we could prevent e1 from happening, then we would succeed in finding a plan. This is the idea proposed by Weld [25], which is called “confrontation.” It is easy to see that with “confrontation” as a choice, we can find a plan <a1,a0>.In Example6, a1 is relevant for reaching a goal state. However, pruning strategies HAP, GRAP, and FHAP all ignore it. With a generalization, we have the following results.Proposition 7.
LetT=(P,A,s,G) be an ADL planning task and the set of plans for T be PLANs(T). If every plan π∈PLANs(T) contains an action a of the form (pre(a),{(con(e0),∅,del(e0)),…,(con(em),∅,del(em))}), then HAP, FHAP, and GRAP are incomplete for T.The correctness of Proposition7 is in that if an action does not have any add effects, then it will not be considered as “helpful” or “relevant” anyway. As a result, this kind of actions will be mistakenly ignored.From Example6, we can see that actions that make “confrontations” are also “helpful” and “relevant.” Following this direction, we extend GRAP to a new pruning strategy that is complete for both STRIPS and ADL planning.


## 3.1. Goal Relevant Actions

Helpful actions for a states are actions in App(s) that is relevant for adding the subgoals in G1(s). To obtain completeness, our goal relevant actions for s are actions in App(s) that is relevant for adding every (sub)goal generated by the GraphPlan algorithm.Definition 1 (Dependency among Facts).
For two factsl,g∈P and a set of actions A, l is dependent ong with respect to A (denoted as l⊲Ag) if(1)
l=g,(2)
∃a∈A:∃e∈E(a):(l∈add(e)∧g∈(pre(a)∪con(e))),(3)
∃h∈P:(l⊲Ah∧h⊲Ag).Definition 2 (Dependency between Facts and Actions).
For an atoml∈P and an action a∈A, l is dependent ona with respect to A (denoted as l⊲Aa) if(1)
∃a∈A:∃e∈E(a):l∈add(e),(2)
∃g∈P:l⊲Ag∧g⊲Aa.We note that Definitions1 and 2 capture the relevant facts and actions to a goal. Specifically, if we are going to reach a goal g, then the actions on which g is dependent are relevant, and further, actions that adds facts on which g is dependent are also relevant. Note that in the previous definitions we use “dependent,” instead of “relevant,” to indicate a directional relation.Now, we are ready to introduce the notion of goal relevant actions. The actions are those a search algorithm could explore for reaching some goal state. Actions that are not relevant are to be ignored.Definition 3 (Goal Relevant Actions, GRA).
Given a planning taskT=(P,A,I,G), actions that are relevant to l∈P are DEP⊲A(l)={a∣a∈Aandl⊲Aa}, actions that are relevant to G⊆P are DEP⊲A(G)=⋃l∈G‍DEP⊲A(l). Given a state s, the “goal relevant actions” for s is RELG,⊲A(s)=DEP⊲A(G)∩App(s).We propose the following pruning strategy based on GRA. For any search algorithm and any states, we only consider actions in RELG,⊲A(s)  and ignore those in App(s)-RELG,⊲A(s). We call the strategy GRA pruning (GRAP). We will prove that GRAP is a generalization of HAP and is complete for STRIPS planning.Proposition 4.
For a planning taskT=(P,A,I,G) and any state s of T, H(s)⊆RELG,⊲A(s).As the directional relation⊲A is transitive, the correctness of Proposition 4 is straightforward in that G1(s)⊆DEP⊲A(G).Next, we will prove that GRAP is complete for STRIPS planning.Proposition 5.
GRAP is a complete pruning strategy for STRIPS planning.Proof.
LetT=(P,A,s,G) be a STRIPS planning task, and let π=〈a0,a1,…,an-1〉 be one of the plans for s. Note that π is not redundant. As we restrict to STRIPS planning, each action a∈A has only one conditional effect, which is denoted by e(a). We will prove that a0∈RELG,⊲A(s). We will compute DEP⊲A(G) with k=n-1,…,0. Initially, DEP⊲A(G)=G. For the action an-1, if its effect e(an-1) does not add a fact in G then π with an-1 removed will still be a plan. This contradicts the assumption that π is not redundant. Following Definition 1, DEP⊲A(G)=DEP⊲A(G)∪pre(an-1). Similarly, for ak(0<k<n-1), ak must add a fact in DEP⊲A(G)∪pre(an-1)∪⋯∪pre(ak+1); otherwise, π with ak removed is still a plan, which contradicts the assumption that π is not redundant. Therefore, DEP⊲A(G)=DEP⊲A(G)∪pre(an-1)∪⋯∪pre(ak+1). For a0, as π is not redundant, it must hold that e(a0)∩(G∪pre(an-1)∪⋯∪pre(a1))≠∅. Following Definition 2, a0 is in DEP⊲A(G). And according to Definition 3, a0∈RELG,⊲A(s) holds. As π is an arbitrary plan, we finish the proof.Note that the above proof cannot be adapted to prove the completeness of HAP, as helpful actions are defined with respect to a specific relaxed plan. In other words, the arbitrariness of plans is not guaranteed.


## 3.2. GRAP is Incomplete for ADL Planning

Hoffmann and Nebel [11] pointed out that HAP is incomplete as the GraphPlan algorithm is greedy in computing shorter relaxed plans. Therefore, the source of this incompleteness could be eliminated if we use other algorithms to compute relaxed plans, other than GraphPlan. The method proposed by Hoffmann and Nebel [11] works in the following way: for a state s and a relaxed planning task T′=(P,A′,s,G), they expand the planning graph to the level |A′| and collect subgoals backward from the level |A′| to level  1. Specifically, let Gi′ be the subgoals at level i, then
(1)G|A′|′=G,Gi′=Gi+1′∪⋃a∈Ai∧(∃e∈E(a):add(e)∩Gi+1≠∅)‍pre(e)∪con(e).Following the method,G1′ is the union of subgoals of every relaxed plan for T′ at level  1. We call actions in {a∣a∈App(s),∃e∈E(a):add(e)∩G1′≠∅} “full helpful actions” (FHAs). Intuitively, an FHA is equivalent to our definition RELG,⊲A(s). However, the former is more procedural, and ours is more formal. We will use our definition to develop a new pruning strategy for ADL planning. Before that, we will show, by example, that both the FHA pruning (FHAP) strategy and GRAP are generally incomplete for ADL planning.Example 6.
Given a planning taskT′′, where P′′={p,q,r,s,m}, I′′={p,q,r}, G′′={r,m}, and A′′={a1,a2} where a1 is ({p},{(∅,{m},∅),({q},{m},{r})}) and a2 is (q,(∅,∅,{q})). The meaning of a1 is as follows: its preconditions are {q} and it has two conditional effects—the first is (∅,{m},∅) (denoted as e0) and the second is ({q},{m},{r}) (denoted as e1). The action a2 has one condition q, and has a conditional effect (∅,∅,{q}) that falsifies q.Next, let us consider the plan for Example6. The difference between G′′ and I′′ is that the atom m is not true in I′′. To make m true, we would use action a1. However, executing a1 on I′′ will result in a state s′′={p,q,m} where atom r does not hold. After that, there is no action that can transform s′′ into a goal state. One could notice that this dead end is due to the fact that e0 and e1 both happened and e1 destroyed r. If we could prevent e1 from happening, then we would succeed in finding a plan. This is the idea proposed by Weld [25], which is called “confrontation.” It is easy to see that with “confrontation” as a choice, we can find a plan <a1,a0>.In Example6, a1 is relevant for reaching a goal state. However, pruning strategies HAP, GRAP, and FHAP all ignore it. With a generalization, we have the following results.Proposition 7.
LetT=(P,A,s,G) be an ADL planning task and the set of plans for T be PLANs(T). If every plan π∈PLANs(T) contains an action a of the form (pre(a),{(con(e0),∅,del(e0)),…,(con(em),∅,del(em))}), then HAP, FHAP, and GRAP are incomplete for T.The correctness of Proposition7 is in that if an action does not have any add effects, then it will not be considered as “helpful” or “relevant” anyway. As a result, this kind of actions will be mistakenly ignored.From Example6, we can see that actions that make “confrontations” are also “helpful” and “relevant.” Following this direction, we extend GRAP to a new pruning strategy that is complete for both STRIPS and ADL planning.


## 4. Complete Pruning Strategy for ADL Planning

We first introduce the notion of “confrontation and goal relevant actions” and then prove that its corresponding pruning strategy CGRAP is complete for ADL planning.Definition 8 (Confrontational Dependency among Facts).
For two atomsl,g∈P, a set of actions A, l is confrontationally dependent ong with respect to A (denoted as l⊴Ag) if(1)
l=g,(2)
∃a∈A:∃e∈E(a):l∈((add(e)∪del(e))∧g∈(pre(a)∪⋃e′∈E(a)‍con(e′)),(3)
∃h∈P:l⊴Ah∧h⊴Ag.Definition 9 (Confrontational Dependency between Facts and Actions).
For two atomsl,g∈P, an action a∈A, l is confrontationally dependent ona with respect to A (denoted as l⊴Aa) if(1)
∃a∈A:∃e∈E(a):l∈(add(e)∪del(e)),(2)
∃g∈P:l⊴Ag∧g⊴Aa.According to the previous two definitions, one could notice that actions that add ordelete an atom l are considered as relevant to l.Definition 10 (Confrontation and Goal Relevant Actions).
Given a planning taskT=(P,A,I,G), actions that are confrontationally relevant to l∈P are DEP⊴A(l)={a∣a∈Aandl⊴Aa}, and actions that are confrontationally relevant to G⊆P are DEP⊴A(G)=⋃l∈G‍{DEP⊴A(l)}. Given a state s, the “confrontation and goal relevant actions” for s is RELG,⊴A(s)=DEP⊴A(G)∩App(s).The pruning strategy that considers actions inRELG,⊴A(s) only, that is, ignores App(s)-RELG,⊴A(s) is called confrontation and goal relevant actions pruning (CGRAP). In the following proposition, we will prove that CGRAP is complete for ADL planning.Proposition 11.
CGRAP strategy is complete for ADL planning.Proof (Proof by Contradiction).
Given a planning taskT=(P,A,I,G) and any plan π=〈a0,a1,…,an-1〉 for it, we use sj+1=aj(sj) to denote the result of executing aj on sj. Without loss of generality, suppose that ai(i=0,…,n-1) is eliminated by CGRAP; that is, ai∉RELG,⊴A(si). When i=n-1, as π is not a redundant plan, an-1 must add one atom of G; that is, ∃e∈E(an-1):add(e)∩G≠∅. Therefore, ai∈DEP⊴A(G). For i≤n-2, ai either (1) adds an atom g∈G, (2) adds an atom q which is the (pre)condition of ai+1,…, or an-1, or (3) deletes one condition r of e′∈E(am)(m=i+1,…,n-1) in order to prevent e′ from happening. In case (1), ∃g∈G:g⊴Aai, in case (2), ∃g′∈G:g′⊴Aqandq⊴Aai, and in case (3), ∃g′′∈G:g′′⊴Arandr⊴Aai. In either cases, and according to our Definitions 8 and 9, ai∈DEP⊴A(G) holds. Note that pre(ai)⊆si. Therefore, we conclude that ai∈RELG,⊴A(si).The completeness of CGRAP for ADL planning costs. One reason is that the pruning power of CGRAP is weak. In other words, CGRAP may cut a rather limited amount of branches of a search space. In addition, computing CGRAP is PSPACE-hard, as deciding irrelevant actions for a planning task is PSPACE-hard [26]. Therefore, it is practical to collect confrontation and goal relevant actions in an approximate way. In the next section, we will discuss some methods from the literature that fall into this scope.


## 5. Discussion

We will first review thehelpful transition notion developed in Fast Downward [12] and then the delayed partly reasoning procedure [27].Fast Downward is a representative planner that uses theSAS+ planning formalism [28], which supports multivalued variables. It translates a propositional planning problem into an SAS+ planning problem by utilizing an invariants analysis procedure [12]. After that, Fast Downward builds a causal graph that involves all the variables and a domain transition graph for each variable. Dependencies among variables are reasoned through the causal graph, and dependencies among values of a variable are reasoned through the corresponding domain transition graph. For details of the two kinds of graphs, please refer to [12]. The goal distance of a state s is the sum of goal distances of variables. For each variable, its goal distance is computed by solving a shortest path problem formulated on the corresponding domain transition graph. In the problem, the source node is the value the variable currently takes, and the target node is the value that goal conditions require. When such a path is obtained, the transition associated with the first edge is labeled as “helpful transition.” Note that transitions are conditional effects of actions. So, we can collect “helpful actions” based on “helpful transitions.” Here we note that “helpful transitions” consider both goal relevant actions and actions that are for confrontations. The ability of collecting actions that are helpful for confrontations originates from the multivalued variable representation. In the representation, the change from one value to another one models both the add and delete effects of an action on a variable. As a result, actions have only one kind of effects, which are considered by Fast Downward to collect “helpful transitions.” In contrast, propositional planners, such as FF, consider only the add effects of actions for collecting “helpful actions.” Therefore, the “helpful transitions” strategy can be considered as an approximation of CGRAP.The “delayed partly reasoning procedure” is proposed by Cai et al. [7]. This procedure is implemented on top of the propositional planning formalism. In the first action level of a planning graph, the procedure tracks harmful inducements with respect to an order of conditional effects and collects actions that confront the inducements. An inducement is that one conditional effect e induces another conditional effect e′. It is harmful if e′ deletes some previously added atoms of other conditional effects. As the procedure only operates on the first actions level and works with a predefined order, it is an approximation of CGRAP. Therefore, the computational cost of the procedure is not high.


## 6. Conclusions and Future Work

In this work, we analyzed some well-known pruning techniques, which are currently utilized by state-of-the-art planners. In particular, we showed that thehelpful actions pruning strategy is incomplete for ADL planning and extended it to a complete strategy called confrontation and goal relevant actions pruning. Though our proposed strategy is computationally hard, we discussed methods from the AI planning literature that can be seen as approximations of it. In addition, we believe that this work will help us gain more insights into why the planner Fast Downward is powerful.This work was done on pruning techniques in search-based planning. Future directions may consider pruning techniques in SAT-based ADL planning and conformant planning. As IPP's method for handling conditional effects does not lead to a high increase in problem size, it is suitable for SAT-based planning. Therefore, developing adaptations or approximations of our proposed strategy CGRAP in that settings could be interesting.



---

*Source: 398245-2013-08-18.xml*