14.2.2 The Discrete-Time Model

This section introduces a simple and effective way to sample the space of action 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 trajectories. 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 ${\cal U}$, as opposed to over ${\cal C}$ as in Chapter 5. This is required because solution paths can no longer be expressed directly on ${\cal C}$ (or $X$).

Figure 14.5: The discrete-time model results in ${\cal U}_d \subset {\cal U}$, 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 $U_d$ of $U$.

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 $\Delta t$. This enables stages to be assigned, in which stage $k$ indicates that $(k-1) \Delta t$ units of time have elapsed.
2. A finite subset $U_d$ of the action space $U$ is chosen. If $U$ is already finite, then this selection may be $U_d = U$.
3. The action $u(t) \in U_d$ must remain constant over each time interval.

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 ${\cal U}_d$ denote the set of all action trajectories allowed under a given time discretization. Note that ${\cal U}_d$ completely specifies the discrete-time model.

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 $U_d \subseteq U$.

Any action trajectory in ${\cal U}_d$ can be conveniently expressed as an action sequence $(u_1,u_2,\ldots,u_k)$, in which each $u_i \in U_d$ gives the action to apply from time $(i-1)\Delta t$ to time $i \Delta t$. After stage $k$, it is assumed that the termination action is applied.