Revisiting Regression in Planning

1 Introduction

Automated planning (AP) is the task of finding a sequence of actions that, from a given initial state, reaches a set of goals. It is one of the oldest areas of research in AI, but only relatively recently domain-independent planners have been able to solve non-trivial tasks. Heuristic search [Bonet and Geffner, 2001] has become one of the most important paradigms in the area, as shown by the results of the most recent International Planning Competition (IPC) 1 and the much higher number of publications in AP about heuristic search compared to publications about other successful approaches like local-search [Gerevini and Serina, 2002] or SAT-based planning [Kautz and Selman, 1999].

Search can be done either advancing from the initial state towards a goal state, called forward search or progression, or from a goal state to the initial state, called backward search or regression. In heuristic search most works use combinatorial domains as benchmarks. Combinatorial domains are in most cases trivially invertible and have a single goal state. Therefore, often forward and backward search are analogous and the same techniques and conclusions are relevant to both cases. However, this is not true in AP. While the initial state is completely defined due to the closed-world assumption, goals are defined as partial states. Thus, the value of propositions not included in the goal set are unknown and multiple goal states are possible. As a consequence, backward search reasons over sets of facts and not complete states, making the search more akin to state-set search [Pang and Holte, 2011] than to traditional heuristic search.

1 http://ipc.icaps-conference.org/

Due to these differences backward search planners have several drawbacks: the techniques developed for forward search may not be applicable, duplicate detection is more complex due to partial states, and spurious states (partial states containing a set of facts that is unreachable from the initial state) may be generated. Early research on heuristic search in AP studied both forward and backward search [Bonet and Geffner, 2001], but these drawbacks lead to a worse performance of regression planners compared to progression planners. For this reason, research on backward search in AP was discontinued in many cases.

Over the last decade important works shed light on both the formal properties of forward search, like the relationship between different heuristics [Helmert and Geffner, 2008; Helmert and Domshlak, 2009], and the empirical impact of widely used techniques, like preferred operators and deferred heuristic evaluation [Richter and Helmert, 2009]. Nevertheless and despite the strong relationship between forward and backward search, this has not been exploited to improve over the results of previous backward search planners. In particular, some techniques that may address the shortcomings of regression in satisficing planning, like preferred operators, seem to have potential. In this work we analyze how efficient techniques commonly used in progression can be extrapolated to backward search. We define some new concepts related with regression and propose several novel techniques implemented in a new regression planner, based on Fast Downward [Helmert, 2006], called FDR (Fast Downward Regression). In particular, the concepts and techniques are the following: formalization of regression in SAS+; disambiguation of states and action preconditions; action pruning using e-deletion; improvements on the computation of the applicable actions; novel definition of reasonable orders in regression; computation of reachability heuristics and preferred operators in regression; usage of P m formulations of the planning task to infer more informed heuristics in regression; and computation of strong precedences related to the context-enhanced additive heuristic in regression.

2 Formalization

In this section we will present the current two main formalizations of the planning tasks: propositional and multi-valued. Additionally, regression in both formalizations is described.

2.1 Propositional Planning

The propositional formalization of a planning task is defined as a tuple P=(S,A,I,G), where S is a set of atomic propositions (also known as facts), A is the set of grounded actions derived from the operators of the domain, I ⊆ S is the initial state and G ⊆ S the set of goal propositions. Each action a ∈ A is defined as a triple (pre(a), add(a), del(a)) (preconditions, add effects and delete effects) where pre(a), add(a), del(a) ⊆ S. Actions can have non-unitary costs. A distinction must be made between satisficing planning, that tries to find a plan preferring those of better quality with respect to a given metric, and optimal planning, where the best plan must be found. In this work we focus on satisficing planning.

2.2 Multi-Valued Formalizations of Planning

