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.