Efficient Sampling-based Approaches to Optimal Path Planning in Complex Cost Spaces

Abstract. In spite of their conceptual simplicity, sampling-based path planning algorithms have been very successful during the last 15 years, thanks to their ability to efficiently solve complex problems in high di-mension. However, basic versions of these algorithms cannot guarantee optimality or even high-quality for the produced paths. In recent years, variants of sampling-based algorithms, taking cost criteria into account during the exploration process, have been proposed to compute high-quality paths (such as T-RRT), some even guaranteeing asymptotic op-timality (such as RRT*). In this work, we propose two new algorithms that combine the underlying principles of RRT * and T-RRT. These algorithms, called T-RRT * and AT-RRT, offer probabilistic complete-ness and asymptotic optimality guarantees. Results presented on several classes of problems show that they converge faster than RRT * toward the optimal path, especially when the topology of the space is complex and/or when dimensionality is high