There has been no consideration so far of the speed at which the robot
must move to avoid obstacles. It is obviously impractical in many
applications if the solution requires the robot to move arbitrarily
fast. One step toward making a realistic model is to enforce a bound
on the speed of the robot. (More steps towards realism are taken in
Chapter 13.) For simplicity, suppose
, which
corresponds to a translating rigid robot, , that moves in
. A configuration,
, is represented as
(since already refers to the whole state vector). The *robot
velocity* is expressed as
, in which
and
. The *robot speed* is
. A *speed bound*, , is a positive
constant,
, for which
.

In terms of Figure 7.1, this means that the slope of a solution path is bounded. Suppose that the domain of is instead of . This yields and . Using this representation, and , in which denotes the th component of (because it is a vector-valued function). Thus, it can seen that constrains the slope of in . To visualize this, imagine that only motion in the direction occurs, and suppose . If holds the robot fixed, then the speed is zero, which satisfies any bound. If the robot moves at speed , then and , which satisfies the speed bound. In Figure 7.1 this generates a path that has slope in the plane and is horizontal in the plane. If , then the bound is exceeded because the speed is . In general, the velocity vector at any state points into a cone that starts at and is aligned in the positive direction; this is depicted in Figure 7.3. At time , the state must stay within the cone, which means that

This constraint makes it considerably more difficult to adapt the algorithms of Chapters 5 and 6. Even for piecewise-linear motions of the obstacles, the problem has been established to be PSPACE-hard [818,819,928]. A complete algorithm is presented in [819] that is similar to the shortest-path roadmap algorithm of Section 6.2.4. The sampling-based roadmap of Section 5.6 is perhaps one of the easiest of the sampling-based algorithms to adapt for this problem. The neighbors of point , which are determined for attempted connections, must lie within the cone that represents the speed bound. If this constraint is enforced, a resolution complete or probabilistically complete planning algorithm results.

Steven M LaValle 2012-04-20