Chapter 10 focuses on robot motion planning, particularly in the case of obstacles in the

environment.

For example, in this video, a motion has been planned for the robot arm to move its end-effector

from one frame to another, without hitting any obstacles in the environment.

Since some versions of the path planning problem have been called the piano-mover's problem,

here's an animation of a piano being maneuvered through a tight space.

In this chapter, the configuration of a robot is described by a vector of n coordinates

q, and the robot's C-space is denoted C, a subset of R^n.

More generally, the C-space of the robot could be an arbitrary manifold, like SE(3) for a

rigid body, but we will focus on configurations explicitly parametrized by a minimum set of

coordinates.

The C-space is the union of C_free, the set of configurations where the robot does not

contact any obstacle, and C_obs, the set of configurations where the robot is in collision

with an obstacle.

The state of the robot is x, where x could simply be the configuration q, if the robot's

control inputs are considered to be velocities, or it could be the configuration plus the

velocity, if the control inputs are considered to be accelerations, or forces.

The state space is capital X.

The equations of motion are x-dot equals f of (x,u), where the control u is an element

of the feasible control set capital U.

The integral form of the equations of motion is shown here.

With these definitions, a fairly general statement of the motion planning problem is: "Given

an initial state x_start and a desired final state x_goal, find a time T and a set of controls

such that the motion satisfies x-of-T equals x_goal and is collision free."

We assume that we have perfect models of the robot and the environment.

There are a number of possible variations on the motion-planning problem: we could plan

a full trajectory, with timing information, or just a collision-free geometric path.

The robot could have an actuator for every degree of freedom, like most robot arms, or

it could have fewer actuators than degrees of freedom, like a car with only two control

inputs, forward-backward speed and turning speed.

The planner might have to make changes in real time as obstacles move in the environment,

or it could be allowed to do its work in advance of the robot motion.

We could ask for minimum-time, minimum-length, or otherwise minimum-cost motions, or we could

be satisfied with any collision-free motion that reaches the goal.

Finally, we might require motions that go exactly to a goal state or we could be satisfied

with a final state anywhere in a goal region.

Apart from the characteristics of the motion planning problem, we can define the following

properties of a motion planner: The planner may be designed for multiple queries or a

single query.

A multiple-query planner is one that invests time in developing a good representation of

C-space, so that future motion-planning problems in that space can be solved quickly.

If the C-space changes often, however, a single-query planner attempts to find the solution to a

single motion-planning problem as quickly as possible.

We say that a planner is complete if it always finds a solution when one exists.

A weaker version of this notion is resolution completeness.

A planner is resolution complete if it always finds a solution when one exists at the level

of discretization employed in the representation of the problem.

There is also probabilistic completeness.

A planner is probabilistically complete if the chances of it finding a solution, if one

exists, goes to 100% as the planning time goes to infinity.

Finally, the computational complexity of a planner refers to how much memory a planner

will use, or how long the planner will take to execute, in either the average or the worst

case, as a function of the description of the planning problem, such as the number of

degrees of freedom of the robot or the number of vertices used to represent obstacles.

Before describing specific planners, in the next few videos I will introduce foundational

concepts in motion planning, such as C-space obstacles, graphs and trees, and graph search.