Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

1 Introduction

One method of formally assessing the efficiency of a heuristic search algorithm is to establish upper and lower bounds on the number of nodes it expands on any given problem instance I. Such bounds can then be compared to a theoretical minimum that a competing heuristic search algorithm would have to expand on I. In this context, one is interested in finding sufficient conditions for node expansion, i.e., conditions describing nodes that must provably be expanded by any competing algorithm. In a unidirectional search an algorithm must expand every node whose f-value is less than the optimal solution cost; this condition establishes the optimality of A* [Dechter and Pearl, 1985].

Sufficient conditions for node expansion have recently been developed for front-to-end bidirectional heuristic search [Eckerle et al., 2017], but no existing front-to-end bidirectional search algorithm is provably optimal. In this paper, we use these sufficient conditions to derive a simple graphtheoretic characterization of nodes that must provably be expanded on a problem instance I by any admissible front-toend bidirectional search algorithm given a consistent heuristic. In particular, the set of nodes expanded must correspond Sandra Zilles University of Regina Regina, SK, Canada zilles@uregina.ca Nathan R. Sturtevant University of Denver Denver, CO, USA sturtevant@cs.du.edu to a vertex cover of a specific graph derived from I. We then adapt a known vertex cover algorithm [Papadimitriou and Steiglitz, 1982] into a new admissible front-to-end bidirectional search algorithm, NBS (Near-Optimal Bidirectional Search), and prove that NBS never expands more than twice the number of nodes contained in a minimum vertex cover. Hence, the number of nodes expanded by NBS is provably within a factor of two of optimal.

We further establish that no admissible bidirectional frontto-end algorithm can be better than NBS in the worst case. In that sense, we formally verify that NBS is near-optimal in the general case and optimal in the worst case. In an experimental study on a set of standard benchmark problems, NBS either competes with or outperforms existing bidirectional search algorithms, and it often outperforms the unidirectional algorithm A*, especially when the heuristic is weak or the problem instance is hard.

2 RelatedWork

Bidirectional search has a long history, beginning with bidirectional brute force search [Nicholson, 1966], and proceeding to heuristic search algorithms such as BHPA [Pohl, 1971]. Other notable algorithms include BS* [Kwa, 1989], which avoids re-expanding states in both directions, and MM [Holte et al., 2016], which ensures that the search frontiers meet in the middle. Along with these algorithms there have been explanations for the poor performance of bidirectional heuristic search, including that the frontiers miss [Nilsson, 1982] or that the frontiers meet early, and a long time is spent proving the optimal solution [Kaindl and Kainz, 1997]. Recent work has refined this, showing that with strong heuristics the frontiers meet later [Barker and Korf, 2015].

3 Terminology and Notation

We use the same notation and terminology as [Eckerle et al., 2017]. A state space G is a finite directed graph whose vertices are states and whose edges are pairs of states. 1 Each edge (u, v) has a cost c(u, v) ≥ 0. A forward path in G is a finite sequence U = (U0, . . . , Un) of states in G where (Ui,Ui+1) is an edge in G for 0 ≤ i < n. We say that forward path U contains edge (u, v) if Ui = u and Ui+1 = v for some i. Likewise, a backward path is a finite sequence V = (V0, . . . , Vm) of states where (Vi, Vi+1) is a "reverse" edge, i.e. (Vi+1, Vi) is an edge in G for 0 ≤ i < m. Backward path V contains reverse edge (u, v) if Vi = u and Vi+1 = v for some i. The reverse of path V = (V0, . . . , Vm) is V -1 = (Vm, . . . , V0). The cost of a reverse edge equals the cost of the corresponding original edge. A path pair (U, V ) has a forward path (U) as its first component and a backward path (V ) as its second component.

1 If G has multiple edges from state u to state v, we ignore all but the cheapest of them.

