Reachability and Completeness

This section provides preliminary concepts for sampling-based planning algorithms. In Chapter 5, sampling over was of fundamental importance. The most impor- tant consideration was that a sequence of samples should be dense so that samples get arbitrarily close to any point in free. Planning under differential constraints is complicated by the specification of solutions by an action trajectory instead of a path through Xfree. For sampling-based algorithms to be resolution com- plete, sampling and searching performed on the space of action trajectories must somehow lead to a dense set in Xfree.

C

C

• • 1. Reachable Sets

For the algorithms in Chapter 5, resolution completeness and probabilistic com- pleteness rely on having a sampling sequence that is dense on . In the present setting, this would require dense sampling on X. Differential constraints, however, substantially complicate the sampling process. It is generally not reasonable to prescribe precise samples in X that must be reached because reaching them may be impossible or require solving a BVP. Since paths in X are obtained indirectly via action trajectories, completeness analysis begins with considering which points can be reached by integrating action trajectories.

C

• • • 1. Reachable set

Assume temporarily that there are no obstacles: Xfree = X. Let U be the set of all permissible action trajectories on the time interval [0, ∞). From each u˜ ∈ U, a

state trajectory x˜(x0, u˜) is defined using (14.1). Which states in X are visited by these trajectories? It may be possible that all of X is visited, but in general some states may not be reachable due to differential constraints.

Let R(x0, U) ⊆ X denote the reachable set from x0, which is the set of all states

that are visited by any trajectories that start at x0 and are obtained from some

u˜ ∈ U by integration. This can be expressed formally as

R(x0, U) = {x1 ∈ X | ∃u˜ ∈ U and ∃t ∈ [0, ∞) such that x(t) = x1}, (14.4) in which x(t) is given by (14.1) and requires that x(0) = x0.

The following example illustrates some simple cases.

Example 14.2 (Reachable Sets for Simple Inequality Constraints) Sup- pose that X = = R2, and recall some of the simple constraints from Section

C

13.1.1. Let a point in R2 be denoted as q = (x, y). Let the state transition equation be x˙ = u1 and y˙ = u2, in which (u1, u2) U = R2.

∈

Several constraints will now be imposed on U, to define different possible action

spaces. Suppose it is required that u1 > 0 (this was x˙ > 0 in Section 13.1.1). The reachable set R(q0, U) from any q0 = (x0, y0) ∈ R2 is an open half-plane that is

defined by the set of all points to the right of the vertical line x = x0. In the case of u1 0, then R(q0, ) is a closed half-plane to the left of the same vertical line. If U is defined as the set of all (u1, u2) R2 such that u1 > 0 and u2 > 0, then the reachable set from any point is a quadrant.

∈

≤ U

For the constraint au1 + bu2 = 0, the reachable set from any point is a line in R2 with normal vector (a, b). The location of the line depends on the particular q0. Thus, a family of parallel lines is obtained by considering reachable states from different initial states. This is an example of a foliation in differential geometry,

and the lines are called leaves [872].

In the case of u2 + u2 ≤ 1, the reachable set from any (x0, y0) is R2. Thus, any

1

2

state can reach any other state. ．

So far the obstacle region has not been considered. Let Ufree ⊆ U denote the set of all action trajectories that produce state trajectories that map into Xfree. In

other words, Ufree is obtained by removing from U all action trajectories that cause

entry into Xobs for some t > 0. The reachable set that takes the obstacle region into account is denoted R(x0, Ufree), which replaces U by Ufree in (14.4). This

assumes that for the trajectories in free, the termination action can be applied to avoid inevitable collisions due to momentum. A smaller reachable set could have been defined that eliminates trajectories for which collision inevitably occurs without applying uT .

U

The completeness of an algorithm can be expressed in terms of reachable sets. For any given pair xI , xG ∈ Xfree, a complete algorithm must report a solution

action trajectory if xG R(xI , free), or report failure otherwise. Completeness is too difficult to achieve, except for very limited cases [171, 747]; therefore, sampling- based notions of completeness are more valuable.

∈ U

• • • 1. Time-limited reachable set

Consider the set of all states that can be reached up to some fixed time limit. Let the time-limited reachable set R(x0, , t) be the subset of R(x0, ) that is reached up to and including time t. Formally, this is

U U

R(x0, U, t) = {x1 ∈ X | ∃u˜ ∈ U and ∃t′ ∈ [0, t] such that x(t′) = x1}. (14.5)

