In this video we'll plan motions on a graph derived from a grid on the C-space.

If the C-space has n-dimensions, we can subdivide each dimension into k intervals, creating

a total of k-to-the-n grid cells.

Each cell is represented in the graph by a single node, representing the configuration

at the center of the cell.

For example, for a 2R robot, if we choose k equal to 32, then there are 32-squared or

1024 grid cells.

Let's draw the start and goal configuration on this grid.

If we add obstacles to the scene, the corresponding C-space obstacles can be made conservative

by marking every C-space grid cell they touch as an obstacle.

To turn this grid into a graph, we have to decide whether the centers of the grid cells

are 4-connected, meaning that an edge exists between two free grid cells if they are directly

north, south, east, or west of each other, or whether the centers of the grid cells are

8-connected, meaning that neighboring free grid cells along a diagonal are also connected.

With this choice, the center of each free grid cell is considered to be a node of the

graph, and edges are between the 4- or 8-connected free grid cells.

To find a short path, we can use A-star to search the graph.

We don't have to explicitly construct the entire graph in advance; we can construct

it as we search, using the 4-connected or 8-connected rule.

The optimistic cost-to-go is just the shortest straight-line path through joint space, accounting

for the wraparound at 0 and 2pi for each joint.

If the cells are 4-connected, this is an optimal path.

This optimal path is not unique; other paths with the same path length also exist.

If the start and goal configurations are in free grid cells, but not at the centers, then

the first path segment is from the start configuration to the center of its grid cell, and the last

path segment is from the center of a grid cell to the goal configuration.

If there are constraints on the robot's motion, such as for a car that can't move sideways,

or if the robot is dynamic and the controls are forces, not velocities, then grid-based

methods must be modified, as described in the book.

But, the simple grid-based path planner I just described can be applied to any fully

actuated kinematic system where the controls are velocities.

Because of the discretization of the C-space, the grid-based planner is not complete, but

it is resolution complete, meaning that it will find a path if one exists at the level

of discretization chosen.

The solution path is optimal for the underlying graph using A-star search.

But, a major drawback is that this approach is not practical for high-dimensional spaces.

The amount of memory needed to represent the grid, and the time to search the graph, grows

quickly with the number of degrees of freedom.

This problem can be mitigated, to some extent, by using multi-resolution grids.

The key idea here is not to choose the discretization level k in advance, but to represent the free

C-space coarsely in wide-open regions, and to use a finer resolution where the C-space

is cluttered.

This should keep the representation of the C-space relatively small, while still allowing

representation of narrow passages of free space.

As an example, imagine this dark gray box is a cell of the C-space, and the lighter

box is a C-space obstacle.

If we used a fixed resolution to represent the C-space, then this whole cell would be

marked as in collision.

If we subdivided the cell into 4 cells, then only one of them would be in collision.

We can subdivide again, then subdivide again, and in the end the original C-space cell is

represented by a tree that looks like this.

The 10 leaves of the tree are the final cells in our representation, and 2 of those cells,

colored gray, are in collision.

If we had used a fixed resolution grid, we would have needed 64 cells to achieve the

same level of resolution.

This kind of representation of a 2-dimensional C-space is called a quadtree, since cells

subdivide into 4.

In 3-dimensional space, cells subdivide into 8, and the representation is called an octree.

In the next video, we will see a different way to generate a graph representing the C-space,

based on random sampling.