If U is a path (forward or backward), |U| is the number of edges in U, c(U) is the cost of U (the sum of the costs of all the edges in U), and Ui is the ith state in U (0 ≤ i ≤ |U|). U|U| is the last state in path U, which we also denote end(U). λF = (start) and λB = (goal) are the empty forward and backward paths from start and goal, respectively. Note that end(λF ) = start while end(λB) = goal. Both λF and λB have a cost of 0. Forward (backward, resp.) path U is optimal if there is no cheaper forward (backward, resp.) path fromU0 to end(U). d(u, v) is the distance from state u to state v, i.e., the cost of the cheapest forward path from u to v. If there is no forward path from u to v then d(u, v) = ∞. Given two states in G, start and goal, a solution path is a forward path from start to goal. C ∗ = d(start, goal) is the cost of the cheapest solution path.

A heuristic maps an individual state in G to a non-negative real number or to ∞. Heuristic hF is forward admissible iff hF (u) ≤ d(u, goal) for all u in G and is forward consistent iff hF (u) ≤ d(u, u′ )+hF (u′ ) for all u and u′ in G. Heuristic hB is backward admissible iff hB(v) ≤ d(start, v) for all v in G and is backward consistent iff hB(v) ≤ d(v′ , v) + hB(v′ ) for all v and v′ in G. For any forward path U with U0 = start define fF (U) = c(U)+hF (end(U)), and for any backward path V with V0 = goal define fB(V ) = c(V ) + hB(end(V )).

A problem instance is defined by specifying two front-toend heuristics, hF and hB, and a state space G represented implicitly by a 5-tuple (start, goal, c, expandF , expandB) consisting of a start state (start), a goal state (goal), an edge cost function (c), a successor function (expandF ), and a predecessor function (expandB). The input to expandF is a forward path U. Its output is a sequence (U 1 , . . . ,U n ), where each U k is a forward path consisting of U followed by one additional state (end(U k )) such that (end(U), end(U k )) is an edge in G. There is one U k for every state s such that (end(U), s) is an edge in G. Likewise, the input to expandB is a backward path V and its output is a sequence (V 1 , . . . , V m), where each V k is a backward path consisting of V followed by one additional state (end(V k )) such that (end(V k ), end(V )) is an edge in G. There is one V k for every state s such that (s, end(V )) is an edge in G.

Although the expand functions operate on paths, it is sometimes convenient to talk about states being expanded. We say state u has been expanded if one of the expand functions has been applied to a path U for which end(U) = u. Finally, we say that a state pair (u, v) has been expanded if either u has been expanded in the forward direction or v has been expanded in the backward direction (we do not require both).

A problem instance is solvable if there is a forward path in G from start to goal. IAD is the set of solvable problem instances in which hF is forward admissible and hB is backward admissible. ICON is the subset of IAD in which hF is forward consistent and hB is backward consistent. A search algorithm is admissible iff it is guaranteed to return an optimal solution for any problem instance in IAD.

We only consider DXBB [Eckerle et al., 2017] algorithms. These are deterministic algorithms that proceed by expanding states that have previously been generated and have only black-box access to the expand, heuristic, and cost functions.

4 Sufficient Conditions for Node Expansion

This paper builds on recent theoretical work [Eckerle et al., 2017] defining sufficient conditions for state expansion for bidirectional DXBB search algorithms. While A* with a consistent heuristic necessarily expands all states with fF (s) < C ∗ , in bidirectional search there is no single state that is necessarily expanded, as the search can proceed forward or backwards, avoiding the need to expand any single state. However, given a path pair (U, V ), that meets the following conditions, one of the paths' end-states must necessarily be expanded.

Theorem 1. [Eckerle et al., 2017] Let I = (G, hF , hB) ∈ ICON have an optimal solution cost of C ∗ . If U is an optimal forward path and V is an optimal backward path such that U0 = start, V0 = goal, and:

then, in solving problem instance I, any admissible DXBB bidirectional front-to-end search algorithm must expand the state pair (end(U), end(V )).

The c(U)+c(V ) condition was not used by BS*, is degenerate in A*, but is used by MM. When the heuristic is weak, this is an important condition for early termination.

