Optimally Efficient Bidirectional Search

1 Introduction and Background

Given a graph G, the shortest-path problem is to find the leastcost path from state start to state goal in G. The traditional approach is to use the A* algorithm [Hart et al., 1968]. A* is a unidirectional best-first search that priorities nodes according to f(n) = g(n)+h(n) where g(n) is the shortest known path from start to the node n and h(n) is an admissible heuristic (lower bound) on the cost of the path from n to the goal.

Bidirectional heuristic search algorithms (denoted henceforth by Bi-HS) interleave two separate searches, a search forward from s and a search backward from g. these algorithms usually halt once both frontiers include the same node. Bi-HS algorithms differ on which node they expand next and when exactly they stop such that optimality is guaranteed (see a survey in [Holte et al., 2017]).

Recent research defined conditions on the node expansions required by Bi-HS algorithms to guarantee solutions optimality [Eckerle et al., 2017]. Following work reformulated these conditions as a must-expand graph (GMX), showing that the Minimum Vertex Cover (MVC) of GMX corresponds to the minimal number of expansions required to prove optimality [Chen et al., 2017]. In this paper we study the GMX structure, characterize properties of the MVC and develop algorithms that expand exactly the MVC.

∗This paper is a is a summary of two papers: "The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search" [Shaham et al. 2017] and "Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics" [Shaham et al. 2018]. Both paper were presented at the Symposium of Combinatorial Search (SoCS). These papers are are the basis for the M.Sc thesis of the first author.

Let d(x, y) denote the shortest distance between x and y and let d(start, goal) = C ∗ .

We use fF , gF and hF to indicate f-, g-, and h-values in the forward direction and similarly, fB, gB and hB to indicate f-, g-, and h-values in the backward direction. The forward 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. The backward 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. Front-to-end algorithms use these two heuristic functions coupled with the g-value of the corresponding node (v or u). Front-to-front bidirectional search algorithms use heuristics between pairs of states on opposite frontiers coupled with their respective g-values.

Let IAD be the set of solvable problem instances in which the heuristics are admissible, and let ICON be the subset of problems in IAD where the heuristics are consistent. Admissible algorithms are algorithms that must be able to optimally solve all instances from IAD. Admissible algorithms have no further knowledge about the problem or the heuristic (besides the fact that it is admissible), and they do not exploit such knowledge even if it is available. We deal with three different settings distinguished by the assumptions on the algorithms and the problem instances.

Case 1: Recent papers on bidirectional search (e.g., [Eckerle et al., 2017]), followed the classic analysis of A∗ [Dechter and Pearl, 1985] and analyzed admissible algorithms running on problem instances with consistent heuristics. That is, the behavior of admissible algorithms was only studied when running on instances from ICON. We denote these assumptions as the base case and label it by IAD/ICON along the following notation: What can be assumed by the algorithm on the problem instances / The instances the algorithm is executed on.

Case 2: In many domains (e.g., with unit-cost edges) the cost of the smallest edge (ϵ) is known. We label this case, where the algorithm knows ϵ and is allowed to exploit this knowledge as IADϵ/ICONϵ and show the adaptations that are needed to generalize existing theory and algorithms from IAD/ICON to IADϵ/ICONϵ. Nevertheless, both of these cases have an inherent discrepancy - the assumptions on the knowledge available to the algorithm and the assumptions on the problem instances it will run on are different. This is the main motivation for the next case.

Case 3: The algorithm is allowed to exploit the fact that both the forward and backward heuristics (hF and hB) are consistent. We label this case ICON/ICON. In this case algorithms can assume that they are running on instances from ICON and we show that they can exploit a front-to-front heuristic that is induced by the consistency of the underlying heuristics.

1.1 Necessary Expansions in Bidirectional Search

Given an admissible heuristic, any admissible unidirectional algorithm must expand all states with f(n) < C ∗ in order to prove a solution is optimal [Dechter and Pearl, 1985].

