14.6.3.3 The path-constrained phase space

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.

Example 14..6 (Path-Constrained Double Integrators)   Consider the case of two double integrators. This could correspond physically to a particle moving in . Hence, . Let and for . The path will be chosen to force the particle to move along a line. For linear paths, is constant and . Using these observations and the fact that , (14.39) simplifies to

 (14.40)

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

 (14.43)

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.

Example 14..7 (Path-Constrained Manipulators)   Suppose that the system is described as (13.142) from Section 13.4.2. This is a common form that has been used for controlling robot arms for decades. Constraints of the form (14.39) can be derived by expressing , , and in terms of , , and . This requires using (14.32), (14.33), and (14.34). Direct substitution into (13.142) yields

 (14.44)

This can be simplified to equations of the form

 (14.45)

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