Switching from Bidirectional to Unidirectional Search

1 Introduction

Linear-space search algorithms such as DFBB (depth-first branch-and-bound) [Lawler and Wood, 1966] or IDA* (iterative-deepening-A*) [Korf, 1985] can solve very difficult problems because they face no real space limitations. How­ ever, they have large search overheads if there are many dis­ tinct cost values, and if the problem graph is not a tree. So, whenever sufficient memory is available, traditional best-first search may be the best choice, since it expands the fewest nodes among all admissible algorithms using the same cost function [Zhang and Korf, 1993]. Since machines with larger and larger memories are becoming available, this approach can be applicable for many problems in practice (e.g., route planning).

Due to the optimality result of A* over unidirectional com­ petitors in [Dechter and Pearl, 1985], the question may arise what to improve here. However, there is some renewed in­ terest in bidirectional heuristic search, which can both ex­ pand fewer nodes and be faster than A* [Kaindl and Kainz, 1997]. Still, there is some drawback involved with this kind of search: the big effort for proving the optimality of solu­ tions found. The issue is to satisfy the specific termination condition of such searches. We address this issue by propos­ ing a new approach that switches to unidirectional search im­ mediately after the bidirectional search finds the first solution.

Gerhard Kainz Austria Roland Steiner Kranzgasse 4/17 A-1150 Vienna Austria Andreas Auer Penzingerstr. 18/12 A-1140 Vienna Austria Klaus Radda Weinwurmweg 1153 A-1220 Wien Austria This paper is organized as follows . In order to make it self­ contained, we sketch some background material on bidirec­ tional heuristic search. Then we propose our new approach to bidirectional search that switches to unidirectional search once a solution is found. After describing a more special­ purpose improvement, we finally demonstrate both the prac­ tical relevance of some theoretical bounds derived in [Kaindl and Kainz, 1997] and the efficiency of our new search ap­ proach through presenting experimental results.

2 Background

First, let us be precise on what constitutes a bidirectional search. When there is one goal node t explicitly given, such a search proceeds both in the forward direction from the start node s to t and in the backward direction from t to s [Pohl, 1971 ]. Bidirectional search is possible if for a given node n the set of parent nodes Pi can be determined for which there exist operators that lead from Pi to n. Searching back­ wards means generating parent nodes successively from the goal node t (see, e.g., [Russell and Norvig, 1995]). In other words, backward search implements reasoning about the op­ erators in the backward direction.

Bidirectional search also works correctly in cases where the costs of inverse arcs between any two nodes are different: the backward search implements reasoning in the backward direction but takes account of the cost of going in the forward direction. More formally, k1 (m,n) = k2 (n,m) is the cost of an optimal path from m to n. So, k2 (m, n) is the cost of an optimal path from n to m, and is used for notational convenience only. 1 All the bidirectional search algorithms dealt with in this paper work correctly under these conditions and do not require that the operators are reversible or that the cost of a path is the same in either direction.

In this paper we focus on the kind of traditional bidirec­ tional search with "front-to-end" evaluations: the heuristic evaluation functions fd(n) estimate the cost of an optimal path to the appropriate endpoint (i .e., h (n) uses t as the target for the forward search, and h ( n) uses s as the tar­ get for the backward search). So, we do not technically deal here with those algorithms with "front-to-front" evalu­ ations, that perform a wave-shaping strategy: neither with the traditional BHFFA [de Champeaux and Sint, 1977] nor with the more recent approach to non-traditional bidirectional search called perimeter search [Dillenburg and Nelson, 1994; Manzini, 1995]. Also the more recently proposed non­ traditional bidirectional search with "front-to-end" evalua­ tions [Kaindl et at., 1995; Kaindl and Kainz, 1997] is not dealt with in this paper.

1 The notation we use in this paper is summarized in the appendix.

So, it is sufficient here to sketch the essentials of tradi­ tional bidirectional search with "front-to-end" evaluations. We can view such a search essentially as two A *-type searches in opposite directions. 2 These are performed quasi­ simultaneously, i.e., on a sequential machine one node is ex­ panded after another, but the search direction is changed at least from time to time. The decision for searching in the forward or backward direction is made anew for each node expansion, most often according to the cardinality criterion [Pohl, 1971 ]: search in the direction with fewer open nodes.

