Original subtitles

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.