Kinodynamic Motion Planning by Interior-Exterior Cell Exploration

Publication Type:

Conference Paper

Authors:

Ioan Alexandru Sucan; Lydia E. Kavraki

Source:

International Workshop on the Algorithmic Foundations of Robotics, Guanajuato, Mexico (2008)

URL:

http://www.wafr.org/papers/wafr08-sucan.pdf

Keywords:

kavrakilab, kinodynamic/physics-based motion planning, project_KPIECE

Abstract:

This paper presents a kinodynamic motion planner, Kinodynamic Motion
Planning by Interior-Exterior Cell Exploration (KPIECE),
specifically designed for systems with complex dynamics, where
physics-based simulation is necessary. A multiple-level grid-based
discretization is used to estimate the coverage of the state
space. The coverage estimates help the planner detect the less
explored areas of the state space. The planner also keeps track of
the boundary of the explored region of the state space and focuses
exploration on the less covered parts of this boundary. Extensive
experiments show KPIECE provides computational gain over
state-of-the-art methods and allows solving some harder, previously
unsolvable problems. A shared memory parallel implementation is
presented as well. This implementation provides better speedup than
an embarrassingly parallel implementation by taking advantage of the
evolving multi-core technology.


Preprint PDF     Publisher's web site