Kavraki Lab

Physical and Biological Computing

URL:

Keywords:

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
integration backward in time is not possible and speed of computation
is important. A 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. An important
characteristic of this discretization is that it 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 that KPIECE provides significant computational
gain over existing state-of-the-art methods and allows solving some
harder, previously unsolvable problems. For some
problems KPIECE is shown to be up to two orders of magnitude
faster than existing methods and use up to forty times less memory. 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.