Page 377 - Introduction to AI Robotics

360
10
Metric Path Planning
been a great deal of interest in path planners which do a “branch and bound”
style of search; that is, ones which prune off paths which aren’t optimal. Of
course, the trick is knowing when to prune!
The A* search algorithm is the classic method for computing optimal paths
for holonomic robots. It is derived from the A search method. In order to
explain how A* works, A search will be first presented with an example, then
A*. Both assume a metric map, where the location of each node is known in
absolute coordinates, and the graph edges represent whether it is possible to
traverse between those nodes.
The A search algorithm produces an optimal path by starting at the initial
node and then working through the graph to the goal node. It generates the
optimal path incrementally; each update, it considers the nodes that could
be added to the path and picks the best one. It picks the “right” node to add
to the path every time it expands the path (the "right node” is more formally
known as the plausible move). The heart of the method is the formula (or
evaluation function) for measuring the plausibility of a node:

f(n) g(n) h(n) = +

where:
f(n) measures how good the move to node n is

g(n) measures the cost of getting to node n from the initial node. Since A
expands from the initial node outward, this is just the distance of the path
generated so far plus the distance of the edge to node n

h(n) is the cheapest cost of getting from n to goal
Consider how the formula is used in the example below. Assume that a
Cspace representation yielded the graph in Fig. 10.8.
The A search algorithm begins at node A, and creates a decision tree-like
structure to determine which are the possible nodes it can consider adding
to its path. There are only two nodes to choose from: B and C.
In order to determine which node is the right node to add, the A search
algorithm evaluates the plausibility of B and C by looking at the edges. The
plausibility of B as the next move is:

:
f(B) g(B) h(B) = : +24=3 =24 1 + 2
where g(B) is the cost of going from A to B,and h(B) is the cost to get from
B to the goal E.