--- title: "Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm" authors: - "Malik Ghallab" - "Dennis G. Allard" doi: "" url: "https://ijcai.org/proceedings/1983/192" pdf: "https://ijcai.org/proceedings/1983/0192.pdf" venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence" year: 1983 pages: "789-790" track: "Planning and Search" keywords: --- # Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm Malik Ghallab, Dennis G. Allard *Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 789-790. ## 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 doesnot 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 (E0). 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 e nted indicating that AE has average complexity of lower order than A* and compares favorably to the related algorithm AE* (Pearl and Kim, 1982). ## Full text ## 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 output f' = «1+£) + tthreshold)f