The two most common multi-valued formalizations are SAS+ [B¨ackstr¨om and Nebel, 1995] and the Finite-Domain Representation proposed by Helmert [2006], based on SAS+. In this work we will refer only to SAS+. A planning task in SAS+ is defined as a tuple Π=(V,s0,s⋆,O). V is a set of state variables, and every variable v ∈ V has an associated extended domain D+ v = Dv ∪ {u} composed of the regular domain of each variable, Dv, and the undefined value u. The total state space is defined as S+ v =D+ v0 × . . . ×D+ vn and the value of a variable v ∈ V in a given state s, also known as fluent, is defined as s[v]. Partial states are states in which at least a fluent s[vi] = u. s0 is the initial state, defined over V such that s0[vi] ̸= u ∀vi ∈ V. s⋆ is the partial state that defines the goals. O is a set of operators (actions), where each operator is a tuple o = (pre(o), post(o), prev(o)), where pre(o), post(o), prev(o) ∈ S+ v represent the pre-, post- and prevail-conditions respectively. An action o ∈ O is applicable in a state s if ∀vi ∈ V : (prev(o)[vi] = s[vi] ∨ pre(o)[vi] = s[vi]) ∧ (pre(o)[vi] = u ∨ pre(o)[vi] = s[vi]). The resulting state s′ from the application of o in s is equal to s except that ∀vi ∈ V s.t. post(o)[vi] ̸= u : s′ [vi] = post(o)[vi].

Fluents in SAS+ are extrapolable to propositions in a propositional representation. For instance, regarding actions, preconditions in SAS+ are preconditions deleted by the action, postconditions are positive effects and prevail conditions are preconditions not deleted by the action. In this work we assume that every concept described in terms of fluents is also relevant to propositions.

2.3 Planning Formalizations in Regression

Regression search in planning starts from the goals and applies the actions backwards to find a path from the goals to the initial state. Action preconditions are partial definitions of the states in which the actions can be applied. Thus, the states generated by regression are partial states. In a propositional representation in regression, the closed world assumption cannot be enforced due to the existence of undefined values unless undefined propositions are represented explicitly.

Given a propositional planning task P=(S,A,I,G), the definition of P for regression is a tuple P'=(S,A,I',SG) where I'= G is the initial (partial) state; SG is the set of goal states, composed by all the sets of propositions (partial states) s ⊆ S for which s ⊆ I, SG = {s | s ⊆ S, s ⊆ I}. The applicability of actions is redefined as follows: a ∈ A is applicable in a partial state s ⊆ S if it is relevant (add(a) ∩ s ̸= ∅) and consistent (del(a) ∩ s = ∅). The resulting state sr ⊆ S obtained from regressing a in s is sr = (s \ add(a)) ∪ pre(a). This can also be seen as a reversed action a′ in which add(a) is a set of disjunctive preconditions of a′ , del(a) are negative preconditions of a′ and pre(a) are the adds of a′ . Progression and regression in planning are not symmetric as each state in the regression state space may represent a set of states of the progression state space.

Similarly, a SAS+ task in regression is a tuple Π′=(V,s′0 ,S′⋆ ,O), where s′0 = s⋆ and S′⋆ is the set of partial states subsumed by s0, following the next definition of subsumption.

Definition 1 (Subsumption of states in SAS+) Given two SAS+ states si and sj, si subsumes sj (si ⊑ sj) when for every v ∈ V, si[v] = sj [v] or si[v] = u.

An action o ∈ O is applicable in a partial state s in regression if ∀vi ∈ V : s[vi] = u ∨ s[vi] = post(o)[vi] ∨ s[vi] = prev(o)[vi] and ∃vi ∈ V : s[vi] = post(o)[vi] ∧ s[vi] ̸= u. The resulting state s′ obtained from applying o in s in regression is equal to s except that ∀vi ∈ V s.t. pre(o)[vi] ̸= u : s′ [vi] = pre(o)[vi] and ∀vi ∈ V s.t. prev(o)[vi] ̸= u : s′ [vi] = prev(o)[vi]. Note that applicability of actions in SAS+ is more restricted than in a propositional representation, as prevail preconditions must be taken into account. All the actions applicable in a propositional representation that are not applicable in SAS+ lead to spurious states: the resulting state s′ would contain s[vi] and prev(o)[vi], which are different values of the same variable unless one of them is undefined.

