Most path planners in Chapter 10 can be applied to omnidirectional mobile robots, because of their ability to move in any direction. The same is not true for nonholonomic mobile robots, due to their motion constraints.

In this video we'll look at optimal motion plans for car-like robots in an obstacle-free plane, as well as motion planning among obstacles.

Let's start with a car with no reverse gear. A typical path looks like this. Our goal is to find paths that minimize the length of the curve followed by the point midway between the rear wheels. Let C represent a circular arc that the car follows when it turns at its minimum turning radius, either to the right or to the left. And let C greater than pi represent such arcs that travel an angle of at least pi. Finally, let S represent the straight-ahead motion of the car.

Then it can be shown that all shortest paths between two configurations are either of the form C, S, C, or C, C greater than pi, C, where any of the C or S segments could be of length zero. These are called Dubins curves in honor of the mathematician who proved this result.

Here are two examples. In the first animation, the shortest path to the goal is a CSC path. In the second animation, the shortest path has the form C, C greater than pi, C.

Now let's consider a car with a reverse gear. A result due to Reeds and Shepp says that all shortest paths belong to one of nine classes of paths, consisting of circular segments at the minimum turning radius, straight-line segments, and direction reversals, also called cusps. The details of the nine classes are in the book.

Here are examples from three of the nine path classes. The first shortest path is a CSC path. The second path reverses the car's orientation using two cusps. The third shortest path has a single cusp.

Dubins curves and Reeds-Shepp curves allow us to consider only a finite number of possible paths when planning the shortest path between two configurations in an obstacle-free plane. Reeds-Shepp curves can also be useful in motion planning for a car among obstacles. Given the start and goal configurations, first we can try connecting them by a Reeds-Sheep curve. If the path is in collision, then we can plan a free path between the two configurations using any path planner, ignoring the car's motion constraints. Provided this path does not graze any obstacle, then, because the car is small-time locally controllable everywhere, even though the car cannot follow the path exactly, it can follow it arbitrarily closely.

To transform this infeasible path to a feasible path, first we can divide the path in half and try using Reeds-Shepp curves to connect q-zero to q-one-half, and q-one-half to q-one. The Reeds-Shepp path from q-one-half to q-one is collision-free, but the Reeds-Shepp path from q-zero to q-one-half is not. So we subdivide the first path segment again and find the Reeds-Shepp paths between q-zero and q-one-quarter and between q-one-quarter and q-one-half. These paths are both collision-free, so we have our final path. This subdivision process is guaranteed to converge to a collision-free path because: one, the original path has some free space around it; two, the car is small-time locally controllable, so it can follow the original path arbitrarily closely; and three, the Reeds-Shepp paths are short, so the distance from the original path goes to zero as the distance between the subdivision points goes to zero.

Once we have a path for the robot, we can convert it to a trajectory by applying a time scaling subject to the robot's velocity limits.

For a diff-drive robot, the shortest path in the obstacle-free plane for the point midway between the two wheels is trivial: spin in place, translate, then spin in place. A more interesting problem is to find the time-optimal motion if each wheel's speed is limited. This problem is discussed in the book. All of the optimal motion results discussed in this video can be derived using techniques from optimal control theory.