Recall the approach in Section 14.4.1 that enabled systems of the form to be expressed as for some suitable (this was illustrated in Figure 14.15). This enabled many systems to be imagined as multiple, independent double integrators with phase-dependent constraints on the action space. The same idea can be applied here to obtain a single integrator.

Let denote a 2D *path-constrained phase space*, in which
each element is of the form
and represents the position
and velocity along . This parameterizes a 2D subset of the
original phase space . Each original state vector is
. Which accelerations are
possible at points in ? At each
, a subset of
can be determined that satisfies the equations of the form
(14.39). Each valid action yields an acceleration
. Let
denote the set of all
values of that can be obtained from an action that
satisfies (14.39) for each (except the ones for
which
). Now the system can be expressed as
, in which
. After all of this work, we have
arrived at the double integrator. The main complication is that
can be challenging to determine for some systems. It
could consist of a single interval, disjoint intervals, or may even be
empty. Assuming that
has been characterized, it is
straightforward to solve the remaining planning problem using
techniques already presented in this chapter. One double integrator
is not very challenging; hence, efficient sampling-based algorithms
exist.

An obstacle region will now be considered. This includes any states that belong to . Given and , the state can be computed to determine whether any constraints on are violated. Usually, is constructed to avoid obstacle collision; however, some phase constraints may also exist. The obstacle region also includes any points for which is empty. Let denote .

Before considering computation methods, we give some examples.

for .

Suppose that , which means that the particle must move along a diagonal line through the origin of . This further simplifies (14.40) to and . Hence any may be chosen, but must then be chosen as . The constrained system can be written as one double integrator , in which . Both and are derived from as . Note that does not vary over ; this occurs because a linear path is degenerate.

Now consider constraining the motion to a general line:

(14.41) |

in which and are nonzero. In this case, (14.40) yields and . Since each , each equation indicates that . The acceleration must lie in the intersection of these two intervals. If , then . We can designate and let . If , then , , and .

Suppose that and . The path is

(14.42) |

in which is fixed and the particle is constrained to move along a vertical line in . In this case, only one constraint, , is obtained from (14.40). However, is independently constrained to because horizontal motions are prohibited.

If independent, double integrators are constrained to a line, a similar result is obtained. There are equations of the form (14.40). The for which is largest determines the acceleration range as . The action is defined as , and the for are obtained from the remaining equations.

Now assume is nonlinear, in which case (14.39) becomes

for each for which . Now the set varies over . As the speed increases, it becomes less likely that is nonempty. In other words, it is less likely that a solution exists to all equations of the form (14.43). In a physical system, that means that staying on the path requires turning too sharply. At a high speed, this may require an acceleration that lies outside of .

The same ideas can be applied to systems that are much more complicated. This should not be surprising because in Section 14.4.1 systems of the form were interpreted as multiple, independent double integrators of the form , in which provided the possible accelerations. Under this interpretation, and in light of Example 14.6, constraining the motions of a general system to a path just further restricts . The resulting set of allowable accelerations may be at most one-dimensional.

The following example indicates the specialization of (14.39) for a robot arm.

This can be simplified to equations of the form

Solving each one for yields a special case of (14.39). As in Example 14.6, each equation determines a bounding interval for . The intersection of the intervals for all equations yields the allowed interval for . The action once again indicates the acceleration in the interval, and the original action variables can be obtained from (14.45). If , then , which corresponds to the case in which the constraint does not apply. Instead, the constraint is that the vector must be chosen so that .

Steven M LaValle 2012-04-20