3 Common Concepts

Here we describe two important concepts used throughout the paper. These concepts are relationships of mutual exclusion and e-deletion. From this point on we will use SAS+ unless otherwise stated.

3.1 Mutual Exclusivity between Facts

An important problem in backward search is the generation of spurious states (states not reachable by a forward search). Mutual exclusivity between fluents can be used to prune such states [Bonet and Geffner, 2001]. A set of fluents M = {p1, . . . , pm} is a set of mutually exclusive fluents of size m (mutex of size m) if there is no reachable state s ⊆ S such that all elements in M are true in s.

The use of mutexes may not detect all the spurious states in regression, but in many domains they are able to prune a significant amount of them. Computing mutexes is exponential on the size m, so in most cases computing mutexes of size m > 2 is not practical. Invariant monotonicity [Helmert, 2006] and hm [Bonet and Geffner, 2001] with m = 2 are usually used to compute mutexes of size two, although the former finds strictly fewer mutexes than the latter.

3.2 E-deletion

The negative effects of an action are not restricted to its explicit delete effects. In particular, whether a fluent is deleted along any path that ends with a particular action can be precomputed. This belongs to the more general definition of edeletion [Vidal and Geffner, 2005].

Definition 2 An action a e-deletes a fluent f if f must be false in every state resulting from the execution of an ordered set of actions whose last action is a from a state in which f is true.

There are three cases in which an action e-deletes a fluent f : it deletes f ; it has a set of preconditions mutex with f and does not add f ; or it adds a set of fluents mutex with f. For instance, the action (stack b c) e-deletes (on a b) because it adds (clear b), which is mutex with (on a b). In multi-valued representations, deleting a fluent means changing the value of the variable it corresponds to, which is equivalent to adding a fluent mutex with f. Hence, the first case is a particular instance of the third case in multi-valued representations.

4 Regression and Backward Heuristic Search: HSPr

In satisficing planning, HSPr [Bonet and Geffner, 2001], one of the best known backward search planners, uses a propositional formalization, a weighted A* algorithm and the additive heuristic, hadd . hadd is the sum of the accumulated cost of achieving every goal proposition in a delete-free version of the problem. The main difference with HSP, its forward version, is that it caches the estimation of the cost from I to every proposition. It uses mutexes found with h2 to prune spurious states. As heuristic search planners spend most of their time computing the heuristic, caching hadd allows HSPr to generate states at a much higher rate. However, doing regression has several important drawbacks. First, mutexes may not suffice to prune spurious states in some domains. Second, when using a propositional representation, detection of duplicate states requires modifications in the algorithm due to the presence of propositions whose value may be unknown. Furthermore, duplicate detection is unable to detect subsumption of states. Finally, hadd is heavily affected by partial states: if the value of a proposition is undefined, its cost is not accounted for, so hadd may differ greatly depending on the number of unknown propositions. For these reasons HSPr performed overall worse than HSP. These problems combined with the success of some techniques introduced by other forward heuristic planners, like Fast Forward [Hoffmann and Nebel, 2001] and Fast Downward [Helmert, 2006], made researchers abandon for the most part backward search in planning.

5 Revisiting Regression in Planning

In this section we revisit some important concepts originally defined for forward search, adapting them to their use in regression planners. Each of the subsections describes the set of techniques, proposes a novel implementation in regression and defines them formally if needed.

5.1 SAS+, Invariant Groups and Disambiguation

