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

$\displaystyle \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.

Steven M LaValle 2012-04-20