#### Sampling-based methods

Many sampling-based methods can be adapted from to 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 . 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 is a metric space, . The metric can be extended across time to obtain a pseudometric, , as follows. For a pair of states, and , let

 (7.3)

Using , several sampling-based methods naturally work. For example, RDTs from Section 5.5 can be adapted to . Using 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 is usually not a single point. It is not clear which 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, and , such that , exactly one valid direction exists for making a potential edge. If , then no edge can be attempted because it would require the robot to instantaneously teleport'' from one part of 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