We now use these conditions for state-pair expansion to define a bipartite graph.

When hF is forward admissible and hB is backward admissible, lb(U, V ) is a lower bound on the cost of a solution path of the form UZV -1 , where Z is a forward path from end(U) to end(V ).

Definition 2. The Must-Expand Graph GMX(I) of problem instance I = (G, hF , hB) ∈ ICON is an undirected, unweighted bipartite graph defined as follows. For each state u ∈ G, there are two vertices in GMX(I), the left vertex uF and right vertex uB. For each pair of states u, v ∈ G, there is an edge in GMX(I) between uF and vB if and only if there exist an optimal forward path U with U0 = start and end(U) = u and an optimal backward path V with V0 = goal and end(V ) = v such that lb(U, V ) < C ∗ . Thus, there is an edge in GMX(I) between uF and vB if and only if Theorem 1 requires the state pair (u, v) to be expanded.

We illustrate this in Figures 1 and 2. Figure 1 shows a problem instance I = (G, hF , hB) ∈ ICON. In this example a is the start state, f is the goal, and C ∗ = 3. Figure 2 shows GMX(I), where d refers to the cost of the shortest path to each state and f refers to the f-cost of that path. By construction, the edges in GMX(I) exactly correspond to the state pairs that must be expanded according to Theorem 1, and therefore any vertex cover for GMX(I) will, by definition, represent a set of expansions that covers all the required state pairs. For example, one possible vertex cover includes exactly the vertices in the left side with at least one edge{aF , cF , dF , eF }. This represents expanding all the required state pairs in the forward direction. This requires four expansions and is not optimal because the required state pairs can be covered with just three expansions: a and c in the forward direction and f in the backward direction. This corresponds to a minimum vertex cover of GMX (I) : {aF , cF , fB}.

Theorem 2. Let I ∈ ICON. Let A be an admissible DXBB bidirectional front-to-end search algorithm, and SF (resp. SB) be the set of states expanded by A on input I in the forward (resp. backward) direction. Together, SF and SB correspond to a vertex cover for GMX(I). In particular, |SF |+|SB| is lower-bounded by the size of the smallest vertex cover for GMX (I).

Proof. Let (uF , vB) be an edge in GMX (I). Then Theorem 1 requires the state pair (u, v) to be expanded by A on input I, i.e., A must expand u in the forward direction or v in the backward direction. Thus the set of states expanded by A on input I corresponds to a vertex cover of GMX (I).

We will show below (Theorem 5) that this lower bound cannot be attained by any admissible DXBB bidirectional front-to-end search algorithm. However, we devise an admissible algorithm, NBS, which efficiently finds a near-optimal vertex cover and thus is near-optimal in terms of necessary node expansions.

The claim of near-optimality is only with respect to the state pairs that must be expanded according to Theorem 1, it does not take into account state pairs of the form

(end(U), end(V )) when lb(U, V ) = C ∗ . In principle, NBS could expand many such state pairs while some other algorithm does not. We investigate this further in our experiments.

5 NBS: ANear-Optimal Front-to-End Bidirectional Search Algorithm

While a vertex cover can be computed efficiently on a bipartite graph, in practice, building GMX(I) is more expensive than solving I. Instead, we adapt a greedy algorithm for vertex cover [Papadimitriou and Steiglitz, 1982] to achieve nearoptimal performance. The greedy algorithm selects a pair of states that are not part of the vertex cover subset selected so far and are connected by an edge in the graph. It then adds both states to the vertex cover. We introduce a new algorithm, NBS, which uses the same approach to achieve near-optimal node expansions while finding the shortest path.

The pseudocode for NBS is shown in Algorithms 1 and 2. NBS considers all pairs for which lb is smallest (line 9). Among these pairs, it first chooses the pairs (U, V ) with smallest cost c(U) (line 12) and then, among those, the ones with smallest cost c(V ) (line 15). NBS picks an arbitrary pair (U, V ) from the remaining candidates and expands both U and V (lines 16/17). Breaking ties in this way is necessary to guarantee that NBS never expands a suboptimal path when its heuristics are consistent; other tie-breaking rules can be used.An efficient data structure for implementing this path pair selection is described in Section 7.