A new line of research was initiated by Eckerle et al. [2017] who generalized this theory to Bi-HS showing that necessary expansions are defined on pairs of states u and v in the forward and backward frontiers, respectively. Here we need to reason whether there can be an optimal path that goes from start to u to v to the goal, as depicted in Figure 1. Three conditions are required to reason about potential paths between u and v:

1. fF (u) < C ∗
2. fB(v) < C ∗
3. gF (u) + gB(v) < C ∗

If all conditions are met, the algorithm must explore to see if there is a shorter path between u and v. In bidirectional search, a pair of states (u, v) is called a must-expand pair if all three conditions are met. Unlike unidirectional search, in a must-expand pair only one of u or v must be expanded, not both. An algorithm that does not expand either u or v cannot be admissible because it may not find an optimal solution.

1.2 The Must-Expand Graph (GMX)

The unique property of the must-expand condition is that it contains an or between the nodes, also a feature of the vertex cover problem. Thus, the conditions for necessary expansions can be represented as the problem of finding a vertex cover on the must-expand graph denoted by GMX [Chen et al., 2017].

Definition 1. TheMust-ExpandGraphGMX on a problem instance is an undirected, unweighed bipartite graph. For each state u ∈ G, there are two vertices in GMX, the left vertex uF and the right vertex uB. For each pair of states u, v ∈ G, there is an edge in GMX between uF and vB if and only if (u, v) is a must-expand pair.

It follows that the minimum number of node expansions required to solve a problem using Bi-HS is determined by the size of the minimum vertex cover of GMX (denoted hereafter as MVC). Naturally, the exact set of vertices in GMX depends on the heuristic used in the problem instance. Therefore, MVC is heuristic dependent as well.

Figure 2(b) shows the GMX graph for the problem instance in Figure 2(a) where the numbers inside nodes are the hvalues. The left vertices are sorted by increasing gF -costs, while the right vertices are sorted by decreasing gB-cost. In this ordering, each horizontal pair of states u and v has gF (u) + gB(v) = C ∗ . C ∗ = 3 in Figure 2.

2 MVC of GMX in the IAD/ICON Case

The MVC of GMX in the IAD/ICON case (Case 1) has the following properties [Shaham et al., 2017]. First, the MVC is contiguous in each direction. That is, if a node n with gF (n) = k is in the MVC, then all nodes with gF (n) ≤ k in GMX must also be in the MVC, and similarly for gB. Second, there exist thresholds t∗F , t∗B such that (1) t∗F + t∗B = C ∗ and (2) a forward node u from GMX is included in the MVC iff gF (u) < t∗F , and a backward node v from GMX is included in the MVC iff gB(v) < t∗B = C ∗ - t∗F . In Section 3 we will generalize this to Case 2 (IADϵ/ICONϵ).

To demonstrate this, consider all pairs of values of tF and tB where tF +tB = C ∗ . There is a family of contiguous vertex covers (VCs) for all such pairs (tF , tB), where all nodes with gF < tF in GMX are included in the forward direction of this VC, and all nodes with gB < tB are included in the backward direction of this VC. One such (tF , tB) partition is the MVC and is denoted by (t∗F , t∗B ). The number of nodes of the (tF , tB) VC partitions is determined by summing up the nodes with gF < tF and with gB < tB. In Figure 2, nodes that correspond to each (tF , tB) pair are aligned horizontally. Nodes that are included in MVC have a double outline - these are nodes with gF < t∗F = 2 and with gB < t∗B = 1.

2.1 Fractional MM

MM is a Bi-HS algorithm that is guaranteed to meet in the middle [Holte et al., 2017]. That is, MM will never expand a state whose g-value exceeds C ∗ /2. Fractional MM (fMM) generalizes MM and can meet at any fraction of the optimal solution cost [Shaham et al., 2017]. fMM(p) uses the following priority functions on nodes in the open lists, where 0 < p < 1:

fMM(p) expands a state with minimum priority in either direction. fMM(p)'s forward and backward searches meet at (p·C ∗ , (1-p)·C ∗ ) by similar reasoning for why MM meets in the middle. That is, fMM(p) will never forward expand a state whose gF -value exceeds p · C ∗ and never backward expand a state whose gB-value exceeds (1 - p) · C ∗ . This attribute is called restrained with respect to p. As a result, a restrained algorithm will always return the optimal solution because it can only meet at the meeting point along the optimal path. MM is a special case of fMM(p) for p = 1/2. Forward A∗ and reverse A∗ (searching from goal to start) are also special cases corresponding to p = 1 and p = 0 respectively.

For every problem instance, there exists a fraction 0 ≤ p∗ ≤ 1 such that fMM(p∗ ) is optimally efficient and will expand the minimal number of necessary nodes - those in the MVC [Shaham et al., 2017]. In practice, however, the exact value for p∗ is not known a priori, as it depends on C ∗ and GMX. Both are not known in advance before the execution of the algorithm. But, given C ∗ and GMX it is possible to find p∗ in time linear in the number of distinct g-values. Finding p∗ and then running fMM(p∗ ) can serve for research purposes as an oracle-any algorithm can now be compared to the theoretical optimum.

The definition of fMM through fractions resulted from the attempt to generalize existing algorithms such as MM and A∗ . Since the MVC theory uses thresholds it is more natural to use an algorithm that uses such thresholds.

2.2 Meet at the Threshold

Given a threshold t, the meet at the threshold algorithm (MT) [Shaham et al., 2018] is restrained with respect to t, or equivalently, MT meets at (t,C ∗ - t). That is, MT will never forward expand a state whose gF -value exceeds t and never backward expand a state whose gB-value exceeds C ∗ - t. MT(t) uses the following priority functions:

The same line of proof for MM and fMM fits here as well. The fact that MT is restrained ensures an optimal solution.

For t = 0, MT(t) is identical to backward A∗ . Similarly, for t ≥ C ∗ , MT(t) is identical to forward A∗ . It is easy to see that MT(t) will expand the same set of nodes in GMX (not necessarily in the same order) as fMM(p) when t = p · C ∗ . For example, MM is identical to MT(t) for t = C ∗ /2. Therefore, for any value of t, MT will return the optimal solution. Moreover, when choosing the optimal value for t (t∗ = p∗ · C ∗ ), MT(t) is also optimally efficient, i.e., it expands exactly the nodes in the MVC. In the next sections we study GMX and its MVC, and generalize MT (and fMM, where possible) to the cases where the algorithm can assume more knowledge in the graph and on h.

2.3 Other Related Bi-HS Algorithms

Both fMM and MT(t) need a parameter as input to determine the meeting point. Another related parametric algorithm is GBFHS [Barley et al., 2018], which iteratively increases the depth of the search. It is parametric in a pre-defined split function that determines how deep to search on each side at each iteration. GBFHS with an optimal split function also converges to an MVC of GMX. However, here too, the optimal split function is not known a priori because it depends on the structure of GMX and on C ∗ ; both are not known in advance.

NBS [Chen et al., 2017] is a Bi-HS algorithm that aims to find some VC of GMX by picking a must-expand pair and expanding both its vertices. Similarly, DVCBS [Shperberg et al., 2019b] is a Bi-HS algorithm that grows GMX on the fly and always expands the MVC of the growing GMX. NBS has a guarantee that the size of its VC is at most twice the size of the MVC. DVCBS does not have that guarantee but was reported to have a better average case performance.

A possible anomaly (first described by Holte et al. [2017]) may arise with many of these algorithms (e.g., fMM) - when using a stronger heuristic the search effort may increase. By contrast, GBFHS was shown to be inherently well-behaved (=anomaly-free). Later, Shperberg et al. [2019a] provided an important study of this anomaly and introduced improved heuristic propagation method that causes many of the algorithms (including the MM family) to be well behaved too.

3 Case 2: Knowing ϵ (IADϵ/ICONϵ)

