All language subtitles for 03_1-4-a-algorithm.en

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) <= H(y) + d(x,y).

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.