The pseudocode for backwards expansion is not shown, as it is analogous to forward expansion. We have proofs that, for all problem instances in IAD, NBS returns C ∗ . These are not included here because of space limitations, and because they are very similar to the corresponding proof for MM.

6 Bounded Suboptimality in State Expansions

Theorem 1 identifies the set of state pairs that must be expanded by any admissible DXBB front-to-end bidirectional algorithm. We refer to these as surely expanded (s.e.) path pairs. The theorem does not stipulate which state in each s.e. pair must be expanded; an algorithm is free to make that choice in any manner. Different choices can lead to vastly

Algorithm 1 NBS

Algorithm 2 NBS: Forward-Expand(U)

1: Move U fromOpenF to ClosedF 2: for eachW ∈ expandF (U) do 3: if ∃Y ∈ OpenB with end(Y ) = end(W) then 4: C = min(C, c(W) + c(Y )) 5: end if 6: if ∃X ∈ OpenF ∪ ClosedF with end(X) = end(W) then 7: if c(X) ≤ c(W) then 8: Continue for loop // discardW 9: else 10: remove X from OpenF /ClosedF 11: end if 12: Add W to OpenF 13: end if 14: end for

different numbers of expansions. Given that VC is the size of a minimum vertex cover for GMX , we have shown above that at least VC expansions are required. In this section we prove that on the subset of consistent problem instances NBS never expands more than 2VC states to cover all the s.e. pairs, and that for every DXBB front-to-end bidirectional algorithm A there exists a problem instance in ICON on which A expands at least 2VC states to cover all the s.e. pairs. That means that the suboptimality of NBS is bounded by a factor of two, and that no competing algorithm can do better in the worst case.

Theorem3. Let I ∈ ICON, let GMX(I) be theMust-Expand Graph, and let VC(I) be the size of the smallest vertex cover of GMX . Then NBS does no more than 2VC(I) state expansions on GMX(I) to cover its s.e. pairs.

Proof. If (u, v) is a s.e. pair then lb(U, V ) < C ∗ for every optimal forward path U from start to u and every optimal backward path from goal to v. NBS will select exactly one such (U, V ) pair for expansion and expand both end(U) = u and end(V ) = v. A minimum vertex cover for I might require only one of them to be expanded, so for each expansion required by a minimum vertex cover, NBS might do two.

Theorems 2 and 3 yield the following result.

Corollary 4. Let I ∈ ICON and let A be any admissible front-to-end DXBB bidirectional algorithm. Then NBS makes no more than twice the number of state expansions on input I than A does in covering I's s.e. pairs.

For any algorithm A, let us use the term worst-case expansion ratio of A to refer to the ratio maxI∈ICON #A(I) #(I) , where #A(I) is the number of states A expands in covering the s.e. pairs in instance I, and #(I) is the smallest number of states any DXBB front-to-end bidirectional search algorithm expands in covering the s.e. pairs in I. By definition, #(I) ≥ V C(I), so we can rephrase Corollary 4 as follows:

NBS's worst-case expansion ratio is at most 2. (1)

We now demonstrate that NBS is optimal in the sense that no admissible DXBB front-to-end bidirectional search algorithm has a worst-case expansion ratio smaller than 2.

Theorem 5. Let A be any admissible DXBB front-to-end bidirectional search algorithm. Then there exists a problem instance I and a DXBB front-to-end bidirectional search algorithm B such that A expands at least twice as many states in solving I as B expands in solving I.

Proof. Consider the two problem instances I1 and I2 in Figure 3. In these instances hF (n) = hB(n) = 0 for all n, s is the start and g is the goal. Assume A is given either one of these instances as input. Since A is DXBB and cannot initially distinguish I1 from I2, it must initially behave the same on both instances. Hence, on both instances, A will initially either expand s in the forward direction, expand g in the backward direction, or expand both s and g.