Partial states require the definition of the undefined value u. SAS+ allows it by adding it to the domain of all the variables in a preprocessing step. Hence, any SAS+ planner can do regression with no changes in their search algorithm apart from changing the applicability and effects of actions. Identical partial states are detected as duplicates, but subsumption of states is not. For example, given two states s0 and s1 such that ∀vi ∈ V : s0[vi] = s1[vi], they are detected as duplicate. However, if this is true except for some vj ∈ V such that s0[vj] = u and s1[vj] ̸= u, s0 ⊑ s1 is not detected.

Planners that use SAS+ transform a planning task expressed in the Planning Domain Definition Language (PDDL) into SAS+ by computing invariant groups.

Definition 3 An invariant group is a set of fluents θ such that every fluent fi ∈ θ is mutex with every other fluent fj ∈ θ and fj ̸= fi. Exactly one fluent fi ∈ θ must be true in every non-spurious complete state.

In partial states the value of some variables may be unknown. 2 Nevertheless, the value of other known variables may reduce the domain of the unknown variables. We call disambiguation to the process of reducing the valid domains of the unknown variables of a partial state. There are three relevant cases for any given invariant group θ: (1) only one fluent f ∈ θ can be true in the partial state; (2) no fluent f ∈ θ can be true; and (3) more than one fluent f ∈ θ can be true. The first case means that f must be true in the state and thus the variable f corresponds to is no longer unknown. The second case means the partial state is spurious, as it is not possible for exactly one fluent f ∈ θ to be true. And in the third case, no additional information can be inferred.

For example, given V = {v0,v1,v2} and Dv0 = {a, b, c}, if in a given partial state s : s[v0] = u, s[v1] is mutex with v0 = a and s[v2] is mutex with v0 = b, then we can infer that s[v0] = c; it is the only possible value for v0. If additionally s[v1] or s[v2] are mutex with s[v0] = c, then v0 has no possible value and the state is spurious.

Disambiguation of partial states fulfills two purposes: adding information to partial states by reducing the number of unknown variables upon generation, and pruning spurious states undetectable by only using binary static mutexes. Having fewer unknown variables impacts the performance in two ways. First, heuristics tend to be more accurate, as the cost of fluents that otherwise would be ignored is accounted for. Second, it reduces the number of cases in which there is subsumption of expanded states thanks to cases in which si, sj ⊆ S, si ⊑ sj before disambiguation and si = sj after disambiguation. Figure 1 shows an example of pruning by disambiguation in the floortile domain.

2 Note that every variable in SAS+ corresponds to an invariant

Problems in floortile consist of two or more robots that have to paint the cells of a grid. The initial state contains the locations where the robots are. The goal contains the painted cells. It is possible to find a plan doing regression in which a single robot traverses and paints the whole grid. This means that there may be a partial state in which all the cells are either painted, clear or occupied by the first robot. When disambiguating the state, we can see that there are no legal values for the variables that represent the position of the other robots, as a robot cannot be at a painted cell, a clear cell or a cell occupied by another robot. Such a state can be safely pruned. Binary mutexes with no disambiguation are ineffective to detect this case in regression.

Disambiguation can also be done over the preconditions of actions after grounding, as the set of preconditions define a partial state. More preconditions lead to fewer unknown variables in partial states. Also, operators whose set of preconditions is spurious can be discarded.

5.2 Enhanced Applicability in Regression and Decision Trees for Successor Generation

HSPr evaluates states at a faster rate than HSP. However, many of those states are spurious and are pruned using mutexes anyway, so often no performance gain is achieved. Consider for example the blocksworld domain: if there is a tower of blocks and (arm-empty) is true in the partial state in regression, half of the actions of the domain are aplicable because they add (arm-empty), whereas only one (stacking the upper block) leads to a non-spurious state. The other applicable actions produce states that contain mutexes. For example, if (on a b) and (on b c) are true and (stack b c) is applied in regression, the generated state would contain the mutex {(on a b), (holding b)}, as (holding b) is a precondition of (stack b c).

This is due to the current definition of applicability of actions in regression. In fact, the current definition makes planners knowingly generate spurious states that will be pruned using mutexes. This is a waste of effort that can be avoided using e-deletion instead of just regular deletes. The applicability of an action in regression can be modified to reflect this.