For the last case in Example 14.2, the time-limited reachable sets are closed discs of radius t centered at (x0, y0). A version of (14.5) that takes the obstacle region

into account can be defined as R(x0, Ufree, t).

Imagine an animation of R(x0, U, t) that starts at t = 0 and gradually increases

1. The boundary of R(x0, U, t) can be imagined as a propagating wavefront that begins at x0. It eventually reaches the boundary of R(x0, U) (assuming it has a boundary; it does not if R(x0, U) = X). The boundary of R(x0, U, t) can actually

be interpreted as a level set of the optimal cost-to-come from x0 for a cost functional that measures the elapsed time. The boundary is also a kind of forward projection, as considered for discrete spaces in Section 10.1.2. In that context, possible future

• 1. (b)

Figure 14.4: (a) The time-limited reachable set for the Dubins car facing to the right; (b) this is not the time-limited reachable set for the Reeds-Shepp car!

states due to nature were specified in the forward projection. In the current setting, possible future states are determined by the unspecified actions of the robot. Rather than looking k stages ahead, the time-limited reachable set looks for duration t into the future. In the present context there is essentially a continuum of stages.

Example 14.3 (Reachable Sets for Simple Cars) Nice illustrations of reach- able sets can be obtained from the simple car models from Section 13.1.2. Suppose

that X = C = R2 × S1 and Xobs = ∅.

Recall that the Dubins car can only drive forward. From an arbitrary con- figuration, the time-limited reachable set appears as shown in Figure 14.4a. The time limit t is small enough so that the car cannot rotate by more than π/2. Note that Figure 14.4a shows a 2D projection of the reachable set that gives translation only. The true reachable set is a 3D region in . If t > 2π, then the car will be able to drive in a circle. For any q, consider the limiting case as t approaches infinity, which results in R(q, ). Imagine a car driving without reverse on an infinitely large, flat surface. It is possible to reach any desired configuration by driving along a circle, driving straight for a while, and then driving along a circle again. Therefore, R(q, ) = for any q . The lack of a reverse gear means that some extra maneuvering space may be needed to reach some configurations.

C

U

U C ∈ C

Now consider the Reeds-Shepp car, which is allowed to travel in reverse. Any time-limited reachable set for this car must include all points from the correspond- ing reachable set for the Dubins car because new actions have been added to U but none have been removed. It is tempting to assert that the time-limited reachable set appears as in Figure 14.4b; however, this is wrong. In an arbitrarily small amount of time (or space) a car with reverse can be wiggled sideways. This is achieved in practice by familiar parallel-parking maneuvers. It turns out in this case that R(q, , t) always contains an open set around q, which means that it

U

grows in all directions (see Section 15.3.2). The property is formally referred to as small-time controllability and is covered in Section 15.4. ．

• • • 1. Backward reachable sets

The reachability definitions have a nice symmetry with respect to time. Rather than describing all points reachable from some x X, it is just as easy to describe all points from which some x X can be reached. This is similar to the alternative between forward and backward projections in Section 10.1.2.

∈

∈

Let the backward reachable set be defined as

B(xf , U) = {x0 ∈ X | ∃u˜ ∈ U and ∃t ∈ [0, ∞) such that x(t) = xf }, (14.6)

in which x(t) is given by (14.1) and requires that x(0) = x0. Note the intentional similarity to (14.4). The time-limited backward reachable set is defined as

B(xf , U, t) = {x0 ∈ X | ∃u˜ ∈ U and ∃t′ ∈ [0, t] such that x(t′) = xf }, (14.7)

which once again requires that x(0) = x0 in (14.1). Completeness can even be de- fined in terms of backward reachable sets by defining a backward-time counterpart to .

U

At this point, there appear to be close parallels between forward, backward, and bidirectional searches from Chapter 2. The same possibilities exist in sampling- based planning under differential constraints. The forward and backward reachable sets indicate the possible states that can be reached under such schemes. The algorithms explore subsets of these reachable sets.

• • 1. The Discrete-Time Model

This section introduces a simple and effective way to sample the space of ac- tion trajectories. Section 14.2.3 covers the more general case. Under differential constraints, sampling-based motion planning algorithms all work by sampling the space of action trajectories. This results in a reduced set of possible action trajec- tories. To ensure some form of completeness, a motion planning algorithm should carefully construct and refine the sample set. As in Chapter 5, the qualities of a sample set can be expressed in terms of dispersion and denseness. The main difference in the current setting is that the algorithms here work with a sample sequence over , as opposed to over as in Chapter 5. This is required because solution paths can no longer be expressed directly on (or X).

