ABSTRACT

Recently there has been a renewed interest in AO* as planning problems involving

uncertainty and feedback can he naturally formulated as AND/OR graphs. In this

work, we carry out what is prohably the first detailed empirical evaluation of AO*

in relation to other AND/OR search algorithms. We compare AO* with two other

methods: the well-known Value Iteration (VI) algorithm, and a new algorithm,

Learning in Depth-First Search (LDFS). We consider instances from four domains.

usc three different heuristic functions, and focus on the optimization of cost in the

worst case (Max AND/OR graphs). Roughly we find that while AO* does better

than VI in the presence of informed heuristics, VI does better than recent

extensions of AO* in the presence of cycles in the AND/OR graph. At the same

time, LOFS and its variant Bounded LOFS, which can be regarded as extensions of

IDA*, are almost never slower than either AO* or VI, and in many cases, are

orders-of-magnitude faster.
Introduction

A* and AO* are the two classical heuristic bestfirst algorithms for searching OR
and AND/OR graphs (Hart, Nilsson, & Raphael 1968; Martelli & Montanari 1973;
Pearl 1983). The A* algorithm is taught in every AI class, and has been studied
thoroughly both theoretically and empirically. The AO* algorithm, on the other
hand, has found less uses in AI, and while prominent in early AI texts (Nilsson
1980) it has disappeared from current ones (Russell & Norvig 1994). In the last
few years, however, there has been a renewed interest in the AO* algorithm in
planning research where problems involving uncertainty and feedback can be
formulated as search problems over AND/OR graphs (Bonet & Geffner 2000).

A* algorithm
In computer science, A* (pronounced "A star") is a best-first graph search
algorithm that finds the least-cost path from a given initial node to one goal node
(out of one or more possible goals).

It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine

the order in which the search visits nodes in the tree. The distance-plus-cost
heuristic is a sum of two functions:

 the path-cost function, which is the cost from the starting node to the current
node (usually denoted g(x))
 and an admissible "heuristic estimate" of the distance to the goal (usually
denoted h(x)).

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must
not overestimate the distance to the goal. Thus for an application like routing, h(x)
might represent the straight-line distance to the goal, since that is physically the
smallest possible distance between any two points (or nodes for that matter).

If the heuristic h satisfies the additional condition for every

edge x, y of the graph (d denoting the length of that edge) then h is called
monotone or consistent. In this case A* can be implemented more efficiently —
roughly speaking, no node needs to be processed more than once (see closed set
below) — and in fact A* is equivalent to running Dijkstra's algorithm with the
reduced cost d'(x,y): = d(x,y) − h(x) + h(y).
The algorithm was first described in 1968 by Peter Hart, Nils Nilsson, and Bertram
Raphael.

This algorithm has been generalized into a bidirectional heuristic search algorithm;
see bidirectional search.

Conceptual explanation
A* is a network searching algorithm that takes a "distance-to-goal + path-cost"
score into consideration. As it traverses the network searching all neighbors, it
follows lowest score path keeping a sorted priority queue of alternate path
segments along the way. If at any point the path being followed has a higher score
than other encountered path segments, the higher score path is abandoned and a
lower score sub-path traversed instead. This continues until the goal is reached..

Algorithm description

A single-step simulation

Like all informed search algorithms, it first searches the routes that appear to be
most likely to lead towards the goal. What sets A* apart from a greedy best-first
search is that it also takes the distance already traveled into account (the g(x) part
of the heuristic is the cost from the start, and not simply the local cost from the
previously expanded node).

Starting with the initial node, it maintains a priority queue of nodes to be traversed,
known as the open set (not to be confused with open sets in topology). The lower
f(x) for a given node x, the higher its priority. At each step of the algorithm, the
node with the lowest f(x) value is removed from the queue, the f and h values of its
neighbors are updated accordingly, and these neighbors are added to the queue.
The algorithm continues until a goal node has a lower f value than any node in the
queue (or until the queue is empty). (Goal nodes may be passed over multiple
times if there remain other nodes with lower f values, as they may lead to a shorter
path to a goal.) The f value of the goal is then the length of the shortest path, since
h at the goal is zero in an admissible heuristic. If the actual shortest path is desired,
the algorithm may also update each neighbor with its immediate predecessor in the
best path found so far; this information can then be used to reconstruct the path by
working backwards from the goal node. Additionally, if the heuristic is monotonic
(or consistent, see below), a closed set of nodes already traversed may be used to
make the search more efficient.

