and their many variants may be unacceptable. This may be due, for example,
to certification and reproducibility requirements for safety-critical applications. An additional, computational
reason to avoid probabilistic algorithms
is the desire to use offline computation
to improve online performance.
One approach is to replace probabilistic sequences with deterministic
ones in sampling-based algorithms. 25, 27
This raises the question regarding the
theoretical guarantees and practical
performance that could be obtained by
using such sequences. In a recent work,
Janson et al. 19 show that using (
low-dispersion) deterministic sampling strategies can provide substantial benefits
when compared to probabilistic ones.
These benefits are both with respect
to reduced computational complexity
(for a given number of samples) and
superior empirical performance on a
wide range of problems. Their work
opens the door to using deterministic sampling in optimal kino-dynamic
motion planning, anytime algorithms
such as RRT, designing new algorithms
that explicitly leverage the structure of
low-dispersion sequences and more. A
key question here is how to employ deterministic sampling sequences when
we are only interested in samples that
lie in the informed set Xinf.
An alternative approach that avoids
probabilistic algorithms, mentioned
previously, is using search-based algorithms that systematically search over
an implicit graph G.
algorithms are the Probabilistic Roadmap Method (PRM) and the Rapidly Exploring Random Tree (RRT), which are
examples of multi-query and single-query motion-planning algorithms,
respectively. 25 For a visualization illustrating the way the PRM algorithm constructs a roadmap in the preprocessing
phase and computes a collision-free
roadmap in the query stage, as illustrated in Figure 2.
General Computational Challenges
in Motion Planning
The high-level description of sampling-based planners provided earlier
leaves many questions that must be
addressed. Here, several of these questions are listed together with the computational challenges they introduce.
While the focus here is on sampling-based planners, many of these questions and challenges arise in search-based planning algorithms as well, but
a detailed analysis of such algorithms
is out of the scope of this article.
How to efficiently and effectively
sample X A key question in sampling-based algorithms that must be
addressed is how to choose the set of
configurations that will serve as vertices in G. Intuitively, we want to cover
the entire C-space (exploration) while
using previous information to bias
where new samples are placed (
exploitation). The simplest approach that
works well in practice is to sample
points uniformly from the C-space.
Many heuristics were suggested in
order to speed up the probability of
finding a solution. Examples include
sampling near the obstacles, on the
medial axis, and more. 25 Recent work
has also used learning to accelerate
the planning in order to devise non-
uniform sampling strategies that favor
sampling in those regions where an
optimal solution might lie (for exam-
ple, Ichter et al. 18).
Once an initial solution is found
only configurations that can provide a
better solution should be considered.
Considering only this set of configurations, termed the informed set Xinf , can
dramatically improve the performance
of asymptotically optimal motion planners such as RRT*. 10 When the C-space
is Euclidean, Xinf is a pro-late hyper-ellipsoid10 and it is possible to directly
sample Xinf Several heuristic approaches
attempt to generalize this result to
non-Euclidean C-spaces (for example,
see Kunz et al. 24), however efficiently
sampling Xinf for general C-spaces remains an open challenge.
From a computational point of view,
sampling uniformly from the C-space
can be done in O ( 1) time. This constant
is inversely proportional to the ratio
of the volume of Xfree and X and may
be extremely large in certain settings.
Sampling in the informed set Xinf for
Euclidean spaces, can still be done in O
( 1) time, however, it is not clear that this
is the case for more complex C-spaces.
Deterministic vs. probabilistic planning.
In certain domains, applying probabilistic algorithms such as the PRM, RRT
Figure 2. A PRM example.
In the preprocessing phase, (a) a roadmap G is constructed by sampling n configurations, or milestones, and (b) adding them as vertices to G if they are collision free.
(c) If the path connecting two close-by configurations (computed using a local
planner) is collision free, then an edge between the two respective vertices is added
to G. (d) In the query phase, start and target configurations (green and red circles,
respectively) are provided to the planner. Using the local planner, local paths connecting these configurations to G are computed. If these local paths are collision
free, then any graph-search algorithm can be used to assess if a path exists between
the start and goal configurations in the roadmap.
(a) PRM-sampled milestone (c) PRM roadmap (d) Query using roadmap (b) PRM-valued milestones