Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm

AE -- AN EFFICIENT NEAR ADMISSIBLE HEURISTIC SEARCH ALGORITHM

Malik Ghallab and Dennis G. Allard

Laboratoire d'Automatique et d'Analyse des Systemes

du C.N.R.S. 7, avenue du Colonel Roche- 31400 TOULOUSE, France

ABSTRACT

The algorithm A* (Nilsson, 1979) presents two significant drawbacks. First, in seeking strict optimal solution paths it necessarily has high order of complexity. Second, the algorithm does not explicitly descriminate between the cost of a solution path and the cost of finding the solution path. To confront these problems we propose the algorithm A£, a generalization of A*. Instead of seeking an optimal solution, it seeks one which is within a factor (I+E) of optimum (E ~ 0). The basic idea is to avoid doing any search at all on most near optimal partial solutions by sticking to a small number of most fruitful paths. Various strategies for searching for near optimal partial solutions are discussed . Experimental results are pres ented indicating that AE has average complexity of lower order than A* and compares favorably to the related algorithm AE* (Pearl and Kim, 1982).

I INTRODUCTION -- ADMISSIBLE SEARCH IS EXPENSIVE

This paper emphasizes the main ideas behind AE and serves to introduce new empirical results concerning its behavior. A more extensive presentation of AE and its properties appears in (Ghallab, 1982) and in (Ghallab and Allard, 1982). We assume familiarity with A* and notation of (Nilsson, 1979). We denote the set of successors of node n by X(n). The cost of arc <n,x> is k(n,x) ~ 0. We denote a path between n and m by <n ·.. m>. For start node s, the true costs of minimal cost paths <s ... n>, <n ... t>, and <s ... n ... t>, over all goal nodes t, are denoted by g*(n), h*(n), and f*(n) respectively. The estimators for these functions are g, h, and f respecti .vely. OPEN is assumed ordered by increasing f (and decreasing g in the case of ties). At all times, n' denotes the first (least

f) element of OPEN.

The complexity of A* has been studied in some detail. For perfect h = h*, A* is linear. But in general it has worst case complexity which is expo­ nential as a function of the number of nodes in the found solution path (Pohl, 1970,77). For a large class of problems A* remains exponential in the average case unless h is very precise and remains

unrealistically close to h* (Pearl, 1983).

The sec:."Ond author i e participating in an exchange progt'(Jin between LAAS du CNRS and the Elect1'01tics Research Laboratory, University o f California, Berkeley.

Two drawbacks to A* explain its high complexity. First, A* tends to do much backtracking due to the invariable choice of n' as the node to be expanded next. A* tends to expand many nodes not in the final solution path since h (being a heuristic) fluctuates in quality and h e nce various near optimal paths take random turns appearing to be optimal. Such paths effectively "race" with one another to reach their goals. So we can trace the cause of backtracking to A*'s desire to fine tune an optimal cost solution.

The second drawback is that A* makes no explicit attempt to minimize search cost, i.e. the number of nodes expanded. Given two equally promising paths with respect to path cost, it would seem wise to develop that path which is the fewest arcs from completion. But for A*, it does not matter too much which promising path is developed next since eventually all promising paths must be. Thus A* does not have much need for an explicit heuristic to reduce search cost. Simply put, admissible search is inherently expensive. .

Our basic premise is that a bounded loss of optimality can always be favorably traded for a gain in computational efficiency. The very notion of "cost" and "optimal cost" are imprecise in most applications involving modelling of the real world. Moreover, in heuristic search one often requires only a near optimal or even just decent solution. For example, in robotics, there is a tradeoff between the cost of generating a plan and the optimality of the plan when the plan is to be executed only once.

II AE AND NEAR OPTIMAL PATH SEARCH STRATIGIES

AE drops the strict optimality criteria and seeks instead a solution within a factor (I+E) of optimum for a user specified E ~ 0. This at least makes possible avoiding A*'s defect of having to investigate all optimal looking paths. The problem now becomes -- which of the many near optimal paths merit attention?

