Bidirectional Best-First Search with Bounded Error: Summary of Results

1 Introduction and Background

Much research in heuristic search has been devoted to al­ gorithms finding optimal solutions. In the unidirectional case A· [4] and its derivatives received much attention. Especially related to NP-complete problems, an impor­ tant approach in relaxing the search for optimality is to provide a bound for the worst case quality of a solution compared to an optimal one [5]. A search algorithm is said to be €-admissible if it guarantees that the costs of its solutions are bounded by (1 +€)C· [14, 13]. An early example is dynamic weighting in the form used in [18]. It uses an upper bound N on the depth of the deep­ est node to be evaluated, which has to be given as a parameter. 1 With N-+ oo, asymptotically the heuristic evaluation function with constant weighting of [15] arises (! = g + wh) . 2 Such an evaluation function is used by HPA [16] . 3 A more recent approach to dynamic weighting [7] compensates for the error made by the heuristic component using learnt weights, and it is e:-admissible without the need for a given upper bound like N. The e:-admissible algorithm A: [14] is designed to allow for in­ corporating an additional heuristic to estimate the effort for finishing a search, which is used as FOCAL-heuristic. All these algorithms perform unidirectional search, and for e: > 0 they are typically more efficient than A · .

1 In fact, besides using an admissible heuristic component h the algorithm must have the possibility to reopen nodes, i.e., to move nodes back from CLOSED to OPEN whenever a new better path is found to them.

