Original subtitles

So far we've talked about two procedures for

planning paths to graphs, the Grassfire Algorithm and Dijkstra's Algorithm.

Both of them work perfectly fine in practice.

They both find the shortest path when one exists and

report failure when one doesn't.

However, both algorithms may end up visiting all or most of the nodes

in the graph, and this can be a problem when you have a large member of nodes.

It turns out that from many motion planning problems,

we can exploit the structure of the problem to come up with

procedures that arrive at good solutions more quickly.

The A* Algorithm is a well know, and

well loved, algorithm that exemplifies this idea.

A* is actually an example of a broader class of procedures

called best first search algorithms.

Which explore a set of possibilities by using an approximating

heuristic cost function to sort the varies alternatives and

then inspecting the options in that order.

The algorithm is very similar to Dijkstra's procedure, and Grassfire, in

that it actually precedes by maintaining a list of nodes that it is investigating.

When we are planning on simple grids, both Grassfire and Dijkstra's Algorithm have

a similar behavior, since all the edges between the nodes are reviewed at length.

Both algorithms end up visiting nodes

based on their distance from the start node.

Here's a little movie that visualizes this behavior.

In this movie, the red cells correspond to nodes that the algorithm has visited,

while the blue nodes correspond to nodes that are on the list,

that are about to be explored.

Notice how the activation of pattern of the algorithm spreads

outward from the start node, evenly in all directions.

If we look at this video, we notice that the Dijkstra/Grassfire Algorithm

basically explores evenly in all directions until it finds the gold node.

It seems that we could do a little bit better here,

since we actually know where the destination is, and

we have some idea which directions may prove to be more fruitful.

The A* Algorithm introduces the idea of a heuristic distance,

which is an estimate for the distance between a given node and the goal node.

And we can use this information to help guide the search

into directions that we think might get it to the goal quicker.

Note, that as with any heading heuristic, we may be wrong.

And there can in fact be situations where the shortest path towards a goal involves

heading in exactly the opposite direction.

However, in many cases, we can come up with informative heuristics

that cause the algorithm to explore more efficiently.

More formally, for

the shortest path problem we're interested in heuristic functions, H.

Which given a node n return a non-negative value

that is indicative of the distance from that node to the goal.

For path finding problems, we often use heuristic functions that are monotonic,

which means that they satisfy the following two properties.

We say that H applied to the goal node returns as 0, which makes sense,

and that for any two nodes, x and y, that are adjacent in the graph,

H(x)

Where d(x,y) denotes the length of the edge between those two nodes x and y.

Given these two properties, it's actually not hard to show that

the heuristic function H(n) serves as an underestimate for

the distance between the node n and the goal.

Here are two heuristic functions that are commonly used for

solving path finding problems on two dimensional grids.

In these expressions xn and yn denote the position of the node in the 2D grid,

while xg and yg denote the coordinates of the goal location in that same grid.

This slide shows a pseudo code for the A* Algorithm.

Note that it is actually very similar in structure to Dijkstra's algorithm.

We associate two numerical attributes with each of the nodes in our graph.

A g value, which indicates the distance between the current node and

the start location, and an f value, which is the sum of the node g value and

the heuristic cost associated with that node.

In other words, it's the sum of the distance between the node and

the start and the estimate for

how much distance is left to go between that node and the goal location.

On every iteration of this algorithm,

the system chooses the node with the smallest associated f value.

That is, it attempts to choose the node

that is most likely to be on the shortest path between the start and the goal node.

Once again, once a node is chosen, the f and

g values associated with each of its neighbors are updated.

In other words, on each iteration, we're trying to pick the node

that is most likely to be on the shortest path from the start to the destination.

We then update the neighbors of those chosen node and

repeat the process until we encounter the goal node or run out of nodes to consider.

This slide shows the progress of the A* Algorithm.

Once again red nodes indicate nodes that the algorithm has visited,

while blue nodes indicate nodes that are on the list

of nodes to be considered on the next iteration.

Notice that this algorithm tends to focus its attention

more directly on nodes that are closer to the destination node, as intended.

Let's compare its performance to that of Dijkstra's Algorithm,

which we saw earlier.

Note how much more diffuse the activity of the Dijkstra's Algorithm is,

when compared to that of the A* Algorithm.

Where Dijkstra's Algorithm effective explores in all directions uniformly,

the A* Algorithm uses its heuristic to focus its efforts

on nodes that appear to be closer to the goal.

Hence it gets there much quicker in this example.

For relatively uncluttered environments like this one, A* can be substantially

faster in practice than the uniform search algorithms like Dijkstra's and Grassfire.

This performance boost can be particularly useful

in environments where we may have tens of thousands of nodes, for instance,

if we're planning a path to guide a robot from one end of a building to another.

In the worst case, the performance of A* is about the same as Djikstra's.