An Improved Di-Directional Heuristic Search Algorithm

1. Introduction

• In this paper we limit ourselves to those problems a) which are re~resentable in the state 1 -operator­
• state2 parad1gm;
• where the goal can be explicitly represented as a state in a set of states;
• whose problem space can be described as a labelled graph;
• where it is equally possible to work from the start state to the goal state as the other w~ round;
• where there is a heuristic function available which can be used to guide the search process.

As is well known, see e.g. /1/, a heuristic func­ tion can be used to guide uni-directional search. The property of ending with a shortest path be­ tween start state and goal state, as can be found with breadth first search without heuristic func­ tion, can even be preserved if the heuristic function is a lower bound on the real minimum ef­ fort to be made. In /2/ and /3/ an algorithm is described which generalizes to the bi-directional case. This algorithm in fact performs two inde­ pendent uni-directional searches, a forward search guided to the goal node, and a backward search guided to the start node. The disadvantage of this is, that in a search space where more than one path exists from the start node to the goal node, the two searches often proceed along two different paths, so that the two sets of closed nodes (for the terminology of 'closed', 'nodes' and other technical jargon see /1/) grow into nearly complete uni-directional trees before in­ tersecting each other, instead of meeting in the 'middle' of the space.

In the next section we discuss another algorithm that remedies this deficiency and we give a sim­ plification of that algorithm which has been im­ plemented in a Fortran program. In section 3 we compare our results with the results of Pohl's uni-di r ectional heuristic search on the 15-puzzle . In section ·4 we mention some possible improve­ ment s of the implemented algorithm.

2.0 Bi-directional, Heuristic, Front-to-Front Algorithm (BHFFA)

Before going into a precise description of the BHFFA, we ~ive an intuitive sketch. Suppose we have the situation as in fig.1, where SandT are the sets of closed nodes and S and f are the two fronts of open nodes, and we decide to ex­ pand a node from~. In Pohl's BHPA algorithm a node was chosen in ~ which had a minimum value of the function g +h , where g was the current mimimum to the stirtsnode s an~ h was an esti­ mator of the distance from the no&e to the goal Lode t. The h we use is different. h is a mi­ nimum of H+gtsover every node in the gpposite front T, where gt is li~e.gs but w~th respect to the goal node t and H 1s an est1mator of the shortest distance between arbitrary pairs of nodes. Immediately the disadvantage of this al­ gorithm with respect to BHPA must be clear, sin­ ce the calculation of the function h in our al­ gorithm is much more complicated th&R the cal­ culation of the distance to t in BHPA. On the other hand there are gains, but we defer dis­ cussing them to the next section.

In order to describe BHFFA we have to give some definitions, where we follow as close as pos­ sible the terminology of /3/.

• s is the start node;
• t is the goal node;
• S is the collection of nodes with known f -value; reached from s
• T is the coliection of nodes with known f -value; reached from t
• S is the collection of nodes, direct successors of nodes i n not in S; S, but
• -' is the collection of nodes, direct successors of nodes in not in T· ' T, but

• H(x,y) is the minimum distance between node x and node y;
• H(x,y) is an estimator of the distance between x andy vith H(x,y)=H(y,x);
• ~~(y) is the minimum distance between s andy for ye:suS, vi th path in S·JS;
• ~t(y) is like~ (y) vit~ respect tot and TU~;
• ye:~
• hs(n) =min (ii(~,y) + ~(y));
• ht(n) =min (H(n,y) + gs(y)); ye:S
• f (x) · g (x) + h (x) ·
• rtx) is tne finit~ set of nodes obtainable by applicable operators on x;
• fs(x) z ~(x) + hs(x)~
• r- 1 (x) is like r(x), but vith inverse operators instead;
• ~(n,x) is the edge length between n and x.

We nov define BHFFA:

1. Place s in H(s ,t). S, and t in~. vith fs(s):·ft(t):=
2. If Su~ 2 ~ then stop without a solution else decide to go forward, step 3, or backv~d, step 10.
3. Select n inS with fs(n) =min f (y), remov~ ye:S s n from S r(n). and put n inS, let descendants(n):=
4. If ne:~ then halt with a solution path.
5. If descendants(n)·¢ then go to step 2.
6. Let xe: descendants(n) and remove x from it.
7. If xe:S then (if g (n)+f(n,x)<g (x) then

g (xJ:=g (n)+f(nJ);

if g'(x)~h (x)<f (x) then

f (x :=g (~) + hs(x);

. g~ to stgp 5]. s

8) If xe:S then [if g (n)+f(n,x)<t; (x) then

s

s

gs(x):=gs(n)+f(n,x);

if g (x)+h (x)<f (x) then

s

s

s

{f 5 (x):=g (x)+h (x); remove x

from s ana put l in '§};

go to step 5].

1. Put x vith step 5. its value fs(x1 in S and go to
2. Do the same as step 3 upto 9 with (s,s,S,r) replaced by (t,T,T,r-1).

In step 2 nothint; 'is said about the decision to t;o forward or backward. As investigated by Pohl the most promising procedure is to count the ' number of nodes in ~ and ' and to select the front which has the fewest (but at least one). Besideo the f-value the g-value needs to be stored at each node, as the g-value mit;ht be updated in step 7 and 8 of BHFFA.

2.1 Some theorems about ~HFFA

We give some theorems and proofs about ~HFFA which parallel the theorems and proofs about the unidirectional A· algorithms of /1/. In this section ve also formulate another bi­ directional alt;orithm BHFFA2 which is interestint; from a theoretical viewpoint and which we com­ pare vith BHFFA in section 2.2.

Theorem 1

If R(x,y),H(x,y) and all edge-labels are not less than some positive 6 then BHFFA halts with a shortest path between s and t (provided there is one~.

Proof 1: As in the unidirectional case we first prove a lemma.

Lemma 2 If H(x,y),H(x,y) then for every iteration of BHFFA and for every optimal path P from s to t there exist open nodes ne:S, me:T, on P with fs(n)~H(s,t) and f (m)~H(s,t).

Proof 2: Let n be the first node on P counted from s, with ne:S. Let m be the first ~ode on P counted from t, with me:T (they exist because ' otherwise BHFFA had already halted).

= H(s,t) since we are on an optimal path. ft(m),H(s,t) is proven in the same way.

Now suppose theorem 1 isn't true. Then we have three cases:

1. BHFFA doesn't halt;
2. BHFFA halts without a .solution path;
3. BHFFA halts without a shortest path.

Case 1: Let P be an optimal path from s tot. According to lemma 2 there exists alw~s an open node n in SuT on P vith f (n) or f (n),H(s,t). Therefore the nodes expanaed must fiave an f-value less or equal to H(s,t). Consequently their g­ values are less or equal to H(s,t). Thus BHFFA only expands nodes at most H(s,t)/6 steps away from s or t, and this is a finite number. Let Ms and Mt be the sets of all nodes which are ever generated from s and t respectively. As every node has only a finite number of successors and as the maximum number of steps any node ia ' avay from s or t is finite, both M and M can only contain a finite number of noaes, ana so M·MsUMt is of finite size. Let the number of nodes 1n M be v. Let p be the (necessarily fi­ nite) number of differWnt paths from s tom if me:Mi:, and from t to m if me:M , and let p be the max1·mum over all p . Then p Is the maximum num­ ber of different trmes a node can be reopened. After p.v iterations of BHFFA all nodes of Mare pe~ently closed. So SuT-¢ and BHFFA halts, vh1ch produces a contradiction.

Case 2: We have just proved that BHFFA eventual­ ly halts, and it can only do so for tvo reasons: It has found a solution path, or SvT is empty. If the latter is the case, then the last node expanded had no successors at all, (otherwise they would have been placed in S or T). But this means that there is no path from s tot, contra­ dictory to assumption. So ~HFFA halts because it has found a solution path.

Case 3: Just before endin~ vith a node m, there would, by lemma 2, be anode n inSwith f (n)~ H(s,t)<f (m)=~ (m)+~(m) and thus n woula be chosen f~r explosion instead of m. q.e.d.1

The next theorem proved in /1/ is the optimality theorem, which states that if two heuristics, R and n·, are related by H*(n,t)<R(n,t),H(n,t) for all n, and if for both heuristics the consistency property holds, (meaning that H(n,t)+H(n,x)~ H(x,t)) then every node expanded by H will also be expanded by H . This theorem doesn't hold for BHFFA. The reason for that is, that, unlike in the uni-directional and in Pohl's bi-directional algorithm, the f-value of an open node is not static in BHFFA, and the w~ in which it changes depends on both the exact form of the heuristic and the real distances between the nodes in the opposite front; and without assuming some de­ tailed information about those, the exact be­ haviour of any heuristic with BHFFA is hard to predict. We haven't succeeded in finding age­ neral proof that, if one heuristic is better (in the above sense) than an other, it will al­ w~s finish in less iterations. We don't con­ sider this a great loss, because in most cases it will nevertheless be true. (Something, for example, which can be proved is, that if there are two heuristics, R = H.6 and R·= H.£ and 0~£<6,1, then H will finish in less iterations).

Now we describe another bi-directional algorithm, BHFFA2, because it can be easily implemented and seems to be elegant. The worst case error ana­ lysis, the results of which are described in the next section, however, suggests that the number of nodes expanded explodes faster. The notation of BHFFA2 follows more closely the terminology of /1/.

BHFFA2

1. Place {(s,t,O,O,H(s,t))} in OPEN.
2. If OPEN=¢ then halt without a solution.
3. Select n=(x,y,v1,v2,v3) in OPEN with minimal v1+v2+v3; OPEN:=OPEN-{n}; CLOSED:=CLOSEDU{n}; descendant~(n):=r(x)xr- 1 (x).
4. If x=y or yer(x) then halt with a solution path.
5. If descendants(n)=¢ then go to step 2.
6. Select m=(m1,m2) in descendants(n) andre­ move m from descendants(n).
7. If meCLOSED which m~ans m1=z1, m2=z2, and (z1,z2,gs(z1),~(z2),H(zl,z2))is in CLOSED then

[if g (z1)>g (x)+i(x,m) and/or gt(z2)>~(y)+ t(y,~) thens

{update g (z1) and/or g (z2); place (z,,z2,g (z1),~fz2),H(z1,z2)) in OPEN}; go to step 5]. s

1. If m£0PEN then

tdo updating of g (z1) and/or gt(z2) as in step 7 if necessa~; go to step 5].

1. g (m1):"'g (x)+((m1,x); g..(m2):=gt(y)+t(m2,y); O~EN:=OPEHu{ (m1,m2,gs(m~).~(m2J,H(m1,m2))}; go to step 5.

Theorem 3

The lemmas and theorems proved in /1/ for the uni-directional A· algorithm, including the op­ timality theorem, also hold for BHFFA2. Proof 3: BHFFA2 is in fact the uni-directional A algorithm in the product space of the nodes with itself. q.e.d.3.

2.2 Worst case analysis

A first order comparison of these algorithms m~ be done by investigating how they behave in worst case situations. We have derived formulas for the uni-directional, Pohl's bi-directional, BHFFA and BHFFA2 algorithms, assuming that the heurist­ ic function used gives a maximum error between relative bounds. We will summarize the results here, an expanded version of this paper contain­ ing their derivations will be sent on request to readers interested in them. Let the search space be a countable collection of nodes, with two nodes, the start and the goal node, having m edges (m>1), while from all the other nodes emanate m+1 edges; and there are no cycles. Let all the edge-lengths be equal to 1, and let there be a path of length K between start node and goal node. From a uni-directional viewpoint this space is a tree with branching-rate m, since the algo­ rithm will not look beyond the goal node. In this space the following results are obtained:

1. Let R be the real distance from some node on the solution path to the goal node in the uni­ directional case, to the start or goal node in Pohl's bi-directional case, and to the other front in the BHFFA cases. If for each node on the solution path nodes off the solution path are expanded until some depth j, and if this

j is a monotonically decreasing function of R, then, no matter what the heuristic exactly looks like,

where~ denotes the number of nodes expand­ ed by algorithm A.

'rhat this indeed must be the case can be under­ stood intuitively by looking at the figures 2 , 3 and 4, where the length of a bar represents the depth to which nodes off the solution path are expanded. The total length of all the bars in­ creases from figure 2 to figure 4.

• 2 . Suppose that for two nodes both lying on the solution path holds that H(n ,m)=H(n,m). ( 1+<5) forsomecS>O,and else (at least one of the two lying off the path) H(n,m)=H(n,m)/(1+<5). Then <5 is a relative error bound and this is the worst possible case. Now for the BHFFA, the uni-directional algorithm and Pohl's bi-di­ re~tional algorithm nodes off the solution path will be expanded until a depth j=cS.R + <5. (<5+1 )/(<5+2).

So here the monotone condition ·holds with the result stated above. Furthermore we give exact formulas for the number of nodes ex­ panded by the different algorithms in this worst case:

where m is the branching-rate, K is the solution path length, and c 6 =<5.(<5+1)/(<5+2).

1. The BHFFA2 case is less easy to handle, the way it ranks in the series depends on m and on K. The analysis, however, shows that with increasing m and K BHFFA becomes the better algorithm in the long run. The exact formula for the number of nodes expanded is very complicated and won't be given here, a reasonable estimate is given by

uni-directional formula with the solution path length halved and the branching rate squared. In general it underestimates the number of nodes expanded by BHFFA2 .

3. Experiments with BHFFA

3. 1 The program

'A modified BHFFA algorithm is implemented as a Fortran program, geared toward solving the 15puzzle. In this search-space all edgelengths are taken as unity. The most important restriction made is that if, afte r having expanded 1000 nodes, the program still has not found a solution path, it gives up. Another important modification is that the number of open nodes in a front can­ not exceed some maximum m, which is given to the program as an input parameter but must be less

100. Wh~never an (m+1)-th node should be added to a front, first the open node with the current worst f-value is deleted from it -unle ss t he node itself has an f-va] ne even worse, i n which cas ~ it won't be inserted. We call this operation "pruning", a term also used in /1/. Thi s step is mainly necessary to save time, as the number of comparisons needed to calculat e h (x) for a node x in S, is equal to the numbe r 3f nodes in T and vice versa. But th i s also means that the algorithm is not admissable anymore , (an al go­ rithm satisfying theorem 1 is called admissible), because it is possible that some node on the op­ timal path will be thrown away because it looked very bad at some i teration. In a search space where only one path exists from start to goal node, some backtracking mechanism would be re­ quired to ascertain that this path is found. In the case of the 15-puzzle, the actual influen­ ce didn't appear to be very large if m was set at 50 (or larger), as will be seen in section 3. 2. Step 8 of BHFFA, where occurrence of a new node in the collection of closed node s of it's own front is checked was eliminated. We did this be­ cause we thought the time gained in pos sibly ex­ panding u few nodes less would not balance t he loss caused by searching through the set of closed nodes for every new open node, whereas the solution path found will most likely not be in­ fluenced. Step 9 was done by estimating all distances to the opposite front, and inserting node x in ·:me of the ordered fronts of open nodes, where the ordering is given by the f-values of the open nodes. A nasty side-effect was that the insertion of a new node in S could i mply a re­ ordening of 'l' and vice versa . The or dering was done using a square matrix in which all combi­ nations of the H(x,y)-values of the fronts were stored. Step 4 (the terminating condi tion) was eliminated and replaced by a test in step 6: 'If x£'l'UT then halt with a solution path'. The testing of x being in TuT instead of just being in T is a necessary consequence of the pruning, as it is possible that a descendant of a closed node is deleted from the open front. Three heuristic functions were implemented in the

program: E

1. P(a,b)= .p . , with p 1 . being the Manhattan dis1 1 tance between the position of tile i in a and

1. S(a,b)= ipi . hi , where pi is as in 1 and hi is the distance in a, of t i le i t o the empty square;
2. R(a,b) is the number of reversals i n a, with respect to b, where a reversal has the meaning that a(i)=b(j) and a(j)=b(i), and i and j are adjacent tiles.

Of these functions the first two or iginally come from /4/, whereas the third comes from / 2/.

1. Results, conclusions and r emarks In order to compare our results wi th the uni­ directional case, the program was run wi th the same 15-puzzle problems as were used by Pohl in / 2/, using t he same heur i stic funct ions wi th t he same -values :

f4 = g + w.( S + 20R) with w = . 5, .75, 1, 1.5, 2, 3, 4, 16,oo (which in fact means f1(x)=g (x) + Min(P(x,y)+ s y£;y. ~{y)) for x inS; :tc.). .

As there were ten d1fferent 15-puzzles, th1s amounts to a total of 320 problems, of which our program solved 240, whereas the uni-directional program of Pohl solved 203 of them. It can be seen that in nearly all these cases the heuristic is not a lower bound on the real effort to be made . This is the main reason why many of the so­ lutions found are not optimal, both for Pohl's program and ours .

Tables 1 and 2 summarize the results, the full r esults on all ten problems may be found in the expanded ve r s ion of thi s paper already mentioned i n section 2 . 2. In table 2, where the performance of the di fferent funct i ons is compared, the s core for pathlength was obtained as f ollows: The program with the shortest path for some pro­ blem scored 1 and the other 0, (and any path is counted shorter than no path at all); if the same pathlength was fotind by both programs they both scored 1; if a problem was not solved by either of the programs they both scored 0. The score for the number of nodes expanded was obtained in a similar way. In so far the solution quality is concerned, BHFFA is an improvement over the uni­ directional algorithm: it solves more problems, finds in general shorter paths, and expands less nodes on the average, although the last effect is less prominent than we expected. BHFFA performs particularly well with a strong heuristic function; with f4 the total number of nodes expanded by our program was 32% less than that by Pohl's program. The frontlength adequate for the problems was found empirically. Experimental runs were made with frontlengths 25, 32 and 50. An increasing number of problems was solved and a higher sta­ bility was reached. (By stability we mean the chance that a longer frontlength preserves a so­ lution obtained with a shorter frontlength; pruning tricks are the obstructing force here).

As could be expected, the performance with res­ pect to the frontlength depends on both the so­ lution path length and the heuristic used: The better the estimator, the smaller the frontlength required (a length of 1 would suffice for a per­ fect heuristic). All problems were run with a frontlength of 50, and the least satisfactory solved were run again with a frontlength of 99, in order to see whether the maximum number of 1000 expanded nodes or the pruning in the fronts was the bottleneck. In general the first seems to be the case, since no significant improvement was made, with the exception of f1 on A9 where six instead of one out of seven problems was solved. The main disadvantage of Pohl's bi-di­ rectional algorithm, as mentioned in section 1, appeared to be remedied. The fronts now did meet near the middle of the search-space, which we coul~ see by comparing gs and ~ of the inter­ sect1on nodes.

The large disadvantage of our algorithm is the very time-consuming calculation of the distance estimator. With a frontlength of 50, I would expect the BHFFA-program to take in the average about 35 times longer to obtain a solution (for the same problem with the same heuristic) than a uni-directional program, run on the same machine. In general, the loss of efficiency will not be sufficiently set-off by the shorter paths found. Nevertheless, it may pay off in, for example, an ABSTRIPS-like environment (see /5/), where it is crucial to find an optimal path from among many different existing paths, as the num­ ber of sub-problem searches depends on the path­ length found in the dominating problen-space. There are BHFFA or a similar algorithm (in the next section we will suggest ways to make it cheaper), with a strong heuristic function, may find an optimal path more efficiently than a uni-directional program with a heuristic satis­ fying the lower bound condition, because this kind of heuristic tends to be rather weak and results in a fast explosion of the number of nodes expanded.

4. Open problems and loose ends.

BHFFA can be simplified by not calculating the heuristic distance to every node in the opposite front but only to the best half or even less of them. This idea is inspired by the fact that, in the limited number of cases where we checked it, a node realised its minimum nearly always to a node which belonged to the best ten of its own front. A further simplification would be to de­ lete the resequencing of the opposite front as the consequence of adding a node to a front. The sensitivity of the solution quality to these computation time and memory savings should be tested.

BHFFA2 needs implementation to be able to com­

pare its performance with that of BHFFA.

Looping as a consequence of the pruning can be recognized but which rescue program should be started then is ·unclear.

The partly expanded node technique, as suggested in /6/, needs investigating.

A l ess technical question however concerns the selection of the most interesting ones among the vast amount of potential macro-operator sequences that appear in a solution ,path. But the real A.I.-question is still: How can the program improve its heuristic function beyond simply optimizing some coefficients. Heavily related to this is the question: How to find automatically the best representation for a problem to be treated by heuristic ·algorithms.

Acknowledgements

This research originated from a grant of the Netherlands Organization for the Advancement of Pure Research (z.w.o.), which enabled the first author to visit U.T. in Austin, Texas, where L. Siklosky introduced him to this field. Discussions with I. Pohl on earlier drafts were highly appreciated.