Pseudo code

function A*(start,goal)
closedset := the empty set % The set of nodes already evaluated.
openset := set containing the initial node % The set of tentative nodes to be
evaluated.
g_score[start] := 0 % Distance from start along optimal path.
h_score[start] := heuristic_estimate_of_distance(start, goal)
f_score[start] := h_score[start] % Estimated total distance from start to goal
through y.
while openset is not empty
x := the node in openset having the lowest f_score[] value
if x = goal
return reconstruct_path(came_from,goal)
remove x from openset
add x to closedset
foreach y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] + dist_between(x,y)

if y not in openset
add y to openset

tentative_is_better := true
elseif tentative_g_score < g_score[y]
tentative_is_better := true
else
tentative_is_better := false
if tentative_is_better = true
came_from[y] := x
g_score[y] := tentative_g_score
 h_score[y] := heuristic_estimate_of_distance(y, goal)
f_score[y] := g_score[y] + h_score[y]
return failure

function reconstruct_path(came_from,current_node)
if came_from[current_node] is set
p = reconstruct_path(came_from,came_from[current_node])
return (p + current_node)
else
return current_node

The closed set can be omitted (yielding a tree search algorithm) if a solution is
guaranteed to exist, or if the algorithm is adapted so that new nodes are added to
the open set only if they have a lower f value than at any previous iteration.

Example
An example of A star (A*) algorithm in action (nodes are cities connected with
roads, h(x) is the straight-line distance to target point).

Key: green: start; blue: goal; orange: visited

Note: This example uses a comma as the decimal separator.

Properties
Like breadth-first search, A* is complete in the sense that it will always find a
solution if there is one.

If the heuristic function h is admissible, meaning that it never overestimates the

actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if
we do not use a closed set. If a closed set is used, then h must also be monotonic
(or consistent) for A* to be optimal. This means that for any pair of adjacent nodes
x and y, where d(x,y) denotes the length of the edge between them, we must have:

This ensures that for any path X from the initial node to x:

where denotes the length of a path, and Y is the path X extended to include y.
In other words, it is impossible to decrease (total distance so far + estimated
remaining distance) by extending a path to include a neighboring node. (This is
analogous to the restriction to nonnegative edge weights in Dijkstra's algorithm.)
Monotonicity implies admissibility when the heuristic estimate at any goal node
itself is zero, since (letting be a shortest path from any
node f to the nearest goal g):

A* is also optimally efficient for any heuristic h, meaning that no algorithm

employing the same heuristic will expand fewer nodes than A*, except when there
are multiple partial solutions where h exactly predicts the cost of the optimal path.
Even in this case, for each graph there exists some order of breaking ties in the
priority queue such that A* examines the fewest possible nodes.

Special cases
Generally speaking, depth-first search and breadth-first search are two special
cases of A* algorithm. Dijkstra's algorithm, as another example of a best-first
search algorithm, is the special case of A* where h(x) = 0 for all x. For depth-first
search, we may consider that there is a global counter C initialized with a very
large value. Every time we process a node we assign C to all of its newly
discovered neighbors. After each single assignment, we decrease the counter C by
one. Thus the earlier a node is discovered, the higher its h(x) value.
Implementation details
There are a number of simple optimizations or implementation details that can
significantly affect the performance of an A* implementation. The first detail to
note is that the way the priority queue handles ties can have a significant effect on
performance in some situations. If ties are broken so the queue behaves in a LIFO
manner, A* will behave like depth-first search among equal cost paths. If ties are
broken so the queue behaves in a FIFO manner, A* will behave like breadth-first
search among equal cost paths.

When a path is required at the end of the search, it is common to keep with each
node a reference to that node's parent. At the end of the search these references can
be used to recover the optimal path. If these references are being kept then it can be
important that the same node doesn't appear in the priority queue more than once
(each entry corresponding to a different path to the node, and each with a different
cost). A standard approach here is to check if a node about to be added already
appears in the priority queue. If it does, then the priority and parent pointers are
changed to correspond to the lower cost path. When finding a node in a queue to
perform this check, many standard implementations of a min-heap require O(n)
time. Augmenting the heap with a hash table can reduce this to constant time.

Why A* is admissible and computationally optimal

A* is both admissible and considers fewer nodes than any other admissible search
algorithm with the same heuristic, because A* works from an “optimistic” estimate
of the cost of a path through every node that it considers — optimistic in that the
true cost of a path through that node to the goal will be at least as great as the
estimate. But, critically, as far as A* “knows”, that optimistic estimate might be
achievable.

Here is the main idea of the proof:

When A* terminates its search, it has, by definition, found a path whose actual cost
is lower than the estimated cost of any path through any open node. But since those
estimates are optimistic, A* can safely ignore those nodes. In other words, A* will
never overlook the possibility of a lower-cost path and so is admissible.

Suppose now that some other search algorithm B terminates its search with a path
whose actual cost is not less than the estimated cost of a path through some open
node. Algorithm B cannot rule out the possibility, based on the heuristic
information it has, that a path through that node might have a lower cost. So while
B might consider fewer nodes than A*, it cannot be admissible. Accordingly, A*
considers the fewest nodes of any admissible search algorithm that uses a no more
accurate heuristic estimate.

This is only true if

 A* uses a admissible heuristic. Otherwise, A* is not guaranteed to expand

fewer nodes than another search algorithm with the same heuristic. See
(Generalized best-first search strategies and the optimality of A*, Rina
Dechter and Judea Pearl, 1985[2])

 A* solves only one search problem rather than a series of similar search
problems. Otherwise, A* is not guaranteed to expand fewer nodes than
incremental heuristic search algorithms. See (Incremental heuristic search in
artificial intelligence, Sven Koenig, Maxim Likhachev, Yaxin Liu and David
Furcy, 2004)

Complexity
The time complexity of A* depends on the heuristic. In the worst case, the number
of nodes expanded is exponential in the length of the solution (the shortest path),
but it is polynomial when the search space is a tree, there is a single goal state, and
the heuristic function h meets the following condition:

| h(x) − h * (x) | = O(logh * (x))

where h * is the optimal heuristic, i.e. the exact cost to get from x to the goal. In
other words, the error of h should not grow faster than the logarithm of the “perfect
heuristic” h * that returns the true distance from x to the goal (see Pearl 1984[4] and
also Russell and Norvig 2003, p. 101[5])

AO*
AO* is a bestfirst algorithm for solving acyclic AND/OR graphs (Martelli &
Montanari 1973; Nilsson 1980; Pearl 1983). Starting with a partial graph
Gcontaining only the initial state s0, two operations are performed iteratively: first,
a best partial policy over Gis constructed and a nonterminal tip state sreachable
with this policy is expanded; second, the value function and best policy over the
updated graph are incrementally recomputed. This process continues until the best
partial policy is complete. The second step, called the cost revision step, exploits
the acyclicity of the AND/OR graph for recomputing the optimal costs and policy
over the partial graph Gin a single pass, unlike Value Iteration (yet see (Hansen &
Zilberstein 2001)). In this computation, the states outside Gare regarded as
terminal states with costs given by their heuristic values. When the AND/OR graph
contains cycles, however, this basic costrevision operation is not adequate. In this
paper, we use the AO* variant developed in (Jimen´ez & Torras 2000), called
CFCrev∗ , which is based in the cost revision operation from (Chakrabarti 1994)
and is able to handle cycles.
Unlike VI, AO* can solve AND/OR graphs without having to consider the entire
state space, and exploits lower bounds for focusing the search. Still, expanding the
partial graph one state at a time, and recomputing the best policy over the graph
after each step, imposes an overhead that, as we will see, does not always appear to
pay off.

AO* has rarely been used in practical applications, to my knowledge. It is useful

for searching game trees, problem solving etc. but in most cases more domain
specific search algorithms (e.g. alpha-beta pruning for game trees, general or
domain specific planning algorithms) are used instead.

In particular, AI uses knowledge-intensive approaches and in practical applications

heavy use is made of domain specific knowledge or problem conditions to produce
better (faster or more optimal solutions).

Game search is an example where full-breadth search is standard, but this may
because of the small (relative to other domains) size of the search space. Even in
game tree search, extensive use is made of problem specific features, i.e. often
search is terminated only in quiescent states (i.e. not during a forced exchange or
when there is a check).

In planning, often knowledge is used to guide a search of a generated solution

space rather than doing a state space search. This gives non-optimal solutions but
for many domains it yields reasonable solutions at much less cost.
 CONTENTS
 Introduction

 Conceptual explanation

 Algorithm description

 Pseudo code

o 1 Example

 Properties

o Special cases

o Implementation details

 Why A* is admissible and computationally optimal

 Complexity

 Variants of A*

 AO*