The typical representatives of traditional bidirectional heuristic search with "front-to-end" evaluations are the two algorithms BHPA [Pohl , 1971] and BS* [Kwa, 1989]. While BHPA explores part of the search space twice, BS* can avoid this due to its major improvements over BHPA. 3 Both BHPA and BS* are admissible if hd is consistent. 4 We assume the availability of a consistent heuristic evaluation function hd in both directions.

Whenever the search frontiers meet at some node n, a so­ lution is found . Its cost is g1 (n) + g2 (n), i.e. , the cost of the path found by the forward search from s to n, plus the cost of the path found by the backward search from n to t. Even when the two parts of such a solution of the forward and the backward search are optimal , however, the concatenated solution path is not necessarily optimal. Therefore, such an algorithm requires a special termination condition for guaran­ teeing optimal solutions. The termination condition of BHPA is as follows :

This condition essentially means that the cost L min of the best (least costly) complete path from s tot found so far is not larger than an estimate computed from the fd-values in both search frontiers . If the heuristic used for these estimates is ad­ missible, this path must already be an optimal solution in order to satisfy thi s termination condition. Implicitly this is also the condition for successful termination of the improved al­ gorithm BS* [Kwa, 1989], which removes all nodes n whose f d-values are 2: Lmin and terminates when 0PEN1 or 0PEN2 is empty.

2The origin is clearly BHPA [Pohl , 1971], which can be intu­ itively viewed to consist of two HPA searches in opposing direc­ tions. For admissible but not consistent heuristic functions, the op­ tion to move nodes back from CLOSED to OPEN is important, if a new better gd-value is found. As long as the heuristic function used is consistent, we can ignore the specific differences for our discus­ sion here.

3 These improvements are the following:

(i) nipping: 'If a node is selected for expansion which is already closed in the opposite search tree, it can just be closed without ex­ pansion.

(ii) pruning: In the same situation, descendants of this node in the opposing OPEN list can be removed.

4 hd is said to be consistent if hd(m):::; hd(n) + kd(m,n) for all nodes m and n. If for any goal node t hd(t) = 0, thi s implies that hd is admissible, i.e., the heuristic function never overestimates the minimal cost.

Since understanding this condition is important for thi s pa­ per, we discuss shortly how it can be achieved (this issue is dealt with more formally in [Kaindl and Kainz, 1997]). If there is a solution path from s to t, BHPA orBS* will termi­ nate successfully (i.e., by finding an optimal path) if and on ly if both the following conditions are satisfied:

1. an optimal solution must have been found, that is, Lmin = C*; and
2. at least in one of the search frontiers d of BHPA or BS* the minimum f -value must have been raised at least to the value of an optimal solution c·' that is, minxE0PENd fd(x) 2: C*.

The minimum !-values of OPENd are at first the values h(s) and h(t), respectively. Since !dis consistent they do not exceed c·. The minimum !-values of OPENd increase only gradually until all the nodes with ! -values < c· of at least one search frontier are expanded (or nipped or pruned by BS*). Since the maximum of those values is used, only one of them must become 2: C*. During the search, Lmin 2: C* always holds, and when an optimal solution is found, Lmin = c·.

3 Switching to Unidirectional Search

Because of the issue of satisfying the termination condi­ tion, we devised an approach of switching from bidirectional search to unidirectional search once a solution is found. De­ pending on the concrete instantiation of this approach, the termination condition may be satisfied earlier, or a different condition of the unidirectional search algorithm used may ap­ ply directly.

The first instantiation actually amounts to a simple modi­ fication of BS *. When the search frontiers meet for the first time, the search direction d with

is selected and kept until the end of the search. According to this condition, it chooses the OPEN set with the higher value, and directs the whole effort of the search after the first meeting towards achieving a minimum !-value of c· in that OPEN set. In case of equality, the cardinality criterion is used as a tie-breaker. We call this algorithm Switch-A*.

The second instantiation is a variant of Switch-A* that uti­ lizes the Max method for dynamically improving heuristic values according to [Kaindl and Kai nz, 1997]. So, we call it Max-Switch-A*. In order to make good use of this method, the differences in one frontier used for improving the heuris­ tic values in the other should be as high as possible. There­ fore, it is useful to have reached the next level of !-values for improving the search in the other direction. That is why Max-Switch-A* does not change its search direction accord­ ing to the cardinality criterion, but whenever the next level of f -values is reached in the current search direction. Also af­ ter the first meeting of the search frontiers, the current search direction is kept until this condition is fulfilled. In effect, this amounts to a delay of switching. Only then, the final decision for the search direction is made by Max-Switch-A*.

The third instantiation can be implemented as follows (we call it Switch-DFBB-Trans):