C

U C

The discrete-time model is depicted in Figure 14.5 and is characterized by three aspects:

1. Time T is partitioned into intervals of length ∆t. This enables stages to be assigned, in which stage k indicates that (k 1)∆t units of time have elapsed.

−

1. A finite subset Ud of the action space U is chosen. If U is already finite, then this selection may be Ud = U.
2. The action u(t) ∈ Ud must remain constant over each time interval.

T T

A trajectory in U A trajectory in Ud

Figure 14.5: The discrete-time model results in d , which is obtained by partitioning time into regular intervals and applying a constant action over each interval. The action is chosen from a finite subset Ud of U.

U ⊂ U

The first two discretize time and the action spaces. The third condition is needed to relate the time discretization to the space of action trajectories. Let d denote the set of all action trajectories allowed under a given time discretization. Note that d completely specifies the discrete-time model.

U

U

For some problems, U may already be finite. Imagine, for example, a model of firing one of several thrusters (turn them on or off) on a free-floating spacecraft. In this case no discretization of U is necessary. In the more general case, U may be a continuous set. The sampling methods of Section 5.2 can be applied to determine

a finite subset Ud ⊆ U.

Any action trajectory in Ud can be conveniently expressed as an action sequence

(u1, u2, . . . , uk), in which each ui Ud gives the action to apply from time (i 1)∆t to time i∆t. After stage k, it is assumed that the termination action is applied.

∈ −

• • • 1. Reachability graph

After time discretization has been performed, the reachable set can be adapted to

Ud to obtain R(x0, Ud). An interesting question is: What is the effect of sampling

on the reachable set? In other words, how do R(x0, ) and R(x0, d) differ? This can be addressed by defining a reachability graph, which will be revealed incrementally by a planning algorithm.

U U

Let Tr(x0, Ud) denote a reachability tree, which encodes the set of all trajectories from x0 that can be obtained by applying trajectories in Ud. Each vertex of

Tr(x0, d) is a reachable state, x R(x0, d). Each edge of Tr(x0, d) is directed; its source represents a starting state, and its destination represents the state obtained

U ∈ U U

by applying a constant action u ∈ Ud over time ∆t. Each edge e represents an action trajectory segment, e : [0, ∆t] → U. This can be transformed into a state

trajectory, x˜e, via integration using (14.1), from 0 to ∆t of f(x, u) from the source

Two stages Four stages

Figure 14.6: A reachability tree for the Dubins car with three actions. The kth stage produces 3k new vertices.

state of e.

Thus, in terms of x˜e, Tr can be considered as a topological graph in X (Tr will be used as an abbreviation of Tr(x0, Ud)). The swath S(Tr) of Tr is

S(Tr) = I I xe(t), (14.8)

e∈E t∈[0,∆t]

in which xe(t) denotes the state obtained at time t from edge e. (Recall topological graphs from Example 4.6 and the swath from Section 5.5.1.)

Example 14.4 (Reachability Tree for the Dubins Car) Several stages of the reachability tree for the Dubins car are shown in Figure 14.6. Suppose that there are three actions (straight, right-turn, left-turn), and ∆t is chosen so that if the right-turn or left-turn action is applied, the car travels enough to rotate by π/2. After the second stage, there are nine leaves in the tree, as shown in Figure 14.6a.

Each stage produces 3k new leaves. In Figure 14.6b, 81 new leaves are added in stage k = 4, which yields a total of 81 + 27 + 9 + 3 + 1 vertices. In many cases, the same state is reachable by different action sequences. The swath after the first

four stages is the set of all points visited so far. This is a subset of C that is the union of all vertices and all points traced out by x˜e for each e ∈ E. ．

From Example 14.4 it can be seen that it is sometimes possible to arrive at the same state using two or more alternative action trajectories. Since each action trajectory can be expressed as an action sequence, the familiar issue arises from classical AI search of detecting whether the same state has been reached from different action sequences. For some systems, the reachability problem can be dramatically simplified by exploiting this information. If the same state is reached from multiple action sequences, then only one vertex needs to be represented.

This yields a directed reachability graph Gr(x0, Ud), which is obtained from