If A first expands s in the forward direction, consider I = I1. On instance I, the algorithm A has to expand a second state (either g in the backward direction or t in the forward direction) in order to be able to terminate with the optimal solution path (s, g). By comparison, an algorithm B that first expands g in the backward direction will terminate with the optimal solution after just a single state expansion. Here we assume that B terminates when there are no pairs satisfying the sufficient condition for node expansion.

If A first expands g in the backward direction, one can argue completely symmetrically, with I = I2 and B being an algorithm that first expands s in the forward direction.

If A begins by expanding both s and g, as NBS does, then on both these instances it will have expanded two states when only one expansion was required.

7 Efficient Selection of Paths for Expansion

Algorithm 1 assumes that NBS can efficiently compute lbmin and select the best path pair (U, V ) for expansion. In this section we provide a new Open list that can do this efficiently. The data structure works by maintaining a lower bound on lbmin, Clb. NBS initalizes Clb to 0 prior to its first iteration and each time a new path pair is needed, Clb is raised until it reaches lbmin and a new path pair is found.

This data structure is illustrated in Figure 4. The data structure is composed of two priority queues for each direction. The first priority queue is waitingF . It contains paths with fF ≥ Clb sorted from low to high fF . The second priority queue is readyF . It contains paths with fF ≤ Clb sorted from low to high c. Analogous queues are maintained in the backward direction. When paths are added to Open, they are first added to waitingF and waitingB. After processing, paths are removed from the front of readyF and readyB. The current value of Clb is the minimum of the f-costs at the front of waitingF and waitingB and the sum of the c-costs at the front of readyF and readyB.

Pseudocode for the data structure is in Algorithm 3. Where forward or backwards queues are designated with a D, operations must be performed twice, once in each direction. We use the notation readyF .c to indicate the smallest c-cost on ready in the forward direction. At the end of the procedure Algorithm 3 NBS pseudocode for selecting the best pair from Open list. Clb is set to 0 when the search begins.

1: procedure PREPAREBEST 2: while min f in waitingD < Clb do 3: move best node from waitingD to readyD 4: end while 5: while true do 6: if readyD ∪ waitingD empty then return false 7: end if 8: if readyF .c + readyB.c ≤ Clb then return true 9: end if 10: if waitingD.f ≤ Clb then 11: move best node from waitingD to readyD 12: else 13: Clb = min(waitingF .f , waitingB.f , readyF .c+readyB.c) 14: end if 15: end while 16: end procedure

the paths on readyF and readyB with the smallest individual c-costs together form the pair to be expanded.

The procedure works as follows. First, paths with f-cost lower than Clb must immediately be moved to ready (line 2). If readyD and waitingD are jointly empty in either direction, the procedure is halted and the search will terminate (line 6). If the best paths in ready have c(U) + c(V ) ≤ Clb, the procedure completes; these paths will be expanded next (line 8).

If the readyD queue is empty in either direction, any paths with f = Clb can be moved to ready (line 10). While we could, in theory, move all such paths to ready in one step, doing so incrementally allows us to break ties on equal f towards higher c first, which slightly improves performance. If there are no paths with f ≤ Clb in waiting and in ready with c(U) + c(V ) ≤ Clb, then the Clb estimate is too low, and Clb must be increased (line 13).

We illustrate this on an artificial example from Figure 5. 2 To begin, Clb ← 0 and we assume that (A,B,C) are on waitingF and (D, E, F) are on waitingB. First, Clb is set to 9 (line 13). Then, A and D can be added to ready because they have lowest f-cost, and Clb = 9. However, c(A) + c(D) = 16 > Clb = 9, so we cannot expand A and D. Instead, we increase Clb to 12 and then add B and E to ready. Now, because c(B) + c(E) = 12 ≤ Clb we can expand B and E.

