On A* as a Special Case of Ordered Search

ABSTRACT

The A· admissibility and optimality proofs presented to date have been based on overly restrictive assumptions about the relation­ ship between real and estimated costs. This paper shows that ideal­ ism, accuracy and se lectivity, properties hitherto thought to be unique to A · , are in fact common to all ordered searches, and do not require the eval uation function I= g+ h traditionally assumed. Consequently , rnuch of A· theory can be greatly simplifi ed.

INTRODUCTION

It is shown that many of the properties hi therto thought to be uniq;re to A· can be proven without recourse to the evaluation func­ tion 1 = g+ h. This permits greatly simplified statements of several well-known results. Moreover, it implies that A·'s properties ori­ ginate largely from the ordered search algorithm itself, rather than from the internal structu re imposed on the evaluation hnction.

The evaluation function I= g+ h was traditionally adopted as a theoretical construction permitting demonstration of A· 's admissi­ bi lity and optimality, when estimates ~ of h were bounded by 0 ~ 1i < h. This decomposition into forward and backward cost com­ po-;;-ents, the linearity of j and the non-negativity of g and ~. together comp ri se the "path-cost paradigm" which forms the basis of A· theory.

T he contribution of this paper is a clearer understanding of the roots of A· behaviour. It begins by showing that the preconditions im­ posed on 7i are overly rest rictive: they are sufficient but not necessary. lienee the path-cost paradigm is refuted . Following on this, the con­ cepts of idealism, accuracy and selectivity - the foundations or the rev ised theory - are defined . The paper concludes by demonstrating how the resulting theory , which for the most p:ut applies to the gen­ eral ordered search, reduces to A· theory as a special case.

II REFUTING THE PATH-COST PARADIGM

The addition or the same constant to the J estimates or all nodes makes no difference to the behaviour or A·. This conclusion may be restated in a more general form (proofs are trivial):

Theorem (equivalence): Let~ and~ be evaluation functions whose values always have identical partial orderings, for any set of open nodes and for any graph. Then A· using~ can close precisely the same nodes as A· using~ -

This research was performed at the Department or Computer Science, Aus tralian National University, Canberra, Australia.

Marcel J. Schoppers University of Illinois at Urbana-Champaign Department of Computer Science 1304 W. Springfield Ave Urbana, TL 61801, U.S.A.

The Coroll aries suggest some novel questions about the natu re and riJie of A·'~ evaluation function. In that capacity they motiv ate the ensu ing discussion.

Corollary 2: A· u si ng~ > h can be admissible.

Therefore, A· can preserve its admissibility for a far wider class of heur istics than is generally supposed. Moreover,

Hence A·'s optimality must originate from something other than the traditional concept or informcd ness (involving, by definition, the relative magnitudes of two~ estimators).

The Equivalence Theorem thus opens two issues. Firstly, the admiss il>ility condition 0 ~ 7i ~ h docs result in admissible behaviour but only because it happens to entail some other, more fundamcn~a! condition which can hold even when 0 :"::: h ~ h docs not. Secondly , and in similar vein , the magnitude of h is not an apt guage of " i n formcdne~s" for opt imali ty proof~. The next section dis­ covers what it is about these cond itions that makes A· admissib le and optimal.

Ill ELEMENTS OF A· BEHAVIOUR

The A· algorithm never deals with real costs: it relies solely on J estimates. Therefore, it seems strained to begin the study of A· by assuming the relation 0 ~ h ~ h between real and estimated costs.

The algorithm is equally unconcerned about the decomposition of J as g+ t Only t he sum, f. is relevant to the order in which nodes arc selected for expansion.

Also, A· is usually discussed in the context of delta-graphs; i.e. directed (possibly infinite) graphs such that the cost of traversing an arc is at least some small positive quantity (delta). However, ordered search is concerned with the !-values attached to open nodes, not with forward and backward path costs. Therefore it is more in accord with the algorithm to think in terms or weighted nodes rather than weight­ ed arcs, and the delta-graph assumption may be relinquished (for the moment).