Definition 4 If e-del(a) is the set of fluents e-deleted by action a, a is consistent with partial state s if e-del(a) ∩ s = ∅.

Using e-deletion causes the actions to have a bigger number of negative preconditions (i.e., a regular move operator e-deletes the moving agent at every location other than the destination). Also, regular adds are disjuntive preconditions

group.

in regression, which imposes an additional complexity when checking applicability. This may cause an important overhead during search. A solution is to use precomputed decision trees as successor generators [Helmert, 2006].

Forward search uses decision trees (similar to RETE networks used for matching rule-based systems [Forgy, 1982]) to avoid checking the applicability of all the actions of the problem. Every inner node represents a variable v ∈ V and has an edge for each d ∈ Dv plus the don't care value. Leaf nodes contain the sets of actions that are applicable on that node. Each edge leads to another inner node representing the next variable or to a leaf node. When building the leaf (action) nodes, an action a is propagated at every inner node down the edge that corresponds to v = d if v = d ∈ pre(a) ∨ v = d ∈ prev(a). If v = d ̸∈ pre(a) ∧ v = d ̸∈ prev(a) then a is propagated down the don't care edge. So, the path from the root to the leaf node represents the preconditions of the action. Every action occurs in at most one leaf node, so the number of leaf nodes is bounded by the number of actions of the problem. When computing the applicable actions of a state s, at every inner node the algorithm follows the don't care edge and the edge that corresponds to s[v]. The union of the sets of actions of the visited leaf nodes is the set of applicable actions.

The main difference with the decision trees used by Fast Downward is that FDR must deal with disjunctive preconditions, negative preconditions and unknown variables. To take this into account, the inner nodes represent fluents (values of variables) instead of variables. They have three edges for the cases ⊤, ⊥ and don't care through which actions that add, e-delete and do not change the variable of the fluent are respectively propagated. If the fluent is unknown in a partial state, all the three children must be explored, as opposed to either ⊤ or ⊥ and don't care. This combines the efficiency of decision trees in progression and the greater expressiveness required in regression.

6 Reachability Heuristics in Regression

In this section, we describe how to compute recent state-ofthe-art heuristics in regression, exploiting advantages of regression like caching schemes. We use a propositional formalization of the task as it is the de facto implementation even in planners that use a multi-valued formalization, like FD.

6.1 Best Supporter Caching

Most forward planners use heuristics based on a deleterelaxation of the problem. There are several heuristics of this kind [Keyder and Geffner, 2009], but HSPr is limited to hadd . Delete-relaxation and critical path heuristics belong to the same family of heuristics. They differ mainly in the functions used to (1) select the best supporter of propositions, (2) aggregate the supporters of preconditions (subgoals) and goals, and (3) compute a cost estimation from a set of aggregated supporters [Fuentetaja et al., 2009]. Supporters and costs are derived from a forward reachability analysis that depends exclusively on the source state. If the source state does not change, all the necessary information can be cached. This allows planners to compute these heuristics in regression without performing additional reachability analysis, which greatly speeds up their computation. In practice, we cache the best supporters determined by Equation 1, which defines how to select the best supporter ap of a proposition p among the set of actions A(p) that add p. 3

Caching the best supporters allows computing the FF heuristic [Hoffmann and Nebel, 2001]: the cost of a plan that reaches a partial state from the initial state in a delete-free version of the problem. Figure 2 shows the difference between caching in HSPr and best supporter caching. In this problem an agent must go from I to K to pick up a key and then carry it to G. hadd adds the distance from I to K to the distance from I to G and to the cost of picking up the key. So, if the cost of all actions is one, hadd = 9. FF computes a relaxed plan by tracing back from the fluents of the partial state to the initial state using best supporters. Moving from I to K and G with no deletes requires 5 actions, so hFF = 6. In either case if the partial state changes no new reachability analysis is needed; both heuristics can be computed with the cached information.