1. Perform A *-type searches in opposite directions as in BHPA orBS*, i.e. , change the search direction accord­ ing to the cardinality criterion.
2. When the search frontiers meet for the first time, deter­ mine the search direction d according to condition (2).
3. Switch to DFBB-Trans 5 and initialize its upper bound with Lmin·
4. Perform a search with DFBB-Trans in direction d (uti­ lizing the hash table entries from the previous searches and starting from the frontier of OPENd) until its normal termination condition holds.

This instantiation strives to befaster, since DFBB-Trans does not have to maintain a priority queue like A*. In ad­ dition, DFBB-Trans does not expand nodes (in the sense of generating all the children of the expanded node at once), so it can save the generation of certain nodes that A* generates during node expansion.

Other instantiations are easy to construct, since in principle this approach may switch to any unidirectional search. When, for instance, "plain" DFBB or IDA* is used, only linear stor­ age is needed for the remaining search. Still, the information already stored in the hash table of the bidirectional search can be used to improve efficiency (e.g. , as in BAI [Kaindl et al., 1995]).

4 Bidirectional Search for the TSP

We also present here another approach for improving bidirec­ tional search that is more specific for domains where a fixed number of items is to be sequenced. In the TSP (traveling salesman problem) these items are the cities. In such a do­ main, it is possible to save the expansion of nodes through recognizing complementary paths in the search graph. In the following, we explain this idea specifically forthe TSP. While it is possible with some additional book-keeping to apply this approach to the asymmetric TSP [Steiner, 1996], we explain here the simpler case of the symmetric TSP.

5 DFBB-Trans was first mentioned in [Kaindl eta/., 1995]. It simply utilizes the approach of improving heuristic values through a 1ransposi1ion /able [Reinefeld and Marsland, 1994] in DFBB.

The key idea is to perform a unidirectional search (that stores nodes) and to interpret every node both as a partial tour in the forward direction that it represents directly, and con­ currently as a complementary tour in the backward direction. So, in just one explicitly stored search frontier, implicitly two frontiers are contained. The search must be able, of course, to identify those nodes that represent complementary tours­ we call them complementary nodes.

The example in Figure 1 illustrates complementary nodes. Let us assume that some node represents the best partial route found so far between some start city A and some cur­ rently visited city, say B, that goes through certain other cities, e.g., { C, E}. Let us take the set of all these cities, e.g., .{A, B, C, E} and compute its set complement, e.g., { D, F, G}. Then the complementary node is the one that rep­ resents the best partial route found so far between the same start city A and the same currently visited city, in this exam­ ple B, that goes through this complementary set of cities, in this example {D, F, G}.

Figure 2 illustrates an example of a TSP search that uti­ lizes this idea. The graph in the left part of this figure defines the problem, and the graph in the right shows a snapshot of a corresponding search. 6 The important point is that the node ABD is complementary to the node ACD, and so the search can already recognize the meeting of the corresponding par­ tial tours and therefore a complete solution.

Apart from admissibility, the most important theoretical re­ sult about this approach is dominance over A* . That is, all the nodes expanded by either BHPA!fSP or BS*ffSP (that include this approach) must be expanded by A*. The corre­ sponding proofs can be found in [Steiner, 1996],

5 Experimental Results

Our experiments showed promising results in several do­ mains: mazes (like those used in [Kaindl and Kainz, 1997]), route planning (like in [Kwa, 1989]), TSP, and 15-Puzzle. In all these domains, the new "switching" approach gives bet­ ter results than BS* in terms of both generated nodes and running time. These results are statistically significant. In addition, we gained empirical evidence that the conjecture in [Kwa, 1989] that BS* would become generally superior to A* for more difficult problems is invalid. In the follow­ ing, we focus on the domains TSP and 15-Puzzle, which are also very interesting in regard to the theoretical results pre­ sented in [Kaindl and Kainz, 1997]. TSP is a domain where the "naive" approach of implementing BHPA leads to nearly twice of the node expansions compared to A*, the theoreti­ cal upper bound. The IS-Puzzle with the Manhattan distance heuristic, however, is a domain with very few different !­ values, where according to the theory in [Kaindl and Kainz, 1997] comparably many node expansions can be saved by the traditional approach of bidirectional search using "front­ to-end" evaluations. So, our results are consistent with this theory and they illustrate that the bounds derived there are reasonable in practice.

6 In this paper we use the minimum spanning tree of the cities not yet visited as the heuristic function hd.

