Kavraki Lab

Physical and Biological Computing

URL:

Keywords:

Abstract:

We propose the combination of techniques that solve
multiple queries for motion planning problems with single query
planners in a motion planning framework that can be efficiently
parallelized. In multiple query motion planning, a data structure is
built during a preprocessing phase in order to quickly respond to
on-line queries. Alternatively, in single query planning, there is
no preprocessing phase and all computations occur during query
resolution. This paper shows how to effectively combine a powerful
sample-based method primarily designed for multiple query planning
(the Probabilistic Roadmap Method - PRM) with sample-based tree
methods that were primarily designed for single query planning (such
as Expansive Space Trees, Rapidly Exploring Random Trees, and
others). Our planner, which we call the Probabilistic Roadmap of
Trees (PRT), uses a tree algorithm as a subroutine for PRM. The
nodes of the PRM roadmap are now trees. We take advantage of the
very powerful sampling schemes of recent tree planners to populate
our roadmaps. The combined sampling scheme is in the spirit of the
non-uniform sampling and refinement techniques employed in earlier
work on PRM. PRT not only achieves a smooth spectrum between
multiple query and single query planning but it combines advantages
of both. We present experiments which show that PRT is capable of
solving problems that cannot be addressed efficiently with PRM or
single-query planners. A key advantage of PRT is that it is
significantly more decoupled than PRM and sample-based tree
planners. Using this property, we designed and implemented a
parallel version of PRT. Our experiments show that PRT distributes
well and can easily solve high dimensional problems that exhaust
resources available to single machines.

• BibTex
• Endnote Tagged
• Endnote XML
• PDF
• Publisher's web site