AE attempts to answer this question by generalizing A* in two primary ways. First, AE performs a depth oriented search, preferring to stay on a single path as long as a successor to the frontier node (the last one expanded) of that path is "acceptable". An open node n is acceptable iff f(n) is bounded by (I+E)maxjHn'l} over all n' which have appeared as the first element (least f)

in OPEN. To choose an acceptable successor to expand next or, in the case that no such successor exists, to choose which node in OPEN to backtrack to, Af can make use of a second heuristic he- hc(n) provides an explicit guess as to the computational cost involved in reaching a goal node by es timating the minimum number of arcs between n and a goal node.

The second difference between AE and A* is that Af poss esses an inner loop invoked when the frontier node has no acceptable successor. The inner loop attempts to render some successors acceptable by expanding a certain number of times the first node of OPEN, n'. Doing so often (if h is monotone, always) increases f<n') and thus may turn unacceptable nodes into acceptable ones. We refer to this idea as the perserverant strategy of A£. A more precis e specification of A£ is as follows.

Algorithm ~£:

I. 2. 2. I 2.2 2.3 2.4 3. OPEN:= lsl CLOSED:= nil SOLVED:= nil g(s):= 0 f(s):= h(s) £threshold:= (1+f)f(s) Expand(s) AX:= I x E X( s) : Acceptable(x) l do until ((3 t E SOLVED)Acceptable(t) or OPEN = nil) od if AX * nil then n:= SelectAX else n:= SelectOPEN fi Expand(n) do until (( 3 x E X(n))Acceptable(x) od or OPEN =nil or not Perservere) Expand(n') AX:= I x E X(n) Acceptable(x) l if OPEN = nil then failure else fi set t to node of least f(t) 1n SOLVED output path <s ... t> output f' = «1+£) + tthreshold)f<t) - 1 where, Acceptabl e (n) iff n E OPEN and f<n) ~ £threshold Expand(n): OPEN:= OPEN - In l do ( \::f x E X ( n) ) CLOSED:= CLOSED union lnl if x ~ OPEN union CLOSED or g(n)+k(n,x)<g(x) then OPEN:= OPEN union I x l g(x):= g(n ) + k(n,x) fi od f(x):= g(x) + h(x) set a back pointer to keep track of path to x if x is a goal node then SOLVED:= SOLVED union I x l fi £threshold:= max l£threshold,(1+t)f(n') l

Notice output E' which gives the actual relative cost of the found solution with respect t o maxlf<n')l. It is always true that £ 1 ~ E since the output solution (if any) satisfies Acceptabl e .

SelectAX selects which acceptable successor of n is to become the new n. A general approach is to minimize a weighted sum Af<x) + Bhc(x). Since the main purpose here is to stay on a path previously seen to be near optimal, we believe that A should be larger than B. The extreme approach of taking A = 1 and B = 0 leads to a depth oriented best first search and has the advantage of simplifying the main loop-- statement 2.1 can be replaced by

if Acceptable(xmin) then n:= xmin else n:= SelectOPEN fi

where xmin is the open successor of n having least f. And statement 2.4 can be removed entirely.

SelectOPEN has the more diff ic ult task of deciding which acceptable n in OPEN to backtrack to. Again we can minimize some weighted function Cf(n) + Dhc(n) over all n in OPEN. Minimizing f(n) gives us precisely n'. This would lead af ter expansion to raising Ethreshold as much as pos sible hence increasing the likelihood that the developed path will remain acceptable. Minimizing hc(n) moves us closer to a solution but increas es th e risk that the inner loop may have to abandon th e selected path soon thus provoking backtracking. Nevertheless, we argue that SelectOPEN should place importance on he since the inner loop will be capable of raising €threshold. In general, experimentation should help determine weights for f and he in any specific application.

The perserverant strategy of A6 is embodied in the predicate Perservere, the heuristic element of the inner loop. Perservere should return true as long as it seems wise to try to render at least one of the successors of n acceptable, i.e . to perser­ vere on the current path. We list below factors which would indicate that doing so is worthwhil e .