Additional information can be extracted by caching supporters. To compute preferred operators [Helmert, 2006], a technique that improves the performance in progression significantly [Richter and Helmert, 2009], an aggregated set of actions is required. We redefine preferred operators in regression as the applicable actions in regression that appear in the relaxed plan. In the former example moving to G from the left is the only preferred operator.

6.2 Computing Heuristics in Pm

Reachability heuristics are usually computed by ignoring the delete effects of actions. These effects can be partially included by using the alternative version of the problem Pm [Haslum, 2009]. Pm is a redefinition of the planning task in which every fluent in Pm is a set of fluents of size m. hmax in Pm is equivalent to hm in P1 ; this is not exclusive to hmax , any other reachability heuristic can be computed in Pm. Computing such heuristics is exponential on m, so in practice it is not viable to use them in progression, as it would require an expensive reachability analysis per evaluated state. New developments regarding semi-relaxed plans in progression [Keyder et al., 2012] have been proposed, although they require complex implementations and are not as informative as the heuristics computed in Pm. Nevertheless, in regression only one reachability analysis is needed, which makes their computation tractable thanks to caching.

3 Ties in Equation 1 are broken arbitrarily.

We propose a general definition of best supporters in P1 that takes into account sets of propositions of size m based on Equation 1. Best supporters are now determined by Equation 2, that defines the best supporter aP of a set of propositions P with size |P | ≤ m.

A(P) is the set of actions that generate at least a proposition in P without deleting any other:

Reg(P, a) is the result of regressing P through a: Reg(P, a) = P \add(a)∪pre(a). The cost of reaching the partial state s from the initial state I is defined as:

where

and

In our implementation we cache best supporters for atom pairs when computing h2 to find mutexes. This allows computing a relaxed plan in P2 (essentially a FF2 version of the original FF heuristic). For partial state s we compute the atom pairs Pi ∈ s. The best supporter aPi of each atom pair Pi is added to the relaxed plan and the atom pairs obtained from Reg(Pi, aPi ) that are not true in I are added as open preconditions. This is repeated until no open preconditions remain.

6.3 Reasonable Orders, Contexts and Paths through Invariants

Reasonable orders between goal propositions were first proposed to create a goal agenda [Koehler and Hoffmann, 2000] and later on extended to landmarks and arbitrary pairs of facts [Hoffmann et al., 2004]. e-deletion allows us a simple and general way to extend the definition to sets of facts.

Definition 5 A fact f is reasonably ordered before a set of fluents Fr (f <r Fr) if all the supporters of f are e-deleters of some fact f ′ ∈ Fr.

Reasonable orders were deemed "unsound" in progression, because it is not true that, if f <r f ′ , then f must be achieved first in every solution plan. Nevertheless, some sound information can be derived: if f <r f ′ and both fluents must be true until the end of the plan, then f ′ must be achieved last. In progression this can only be proved for top level goals. But, in regression, this holds for every f <r f ′ if f and f ′ are true in a partial state, as partial states in regression can be treated as top level goals. In this case, the supporters of f can be pruned because f ′ must be supported first.

If consistency is defined as in Definition 4 no additional pruning is obtained. However, reasonable orders in regression also allow us inferring stronger precedence constraints.

The context-enhanced additive heuristic, hcea [Helmert and Geffner, 2008], is a variation of hadd . Several contexts or pivots are selected during the heuristic computation and the cost of some goals is computed from a state that results from achieving the pivots. In Figure 2 the most informative context is agent-at=K, in which case hcea would add the distance from I to K to the distance from K to G and to the cost of picking up the key, yielding hadd = 7, the cost of the optimal solution. Choosing the right context is still an open question. Reasonable orders were proposed as a way of computing contexts [Cai et al., 2009], although in progression they may be misleading. In regression, though, if f <r f ′ and f and f ′ are true at the same time, f ′ must be supported after having achieved f. This hints from which context f ′ is achieved in most solution plans. A likely context is the conflicting fluents that cause the e-deletion of f ′ by the best supporter of f [Nguyen and Kambhampati, 2001]. In Figure 2, the best supporter of have-key=⊤ is pick-key(K), whose precondition agent-at=K is the cause of the e-deletion of agent-at=G. This suggests that agent-at=K is indeed a useful context.

