14.2.3 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 discretization. The discrete-time model can be used to formulate a discrete-time state transition equation of the form

$$x_{k+1} = f_d(x_k,u_k) ,$$ (14.12)

in which $x_k = x((k-1)\Delta t)$, $x_{k+1} = x(k \Delta t)$, and $u_k$ is the action in $U_d$ that is applied from time $(k-1) \Delta t$ to time $k \Delta t$. Thus, $f_d$ is a function $f_d: X \times U_d \rightarrow X$ that represents an approximation to $f$, the original state transition function. Every constant action $u \in U_d$ applied over $\Delta t$ can be considered as a motion primitive.

Now generalize the preceding construction to allow more general motion primitives. Let ${\tilde{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 $t_F({\tilde{u}}^p)$, which is a final time that depends on the particular primitive. From any state $x \in {X_{free}}$, suppose that a set ${\cal U}^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

$$x_{k+1} = f_p(x_k,{\tilde{u}}^p_k),$$ (14.13)

in which ${\tilde{u}}^p_k$ is a motion primitive that must be chosen from ${\cal U}^p(x_k)$. The time 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,\Delta t)$. Note that in (14.13) the stage index $k$ does not necessarily correspond to time $(k-1) \Delta 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 $k$th motion primitive. The current time is determined by summing the durations of all $k-1$ primitives applied so far. If a set ${\cal U}^p(x)$ of primitives is given for all $x \in X$, then a reachability graph and its swath can be defined by simple extensions of the discrete-time case. The discrete-time model ${\cal U}_d$ can now be interpreted as a special set of motion primitives.

Figure 14.8: A maneuver automaton, proposed by Frazzoli [360], captures the constraints on allowable sequences 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 transitions 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 \times 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 possible 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 particular 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.