SARRT: A structure-aware RRT-based approach for 2D path planning

Abstract

Motion/path planning remains one of the most important research topics in robotics for decades, since mobility is a defining characteristics of robots. Sampling-based approaches have proven to be effective for problems with complex constraints and high dimensionality. Specifically, Rapidly-exploring Random Tree (RRT) is one of the most popular sampling-based algorithms. However, it suffers from problems such as unstable performance and suboptimal results. This paper presents a novel RRT variant, namely, Structure-Aware RRT (SARRT), which utilizes a physically-based costmap to bias the tree growth to regions closer to the goal. Instead of typical distance metrics, such as Euclidean and Manhattan distances, the cost function is based on a simulated diffusion process and is able to reflect the structure of the free space and problem settings. Furthermore, a Laplacian smoothing step is performed on the resulting path to improve the smoothness of the path. Experimental results on 2D path planning problems show the effectiveness of SARRT, in terms of both algorithm runtime and resulting path quality.