Best supporter caching is also possible in hcea . If the conflicting fluents belong to the same invariant group θ, the best supporters can be cached when a fluent f is used as context. For this, a Dijsktra algorithm in the Domain Transition Graph (DTG) defined by θ is done with f as the source. This allows computing relaxed plans and preferred operators in DTGs. In our implementation relaxed plans are computed instead of adding costs.

7 Experimentation

The proposed techniques were implemented on top of Fast Downward (FD). We used the benchmark suite from IPC2011 and compared FDR against HSPr, FD with greedy best-first search (GBFS), hFF and delayed evaluation and Mp [Rintanen, 2010]. Mp was included because it includes several modifications that make the SAT solver prefer actions that support open goals and preconditions like in regression. Four configurations were tested: FDrFF , FDradd , FDrcea , FDr2 , which use hFF , hadd , hcea and hFF in P2 respectively. FDr's search algorithm is GBFS with regular evaluation. Since the focus of the experimentation is coverage, action costs were ignored. Time score was omitted for lack of space.

Preferred operators were not used. Although promising a priori, they were not helpful. This may seem counterintuitive, as the reduced branching factor and the additional heuristic guidance should help, but in partial states they often commit strongly to unpromising areas of the search space. When enabled, FDrFF only solved one more problem in woodworking while losing coverage in parcprinter, transport and visitall.

As seen in Table 1, FDrFF solves consistently more problems than HSPr and is close to Mp in coverage. FDr2 performed worse except in parcprinter, in which it solved the whole set of problems. The overhead of hcea does not pay off, surpassing other heuristics only in two domains. No regression planner was able to solve any instance in barman due to spurious states that could not be detected (i.e. due to some imprecisions in the domain formulation h2 cannot detect mutexes like a shaker being clean and containing an ingredient at the same time). The regression planners fare worse than FD in total coverage, although this varies among domains. FDR is superior to FD in floortile, as this domain contains a high number of dead ends in progression that are difficult to detect. FDradd also solves many more problems in visitall, a domain in which heuristics like FF are affected by big plateaus. openstacks and sokoban are the opposite case: problems trivial for FD are hard for all the regression planners. As hypothesized, Mp seems to behave similarly to regression planners, with the exceptions of nomystery and pegsol. This confirms the impact of directionality in planning [Massey, 1999].

An ablation study was also done disabling disambiguation and decision trees as successor generators. 8 fewer problems were solved using FDradd after disabling disambiguation. The number of expansions increased by an order of magnitude in parcprinter and woodworking, staying the same or very similar in other domains. When disabling decision trees, 5 fewer problems were solved. The impact was proportional to the number of grounded actions and the number of effects of those actions, increasing search time by an order of magnitude in domains like floortile and woodworking.

8 Conclusions

In this work we analyzed several state-of-the-art techniques in forward search and explored their potential in regression. Some novel definitions were also proposed. We implemented a new regression planner, FDR, which performed consistently better than its predecessor HSPr. Overall performance seems to depend greatly on the topography of the search space, which means that one should not rule out regression in domain-independent planning. This also implies that there may be a high synergy between FD and FDr, potentially leading to a bidirectional planner better than the combination of the individual planners in a portfolio. The implementation of such a planner remains as future work along with the use of other state-of-the-art techniques which are simple to employ in regression, like landmarks [Richter and Westphal, 2010] and multiple queues [R¨oger and Helmert, 2010].

Acknowledgments

This work has been partially supported by the Spanish government through MICINN projects TIN2008-06701-C03-03 (as a FPI grant) and TIN2011-27652-C03-02.