Efficient Sampling-based Motion Planning with Asymptotic Near-Optimality Guarantees for Systems with Dynamics

TitleEfficient Sampling-based Motion Planning with Asymptotic Near-Optimality Guarantees for Systems with Dynamics
Publication TypeConference Paper
Year of Publication2013
AuthorsLittlefield, Z, Li, Y, Bekris, KE
Conference NameIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Date Published11/2013
Conference LocationTokyo Big Sight, Japan
Abstract

Recent significant progress has provided sampling-based motion planners, such as RRT*, that asymptotically converge to optimal solutions. The basic variant of such methods requires a local planner, which connects two states with a trajectory. For systems with dynamics, the local planner needs to solve a two-point boundary value problem (BVP) for differential equations. Such a solver is not always available for state update equations of interesting systems with dynamics. Furthermore, asymptotically optimal solutions tend to impose increased computational requirements in practice relative to alternatives, such as RRT, that focus on feasibility, state-space exploration speed and which do not require a local planner. This paper describes a sampling-based motion planning solution with the following desirable properties: a) it does not require a BVP solver but only uses a forward propagation model, b) it employs a single propagation per iteration similar to RRT, making it very efficient, c) it is asymptotically near-optimal, and d) provides a sparse data structure for answering path queries, which further improves computational performance. Simulations on prototypical dynamical systems show the method is able to improve the quality of feasible solutions over time and that it is computationally efficient.

URLhttp://www.cs.rutgers.edu/~kb572/pubs/sparse_rrt_iros13.pdf
Refereed DesignationRefereed