Learning Approximate Cost-to-Go Metrics To Improve Sampling-based Motion Planning

TitleLearning Approximate Cost-to-Go Metrics To Improve Sampling-based Motion Planning
Publication TypeConference Paper
Year of Publication2011
AuthorsLi, Y, Bekris, KE
Conference NameInternational Conference on Robotics and Automation (ICRA-11)
Date Published9-13 May
Conference LocationShanghai, China

Sampling-based planners have been shown to be effective by utilizing properties for quickly searching unexplored parts of the state space. Such desirable properties, however, depend on the availability of an appropriate metric, which is often difficult to be defined for important robotic systems, such as non-holonomic and underactuated ones. This paper investigates a general methodology to approximate optimum cost-to-go metrics by employing an offline learning phase in obstacle-free environments. The proposed method utilizes sampling to construct a dense graph that approximates the connectivity properties of the state space. This graph can be employed online to compute approximate distances between states using nearest neighbor queries and standard search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. The paper proceeds into investigating ways that allow the computationally efficient utilization of the learned metric during the planner's online operation. One idea considered is the mapping of the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling so as to retain the relative distances represented by the sampled graph. Proof of concept simulations on a first-order car and on an illustrative example of an asymmetric state space, indicate that the approach has merit and can lead into more effective sampling-based algorithms.

Refereed DesignationRefereed