Abstraction Heuristics for Symbolic Bidirectional Search

1 Introduction

Most cost-optimal planners are based on A⇤ guided with an admissible heuristic. Bidirectional search has not been explored so extensively, due to the inherent difficulties of regression in planning and the computational cost of detecting collisions between both frontiers [Alc´azar et al., 2014]. Symbolic search [McMillan, 1993] reasons over sets of states, substantially reducing the cost of detecting the collision of frontiers. Besides, recent advances have alleviated the problem of spurious states in symbolic regression [Torralba and Alc´azar, 2013]. Thus, symbolic bidirectional uniform-cost search (SB) is among the best algorithms for cost-optimal planning, outperforming not only A⇤ -based planners but also BDDA⇤ , the symbolic search variant of A⇤ .

These observations lead to the question of whether heuristics can further improve SB. Bidirectional heuristic search (BHS) has a long history [Pohl, 1969; de Champeaux, 1983], but it has never convincingly outperformed A⇤ across a significant number of domains. There have been various attempts to explain the main reasons behind the limitations of front-to-end BHS, from the search frontiers passing each other without intersecting [Nilsson, 1982] to the hardness of proving optimality [Kaindl and Kainz, 1997]. A recent study conjectures that the quality of heuristics is a ma-

Carlos Linares L´opez and Daniel Borrajo

Universidad Carlos III de Madrid Madrid, Spain ¶carlos.linares,daniel.borrajo♦@uc3m.es

jor factor for explaining the disappointing empirical results of BHS [Barker and Korf, 2015] and motivating new approaches [Holte et al., 2016].

Perimeter search is a variant of BHS that creates a perimeter around the goal, and uses heuristics that estimate the distance to the perimeter instead of to the goal [Dillenburg and Nelson, 1994]. Abstraction heuristics are a good fit because they precompute the heuristic, avoiding a large overhead during the search [Eyerich and Helmert, 2013]. Moreover, symbolic perimeter abstraction heuristics are state-of-the-art for cost-optimal planning [Torralba et al., 2013].

We present a new planner, SymBA⇤ , that combines symbolic bidirectional search with perimeter abstraction heuristics, exploiting their synergy to benefit from the advantages of BHS and overcome its limitations. SymBA⇤ performs bidirectional searches over different state spaces. It starts in the original search space and, when the search becomes too hard, it derives a perimeter abstraction heuristic. The planner decides at any point whether to advance the search in the original state space, enlarging the perimeter, or in an abstract space to improve the heuristic. To that end, we introduce a new type of abstraction heuristics that uses bidirectional search combined with perimeter and partial abstractions. This is the first time bidirectional search is used to explore abstract state spaces to the best of the authors' knowledge. Even though the theory behind partial and perimeter abstractions has been well studied, they have to be adapted for their combination with bidirectional search. In particular, we study how partial abstractions can be used when A⇤ search is used to traverse the abstract state space and how the initialization of perimeter abstractions can be improved in the bidirectional setting.

2 Preliminaries

A planning task is a 4-tuple ⇧ = hV↪A↪ I↪ Gi. V is a finite set of variables v, each v 2 V being associated with a finite domain Dv. A partial state over V is a function s on a subset V (s) of V, so that s(v) 2 Dv for all v 2 V (s); s is a state if V (s) = V. The initial state I is a state. The goal G is a partial state. A is a finite set of actions, each a 2 A being a pair (prea↪ e↵ a) of partial states, called its precondition and effect. Each a 2 A has a non-negative cost, c(a) 2 R+0 .

The state space of a planning task ⇧ is a labeled transition system ⇥⇧ = (S↪ L↪ T↪ s0↪ SG) where: S is the set of all states; s0 is the initial state I of ⇧; s 2 SG iff G ✓ s; the labels L correspond to the actions A, and s a-! t is a transition in T if s complies with prea, and t(v) = e↵ a(v) for v 2 V (e↵ a) while t(v) = s(v) for v 2 V ∩V (e↵ a). A plan for s is a path from s to any sG 2 SG. The cost of a plan is defined as c(⇡) = Pai2⇡ c(ai). The cost of a cheapest plan for s is denoted h⇤ (s) and the cost of the cheapest path from s0 to s is denoted g⇤ (s). A plan for s0 is a plan for ⇧, and is optimal iff its cost equals h⇤ (s0).

