All language subtitles for 01_1-2-grassfire-algorithm.en

In the example that we've been talking
about so far, what we want to do,

is come up with a procedure
that the computer can use

to guide the robot from its start
location to its end location,

while minimizing the total number
of steps that are performed.

For this particular problem,

where we're planning paths on the grid,
it turns out that we can employ

a particularly simple procedure known as
the grassfire, or brush fire, algorithm.

Conceptually, we're going to
begin by marking the destination

node with a distance value of 0.

Then, we find all of the nodes that are 1
step away from the destination, and

mark them with a 1.

Then, all the nodes that are 2 steps away,
mark them with a 2..

All of the nodes that are 3 steps away,
mark with a 3, etc, etc,

etc, until we encounter the start node.

For every cell in the grid,

the distance value that it gets marked
with indicates the minimum number of steps

that it would take to go from that
point to the destination node.

Note how the numbers radiate outward
from the destination node, like a fire,

hence the name.

Practically speaking, one way that you
would actually run this procedure,

is by maintaining a list of nodes.

On every iteration of the algorithm, you
would take the first node off the list,

mark all of its unvisited neighbors with
the current nodes distance value plus 1,

and then add them to the end of the list.

This slide outlines the basic
marketing algorithm in pseudo-code.

For those of you that studied graph-based
algorithms before, you'll recognize that

this is a simple example of a bread first
search algorithm applied to our graph,

starting at the destination node.

Let's see how this marking procedure
helps us to solve our original problem.

In this example,
once our start node has been marked,

we can construct the shortest
path to the goal

by repeatedly moving into the adjacent
cell with the smallest distance value.

This slide shows a path from the start
to the goal that is constructed

in this manner.

Note that if two neighbors
have the same distance value,

you can choose one arbitrarily.

This happens when the shortest
path to the goal is not unique.

You could also reverse this algorithm
by starting at the start node and

iterating towards the destination, and you
end up with a path with the same length.

Here's another example of running
the grassfire algorithm on another grid.

Once again,
we start at the destination and

proceed to mark nodes in order,
based on their distance from the goal.

In this case, however,
the algorithm terminates at this point,

where there are no more nodes that
can be reached from the destination.

At this point, we can conclude that since
the start node has not been marked,

there is no path from
the start to the destination.

So, we see that the grassfire algorithm
has the following desirable properties.

If a path exist between the start and

the destination node, it will find
one with the fewest number of edges.

If no path exists,
the algorithm will discover that fact and

report it to the user.

In this sense, we say that
the grassfire algorithm is complete.

It covers all of the possible cases.

Another question that we might to
ask about the planning procedure

is how much work does it require.

If we think about running our
grassfire algorithm on a regular grid,

as in our examples,

we notice that every grid cell is marked
at most once during this procedure.

More formally we can say that
the amount of computational effort

that we'd need to expend in order to
run the grassfire algorithm on a grid

grows linearly with the number of nodes.

We can express this a little bit more
formally using big o notations as follows.

Practically speaking all this means
is that if we consider two grids one

10 by 10 and the other 20 by 20 we would
expect that it would take approximately

four times as long to run the grassfire
algorithm on the second problem.

Since it has four times as many
nodes as the first instance.

It's also interesting to note that we can
use exactly the same kind of procedure to

plan past for a robot that could move in
three dimensions, for example, quadrotor.

Here we can imagine breaking
the work space of the robot into

a three dimensional grid where
each cell is acute and then using

the grassfire algorithm to plan a path
between two different cells in that grid.

If we compare the work required to
run the grassfire algorithm on a 100

by 100 grid in 2D and
a 100 by 100 by 100 grid in 3D.

We see that the latter planning
problem should require about

a 100 times more effort, or take 100
time longer to run on the same computer.

We could actually take
this a little bit further.

Imagine planning paths on
a grid in six dimension.

Now I know that at first this
sounds like a bit of overkill.

Planning paths in two dimensions and
three dimensions make sense.

We can imagine robots that do that.

But it seems a little bit odd to be
considering a robot that moves in

six dimensions.

However, as we will see when we start
to consider more complicated robotic

platforms like robotic arms,
we're going to find systems that are going

to have us planning paths in
six dimensions and even more.

A six dimensional cube with 100 elements
on each side would contain a grand

total of 10 to the 12 nodes
which is a very large number.

Actually to put it into perspective that's
approximately equal to the number of fish

in the ocean or the number of
stars in the Andromeda galaxy.

At this point it becomes very
difficult to imagine running

any computation that would involve
visiting all the nodes in such a grid.

At this point we're probably going to need
a different kind of algorithm to solve

these kinds of planning problems.

It turns out that this behavior with the
amount of computational effort required to

solve the problem grows exponentially as
we increase the number of dimensions or

degrees of freedom is a characteristic
feature of motion planning problems and

something that we're going
to see as we move forward.