Learning approximate cost-to-go metrics to improve sampling-based motion planning

Abstract

Sampling-based planners have been shown to be effective in searching unexplored parts of a system's state space. Their desirable properties, however, depend on the availability of an appropriate metric, which is often difficult to be defined for some robots, such as non-holonomic and under-actuated ones. This paper investigates a methodology to approximate optimum cost-to-go metrics by employing an offline learning phase in an obstacle-free workspace. The proposed method densely samples a graph that approximates the connectivity properties of the state space. This graph can be used online to compute approximate distances between states using nearest neighbor queries and standard graph search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. This work then investigates ways for the computationally efficient utilization of the learned metric during the planner's online operation. One idea is to map the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling that retains the relative distances represented by the sampled graph. 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 planning.