SARRT: a Structure-Aware RRT-based Approach for 2D Path Planning
Xuefeng Chang* Yanzhen Wang* Xiaodong Yi Nong Xiao
HPCL | School of Computer, National University of Defense Technology
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.
paper (1.9MB) codes (GitHub) slides (1.1MB)
This work was partially supported by National Science Foundation of China under Grant No. 61303185, and University Grants from NUDT under No. 434513322532 and 434513322412.
*Xuefeng Chang and Yanzhen Wang are joint first authors.