2 For constant w, this is equivalent to f = (1- w')g + w'h with w' = 1 ~.., .

3 For our comparisons, we use a slight variant of HPA, which includes the option to move nodes back from CLOSED

BH PA 4 [15, 17] was the first bidirectional algorithm using a heuristic evaluation function for finding optimal solutions. While BS* [10] improved BHPA technically, its performance was only nearly as good as the unidi­ rectional A · . There was consensus that the main reason for the superiority of unidirectional search is that the bidirectional heuristic search is afflicted by the problem of search wavefronts missing each other ( cf. the missile metaphor in [15]) .

Wave-shaping techniques like those used in BHFFA [3], BHFFA2 [2] and d-node retargeting [19] showed that bidirectional heuristic search can be rather efficient, es­ pecially in terms of the number of expanded nodes. Davis [1] presented a generalized algorithm (contain­ ing BHPA and BHFFA2) and analyzed it theoretically. However, these algorithms are either excessively compu­ tationally demanding, or they have no restriction on the solution quality.

Considering the missile metaphor of Pohl, the use of e:-admissible approaches in bidirectional search should be dangerous without wave-shaping, since the chance of search wavefronts missing each other could be even increased. However, we found that in bidirectional searches the first meeting of the fronts typically occurred early, compared to the effort for finally satisfying the ter­ mination condition.

Fig. 1 illustrates this phenomenon. 5 These data are normalized in the sense that every data point represents the ratio of the number of nodes expanded by the cor­ responding algorithm to that expanded by A · . In the average, the fronts meet rather early even without using wave-shaping techniques, requiring only slightly more than half the effort of complete A* on the 8-Puzzle for e: = 0. On the much more difficult 15-Puzzle, the fronts meet already when about 3 orders of magnitude fewer nodes are generated than by complete IDA* [9] searches (data for A* are unavailable here).

Especially when aiming for optimal solutions, how­ ever, much effort has to be spent for subsequently im­ proving the solution quality. (In the average, this is achieved with less effort than that of a complete A* search on the 8-Puzzle.) Finally, for proving that there is indeed no better solution possible, many more nodes have to be expanded. Therefore, we were interested in in­ vestigating e:-admissible bidirectional search and in com­ paring its efficiency to the corresponding unidirectional case.

to OPEN, if a new better g-value is found. Moreover, we include a check whether OPEN has become empty. Since this is like A* (4], we call this variant HPA* .

4 The earlier version named VGHA in (15] did not move nodes back from CLOSED to OPEN. Hence, it needed a con­ si8tent heuristic function for being admissible.

5 For & = 0, IBS: - one of our new algorithms as intro­ duced below - is identical to BS*.

2 Improved Bidirectional Search

In the following, we describe several e:-admissible bidirec­ tional search algorithms which do not use wave-shaping techniques. We relate them to the earlier known al­ gorithms in pointing out the differences. The origin is clearly BHPA (15, 17], which can be intuitively viewed to consist of two H PA searches in opposing directions. The termination condition compares the length of the best path found so far to an optimistic estimate computed from the nodes in both search frontiers (see also below). While BHPA only considered meeting points between CLOSED nodes from both sides, Kwa [10] showed that meeting of a newly generated node with any node in the opposing front is sufficient. All the algorithms described below use this improvement. This technical change to­ gether with the incorporation of checks for empty OPEN lists results in a version we call BHPA'.

2.1 Constant weighting (IBHPAe and IBS;)

There are two ways of achieving an e:-admissible variant of BHPA' : .

• BHPAw using an evaluation function of the form f = g+wh, where f can be rewritten as f = g+(1+ e:)h. The original termination condition of BHPA Lmin $ max(min:~:eOPEN, ft (x), min:~:e0PEN 2 h(x)](l) turns out to include (1 +c)h implicitly in BHPAw : Lmin $ max(min:~:e0PEN 1 (gl(x)+(l+&)hl(x)) ,

In fact, Pohl [17] proposed such a change in the evaluation function, when not concerned with find­ ing a shortest path. For this reason, he suggested to simplify the termination condition to just meet­ ing. In contrast, BHPAw using (1) or equivalently (2) as termination condition is e:-admissible when h is admissible.

• BHPAc using f = g+h (like BHPA or a bidirectional admissible version of A*), but using the termination criterion

BHPAc is also €-admissible when h is admissible.

These ideas can be combined in an improved version as follows: IBHPAe uses f = g + (1 + c:)h with e ~ 0 and the termination criterion (3) still guaranteeing £­ admissibility.

Another approach is to modify Bs· [10] similarly, in order to utilize its technical improvements. When a node is selected for expansion which is already closed in the opposite search tree, it can just be closed without ex­ pansion (nipping). Moreover, it is possible in such a situation to remove the descendants of this node in the opposing open set (pruning). Likewise, it is possible to remove all those open nodes (in both directions) whose /-values are greater or equal than Lmin (trimming). Of course, such newly generated nodes are not placed in the open sets at all (screening) . The interested reader will find a pseudo-code formulation of these improvements in Appendix A.

Generally, the provision for reopening nodes must be incorporated, since otherwise £-admissibility cannot be guaranteed. In particular, without this provision there could be no guarantee that the shallowest open node n' on an optimal path always satisfies g(n') = g·(n'). In addition, we have to assume a consistent h because of the Bs· specific actions nipping and pruning. 6

• BS~ using f = g+wh with w ~ 1like HPA (in step 14 of [10, p. 101]). 7
• BS; using f = g + h and the following termination criterion (in step 3 of[10, p. 100]): OPEN1 or OPEN2 is empty or (3).

Again, these modifications can be combined, resulting in an improved algorithm we call IBS;.

2.2 Derivatives of A; ( BA~, e and BSA~, e)

Especially, when there is another heuristic function avail­ able that estimates the effort for completing a search, it can serve as a FOCAL-heuristic in the unidirectional A; [14]. 8 Using A; type of search in both directions and the termination condition .(3), BA; arises, which is £­ admissible.

In contrast to the bidirectional algorithms IBHPAe and IBS; described above, BA; is normally less efficient than the corresponding unidirectional algorithm (A;). We found out that its searches are too greedy, leading to comparably bad solutions at the first meeting and consequently to much effort for subsequent satisfaction of the termination condition guaranteeing £-admissible solutions. Generally, we conjecture that bidirectional searches without wave-shaping tend to meet first with a solution quality which is worse than that achieved by the respective evaluation function in a corresponding unidi­ rectional search.

6 Despite consistency, reopening of nodes is necessary be­ cause of the (I+ e)-factor in the evaluation function.

7 This variant is only of interest for showing the genesis of the improved algorithm below, since by itself it is very inef­ ficient due to lacking an appropriate termination condition.

8 Pearl and Kim propose to use the same heuristic for both purposes if no estimator for the effort of completion is avail­ able. We wanted to compare all the algorithms with the same domain-specific knowledge, and consequently used the available admissible heuristic h also as a FOCAL-heuristic.

Therefore, we found an improvement by adding an­ other parameter 6. BA6 e uses 6 for creating the FOCAL­ lists, and e for termin~tion . Much better results were achieved, for instance, with 6 = ~ and 6 = ~.

Of course, it is also possible to incorporate the ap­ proach of A; into the framework of Bs· . BSA; arises from Bs· by the following changes:

• reopening of closed nodes if a new better path to them has been found,
• the termination condition (in step 3 of [10, p. 101]) analogously to Bs; (see above),
• the selection of a node m for expansion (in step 7 of [10, p. 100]) as usual for A;.

Moreover, another parameter can be used. BSA6,e arises from BSA; analogously to BA~,e from BA;. Since this algorithm is already somewhat different from BS· , we present a complete pseudo-code description in Ap­ pendix A. 9

Fig. 2 provides an overview of all the presented algo­ rithms and their genesis.

3 Theoretical Results

Due to lack of space we cannot present here all the proofs for the various algorithms introduced above (the inter­ ested reader is referred to [6]). Since the proofs for BSA; and BSA6 e are the ones most different from simi­ lar proofs for Af, BHPA and Bs·, we selected them for presentation below. Moreover, we will show an interest­ ing result about dominance between bidirectional algo­ rithms which is due to the improved termination condi­ tion (3) . We assume that the branching degrees of all nodes are finite, the arc costs ci(m, n) ~ e > 0 for some e, and a consistent heuristic estimator is used.

Definition 3.1 A path P from s to t is €-optimal, if cost(P )'.5. (1 + c:)c· .

Definition 3.2 A search algorithm is said to be €­ admissible, if it terminates with an £-optimal solution whenever a solution exists {14, 13}.

Definition 3.3 An algorithm A1 is said to dominate A2 if every node expanded by A1 is also expanded by A2 {13}.

9 Due to the inclusion of reopening of nodes in our algo­ rithms and a technical bug in step 22 of the Bs· description in [10, p. 101], we restructured the code.

Lemma 3.1 Before BSA6,£ (6 ~ ~J tenninates either an ~-optimal path P' has already been found or there exist n; and n; in OPEN 1, OPEN 2 respectively, such that n; and n; are shallowest open nodes along an op­ timal path P = (s = n1 , .·. ,n;, ... ,nj,····t = nt) with gt(n;) = gi(n;) and U2(n.;) = g2(n;).

Proof: Except for the BS 6pecific action., 6uch node., mu6t e:&i.st at any time before termination, 6ince we account for re­ opening of nodes (cf. {13]}, and before the first meeting no 6uch actions can occur. Furthermore, i < j. Otherwise the optimal path would have been found. There are four cases where theses nodes could be removed from 0PENd without in­ stalling a successor substituting them along P. We consider the case of n; to be removed from OPENt (the case of n; to be removed from OPEN2 is analogous}.

1. Nipping: Node n; is nipped in TREEt, i.e. n; must be in CLOSED2. n~o is a node in OPEN2 having the smallest h value. Since n; is closed in TREE2, n; was selected for ezpansion before n; (while searching in the backward direction} and we have

We distinguish two cases

(1.1) (1+e)[g;(n;)+k2(n;, n;)]+eg;(n;) 2: g2(n;)

This implies Lmin $ (1 + e)c·. (1.2) (1+e)[g;(n;)+k2(n;,n;)]+eg;(n;) < g2(n;) Due to consistencyh2(n;) $ k2(n;,n;)+h2(n;).

• !!. Pruning: Node n; has an ancestor node nz in TREEt which was nipped in TREE2. nz must be on an optimal path (say P }, otherwise n; cannot have its parent pointer set to nz. Therefore, g1 ( nz) = gi ( nz) and the proof is analogous to case 1, subdituting nz for n;.

Since n; is on an optimal path and g1(n;) = g;(n;), and since ht is consistent and consequently admissible, ht (n;) $ hi( n;), this implies g1 (n;) + h1 (n;) $ g;(n;) + hi(n;) = c·. If no path P' with cod(P') $ (1 + e)c· was found yet, c· $ (1 + e)c· < Lmin, contradicting {5).

1. Screening: If n; is expanded and not nipped, there is one of its successors n;+l .substituting it a.s the shallowest open node on P. If n;+l would be screened and c· < Lmin, this would lead to an analogous contradiction as in case 3. 0

Lemma 3.2 If a path exists from s tot, BSA6 e will not tenninate before finding an ~-optimal path. '

Proof: The proof i.s analogous to the one in {17, p. 133}, but using our termination condition {3}. 0

Lemma 3.3 If a path exists from s to t, BSA6 e tennina~~ '

Proof: Either the graph is finite and exhau.sted, or it is in­ finite and the co.st8 become unbounded (analogous proof.s can be found in [.4, 1!!, 13, 10}). 0

Theorem 3.1 If a path exists from s tot, BSA6 e ter­ minates with a solution whose cost does not exce~d the optimal cost by more than a factor (1 + ~), i.e., BSA6 e is ~-admissible. '

Proof: This result follows from the lemmas above.

0

Corollary 3.1 BSA; is ~-admissible.

Theorem 3.2 A bidirectional algorithm B1 using the tennination condition {9) dominates another bidirec­ tional algorithm B2 differing from B1 only in using the condition {2) instead.

Proof: Since the right side of {3} i.s always greater than or equal to the right side of{!!}, algorithm B1 cannot terminate later than B2. 0

Corollary 3.2 IBHPAc dominates BHPAw.

4 Experimental Results

Experiments were conducted to compare the per­ formance of these bidirectional algorithms. The test domains used were sliding-tile puzzles and route planning. 10 These puzzles have been often used in the literature for explanations and comparisons of search al­ gorithms in AI. Therefore, we also used them in order to make it easier to compare our results with published ones. Since finding optimal solutions is NP-complete, it is interesting to study finding approximate solutions, and the effects of scaling up.

However, while the puzzle is illustrative, it is just a game. In contrast, the route planning domain we se­ lected has more real world flavor (though it is easier to scale up). We used randomly generated route planning problems in a map of the Viennese network of public transportation [6] rather than synthetically generated problems as used in [10].

4.1 Constant weighting

We were primarily interested in comparing the bidirec­ tional best-first search algorithms with their correspond­ ing unidirectional counterparts. Let us first summarize the 8-Puzzle results. The case of~ = 0 is identical to a comparison of HPA· with ns· and BHPA'. There, the unidirectional HPA* is clearly more efficient. However, already for ~ 2:: 0.2 the bidirectional search algorithms are in terms of the number of generated nodes more ef­ ficient than the corresponding unidirectional algorithm. The linear-space algorithms WIDA · (an ~-admissible ex­ tension of IDA·) and REFS [8] showed relatively bad performance in terms of generated nodes. However, since node generation and evaluation is very efficient for the puzzle, they are still competitive in terms of running time, due to avoiding the overhead for managing the lists used for implementing classical best-first search.

10 These domains are not especially selected to fulfill the conditions under which classical best-first search is best. In particular, the puzzles have uniform cost and the usual eval­ uation functions there do not have many distinct values.

An important question is how significant the results are. In addition to comparing the numbers of nodes searched, we look at the empirical data from a differ­ ent viewpoint. Instead of summing up the numbers of generated nodes for each sample, we compare the per­ formance on each instance. We count how often one or the other algorithm "wins" in the sense that it expands ~ewer nodes than its competitor when solving the same mstance .. The statistical details of using the sign test can be found m {6]. Although it is statistically significant ac­ cording to this test that for c ~ 0.1 HPA* expands more often fewer nodes than IBS* on the same instance the · · £ ' mverse 1s true for c > 0.3.

Since the sliding-tile puzzle is NP-complete it is in­ ~erestin~ to investigate scaling up. In partic~lar , it is mterestmg to see the effect of relaxing the solution qual­ ity (5] . Fig. 3 compares IBHPAe and IBS* with HPA* WIDA~ and RBJ!'S on the 15-Puzzle (usi~g the sampl~ of 100 mstances m (9]) . Due to their memory problem it is infeasible for IBHPAe , IBS; and HPA* to find o~ even to guarantee optimal solutions here.

F~r c = ~· HPA* can solve all the 100 instances of (9], but 1t reqmres memory for nearly 1 million nodes in the maximu~. In contrast, IBHPAe requires only a stor­ age of shghtly more than 300k nodes in maximum and IBS; slightly more than 250k nodes. Both are cl~arly more efficient than the others in terms of nodes gener­ ated. Interestingly, HPA* "wins" against both IBHPA and IBS; slightly more often, but the results are not sta~ tistically significant according to the sign test. While the worst case bound c = 1 would allow solutions with twice the cost of optimal ones, the solutions actually found by these best-first algorithms are in the average just about 20 percent worse.

_For c = 0.75, IBHPAe and IBS; require storage of shghtly more than 600k nodes in maximum. In contrast HPA* requires to store nearly 2 million nodes for thi~ task. The advantage of our bidirectional algorithms over HPA* in terms of the total number of nodes searched is ~ighly statist~cally signi~cant (testing the means), but it 1s not accordmg to the stgn test. From this we can con­ clude that they are better especially on the difficult prob­ lems. Generally, the advantage of IBHPAe and IBS* is even clearer than for c = 1, generating an order of U:agnitude fewer nodes than WIDA* .

For c = 0.5, IBHPAe and IBS; require less than 1.5 m~llion nodes in maximum for the whole sample. While thts worst case bound would allow solutions that are 50 percent worse than optimal ones, in the average these al­ gorithms find solutions that are about 10 percent worse. HPA* cannot solve 8 instances with this amount of stor­ ~g~ . The number of nodes generated by IBHPAe (IBS;) ISm the average smaller by a factor of 21 (25) than that generated by WIDA* . Therefore, it appears that the performance advantage of our bidirectional algorithms ~teadily increases with decreasing values of c (at least m the range where memory suffices) . Moreover, their advantage is much more pronounced on the much more difficult 15-Puzzle than on the smaller 8-Puzzle.

4.2 Derivatives of A;

In contrast, the bidirectional algorithms BA* and BSA* are normally less efficient than the corresp~nding uni~ directional A; (see FiR.' 4 for the results on a random set of 50? 8-Puzzl~s) . 1 Therefore, we designed BA:i,e and BSA 6 ,e, and Ftg. 4 also shows a comparison vs. A; in terms of the total number of expanded nodes, using 6 = ~ · In total, BA:i,e and BSA:i,e expanded fewer nodes than A; for c ~ 0.2.

It is statistically significant that for c ~ 0.2, A; ex­ pands more often fewer nodes on the same instance than BSA:i,e with 6 = 1· However, using c = 0.3 the inverse is. tr~e .. For c ~ 0.5 the bidirectional search algorithm dtd stgmficantly better than the corresponding unidirec­ tional one.

Moreover, it is interesting to have a look at the data of the first meeting in Fig.4. The worse bidirectional al­ gorithms in the average met earlier than the better ones (but with worse solutions) . After that , the latter could terminate rather quickly (or even immediately), while the former needed much time to satisfy the termination condition.

11 The performance of A; with ~ = 0 is better than that of A · since it uses its FOCAL-heuristic as a. tie-breaking rule.

4.3 Cross-domain comparison

Since we conducted experiments in two different do­ mains, the question arises whether there are major dif­ ferences in the results. Fore = 0, IES* (equivalent to IJ_S* there). did relatively much better ine the route plan­ nmg domam than for the 8-Puzzle. Most interestingly, ES* was even 3 percent more efficient than A · in terms of overall nodes expanded. However, with high statisti­ cal significance it was beaten by the latter in 63 percent of the cases which were not "draws". This observation reinforces the conjecture in [10] that ES* is relatively more efficient than A* on difficult problems.

Moreover, we found that ESA; was not that bad in comparison to A; in the route planning domain as it was for the puzzle. Generally, for both domains used f?r our experiments th.e better bidirectional search algo­ ri.thm~ were more efficient than their corresponding uni­ directiOnal counterpart when the goal of finding optimal solutions is slightly relaxed.

4.4 Which is the best algorithm?

Since we investigated several bidirectional algorithms, the question arises which one is the best. Generally the bidirectional algorithms using the improved termin~tion condition (3) are more efficient than the others.

In particular, let us compare IES; vs. IEHPAe. For e = 0, IES; was clearly superior to IEHPAe on the 500 8-Puzzle instances. Although already for e > 0.1 the total number of expanded nodes was nearly the same the ES* derivative was significantly better for e < o.9 in terms of "winning", but with increasing values of e the vast majority of cases were "draws". On the 100 15Puzzle instances, the advantage of IES* over IEHPA ~as statistically significant over the wh~le range inves~ tigated, and according to both statistic tests. In the route planning domai~, IES; was superior to IEHPAe fore :::; 0.3 both regardmg the total number of expanded nodes and in terms of "winning" . However, for larger values of e the majority of cases were "draws". In most of these cases both algorithms terminate immediately af­ ter first meeting, and up to this point they do the same. Generally, the difference appears to be more pronounced for more difficult problems.

Although the ES* derivatives do not strictly dominate the corresponding derivatives of HPA (especially because of the cardinality criterion for selecting the search di­ rection), they generally "lose" very seldom. Therefore, IBS; and ESA6,e with 6 = ~ are candidates for being the best bidirectional heuristic search algorithms. We could not find that one of these is generally better than the other.

In general, it strongly depends on the properties of the given problem which algorithm is "best". Of course linear-space algorithms must be used when there is in~ sufficient memory available. However, whenever there is, our bidirectional algorithms should be considered. Of course, running time is another important issue. Again, it strongly depends on the domain, whether the overhead of maintaining the lists deteriorates the performance or ~ot. In pa~ticular, it ~epends on the effort for comput­ mg heunstic values. Fmally, of course, also the efficiency of i~ple~entation plays an important role regarding the runnmg time.

5 Conclusion

For more than two decades there has been consensus that the main reason for the superiority of unidirectional search is that the bidirectional heuristic search is afflicted by the problem of search wavefronts missing each other. However, our results show that the missile metaphor of Pohl [15] is not really applicable. The primary problem appears to be that after the first meeting especially an al­ gorithm aiming for optimal solutions has to spend much effort for subsequently improving the solution quality, and finally for. proving that no other open node can give a better solutiOn. Therefore, only a slight relaxation of solution quality already leads to strong improvements in efficiency, and in particular to even more than in the unidirectional case. Our novel termination criterion con­ tributes strongly to this result because of the importance of this problem.

However, a serious limitation of classical best-first search is its memory problem. In contrast, WIDA* and REFS have only linear space requirements. Rao et a/. [20] com~ared depth-first with best-first search gener­ ~lly. While the latter has the serious disadvantage of Its memory problem, there are conditions, where classi­ ~al. best-first search is still most efficient. In particular, It IS useful when both density of solutions and heuris­ tic branching factor are very low (and there is sufficient memory available). Moreover, both IDA* and REFS have large search overhead when there are many distinct values, and when the problem graph is not a tree [11].

Our bidirectional algorithms are designed to improve the performance under these conditions. While there are some differences, for both domains used for our ex­ periments the main result about these algorithms is the same. We showed that and how bidirectional best-first search can be more efficient than the corresponding uni­ directional counterpart without expensive wave-shaping. Therefore, even for only slightly relaxing the require­ ments on the solution quality, the best of our algorithms are the most efficient €-admissible algorithms known for those domains where sufficient memory is available. Such domains are not the most difficult ones address­ able by search techniques like WIDA · and REFS. But in those areas dominated by classical best-first search we found even better algorithms, based on a paradigm that was thought for long to be bad.

Currently, we are investigating a bidirectional combi­ nation of best-first search with linear-space search in order to mitigate the issue of storage requirements. 'we hope that this will renew the interest in bidirectional search, which has additional potential for efficient Im­ plementation on parallel hardware.

Acknowledgements

The original implementation of our algorithms was based on a program written by Max Hofferer. A more efficient imple­ mentation was done by Angelika Giingl-Ehrenwerth and Har­ ald Smetana, and the most efficient implementation based on code provided by Richard Korf is due to Ali Khorsand. The help of Harald Smetana and Ali Khorsand in running the IS­ Puzzle experiments is highly appreciated. The experiments requiring very large memory were run on a machine of the computing center of the Technical University of Vienna.

A Pseudo Code of BSA6,e:

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. procedure BSA6,.(s, t) g1(s) +- g2(t) +- 0; /I(s) +- h(t) +- h1(s); Lmin +- oo; 0PENI +- {s}; OPEN2 +- {t}; CLOSED1 +- CLOSED2 +- 0; until OPEN I = 0 or 0PEN2 = 0 or Lmin ~ (1 + e:) ma.x[minze0PEN 1 (g1(x) + h1(x)), minzeOPEN (g2(x) + h2(x))] do if IOPENII ~ IOPEN2I J· cardinality criterion *I then d +- 1 else d +- 2 endif d' +- 3 - d; /* set the opposite search direction *I Select m E FocALd with lowest hF 4 -value; OPENd +- 0PENd \ {m}; CLOSEDd +- CLOSEDd U {m}; if m E CLOSEDd' then /* nip m in TREEd and prune TREEd' *I ilm +-{nInE Fdt(m) Apdt(n) = m}; OPENd' +- 0PENd' \ ilm; else EXPAND(m); endif end until 15. if Lmin = 00 then no path exists else 16. the solution path with costs Lmin is (s, . .. ,p~(MeetingNode),PI(MeetingNode), MeetingNode,p2(MeetingNode), .. . , t). endif end procedure. procedure EXPAND(m) 1. TrimFlag +- false; . 2. foreach n E Fd(m) do 3. g+-gd(m)+cd(m,n); 4. if g + hd(n) < Lmin then /* no screening *I 5. f +- g + hd(n); 6. if n fl. TREEd /* n is a. new node *I then 7. gd(n) +- g; /d(n) +- f;pd(n) +- m; 8. OPENd +- OPENd U {n}; 9. elsif g < gd( n) I* better path to n found *I then 10. gd(n) +- g; /d(n) +- fiPd(n) +- m ; 11. if n E CLOSEDd then /* reopen n *I 12. CLOSEDd +- CLOSEDd \ {n}; 13. OPENd +- 0PENd U {n}; endif endif 14. if n E TREEd' and g1 (n) + g2(n) < Lmin then /* update Lmin *I 15. Lmin +- 91(n) + g2(n); 16. MeetingNode +- n ; 17. TrimFlag +- true; end if endif endforeach 18. if TrimFlag then I* trim the open lists *I 19. Remove from OPEN1 and OPEN2 those nodes n with(g +h)-values ?:: Lmin (d = 1, 2) and which are not source nodes (for OPEN1 the source node is s; for OPEN2 it is t) endif end procedure.