Tr(x0, d) by merging its duplicate states. If every action sequence arrives at a unique state, then the reachability graph reduces to the reachability tree. However, if multiple action sequences arrive at the same state, this is represented as a single vertex r. From this point onward, the reachability graph will be primarily used.

U

G

As for a reachability tree, a reachability graph can be interpreted as a topological graph in X, and its swath S(Gr) is defined by adapting (14.8).

The simplest case of arriving at the same state was observed in Example 2.1. The discrete grid in the plane can be modeled using the terminology of Chapter

13 as a system of the form x˙

= u1 and y˙

= u2 for a state space X = R2. The

discretized set Ud of actions is (1, 0), (0, 1), ( 1, 0), (0, 1) . Let ∆t = 1. In this

{ − − }

case, the reachability graph becomes the familiar 2D grid. If (0, 0) is the initial state, then the grid vertices consist of all states in which both coordinates are integers.

Through careless discretization of an arbitrary system, such a nice grid usually does not arise. However, in many cases a discretization can be carefully chosen so that the states become trapped on a grid or lattice. This has some advantages in sampling-based planning. Section 14.4.1 covers a method that exploits such structure for the system q¨ = u. It can even be extended to more general systems, provided that the system can be expressed as q¨ = g(q, q˙, u) and it is not under- actuated. It was shown recently that by a clever choice of discretization, a very large class of nonholonomic systems4 can also be forced onto a lattice [762]. This is usually difficult to achieve, and under most discretizations the vertices of the reachability graph are dense in the reachable set.

It is also possible to define backward versions of the reachability tree and reachability graph, in the same way that backward reachable sets were obtained. These indicate initial states and action sequences that will reach a given goal state and are no more difficult to define or compute than their forward counterparts.

4The class is all driftless, nilpotent systems. The term nilpotent will be defined in Section 15.5.

They might appear more difficult, but keep in mind that the initial states are not fixed; thus, no BVP appears. The initial states can be obtained by reverse-time integration of the state transition equation; see Section 14.3.2.

• • • 1. Resolution completeness for x˙ = u

Sampling-based notions of completeness can be expressed in terms of reachable sets and the reachability graph. The requirement is to sample in a way that causes the vertices of the reachability graph to eventually become dense in the reachable set, while also making sure that the reachability graph is systematically searched. All of the completeness concepts can be expressed in terms of forward or backward reachability graphs. Only the forward case will be described because the backward case is very similar.

U

To help bridge the gap with respect to motion planning as covered in Part II, first suppose: 1) X = C = R2, 2) a state is denoted as q = (x, y), 3) U = [−1, 1]2,

and 4) the state transition equation is x˙ = u1 and y˙ = u2. Suppose that the

discrete-time model is applied to U. Let ∆t = 1 and

Ud = {(−1, 0), (0, −1), (1, 0), (0, 1)}, (14.9)

which yields the Manhattan motion model from Example 7.4. Staircase paths are produced as was shown in Figure 7.40. In the present setting, these paths are obtained by integrating the action trajectory. From some state xI , the reachability graph represents the set of all possible staircase paths with unit step size that can be obtained via (14.1).

Suppose that under this model, Xfree is a bounded, open subset of R2. The connection to resolution completeness from Chapter 5 can be expressed clearly in this case. For any fixed ∆t, a grid of a certain resolution is implicitly defined via

the reachability graph. The task is to find an action sequence that leads to the goal (or a vertex close to it in the reachability graph) while remaining in Xfree. Such a sequence can be found by a systematic search, as considered in Section 2.2. If the search is systematic, then it will correctly determine whether the reachability graph encodes a solution. If no solution exists, then the planning algorithm can decrease ∆t by a constant factor (e.g., 2), and perform the systematic search again. This process repeats indefinitely until a solution is found. The algorithm runs forever if no solution exists (in practice, of course, one terminates early and gives up). The approach just described is resolution complete in the sense used in Chapter 5, even though all paths are expressed using action sequences.

The connection to ordinary motion planning is clear for this simple model because the action trajectories integrate to produce motions that follow a grid. As the time discretization is improved, the staircase paths can come arbitrarily close to some solution path. Looking at Figure 14.5, it can be seen that as the sampling resolution is improved with respect to U and T , the trajectories obtained via discrete-time approximations converge to any trajectory that can be obtained by integrating some u˜. In general, convergence occurs as ∆t and the dispersion