5.1 Euclidean TSP

First we present here our experimental results on the Eu­ clidean TSP. These experiments did not attempt to achieve the best ever results in this particular domain, but they were intended to compare our new algorithms with the standard heuristic search algorithms. All the compared algorithms use no domain-specific knowledge about the Euclidean TSP other than the minimum spanning tree heuristic. Figure 3 shows the results for 19-city problems. 7 We selected these particu­ lar results for presentation since they are reproducible using any standard PC with 48MBytes of main memory. On aver­ age, A* generated 73,650 nodes in 7.0 seconds for solving one problem instance.

On such problem instances, both BHPA (result is rounded to 200%) and BS* expand close to twice the number of nodes compared to A*. BS* can save only 7% of the node expan­ sions compared to BHPA. In fact, the naive implementations explore the same space twice, and so they treat the TSP as a perfectly A *-symmetric domain as defined in [Kaindl and Kainz, 1997].

The versions BHPAffSP and BS*ffSP that recognize com­ plementary nodes as described above expand half of the nodes compared to the "naive" implementations. So, they are slightly better in terms of node expansions than A* (as they dominate A*), but they are actually slower than A*.

7 We do not include here results from perimeter search, since ac­ cording to our experiments this approach appears not to work satis­ factorily in this domain (like for maze problems as shown in [Kaindl and Kainz, 1997]).

The best results in terms of running time achieves Switch­ DFBB-Trans as presented above. After 8% of its overall node generations, it switches to DFBB-Trans. At this time it has on average found a solution with cost 1.02 x C*, which is used as the initial upper bound by DFBB-Trans. Note, that due to its depth-first search DFBB-Trans cannot make use of com­ plementary nodes and really works unidirectionally. While overall Switch-DFBB-Trans generates more nodes than A* or BS*ffSP, it is faster than both of them due to the fact that DFBB-Trans is faster per node searched.

The only other algorithm competing here is DFBB-Trans itself. However, the initial bound gained through the nearest­ neighbor heuristic is worse than the bound gained through the bidirectional approach running first , and within the time required for finding the better bound by Switch-DFBB-Trans, DFBB-Trans alone cannot achieve such a good bound on its own.

It is intersting to compare this bidirectional approach with unidirectional approaches that first find an approximate so­ lution and continue the search until they find an optimal so­ lution [Gent and Walsh, 1997; Korf, 1995]. For instance, in the number partitioning problem such an algorithm may of­ ten know from the solution itself that it is already optimal. Our approach does not need such a domain-specific property. It gradually raises the minimum !-values of OPENd until the termination condition (l) is satisfied. While this is time con­ suming, our "switch" approach improves the efficiency.

In summary, Switch-DFBB-Trans is better in terms of run­ ning time than all these competitors, which include the stan­ dard search algorithms that have the same knowledge avail­ able. This result is statistically significant. For example, the probability that the improvement of the running time over DFBB-Trans is due to chance fluctuation is 0.66 percent ac­ cording to a test that compares the means of the paired sam­ ples of the absolute running times, and it is even much smaller according to the same test for the data relative to the difficulty of each instance (0.02 percent) as well as according to the sign test (0.06 percent). 8 In comparison with A*, this chance is even smaller than 0.05 percent for all these statistic tests.

8 For more details on the statistic tests used we refer the interested reader to [Kaindl and Smetana, 1994].

5.2 15-Puzzle

Now let us have a look on specific experimental results for finding optimal solutions to a set of (sliding-tile) 15-Puzzle problems. 9 We compare algorithms that achieve the best published results in this domain with IDA* and BS* as well as Switch-A* and Max-Switch-A* (as presented above) . All the compared algorithms use no domain-specific knowl­ edge about the puzzle other than the Manhattan distance heuristic. 10 The main storage available on a Convex C3220 was up to 256 Mbytes.

Within this given amount of storage, A*, BHPA, BS* and Max-BAI-Trans [Kaindl and Kainz, 1997] can store a max­ imum of 5 million nodes in our implementations. BIDA * [Manzini, 1995] requires more storage per node, so it can store a maximum of I million perimeter nodes within 256 Mbytes. 11

While Max-BAI-Trans and BIDA* can find optimal so­ lutions to all of the given instances, the traditional best­ first searches cannot (with this amount of storage and the Manhattan distance as the only knowledge source): A* solves 34 and BS* 59 from the given set of 100 problem instances (for BHPA we did not gather the complete data since they would be clearly worse than those of BS*).

