Sampling-based methods

Many sampling-based methods can be adapted from ${\cal C}$ to $X$ without much difficulty. The time dependency of obstacle models must be taken into account when verifying that path segments are collision-free; the techniques from Section 5.3.4 can be extended to handle this. One important concern is the metric for $X$. For some algorithms, it may be important to permit the use of a pseudometric because symmetry is broken by time (going backward in time is not as easy as going forward).

For example, suppose that the C-space ${\cal C}$ is a metric space, $({\cal C},\rho)$. The metric can be extended across time to obtain a pseudometric, $\rho_X$, as follows. For a pair of states, $x = (q,t)$ and $x^\prime = (q^\prime,t^\prime)$, let

$$\rho_X(x,x^\prime) = \left\{ \begin{array}{ll} 0 & \mbox{if $q = ... ...$t^\prime \leq t$} \rho(q,q^\prime) & \mbox{otherwise} . \end{array} \right.$$ (7.3)

Using $\rho_X$, several sampling-based methods naturally work. For example, RDTs from Section 5.5 can be adapted to $X$. Using $\rho_X$ for a single-tree approach ensures that all path segments travel forward in time. Using bidirectional approaches is more difficult for time-varying problems because ${X_{G}}$ is usually not a single point. It is not clear which $(q,t)$ should be the starting vertex for the tree from the goal; one possibility is to initialize the goal tree to an entire time-invariant segment. The sampling-based roadmap methods of Section 5.6 are perhaps the most straightforward to adapt. The notion of a directed roadmap is needed, in which every edge must be directed to yield a time-monotonic path. For each pair of states, $(q,t)$ and $(q^\prime,t^\prime)$, such that $t \not = t^\prime$, exactly one valid direction exists for making a potential edge. If $t = t^\prime$, then no edge can be attempted because it would require the robot to instantaneously ``teleport'' from one part of ${\cal W}$ to another. Since forward time progress is already taken into account by the directed edges, a symmetric metric may be preferable instead of (7.3) for the sampling-based roadmap approach.