In many cases, the problem instance is coupled with a lower bound (ϵ) on the edge costs. For example, in unit edge-cost domains ϵ = 1. In other domains, one might iterate over all actions costs and take their minimum. This bound provides an admissible front-to-front heuristic of ϵ between any two distinct nodes. We now study the case where algorithms are allowed to assume the existence of ϵ but as done in previous work can still only assume an admissible heuristic. Similarly, we assume that they are evaluated in instances where the heuristic is consistent. In our notation, this case is labeled by IADϵ/ICONϵ. For this case we adapt the conditions for must-expand pairs in domains with front-to-front heuristics as defined by Eckerle et al. [2017] with ϵ as the front-to-front heuristic. In such cases two nodes u, v are a must-expand pair if the following conditions are met:

Condition 3 is more informative than the front-to-end version of the IAD/ICON case (Case 1) due to the addition of ϵ. In Figure 1, ϵ is a lower bound on the cost of the path from u to v. Therefore, some edges that exist in the old GMX no longer exist in the new GMX. Figure 2(c) shows such a GMX for the instance in Figure 2(a). In this instance,

ϵ = 1 and thus (B, A) is no longer a must-expand pair, since gF (B) + gB(A) + ϵ = 1 + 1 + 1 = C ∗ .

Similar to the IAD/ICON case we show that there exist thresholds t∗F , t∗B such that a forward node u from GMX is included in MVC iff gF (u) < t∗F , and a backwards node v from GMX is included in MVC iff gB(v) < t∗B . The main difference being that this time t∗F + t∗B + ϵ = C ∗ .

We now define the following four terms:

Based on these terms we define the following thresholds:

Note that t∗F +t∗B +ϵ = C ∗ . Furthermore, these thresholds indeed satisfy the following theorem.

Theorem 1. For a forward node u, u ∈ MVC iff gF (u) < t∗F . For a backward node v, v ∈ MVC iff gB(v) < t∗B .

For Figure 2(c) we have t∗F = 1 and t∗B = 1 (as opposed to the IAD/ICON case which had t∗F = 2).

Theorem 1 implies a simple algorithm for finding MVC given that GMX and C ∗ are both known. We iterate over all possible thresholds that satisfy tF + tB + ϵ = C ∗ and sum up the costs of the forward nodes u ∈ GMX for which gF (u) < tF as well as the costs of the backward nodes v ∈ GMX for which gB(v) < tB. This algorithm runs with complexity linear in the number of distinct g-values of states in GMX. It is similar to the Calc-VC() algorithm provided by Shaham et al. [2017].

3.1 Meet at the Threshold ϵ (MTϵ)

The priority function of MT can easily be adapted to create a new algorithm MTϵ:

Similar to MT(t) in the IAD/ICON case, for any given problem instance I in ICONϵ there exists t∗F such that MTϵ(t) is optimally efficient-it expands the minimal number of nodes in GMX of I. The proof for this is nearly identical to the respective proof on fMM.

4 Case 3: Consistency ICON/ICON

As explained above, the analysis of Bi-HS by [Eckerle et al., 2017] and subsequent papers [Chen et al., 2017; Shaham et al., 2017] assumed admissible algorithms. However, they all analyzed the case where such algorithms are executed on instances from ICON. We next investigate the case where the algorithms know that the heuristics are consistent (i.e., they know that the instances are from ICON) and they are allowed to exploit that knowledge.

Given consistent heuristics, |hF (u) - hF (v)| is a lower bound on the distance between u and v, so |hF (u) - hF (v)| can be used as a front-to-front heuristic between u and v. Similarly, |hB(u)-hB(v)| can be used as a heuristic as well. This was called the Add method by Kaindl and Kainz [1997].

Definition 3. (Front-to-front heuristic) For each pair of nodes (a, b) define the following admissible heuristic:

This heuristic results from the combination of assuming both forward and backward consistency (hence hC).

4.1 Necessary Node Expansions

Using the conditions for must-expand pairs [Eckerle et al., 2017] in problems with hC as a front-to-front heuristic results in the following claim: two nodes u, v are a must-expand pair if the following conditions are met:

