DCB-RRT*: DYNAMIC CONSTRAINED SAMPLING BASED BIDIRECTIONAL RRT* WITH IMPROVED CONVERGENCE RATE

Xining Cui, Caiqi Wang, Yi Xiong, and Shiqian Wu

Keywords

Path planning, dynamic constrained sampling, collision detection, bias extension, dynamic step

Abstract

Rapidly-exploring random tree star (RRT) is widely used in path planning problems because of its probabilistic completeness and asymptotic optimality. The bidirectional RRT (B-RRT) is proposed to speed up finding the optimal path. However, both algorithms perform blind exploration in space, which suffer from low node utilisation and poor expansion orientation. To overcome these problems, dynamic constrained sampling based on the bidirectional RRT (DCB-RRT) is presented. The proposed DCB-RRT grows two random trees from the start and the end points for expansion, respectively, and dynamically adjusts the sampling area (Dyn- Sample) based on the number of collision detection failures, improving the effectiveness of sampling points in the initial path. In the convergence stage, a method of the dynamic angle to limit the sampling area (Limit-Sample) is proposed to improve the path convergence rate. The sampling point bias extension (DCB-Extend) is developed to increase the mutual guidance between the dual-trees and reduces the time to find the initial path. A dynamic step is also used to improve node utilisation. Numerical simulations under various environmental conditions demonstrate that DCB-RRT has certain advantages in terms of convergence rate.

Important Links:



Go Back