Sampling-based Motion Planning: Analysis and Path Quality
One of the fundamental tasks robots have to perform is planning their motions
while avoiding collisions with obstacles in the environment. This is the
central topic of the thesis. We restrict ourselves to motion planning for
two- and three-dimensional rigid bodies and articulated robots moving in static
and known virtual environments.
This thesis has been divided into two parts. The first part deals with
comparing and analyzing sampling-based motion planning techniques, in
particular variants of the Probabilistic Roadmap Method (PRM).
The PRM consists of two phases: a construction and a query phase. In the
construction phase, a roadmap (graph) is built, approximating the motions that
can be made in the environment. First, a free random sample is created. Such a
sample describes a particular placement of the moving object (robot) in the
workspace. Then, a simple local planner is employed to connect the sample to
some neighbors. Samples and connections are added to the graph until the
roadmap is dense enough. In the query phase, the start and goal samples are
connected to the graph. The path is obtained by a Dijkstra's shortest path
Many variants of the PRM have been developed over the past decade. Using both
time-based as well as
reachability-based analysis, we compare some of the most
prominent techniques. The results are surprising in the sense that techniques
often perform differently than claimed by the designers. In addition, contrary
to general belief, the main challenge is not getting the free space covered but
getting the nodes connected, especially when the problems get more complicated,
e.g. when a narrow passage is present. By using this knowledge, we can tackle
the narrow passage problem by incorporating a more powerful local planner, a
refined neighbor selection strategy and a hybrid sampling strategy. The
analysis also shows why the PRM successfully deals with many motion planning
The second part deals with quality aspects of paths and roadmaps. A good path
is relatively short, keeps some distance (clearance) from the obstacles, and is
We will provide algorithms that increase path clearance.
A big advantage of
these algorithms is that high-clearance paths can now be efficiently created
without using complex data structures and algorithms. We also elaborate on
algorithms that successfully decrease path length.
Then, we introduce the
Reachability Roadmap Method which creates small roadmaps
for two- and
three-dimensional problems. Such a small roadmap has many advantages over a
roadmap that is created by the PRM. In particular, the method assures low query
times, low memory consumption, and the roadmap can be optimized easily. The
algorithm also ensures that a path is always found (if one exists) at a given
We unify the techniques to create high-quality roadmaps
for interactive virtual
environments. That is, we use the Reachability Roadmap Method to create an
initial roadmap. We add useful cycles to provide alternative routes and short
paths, and we add clearance to the roadmap to obtain high-clearance paths in
Roland Geraerts. Sampling-based Motion Planning: Analysis and Path Quality.
Ph.D. thesis. Utrecht University. 2006.
Full text: [pdf low compression;
11.5MB, pdf high compression; 3MB]
Cover of the thesis.