Most cost-optimal planners use heuristic search with A⇤ . A heuristic is a function h : S ! R+0 [¶1♦ which estimates the remaining cost to reach the goal. A heuristic is perfect if it coincides with h⇤ , and it is admissible if it never overestimates the optimal cost, that is, 8s : h(s)  h⇤ (s). A heuristic is consistent if for every transition s a-! t, h(s)  h(t)+c(a). A⇤ expands the nodes with lowest f(s) = g(s) + h(s) first so that no node with f(s) > h⇤ (I) is ever expanded. If the heuristic is admissible A⇤ is guaranteed to return an optimal solution. Moreover, if the heuristic is consistent, A⇤ always closes states with their optimal g-value, g⇤ (s), so it does not re-expand any node.

2.1 Bidirectional Search

A bidirectional search, T is composed of a forward, Tfw, and a backward, Tbw, unidirectional search. We use Tu to denote a unidirectional search in an unspecified direction and T≻u for the search in the opposite direction. Each search Tu consists of an open, open(Tu), and a closed list, closed(Tu). We denote by g(Tu) and f(Tu) the minimum g and f-values of any state in open(Tu), respectively.

Nipping is an optimization that avoids expanding any state if it has already been expanded in the opposite direction [Kwa, 1989]. We apply nipping at generation time in order to avoid unnecessary evaluations. We rely on states always being closed with their optimal g-value, g⇤ , so that g⇤ (s) is known for all s 2 closed(Tu) and those s 2 open(Tu) with g⇤ (s)  g(Tu) + mina2A c(a). Thus, whenever a state s is generated or is going to be expanded in Tu, if g⇤ (s) is known for T≻u, we discard s (without introducing it in closed(Tu)) and store the plan through that state if it is the best plan found so far. The algorithm terminates when the best solution found so far, ⇡, has been proven optimal, i. e., c(⇡)  max(f(Tfw)↪ f(Tbw)). Both frontiers use each other as a heuristic, assigning an admissible value of g(T≻u)+mina2A c(a) to all states in open(Tu). As all states in open(Tu) have the same heuristic value, this does not affect to the expansion order of uniform-cost search, but allows to terminate the algorithm whenever c(⇡)  g(Tbw )+g(Tfw )+ mina2A c(a).

2.2 Abstraction Heuristics

An abstraction is a mapping ↵ : S ! S ↵ from states to abstract states. The abstract state space is a tuple ⇥↵ = hS ↵↪ L↪ T ↵↪ I ↵↪ S ↵ ? i where S ↵ is the set of abstract states, L is the set of labels, T ↵ = ¶(↵(s) a-! ↵(t)) ♣ s a-! t♦, I ↵ = ↵(s0) and S ↵ ? = ¶s↵ ♣ 9s 2 S?↪ s↵ = ↵(s)♦. T ↵ denotes a bidirectional search in ⇥↵, in contrast to the search in the original state space, T ⇧. Abstraction heuristics use the optimal solution cost in ⇥↵, h↵, as an admissible estimation. Similarly, g↵(s) is the optimal solution cost from I ↵ to ↵(s).

There are different types of abstraction heuristics depending on the mapping definition, ↵. Pattern Databases (PDBs) [Culberson and Schaeffer, 1998; Edelkamp, 2001] are projections of ⇧ onto a subset of variables (called pattern), so that two states are equivalent iff they agree on the value of variables in the pattern. Merge-and-shrink (M&S) abstractions generalize PDBs, allowing abstractions that use all variables [Helmert et al., 2007; 2014].

The optimal solution cost from every abstract state, h↵(s↵), is precomputed and stored in a lookup table prior to the search by performing a backward uniform-cost search from the abstract goal, T ↵ bw . Partial abstractions do not search the entire abstract state space completely [Anderson et al., 2007; Edelkamp and Kissmann, 2008b]. Thus, h↵ is only known for states that were expanded during the precomputation phase or were left in open with g-value lower or equal than g(T ↵)+mina2A c(a). For every other abstract state, the heuristic returns the minimum cost with which a state could be generated g(T ↵) +mina2A c(a). Partial abstractions are admissible and consistent.

Perimeter abstractions construct a perimeter around the goal in the original state space and use it to seed the search in the abstract state space [Felner and Ofek, 2007; Eyerich and Helmert, 2013]. The perimeter is constructed by a backward search, T ⇧ bw , which computes the perfect heuristic for all states in closed(T ⇧ bw ). For every state outside the perimeter, an abstract search, T ↵ bw computes the minimum distance from each abstract state to the closest abstract state in the perimeter. Formally, T ↵ bw is initialized with: open(T ↵ bw )[g] = ¶s↵ ♣ 9s2S↪↵(s)=s↵ s 2 open(T ⇧ bw )[g]♦ and closed(T ↵ bw ) = ¶s↵ ♣ 8s2S↪s↵=↵(s) s 2 closed(T ⇧ bw )♦.

2.3 Symbolic Search

Symbolic search algorithms use succinct data-structures like Binary Decision Diagrams [Bryant, 1986] to efficiently represent and manipulate sets of states. BDDs offer a compact representation of sets of states that sometimes can get an exponential advantage in memory with respect to their explicit enumeration [Edelkamp and Kissmann, 2008a]. Furthermore, BDD operations can be used to compute the union or intersection of two sets of states. Using these operations, it is possible to define symbolic versions of different search algorithms like uniform-cost search or A⇤ .

BDDA⇤ is the symbolic version of A⇤ . As usual, it expands states in ascending order of their f -value, but expanding at the same time all the states sharing the same f and g values. A difference with typical explicit implementations of A⇤ is that it uses the opposite tie-breaking. In BDDA⇤ states with lower g-value are preferred in order to generate all the states with the same f and g value before expanding any of them.

Symbolic search is not limited to the original state space. Symbolic PDBs take advantage of symbolic search in order to traverse the abstract state space. This allows for the use of larger patterns, since the state space is not explicitly enumerated [Kissmann, 2012]. The combination of symbolic search and perimeter abstractions is a state-of-the-art heuristic [Torralba et al., 2013], which we extend to the bidirectional case.

3 SymBA⇤ : Symbolic Bidirectional A⇤

SymBA⇤ performs several symbolic bidirectional A⇤ searches on different state spaces. First, SymBA⇤ starts a bidirectional search in the original state space, T ⇧. At each iteration, the algorithm performs a step in a selected direction, i. e., expands the set of states with minimum f-value in the frontier. Since no abstraction heuristic has been derived yet, it behaves like symbolic bidirectional uniform-cost search. This search continues until the next layer in both directions is deemed as unfeasible, because SymBA⇤ estimates that it will take either too much time or memory. Only then, a new bidirectional search is started in an abstract state space, T ↵ initialized with the current frontiers of T ⇧. The abstract searches provide heuristic estimations, increasing the f-value of states in the original search frontiers. Eventually, the search in the original state space will be simplified (as the number of states with minimum f -value will be smaller) 1 and SymBA⇤ will continue the search in the original state space.

One important feature of the algorithm is the lazy evaluation of the heuristics. The search in abstract state spaces is delayed until strictly needed to simplify the original search, allowing SymBA⇤ to use multiple abstraction heuristics without a large overhead. We model this by considering a pool of active searches and letting the algorithm decide which search should be advanced at any step, as shown in Alg. 1. The pool of searches is initialized with a bidirectional search in the original state space. At each iteration, the algorithm filters the searches that are valid candidates from the pool and selects the most promising one. The algorithm depends on this search selection strategy, further explained in Section 7.

Once a search has been selected, the procedure ExpandFrontier expands the set of states that have a minimum g-value among those that have a minimum f -value, as usual in BDDA⇤ . If we progress the original search, a new plan with a lower cost than the incumbent solution may be found. If an abstract search is selected, we update the heuristic value of states in searches in the opposite direction in the pool, both in the abstract and original state spaces. If several abstraction heuristics are generated, SymBA⇤ will use their maximum value, so that the heuristic value of states can only be increased. If there are no valid search candidates (line 10), a new bidirectional search is added to the pool (which amounts to two new searches). The abstraction strategy relaxes the current frontiers of the original search, until the frontier size is small enough to continue the search.

One of the main characteristics of SymBA⇤ is that the heuristics change dynamically during the search. Not only may the algorithm decide to initialize a new abstract search at any point, but also every time that an abstract search performs a step, the heuristic value of states in the original search may increase. Re-evaluating the entire search frontier repeatedly may be too costly if done na¨ıvely, becoming a bottleneck and making the entire algorithm unfeasible. We avoid this problem using the lazy implementation of BDDA⇤ [Edelkamp et al., 2012], which keeps the states organized by g-value and defers the heuristic evaluation. Thus, whenever the heuristic

1 Having fewer states does not necessarily imply that the BDD is smaller, but in most cases there is a positive correlation.

Algorithm 1: SymBA⇤

Input: Planning problem: ⇧ = hV↪ A↪ I↪ Gi Output: Cost-optimal plan or "no plan" 1 SearchPool ¶T ⇧ fw ↪ T ⇧ bw ♦ 2 ⇡ "noplan00 3 while max(f(T ⇧ fw )↪ f (T ⇧ bw )) < cost(⇡) do 4 if 9T X u 2 SearchPool s.t. Is-Candidate(T X u ) then 5 T X u Select-Search(SearchPool) 6 ⇡0 Expand-frontier(T X u ) 7 if X = ⇧ ^ ⇡0 6= ; ^ cost (⇡0 ) < cost (⇡) then 8 ⇡ ⇡0 9 Notify-h(T X ≻u ↪ T ⇧ ≻u) 10 else 11 ↵ Select-abstraction(⇧↪ T ⇧ fw , T ⇧ bw ) 12 DT ↵ fw ↪ T ↵ bw E Apply(↵, T ⇧ fw , T ⇧ bw ) 13 SearchPool SearchPool [ ¶T ↵ fw ↪ T ↵ bw ♦

14 return ⇡

changes in the middle of the search only the set of states currently selected for expansion must be re-evaluated, without any additional computation in the open list.

The next sections describe the abstraction heuristics that we use. Summarizing, (i) bidirectional search can be used in the abstract state space allowing two searches, in opposite directions, to exchange information and avoid redundant work; (ii) partial abstractions allow SymBA⇤ to traverse larger abstract state spaces with less effort, since exploring them completely is unnecessarily expensive; and (iii) perimeter abstractions take advantage of the searches in the original state space in order to obtain better estimates, overcoming the limitations of front-to-end BHS. Perimeter and partial abstraction heuristics are not new and the conditions for consistency and admissibility are well-known for them. However, the use of bidirectional abstract searches and, in particular, the use of A⇤ searches for exploring the abstract state space and constructing the perimeter, requires us to reconsider partial and perimeter abstractions. Our aim is to obtain heuristic estimations as informed as possible while preserving the optimality of the algorithm. Inconsistency of heuristics is not necessarily a problem [Felner et al., 2011], but states must be closed with their optimal g⇤ -value to ensure that perimeter abstractions are admissible.

4 Bidirectional Abstractions

To perform bidirectional search in abstract state spaces, a distinction must be made between the searches used in the original and abstract state spaces. T ⇧ aims to find a plan. So, whenever the two frontiers meet, a plan is retrieved and nipping avoids the expansion of the state to eliminate redundant work between T ⇧ fw and T ⇧ bw . On the other hand, searches on abstract state spaces are used to derive heuristic estimates for the original search. Therefore, nipping must be disabled in order for the estimations to be admissible.

Thus, the interaction between both searches is reduced to use each other as a (perfect) heuristic. But, otherwise, they do not directly interact to detect the collision of their frontiers. Hence, bidirectional searches in the abstract state space are two A⇤ searches using each other as a heuristic. They must redundantly expand states that have already been expanded in the other direction in order to provide admissible estimations to the original search. In the worst case, if both abstract searches traverse the entire abstract state space, the search effort is doubled plus an overhead for using heuristics. Here it is where partial abstractions come in handy to avoid the exploration of the entire abstract state space.

5 Partial Abstractions with Heuristic Search

SymBA⇤ uses partial abstractions to traverse large abstract state spaces that could not be entirely explored otherwise. In order to compute the heuristic value of every state, we will likely need to expand most parts of the abstract state space. For example, if one single state is a dead-end both in the original and the abstract state space, the abstract state space must be completely traversed before continuing the search. Most parts of that computation are irrelevant, since the termination criterion of A⇤ is that, for every state s not expanded yet, f ⇤ (s) ≥ c(⇡). In other words, the heuristic value of a state does not matter provided it is large enough to guarantee that its f-value is not the minimum among the current f-value of other states in the search. To simplify the notation, we assume wlog (the same arguments hold for opposite directions) that a backward abstract A⇤ search, T ↵ bw guided with an admissible estimation of g↵ is used to compute h↵ in order to inform a forward search in the original state space, T ⇧ fw .

Proposition 1. Let T ↵ bw be a search in ⇥↵ and s 2 S be a state s.t. ↵(s) 62 closed(T ↵ bw ). Then f(T ↵ bw ) - g(s)  h⇤ (s).

In partial abstractions, abstract states can be classified depending on whether h↵(s) is known or not. h↵(s) is known for those abstract states that have already been expanded and those that remain in open with a g-value lower or equal than g(T ↵ bw )+mina2A c(a). The question is which heuristic value do we assign to states for which h↵(s) is not known. The usual answer is to use the minimum g-value with which they could be generated, g(T ↵ bw ) +mina2A c(a). Usually, this is a satisfactory lower bound because the abstract state space is explored with a uniform-cost search so g(T ↵ bw ) is constantly increasing. However, in SymBA⇤ the abstract state space is explored with an A⇤ search because it uses the other frontier as (perfect) heuristic. Thus, a bound only based on g(T ↵ bw ) is no longer useful, because it may remain constant as the search progresses. Therefore, states, we set a bound for the f-value of the states, based on the following inequality: f(T ↵ bw )  f ↵(s)  f ⇤ (s). As f(s) = g(s) + h(s), we can translate the bound for f(s) to a heuristic value that depends on the g-value of s: h(s) = f(T ↵ bw ) - g(s).

The problem is that such heuristic may be inconsistent, as illustrated by Figure 1. Consistency requires that for every s a-! t, h(s)  h(t) + c(a). However, if ↵(s) has been expanded by the abstract search and ↵(t) not, the bound for ↵(t), f(T ↵ bw ) - g(t) might be a lot weaker than h↵(s), generating an inconsistency. This may cause t to be expanded before s with a suboptimal g-value. In order to avoid closing any state with a suboptimal g-value, one must ensure that the lower-bound h↵(s) is only used when f(T ↵ bw ) is large enough to satisfy h↵(s)  f(T ↵ bw ) - g(t). So, the abstract search cannot be stopped at any point, it must continue until f (T ⇧ fw )  f(T ↵ bw ). We model this by computing the minimum between h↵ and our f -based bound.

Definition 1 (Partial abstraction heuristic). Let T ↵ bw be an A⇤ search over ⇥↵ informed with an admissible and consistent heuristic. We define the bound for unexplored states B, as B(s↪ T ↵ bw ) :=max¶f(T ↵ bw ) - g(s)↪ g(T ↵ bw ) + mina2A c(a)♦. We define the partial abstraction heuristic as:

hT ↵ is still an inconsistent heuristic because if neither h↵(s) nor h↵(t) are known, B(s↪ T ↵ bw ) = f (T ↵ bw ) - g(s) and B(t↪ T ↵ bw ) = f(T ↵ bw ) - g(t) then h(s) = f(T ↵ bw ) - g(s) and h(t) = f(T ↵ bw ) - g(t). This is clearly inconsistent since it may be that g(s) ⌧ g(t), since g⇤ (t)  g⇤ (s) + c(a) but s has not been expanded yet so g⇤ (t) ⌧ g(t) is possible. However, then f(s) = f(t), and the one with lower g-value is selected for expansion. Theorem 2 proves this in general.

Theorem2. Let T ⇧ fw be an A⇤ search that breaks ties in favor of states with lower g-value 2 and is informed with a hT ↵. Then, for any s 2 closed(T ⇧ fw )↪ g(s) = g⇤ (s).

Proof Sketch. (Full proof in TR) Suppose that g(s) > g⇤ (s). By Lemma 1 in [Hart et al., 1968], there exists a state r 2 open(T ⇧ fw ), r 6= s, which is in the optimal path from I to s such that g(r) = g⇤ (r)  g⇤ (s) < g(s). Since s was selected for expansion, f(s) < f(r). This leads to contradiction for any possible values of hT ↵(s) (and hT ↵(r)):

• ÷ Assume hT ↵(s) = h↵(s). As hT ↵(r)  h↵(r), this leads to contradiction with the consistency of h↵.
• ÷ Assume hT ↵(s) = f(T ↵ bw ) - g(s). As g(s) ≥ g⇤ (r) = g(r), it follows that B(r↪ T ↵ bw ) = f (T ↵ bw )-g(r). Therefore, f(r)  f(T ↵ bw ) = f (s) with contradiction.
• ÷ Assume hT ↵(s) = g(T ↵ bw ) +mina2A c(a). As g(s) ≥ g⇤ (r) = g(r), it follows that B(r↪ T ↵ bw ) = g(T ↵ bw ) + mina2A c(a). Hence, h(r)  f(s) with contradiction.⇤

2 The tie-breaking condition is not needed if f(T ↵ bw ) > f (T ⇧ fw ).

6 Perimeter Bidirectional Abstractions

Perimeter abstractions must also be redefined to handle bidirectional and heuristic searches appropriately. First, in bidirectional search we have forward and backward perimeters. This can be leveraged in the initialization of the abstract searches by ignoring states in both closed lists. The abstract bidirectional search T ↵ is initialized with the perimeter of T ⇧ as: open(T ↵ u )[g] = {s↵j ♣ 9s2S ↵(s) = s↵j ^ s 2 open(T ⇧ u )[g] and closed(T ↵ u ) = {s↵j ♣ 8s2S ↵(s) = s↵j =) s 2 closed(T ⇧ fw ) [ closed (T ⇧ bw) .

Second, the perimeter search is carried out with A⇤ instead of uniform-cost search. Hence, the perimeter is not uniform, i. e., it has not only expanded all states up to a fixed radius. The resulting heuristic is still admissible as long as every state in the perimeter is closed with its optimal value, g⇤ (s) in T ⇧ fw and h⇤ (s) in T ⇧ bw . However, non-uniform perimeters may cause the heuristic to be inconsistent. For example, consider two states s↪ t such that s a-! t, s 2 closed(T ⇧ bw ) and t 62 closed (T ⇧ bw ). In this case, h(s) = h⇤ (s) and h(t) = h↵(t), so consistency may be violated: h(s) 6 h(t) + c(a). However, this poses no problem if nipping is used to eliminate all states in the opposite perimeter because the heuristic will never be evaluated on those states anyway. Theorem 3 proves that the perimeter abstraction heuristic is still admissible and consistent for all relevant states, i. e., those that are not pruned by nipping.

Theorem 3. Let T ↵ u be a perimeter abstraction in ⇥↵ initialized with the perimeters of T ⇧. Then, h is admissible and consistent for any state s 62 closed(T ⇧ fw ) [ closed (T ⇧ bw ).

Proof. A heuristic h is consistent if and only if h(s)  h(t) + c(a) 8s a-! t. In our case, we only contemplate states s↪ t 62 closed(T ⇧ fw ) [ closed (T ⇧ bw ), so ↵(s) and ↵(t) will not be introduced in closed(T ↵ u ) when initializing the abstract search. ↵(t) may be generated by T ↵ u or not. If not, h(t) = 1 and consistency follows. If ↵(t) is expanded by T ↵ u , ↵(s) will be inserted in open(T ↵ u ) and later expanded. Hence, by consistency of h↵, it follows that h(s)  h(t) + c(a).

Therefore, bidirectional A⇤ guided with perimeter abstraction heuristics returns the optimal solution since the heuristic is consistent for every state outside the perimeter and nipping prevents its evaluation in states in the perimeter.

7 Search Selection Strategy

The core of SymBA⇤ , as outlined in Algorithm 1, is how to decide which search should be pushed forward at each iteration. A search is a valid candidate if and only if it is both feasible and useful. A search is feasible if the estimated time and number of nodes needed to perform the next step does not surpass any of the bounds imposed as parameters. The search in the original search space is always useful. A search in an abstract search space is useful if and only if it can further inform the next layer in the original search space, i.e., it has the potential of simplifying the search in the original state space by changing which states are selected for expansion.

Definition 2 (Useful abstract search). Let T ⇧ u be an A⇤ search over ⇥⇧ and let T ↵ ≻u be an abstract search over ⇥↵ in the opposite direction. Let Sf be the set of states currently selected for expansion in T ⇧ u , i. e., a subset of those with minimal f-value according to any given tie-breaking criteria. We say that T ↵ ≻u is useful for T ⇧ u if f(T ↵ ≻u )  f(T ⇧ u ) and 9s2Sf h↵(s) is not known or B(s↪ T ↵ ≻u ) < h↵(s).

Theorem4. Let T ⇧ u be an A⇤ search informed with a heuristic generated by an abstract search T ↵ ≻u . If T ↵ ≻u is not useful for Tu, continuing the abstract search cannot alter the set of states selected for expansion, Sf .

Proof Sketch. (Full proof in TR) Continuing T ↵ ≻u can only increase the h-value of the states. Therefore, the only way to alter Sf is to increase the heuristic value of some s 2 Sf . Since h↵(s)  B(s↪ T ↵ ≻u ), h(s) can only be increased if h(s) < h↵(s), which cannot be true if the search is not use-

• ful.÷ If f(T ⇧ u ) = f(s) < f(T ↵ ≻u ) then hT ↵(s) < B(s↪ T ↵ ≻u ) and h(s) = h↵(s).
• ÷ If h↵(s) is known and h↵(s)  B(s↪ T ↵ ≻u ) then h(s) = h↵(s).

⇤

The search in the original state space is preferred whenever it is feasible. Otherwise, among all the abstract searches that are valid candidates, we prefer those that have a greater minimum f-value, just because they are closer to proving that the current solution is optimal. In case of a tie, the search whose next step is expected to take less time is selected.

In summary, in order to prove optimality, it is enough to expand abstract searches until f(T ↵) ≥ h⇤ (I). All the states whose abstract counterparts have not been expanded in any of the abstract searches do not need to be explored because their f-value is guaranteed to be non-optimal.

8 Experiments

SymBA⇤ is implemented on top of Fast Downward [Helmert, 2006] and uses h2 in a precomputation step to remove irrelevant actions and obtain mutex constraints for pruning the symbolic search [Alc´azar and Torralba, 2015]. For our experiments we used the version of SymBA⇤ that was submitted to IPC'14 after fixing some bugs. We run experiments on the optimal-track STRIPS planning instances from IPC'98 until IPC'14. All experiments were conducted on a cluster of Intel E5-2660 machines running at 2.20 GHz, with time (memory) cut-offs of 30 minutes (4 GB).

We consider a search feasible if the frontier has less than 10 million BDD nodes and each step takes less than 45 seconds, which are adequate values for the memory and time limits of our experiments. SymBA⇤ can use any abstraction function that can be efficiently represented as BDDs such as PDBs and M&S with linear merge strategies [Edelkamp et al., 2012; Helmert et al., 2015]. In our evaluation we focus on the simpler variant, PDBs. To select the "pattern" of the PDBs we follow a strategy previously used for symbolic perimeter abstractions [Torralba et al., 2013], which selects a variable ordering and relax variables one by one until the search can be continued. We use six different variable orderings. lev and rev use the variable ordering of the BDD and its reverse, respectively. rnd is a completely random ordering. cgl and cgr preserve variables interconnected in the causal graph giving preference to goal variables and breaking ties by lev or rnd, respectively. Finally, gcl preserves goal variables preferring those that are interconnected in the causal graph and breaking ties by lev. We also include the two configurations of SymBA⇤ used in IPC'14, which use a combination of abstraction strategies in a round-robin schema. ipc1 uses cgr, gcl and rev. ipc2 uses the same PDB strategies plus a M&S strategy based on bisimulation with a limit of 10 000 abstract states. Finally, ; is a strategy that stops the algorithm instead of using any abstraction, to understand in which cases abstractions are being used. As an ablation study, we run all configurations disabling the perimeter abstractions (≻P) and substituting the bidirectional search in the abstract state spaces for a standard backward search (≻B).

Table 1 compares SymBA⇤ with different abstraction strategies against the current state-of-the-art planner in symbolic search, bidirectional uniform-cost search (SB), and one state-of-the-art explicit-state search planner, METIS [Alkhazraji et al., 2014]. Domains in which all planners got the same coverage are excluded from the table. We report total coverage and a final score that gives the same weight to every domain (versions of the same domain in different competitions are considered the same domain), normalizing the coverage of every planner by the number of problems in that domain. The results show that the use of abstractions can improve the results of our baseline, SB, in 25 problems from 14 different domains. However, generating abstractions implies a non-negligible overhead that affects negatively the coverage in 35 problems from 20 different domains. The conclusion is that using abstraction heuristics is beneficial in domains where the "right" abstraction is selected. Since the performance of all the strategies is close to a random selection of variables (rnd), all configurations are nearly tied in total coverage. The best strategy is ipc2, which won the optimal-track of IPC'14. With it, the standard configuration of SymBA⇤ gets a score of 21▷24; more than the baseline and METIS.

In the 936 problems solved by ;, all the configurations behave in the same way. In the rest of the problems, abstractions are used in around 500 cases. This reflects that, by limiting the frontier size to 10 million BDD nodes, SymBA⇤ is able to identify in which cases the blind search is going to fail and resort to abstractions. If this parameter is set to 1 million nodes, most configurations improve in domains where they are better than the baseline (e.g., ipc1/2 solve 18 problems in NoMystery except for ≻B and ipc2 with ≻B solves 11 instances in Satellite.) but their total coverage slightly decreases: ; solves 898 instances, ipc2 961 and ipc2 with ≻B, 962.

The ablation study shows that using perimeter abstractions is usually helpful. Regarding bidirectional search in abstract state spaces, however, the results are less clear. When a single PDB is used, both versions are closely tied though sometimes working best in different domains. However, when combining several strategies, as in the ipc configurations, the version disabling bidirectional search in abstract state spaces obtains better results. Our best configuration is ipc2 with backward search in the abstract state spaces, improving the previous state-of-the-art techniques both in coverage and score.

9 Conclusions

This paper addresses the question of whether heuristics can be used to further improve the results of symbolic bidirectional uniform-cost search (SB). This is a hard task, given that multiple BHS algorithms have been proposed in the past failing to outperform A⇤ search and SB. We have introduced a new algorithm, SymBA⇤ , that uses bidirectional A⇤ with abstraction heuristics. SymBA⇤ leverages the performance of SB by deferring the use of heuristics until a blind search seems unfeasible. In order to generate heuristics for both search frontiers, a bidirectional search is carried out in an abstract state space, initialized with the current frontier as a perimeter abstraction. To this end, we extended the definition of partial and perimeter abstractions to the bidirectional case. These extensions are not limited to SymBA⇤ and they can be applied to other algorithms that use A⇤ to explore abstract state spaces such as the hierarchical heuristic search algorithm Switchback [Larsen et al., 2010; Leighton et al., 2011].

Our experimental results show that abstractions can further improve the current state-of-the-art in symbolic bidirectional search, helping SymBA⇤ to win the optimal track of the last IPC. However, finding the right abstractions in a domainindependent way is not a trivial task and there is still room for improvement in future work.

Acknowledgments

We'd like to thank Rosa Moreno Morales for her advice and support. This work was partially supported by MICINN projects TIN2014-55637-C2-1-R and TIN2011-27652-C0302.