Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning

Publication Type:

Conference Paper

Authors:

Plaku, E.; Kavraki, L.E.; Vardi, M.Y.

Source:

Robotics: Science and Systems, MIT Press, Atlanta, Georgia, p.313-320 (2008)

URL:

http://www.kavrakilab.org/sites/default/files/PaperRSS_DSLX-h.pdf

Keywords:

kinodynamic/physics-based motion planning; hybrid systems; path planning; project_DSLX; project_Hybrid

Abstract:

This paper presents the Discrete Search Leading
continuous eXploration (DSLX) planner, a multi-resolution
approach to motion planning that is suitable for challenging
problems involving robots with kinodynamic constraints. Initially
the method decomposes the workspace to build a graph that
encodes the physical adjacency of the decomposed regions. This
graph is searched to obtain leads, that is, sequences of regions that
can be explored with sampling-based tree methods to generate
solution trajectories. Instead of treating the discrete search of
the adjacency graph and the exploration of the continuous state
space as separate components, DSLX passes information from
one to the other in innovative ways. Each lead suggests what
regions to explore and the exploration feeds back information
to the discrete search to improve the quality of future leads.
Information is encoded in edge weights, which indicate the
importance of including the regions associated with an edge in
the next exploration step. Computation of weights, leads, and the
actual exploration make the core loop of the algorithm.

Extensive experimentation shows that DSLX is very versatile.
The discrete search can drastically change the lead to reflect
new information allowing DSLX to find solutions even when
sampling-based tree planners get stuck. Experimental results on
a variety of challenging kinodynamic motion planning problems
show computational speedups of two orders of magnitude over
other widely used motion planning methods.