of the sampling in U are driven to zero. This also holds in the same way for the more general case in which x˙ = u and X is any smooth manifold. Imagine placing a grid down on X and refining it arbitrarily by reducing ∆t.

• • • 1. Resolution completeness for x˙ = f(x, u)

Beyond the trivial case of x˙ = u, the reachability graph is usually not a simple

grid. Even if X is bounded, the reachability graph may have an infinite number of vertices, even though ∆t is fixed and Ud is finite. For a simple example, consider

the Dubins car under the discretization ∆t = 1. Fix uφ = −φmax (turn left) for

all t ∈ T . This branch alone generates a countably infinite number of vertices

in the reachability graph. The circumference of the circle is 2πρmin, in which ρmin is the minimum turning radius. Let ρmin = 1. Since the circumference is an irrational number, it is impossible to revisit the initial point by traveling k seconds for some integer k. It is even impossible to revisit any point on the circle. The set of vertices in the reachability graph is actually dense in the circle. This did not happen in Figure 14.6 because ∆t and the circumference were rationally related (i.e., one can be obtained from the other via multiplication by a rational number). Consider what happens in the current example when ρmin = 1/π and ∆t = 1.

Suppose that x˙ = f(x, u) and the discrete-time model is used. To ensure

convergence of the discrete-time approximation, f must be well-behaved. This can be established by requiring that all of the derivatives of f with respect to u and x are bounded above and below by a constant. More generally, f is assumed to be Lipschitz, which is an equivalent condition for cases in which the derivatives exist, but it also applies at points that are not differentiable. If U is finite, then

the Lipschitz condition is that there exists some c ∈ (0, ∞) such that

If(x, u) − f(x′, u)I ≤ cIx − x′I (14.10)

for all x, x′ ∈ X, for all u ∈ U, and I · I denotes a norm on X. If U is infinite, then the condition is that there must exist some c ∈ (0, ∞) such that

If(x, u) − f(x′, u′)I ≤ c(Ix − x′I + Iu − u′I), (14.11)

for all x, x′ X, and for all u, u′ U. Intuitively, the Lipschitz condition indicates that if x and u are approximated by x′ and u′, then the error when substituted into f will be manageable. If convergence to optimal trajectories with respect to a cost functional is important, then Lipschitz conditions are also needed for l(x, u). Under such mild assumptions, if ∆t and the dispersion of samples of Ud is driven down to zero, then the trajectories obtained from integrating discrete action sequences come arbitrarily close to solution trajectories. In other words, action sequences provide arbitrarily close approximations to any u˜ U. If f is Lipschitz, then the integration of (14.14) yields approximately the same result for u˜ as the approximating action sequence.

∈

∈ ∈

In the limit as ∆t and the dispersion of Ud approach zero, the reachability graph becomes dense in the reachable set R(xI , U). Ensuring a systematic search

6

5

4

Iteration

3

2

1

∆t 1 ∆t 1 ∆t 1 ∆t 1 ∆t 1 ∆t 1 ∆t

2 4 8 16 32 64

Time step

Figure 14.7: By systematically alternating between exploring different reachability graphs, resolution completeness can be achieved, even if each reachability graph has a countably infinite number of vertices.

for the case of a grid was not difficult because there is only a finite number of vertices at each resolution. Unfortunately, the reachability graph may generally have a countably infinite number of vertices for some fixed discrete-time model, even if X is bounded.

To see that resolution-complete algorithms nevertheless exist if the reachability graph is countably infinite, consider triangular enumeration, which proves that

N N is countable, in which N is the set of natural numbers. The proof proceeds by giving a sequence that starts at (0, 0) and proceeds by sweeping diagonally

×

back and forth across the first quadrant. In the limit, all points are covered. The same idea can be applied to obtain resolution-complete algorithms. A sequence of discrete-time models can be made for which the time step ∆t and the dispersion of the sampling of U approach zero. Each discretization produces a reachability graph that has a countable number of vertices.

A resolution-complete algorithm can be made by performing the same kind of zig-zagging that was used to show that N × N is countable. See Figure 14.7;

suppose that U is finite and Ud = U. Along the horizontal axis is a sequence of improving discrete-time models. Each model generates its own reachability graph, for which a systematic search eventually explores all of its vertices. Imagine this exploration occurs one step at a time, in which one new vertex is reached in each step. The vertical axis in Figure 14.7 indicates the number of vertices reached so far by the search algorithm. A countably infinite set of computers could explore all

