Progressive Rapidly-exploring Random Tree for Global Path Planning of Robots

Abstract

Global path planning is an essential task for autonomous robots operating on the moon. To increase the efficiency of global path planning, we propose a Progressive Rapidly-exploring Random Tree (P-RRT) algorithm, which improves RRT in three aspects. First, to speed up the convergence rate, we proposed the Feasible Region-aware Ellipse Sampling strategy, which incrementally draws biased samples from an elliptical subspace with the current point and the target point as the focus. Second, we introduce dynamic forward step length to accelerate random tree growth. Third, given the wide range of applications for multi-core processors, we introduce parallel path planning, segmenting global path planning into several processing units, in an effort to further enhance the application efficiency of the algorithm. Finally, the proposed P-RRT is verified by extensive simulation experiments. The experimental results demonstrate the efficiency and practicability of the P-RRT algorithm.