Switch-A* solves 63 instances of this set under these con­ straints, so in this regard it is better than both A* and BS*. On the set of 34 problem instances solvable by A*, Switch-A* just expands 42.3% of the nodes expanded by A* and needs 55 .5% of its time. Max-Switch-A* solves 79 problems of the set of I 00 instances.

On the set of 56 problem instances solvable by both BS* and Switch-A*, the latter expands 93.1% of the nodes ex­ panded by BS* and needs 93.6% of its time. 12 On average, Switch-A* finds the first solution after 7% of its overall time, and the average cost of these solutions is 1.06 x C*. For the overall data see Table I . This table shows that on this set of instances, our new algorithm Switch-A* is as good as the best published approaches so far [Kaindl and Kainz, 1997; Manzini, 1995]. 13 While the precise mean data might even suggest a slight improvement, statistic tests tell us that there is a high chance fluctuation. So, we cannot reject the null hypothesis that Switch-A* and Max-BAI-Trans are equally good. In fact, the difference amounts to less than 1% (in ef­ fect, less than I second) per problem instance on average.

9 We used the set of 100 instances from [Korf, 1985].

10 With much improved heuristic functions, much more efficient searches result [Culberson and Schaeffer, 1996] and even solving 24-Puzzle instances has become feasible [Korf and Taylor, 1996].

11 Since a given machine has a fixed storage size, it would not be fair to compare algorithms with the same number of nodes when these require different amounts of storage. However, BIDA * has an optimum in running time for a smaller perimeter size that does not even require that available amount of storage [Kaindl and Kainz, 1997] .

12 A* cannot be compared on this set. Just to give an idea of the overall difficulty of this problem set, note that BS* generates some 2.25 million nodes on average, which needs slightly less than 90 seconds on a Convex C3220.

13 BIDA *'s result here is worse than the data reported in [Manzini, 1995]. This is primarily due to the use of a different machine and a different implementation that is based on the very efficient code of IDA* for the puzzle provided to us by Korf that we are using. In such an implementation the overhead especially of wave shaping shows up more clearly even when using the runtime optimizations described in [Manzini, 1995]. While we had no access to the im-

Max-Switch-A*, however, improves the performance on these problems. It expands only 62.1% of the nodes expanded by BS*, but due to the overhead of applying the Max tech­ nique, it needs 78.8% of its time. Still, this result is better than the results of the previously best methods BIDA* and Max-BAI-Trans both in terms of the mean and the median values. It is statistically significant according to the sign test and a test that compares the means of the paired samples of the absolute running times.

Still, the question may arise, whether the application of the Max technique directly in BS* could not be better. This ap­ plication was also studied in [Kainz, 1996] and achieved im­ provements, but for a good utilization of this technique the search direction should stay constant at least for a while. Fi­ nally, it turned out that the switching approach presented in this paper is the limit of what can be achieved by the applica­ tion of Max in the context of BS*.

The major issue with this approach is that it was not able to solve all the problem instances. However, machines with larger and larger memories are becoming available now. In contrast to several approaches to memory-bounded search like MA * [Chakrabarti et al., 1989], MREC [Sen and Bagchi, 1989], SMA* [Russell, 1992] and ITS [Ghosh et al., 1994], our approach showed clear improvements in running time over IDA*.

Moreover, using much improved heuristic functions like those developed by [Culberson and Schaeffer, 1996; Korf and Taylor, 1996] would make it possible to run Switch-A* and Max-Switch-A* even with smaller available memory. We conjecture that also Switch-A* would be better under these conditions than both BIDA * and Max-BAI-Trans, since these approaches perform dynamic improvements of the heuristic during their search, which may not be as effective for such improved heuristics as it is for the Manhattan distance heuris­ tic.

plementation by Manzini, in E-mail communication with him we were given some hints about it, and there was agreement about the overall effect on the relative running times due to the different im­ plementations of IDA*. The data for BID A* and Max-BAI-Trans in this table are also not exactly those reported in [Kaindl and Kainz, 1997], since not all of the problem instances are included.

6 Conclusion

The major problem of traditional bidirectional search with "front-to-end" evaluations as exemplified by BHPA and BS* is the cost of satisfying the termination condition. So, we addressed this problem and developed a new approach to im­ proving this kind of search: switching to unidirectional search after the search frontiers meet for the first time (with the first solution found). This new approach shows improvements over previous bidirectional search approaches and partly also over the corresponding unidirectional search approaches in different domains.

Appendix. Glossary of Notation