Page 381 - Introduction to AI Robotics

364
Metric Path Planning
10
of how it is visualized, each node is evaluated to determine which is the
most plausible move. The above figure shows what the algorithm “sees” at
this point in the execution. The choices evaluate to:

f (B) = g (B) h (B) +24= :24 = 1 + 2
:
3

f (D) = g (D) h (D) :4 + :4 :8 = + = 1 1 2
A path going from A D ? E has the potential to be shorter than a
path going from A B ? E.So, D is the most plausible node. Notice
that A* can’t eliminate a path through B because the algorithm can’t “see” a
path that actually goes from D to E and determine if it is indeed as short as
possible.
At step 2, A* recurses (repeats the evaluation) from D,since D is the most
plausible, as shown in Fig. 10.10.
The two options from D are E and F, which are evaluated next:

f (E) = g (E) h (E) :8 + :8 = + 0 2 = 2

f (F ) = g (F ) h (F ) :4 + :0 :4 = + = 1 2 3
Now the algorithm sees that E is the best choice among the leaves of the
search tree, including the branch through B.(If B was the best, then the
algorithm would have changed branches.) It is better than F and B.When it
goes to expand E, it notices that E is the goal, so the algorithm is complete.
The optimal path is A D E, and we didn’t have to explicitly consider
A B F E. There are other ways to improve the procedure described

so far. f (F ) didn’t need to be computed if the algorithm looks at its choices
and sees that one of them is the goal. Any other choice has to be longer
because edges aren’t allowed to be negative, so D F E has to be longer
than D E.
Another important insight is that any path between A and E has to go
through D,so the B branch of the search tree could have been pruned. Of
course, in the above example the algorithm never had an opportunity to no-
tice this because B was never expanded. It’s easy to imagine in a larger graph
that there might be a case where after several expansions through D,the leaf
at B in the search tree came up the most plausible. Then the algorithm would
have expanded A and seen the choices were D.Since D already occurred in

another branch, with a cheaper g (D),the B branch could be safely pruned.