Dynamic step BI-RRT UAV path planning algorithm

Abstract

To solve the problems of traditional RRT algorithm, such as slow convergence and long path length, the dynamic step BI-RRT algorithm is proposed. The sampling efficiency of the RRT algorithm is improved by using a target-oriented sampling strategy. The dynamic step algorithm improves the local smoothness of the path in the obstacle environment. A new tree cutting strategy is proposed to make the growth trend of random trees more obvious and improve the convergence rate of the algorithm. For the initial path, the path nodes are filtered by applying greedy algorithm to reduce the invalid nodes and path length of the unmanned aerial vehicle (UAV). Finally, a feasible smooth path is obtained by using B-Spline. The simulation maps in 2D and 3D environment are built to verify the effectiveness of the algorithm. Compared to the segmentated optimization RRT algorithm, the dynamic step BI-RRT algorithm proposed in this paper improves the convergence rate and reduces the path distance, while ensuring that the number of path nodes is optimal. This path planning algorithm has some advantages such as good real-time performance and smoothness of path.

Keywords

• basic science and technology of aeronautics and astronautics other disciplines
• bidirectional rapidly-exploring random tree (BI-RRT)
• probability search
• target oriented dynamic step size
• branch cutting strategy