2 This example also illustrates why we cannot just sort by minimum fF or c when performing expansions.

We can prove that the amortized runtime over a sequence of basic operations of our data structure (including insertion and removal operations) is O(log(n)), where n is the size of waiting ∪ ready.

8 Experimental Results

There are two primary purposes of the experimental results. First, we want to validate that our implementation matches the theoretical claims about NBS. Second, we want to compare the overall performance of NBS to existing algorithms. This comparison includes total node expansions, necessary expansions, and time. We compare A*, BS* 3 , MMe (a variant of MM) [Sharon et al., 2016], NBS, and MM0 (bidirectional brute-force search). We also looked at IDA*, but it was not competitive in most domains due to cycles.

In Table 1 we present results on problems from four different domains, including grid-based pathfinding problems [Sturtevant, 2012] ('brc' maps from Dragon Age: Origins (DAO)), random 4-peg Tower of Hanoi (TOH) problems, random pancake puzzles, and the standard 15 puzzle instances [Korf, 1985]. The canonical goal state is used for all puzzle problems. 4 On each of these domains we use standard heuristics of different strength. The octile, GAP [Helmert, 2010], and Manhattan Distance heuristics can be easily computed at runtime for any two states. The additive pattern databases used for Towers of Hanoi are computed for each instance. We selected the size of problems to ensure that as many algorithms as possible could solve them in RAM.

3 BS* is not an admissible algorithm (it will not optimally solve problems with an inconsistent heuristic) so the theory in this paper does not fully apply to BS*.

4 On the 15-puzzle and TOH it is more efficient to search backwards because of the lower branching factor, but we search forward to the standard goal states.

In grid maps we varied the difficulty of the problem by changing the map type/topology. In TOH and the pancake puzzle we varied the strength of the heuristic. The GAP-k heuristic is the same as the GAP heuristic, except that gaps involving the first k pancakes are not added to the heuristic. The approximate heuristic strength on a problem is indicated by a + or -. The general trend is that with very strong heuristics, A* has the best performance. As heuristics get weaker, or the problems get harder, the bidirectional approaches improve relative to A*. NBS is never far from the best algorithm, and on some problems, such as TOH, it has significantly better performance than all previous approaches. Runtime and node expansions/second are found in Table 2. NBS is 30% slower than A* on the DAO problems, but competitive on other problems. NBS is slower than BS*, but this is often compensated for by performing fewer node expansions.

In Table 3 we look at the percentage of total nodes on closed compared to total expansions with f = C ∗ by each algorithm in each domain. For the majority of domain and heuristic combinations there are very few expansions with f = C ∗ . The exception is the pancake puzzle with the GAP heuristic. On random instances this heuristic is often perfect, so all states expanded have f = C ∗ . This is why NBS does more than twice the number of expansions as A* on these problems-these expansions are not accounted for in our theoretical analysis. BS* puts nodes on closed that it does not expand, which is why it has a negative percentage.

Figure 6 shows a scatter plot of necessary node expansions on 1171 instances from the brc203d grid map where NBS has slightly worse performance than A* and BS*, but better performance than MM. Each point represents one problem instance, and plots NBS necessary expansions against the minimum of the expansions with f < C ∗ by A*, BS* and MMe. The y = 2x line represents the theoretical maximum expansion ratio (Theorem 4), which is never crossed. NBS often does much better than this theoretical worst case, and on approximately 30 instances is more than 2x better than all alternate algorithms, as they do not have similar 2x expansion bounds.

9 Conclusion

This paper presents the first front-to-end heuristic search algorithm that is near-optimal in necessary node expansions. It thus addresses questions dating back to Pohl's work on the applicability of bidirectional heuristic search [Pohl, 1971]. When the problems are hard or the heuristic is not strong, NBS provides a compelling alternative to A*.

Acknowledgements

Financial support for this research was in part provided by Canada's Natural Sciences and Engineering Research Council (NSERC). This material is based upon work supported by the National Science Foundation under Grant No. 1551406.