1. fF (u) < C ∗
2. fB(v) < C ∗
3. gF (u) + gB(v) +hC(u, v) < C ∗

Any pair of nodes u, v that satisfy these conditions is a must-expand pair and induces an edge in GMX between u and v. Condition 3 is more informative than the front-to-end version due to the addition of hC. Therefore, some edges that exist in the old GMX no longer exist in the newGMX.

4.2 Equivalence Classes

In the IAD/ICON case hC(u, v) did not exist. To imitate this in the ICON/ICON case, we partition GMX into equivalence classes, such that any given pair of nodes in each class (u, v) has hC(u, v) = 0.

Definition 4. (heuristic equivalence) Two nodes u, v are heuristically equivalent (or h-equivalent) iff hC(u, v) = 0.

Directly from the definition, two nodes u, v are hequivalent (belong to the same h-equivalence class) iff hF (u) = hF (v) and hB(u) = hB(v).

Lemma 2. (Restrained with respect to t∗FQ) For every hequivalence class Q there exist thresholds t∗FQ +t∗BQ = C ∗ such that MVC ∩ Q contains exactly the forward nodes in Q for which gF < t∗FQ. and exactly all backward nodes for which gB < t∗BQ.

Another way of looking at this would be to describe t∗FQ as a function of the h-values of Q:

Corollary 3. There exists a function b : R+ × R+ → R+ such that a forward node u is in MVC iff gF (u) ≤ b(hF (u), hB(u)) and a backward node v is in MVC iff gB(u) ≤ C ∗ - b(hF (u), hB(u)).

Below we use b(u) as shorthand for b(hF (u), hB(u)). We can now adapt MT to work in the ICON/ICON case. We define the algorithm MTCON(b) with the following priorities:

4.3 Attributes of b

As discussed above, given any threshold tF ∈ R+, MT and MTϵ (and similarly, fMM and fMMϵ) will always return an optimal path, although they might do more work than the minimal number of necessary expansions (as achieved by t∗F ). MTCON, however, is not guaranteed to return an optimal path for any b : R+ × R+ → R+.

Fortunately this issue can be solved by constraining b to be a member of the following set of functions B:

This is a stronger version of the global 1-Lipschitz attribute on the continuity of functions. We prove two theorems:

(1:) Given a function b ∈ B, MTCON(b) will return an optimal path on any problem instance in ICON .

(2:) Given a problem instance in ICON there exists b∗ ∈ B such that MTCON(b) will expand the minimal number of necessary expansions on that instance.

From these theorems we can deduce that MTCON is optimally efficient in the ICON/ICON case, provided that only functions b ∈ B are allowed as the argument. A detailed analysis and related proofs are provided in [Shaham et al., 2018].

5 Summary and Conclusions

We have shown the nature of MVC for GMX for cases with different assumptions on the knowledge of the algorithm about the heuristics used and on the nature of the underlying graph. This enriches the theory on GMX to more cases. We have also developed MT, which is equivalent to fMM but is simpler for our purposes.

Table 1 summarizes our findings. Each column represents a different case. The first row presents the structure of MVC. The second row presents the optimally efficient algorithm. The third row gives the number of clusters of indistinguishable nodes in GMX, i.e., clusters that are either fully contained within an MVC or not at all. The complexity row gives the complexity of the best-known algorithm to calculate MVC given that GMX and C ∗ are known. While an algorithm for the IAD/ICON case and the IADϵ/ICONϵ case were provided, for the ICON/ICON case one should resort to the known algorithm for finding a MVC in a bipartite graph [Papadimitriou and Steiglitz, 1982].

Future work can further expand this theory to more cases such as the case where we add ϵ to the ICON/ICON case. In addition, an important line will be to develop such a theory to the case where we have a full front-to-front heuristic.

Acknowledgments

The work was supported by Israel Science Foundation (ISF) grant #844/17, by BSF grant #2017692, by NSF grant #1815660 and by the HUJI Cyber Security Research Center.