Lastly, though tbe search may be . c 11 .. ,uea as traversing a problem-space whose states and operations define a graph, the algo­ rit hm itself generates a tree . Even if one state recurs many times, A·

generates a diffen·nt node for each occurrence, and each node is weighted by one of the various [-values assoc iated with thJ.t state .

For the purposes of this paper, visualise A* as traversing a (possibly infinite) t ree hJ.ving numerical weights attached to its nodes. Those weights may be quite arbi trary , being ].values. Also attach a second "layer" of weigh ts to the nodes, as their real weighting f. Now se lect a subset of the nodes to be goJ.b, and select from them a small­ er subset or goals hav ing minimall-values. Then the following termi­ nology appli ~s.

Definition: A solution path is any path lead ing from the start node to a goal node.

Definition: A goal node is ].optimal if it has the minimal .-alue off among the goal set.

Definition: A solution path is ]. op timal if it leads to an J­ opt im:1l goal.

In the tradition:.tl admissibility proofs, 0 ~ ~ ~ h was imposed to guarantee l(n) ~ f (s) for all nodes non an [-optimal solution path. Th is <:omparison bet W<'r n real and estimated path costs may be elim­ inated as follows. Let p(s, t) be any [-optimal solution path from s tot.

Defi ni tion: A· is [-idealist ic if it cannot, in any graph, ter­ minate with a solution path that is not f optimal.

Lemma (idealism): If [(n) ~ [(t) \fnEp(s,t) then A· is !­ idealistic. The proof is trivial: since A* always chooses the open node of lowest 1. all nodes on p(s, t) must be closed before any fnon-optimal goal.

Notice th at this Lemma ignores the internal structure off­ only its value is relevant .

II ow ever , there is no longer any guarantee that f opt imal paths will also be /-optimal. T he correspondence between ].optimal and /­ optimal paths can be restored by analysing the concept of informed­ ness.

C. Accuracy

Traditionally , the inequ ality h 1 < h 2 implied that h 2 was a closer app rox imation to h, from which it could be proYen that ~ 2 could not be less efficient than ~~- However, Corollary 3 shows that a comparison between the relative magnitudes or two heuristics is not an adequate indication or their efficiencies.

At this point is necessary to distinguish the notions of selectivi­ ty and accuracy. While some heuristics will guide A· to an /-optimal path (they are accurate), they may not be very efficient (they have low selectivity). Conversely , other heuristics can lead A· to an /­ non-optimal goal (by being inaccurate) via a minimal number of nodes (good select ivity). Accuracy is thus a correlation between real and e~ timated weightings, while selectivity is an efficiency relation between two estimated weightings. Both these concepts were included in the term "informcdness".

• Definition: Aj is at least as selective as A; if every node closed by A j is also closed by A;.
• Definition: A· is accurat e if it cannot, in any graph, ter­ minate with a solution path that is not f-optimal .

We are now in a position to corellate real and estimated weightings, preferably as loosely as possible Ych ile still ensuring that an !-opt imal path will be found . Again, proof of the Lemma is trivial.

Lemma (accuracy) : If the set or f-optimal goals is a (non­ empty) subset of the set off-optimal goals, and if A* is J. idealistic, then A· is accurate.

D. Selectivity

Finally , let us devise a generalised performance yardstick . Sup­ pose that 1, and 1 2 are strictly monotonic increasing evaluation func­ tions used m { wo searches over the same graph, and that they result in termination with the same goal node t. Coroll ary 1 shows that any search using P' = f - J.(t) + ~(t) will also find an !-optimal path . Since P' is strihtty ~onotonic increasing, all nodes h;ving ft' -values below fr (t) will be closed by A·. Likewise, all nodes having /. 2 -values A\ I A p, ~clow ! 2 \t) will be closed by At But because f 2 (t) = r 1 (t) , if also f. (n) < P' (n) Vnolt , then A; closes at least all the nodes closed by ;{. _ Substituting for f- 1 and rearranging, J, is at least as selectiYe as~ wtencver

As soon more general evaluation functions are permitted , "cri t­ ical ties" l3p. 100I must be dealt with . Gelperin 121 formulated two Theorems to avoid this problem. At bottom, both Theorems required that for the less sel ective~· ~(n) < ~(t) for all n on some ~-optimal path . Under this condition crittcal ties cannot arise.

Once critical ties have been eliminated it can be seen that (1) rem:>ins valid even for non-monotonic evaluation fun ctions. This e~ tablishes the following:

Theorem (selectivity): For any graph containing solution paths p 1 , p 2 (possibly p 1 = p ) to a goal t which is both f. -optimal and ~-optimal, if "(n) ~ J.(t) V'nEp 1 (s,t) and ~(n) < ~(t) \fnE{p 2 (s,t)-t}, then J. is at least as selective as~ whenever ( 1) holds.

As a simple consequence: regardless of the nature of J. increas­ ing the [-weight of any non-goal node cannot result in A·'s closing more nodes.

Again, this Selectivity Theorem ignores the internal structure or J It also says nothing about the real weighting. This is counter­ intuitive because it imp iies that

1. an unrealistic evaluation function can be optimally selec­ tive;
2. the "perfect" evaluation function is not necessarily the most selec tive .

Both implications are correct, but the original concept of informed­ ness could not do justice to either.

Concerning the first point, take the perfect evaluation function I and subtract some arbitrary positive numbers from the weights of the nodes on some f-optimal path. The result is clearly unrealistic, but the search using that evaluation function is nevertheless optimal.

Secondly, when there are several /-optimal paths A · can choose to expand a node on auy one of them, since the traditional I gives all nodes on all !-optimal paths the same value l(s). Reducing the weights of nodes on one !-optimal path forces A· to close only the nodes on that path. Hence unrealistic evaluation functions can be more selective than the most realistic one.

A. Ordered Search Theory

As shown above, idealism, accuracy and selectivity - proper­ ties hitherto thought to be peculiar to A·- can be generali'led to ap­ ply to ordered search behaviour. The internal structure of f is ir­ relevant to these properties, which can therefore be easily demonstrat­ ed without recourse to elaborate proofs.

The disproportionate extent to which the path-cost paradigm has been allowed to permeate A· theory can be seen from work on quant ifying A· performance [1,7] . lnformedness was understood as an h magnitude comparison; yet the concept of selectivity rests neither on such informedness nor on path costs.

B. Completen ~1:!.

However, if termination is not a~sured, neither is an optimal solution path. To realise the admissibility of A· it is necessary to add tl1e ''completeness" property. Here the path-cost paradigm has its only justificat ion: completeness is the only property possessed by A· which has no origin in the general ordered search.

Defin ition: A· is complete if, for any graph, it terminates with a solution path whenever one exists.

Lemma (completeness): A· using J = g+ ~ is complete on any delta-graph.

Defin ition: A· is admissible if, for any graph containing solu­ tion paths, it terminates with an /-optimal solution path.

Theorem (admissibility): If A· is accurate and complete, then A· is admissible.

C. Derivation of A· Results

This perspective provides a closer affinity between theoretical precond it ions and search behaviour. It is easy to see how J = g+ h is comp lete on delta-graphs; how f(n) ~ f(t) \lnEp(s,t) results in ideal­ ism; and how accuracy is guaranteed if the set of foptimal goals is a subset of the set of /-optimal goals. Admissibility is simply the con­ junction of these conditions. Then A· will find a goal if one exists; that goal will be fopt imal ; and therefore it will also be /-optimal.

To show that A· theory is a special case of this ordered-search perspective, substitute J = g+ h into the Idealism condition and rear­ range to get

Now if h (t) is zeroed, this reduces to ~ ~ h (for n on an /-optimal path, not n eces~arily in general!).

Next, it is easy to show that J = g+ h is accurate if h = 0 at goal nodes. For then ,

for all goals t , with equality only for f-optimal paths to t.

Finally, the informed ness condition ~I < ~ can be derived from the Selectivity Theorem by noting that when i (t) = ~ (t) = 0, J\(t) = ~(t) = /(s); and since g 1 (n) = g 2 (n) for an/ given n 2 ode n in t 1e search tree, the result is immediate.