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
2020-08-14