of reachability graphs in parallel. With a single computer, it can still be assured that everything is eventually explored by zig-zagging as shown. Thus a resolution- complete algorithm always exists if U is finite. If U is not finite, then Ud must also be refined as the time step is decreased. Of course, there are numerous other ways to systematically explore all of the reachability graphs. The challenging task is to find a way that leads to good performance in practice.

The discussion so far has assumed that a sampling-based algorithm can un- cover a subgraph of the reachability graph. This neglects numerical issues such as arithmetic precision and numerical integration error. Such issues can additionally be incorporated into a resolution completeness analysis [196].

• • 1. Motion Primitives

The discrete-time model of Section 14.2.2 is just one of many possible ways to discretize the space of action trajectories. It will now be considered as a special case of specifying motion primitives. The restriction to constant actions over fixed time intervals may be too restrictive in many applications. Suppose we want to automate the motions of a digital actor for use in a video game or film. Imagine having a database of interesting motion primitives. Such primitives could be extracted, for example, from motion capture data [35, 553]. For example, if the actor is designed for kung-fu fighting, then each motion sequence may correspond to a basic move, such a kick or punch. It is unlikely that such motion primitives correspond to constant actions over a fixed time interval. The durations of the motion primitives will usually vary.

Such models can generally be handled by defining a more general kind of dis- cretization. The discrete-time model can be used to formulate a discrete-time state transition equation of the form

xk+1 = fd(xk, uk), (14.12)

in which xk = x((k − 1)∆t), xk+1 = x(k∆t), and uk is the action in Ud that is applied from time (k 1)∆t to time k∆t. Thus, fd is a function fd : X Ud X that represents an approximation to f, the original state transition function. Every

− × →

constant action u ∈ Ud applied over ∆t can be considered as a motion primitive.

Now generalize the preceding construction to allow more general motion prim- itives. Let u˜p denote a motion primitive, which is a function from an interval of time into U. Let the interval of time start at 0 and stop at tF (u˜p), which is a final time that depends on the particular primitive. From any state x Xfree, suppose that a set p(x) of motion primitives is available. The set may even be infinite, in which case some additional sampling must eventually be performed over the space of motion primitives by a local planning method. A state transition equation that operates over discrete stages can be defined as

U

∈

xk+1 = fp(xk, u˜p ), (14.13)

k

Figure 14.8: A maneuver automaton, proposed by Frazzoli [360], captures the constraints on allowable sequences of motion primitives.

in which u˜p is a motion primitive that must be chosen from U (xk). The time

k

p

discretization model and (14.12) can be considered as a special case in which the

motion primitives are all constant over a fixed time interval [0, ∆t). Note that in (14.13) the stage index k does not necessarily correspond to time (k 1)∆t. The index k merely represents the fact that k 1 motion primitives have been applied so far, and it is time to decide on the kth motion primitive. The current time is determined by summing the durations of all k 1 primitives applied so far. If a set

−

−

−

p

U (x) of primitives is given for all x ∈ X, then a reachability graph and its swath

can be defined by simple extensions of the discrete-time case. The discrete-time model Ud can now be interpreted as a special set of motion primitives.

For some motion primitives, it may not be possible to immediately sequence them without applying transitional motions. For example, in [362], two different kinds of motion primitives, called trim trajectories and maneuvers, are defined for autonomous helicopter flight. The trim trajectories correspond to steady motions, and maneuvers correspond to unsteady motions that are needed to make transi- tions between steady motions. Transitions from one trim trajectory to another are only permitted through the execution of a maneuver. The problem can be nicely modeled as a hybrid system in which each motion primitive represents a mode [360] (recall hybrid system concepts from Sections 7.3, 8.3.1, and 10.6). The augmented state space is X M, in which M is a set of modes. The transition equation (14.13) can be extended over the augmented state space so that motion primitives can change modes in addition to changing the original state. The pos- sible trajectories for the helicopter follow paths in a graph called the maneuver automaton. An example from [360] is shown in Figure 14.8. Every edge and every vertex corresponds to a mode in the maneuver automaton. Each edge or vertex actually corresponds to a parameterized family of primitives, from which a partic- ular one is chosen based on the state. A similar state machine is proposed in [452] for animating humans, and the motion primitives are called behaviors.

×

Discretizations based on general motion primitives offer great flexibility, and in many cases dramatic performance improvements can be obtained in a sampling- based planning algorithm. The main drawback is that the burden of establishing

resolution completeness is increased.