• n has a successor which is "almost" acceptable.
• n has a successor close to a goal (he small).
• The second or third best f(n) over n in OPEN is significantly greater than f(n').
• -The inner loop has iterated few times.
• A node already in SOLVED is almost acceptable (n' should be expanded to try rendering a found goal acceptable).
• (l+ f )f(n') = £threshold. If h is monotone this will always be true so this condition would not be useful in that case .

Notice that A* halts when it runs into a goal node as first element of OPEN whereas A£ continually surveys all generated goal nodes and explicitly attempts to render one or more of them acceptable.

For search in a 8-graph (one in which no infi­ nite path has finite cost) where a path from s to a goal node exists, the following properties of A, hold. See (Ghallab, 1982) and (Ghallab and Allard, 1982) for proofs and discussion.

I. A1 halts after finding a goal node t satisfying Acceptable(t).

2. If for some 0 .:;:: h ( n) ..:;:: ( 1 +e )h * ( n) for found goal node t satisfies fixed constant e, all nodes n, then the f<t) .:;:: (1+e)(1+ E' )h*( s).

Taking e = 0 in the above result and noticing that ,· .:::: < gives:

3 . If h is admissible then A, is E- admissible .

4. If h is monotone then f(n') increases monotonically and, for all expanded n, g*(n) .:::: g(n) ~ (1+ r)g*(n) + f h(n).

Le t us briefly mention how Ac differs from A,* (Pe arl and Kim, 1982). A,* is like A* except that A1 * e xpands the node with least he among all n in OPEN satisfying E<n) ..:;:: (1+l)f(n'). This last condition is more restrictive than our Acceptable predicate. But most importantly, A,* uses neither depth oriented search nor a perserverant strategy (no inner loop) and hence may perform unnecessary backtracking. Also, if a good he is not available, A, is only partially handicapped (see SelectOPEN) and can still perform depth oriented search, whe r eas A,* simply reduces to A*.

III EXPERIMENTAL RESULTS AND CONCLUSION

We have tested the behavior of A( on TSP (the travelling salesman problem) under the same test c onditions (N = 9 cities randomly distributed uniformly in the unit square) and using the same heuristics h and he as (Pearl and Kim, 1982). Tests were made on sixty different distributions of cities. For each test A, was run with f set succ e ssively to 0, 0.01, 0.05, 0.10, 0.15, 0.25, and oo ( f = 0 yields the optimum solution; E = oo yi e lds a solution in the minimum number of steps -­ exactly N-2 nodes are expanded).

Table indicates the computational effort e xe rted by A,. Three complexity indicators were employed : E, the number of nodes expanded, G the number of . nodes generated, and B ,the number of times A 1 had to backtrack (switch paths). Table 2 gives the actual cost of the solutions obtained and ·', the guarantee returned by AE of the degree of optimality of the solutions. All figures (,· excepted) are given relative to their values for = 0 (corresponding to what A* would do). The numbers in parentheses give the standard deviation u for the corresponding mesures.

Notice that for all indicators (Table 1), compu­ tational cost decreases rapidly wi thi nc reas ing E (from exponential complexity for E = 0 down to linear complexity for f = oo ). The obtained results compare favorably with those of (Pearl and Kim, 1982, Fig. 4) shown as E' in Table I below.

As Table 2 shows, the actual solution costs remain quite near optimal. It is interesting that with c = oo , the found solution ~s guaranteed to be within 27% of optimal.

I !

I

.I

To obtain completeness with respect to Pearl's results we also tested A 1 on "difficult problems" in which intercity distances are confined to the interval (0,75,1.25). In 25 test cases, as soon as < exceeded .05, no backtracking was ever performed. Our results fo~ number of nodes developed are similar to those of Pearl (c.f. his Fig. 6); E = 81 and 28 for r = . 01 and .05 respectively.

These results compare A, favorably to A* and to A,*. We are currently conducting further tests on TSP and other search problems in order to experiment with the search strategies discussed ~n section I I.