Agile-RRT*: A Faster and More Robust Path Planner With Enhanced Initial Solution and Convergence Rate in Complex Environments

Abstract

Path planning is a critical process in mobile robot navigation. Sampling-based path planning algorithms represented by Rapidly Exploring Random Tree star (RRT*) have gained widespread adoption due to their asymptotic optimality and proven efficiency. However, when applied to intricate environments, characterized by narrow passages and cluttered obstacles, these algorithms encounter challenges in both the initial solution generation and the convergence towards the optimal path, mainly caused by the inefficient sampling strategy, thereby impeding its overall effectiveness. To address these limitations, we introduced Agile-RRT* (A-RRT*), an advancement of RRT* algorithm. Our contributions are twofold: firstly, we introduce an adaptive goal-biased sampling strategy, which employs an adaptive principle for determining the step size on the basis of the goal-biased strategy. This avoids getting trapped in local minima and enhances the efficiency of the initial solution generation. Secondly, we introduce a path optimization approach using a secondary tree and subset-informed sampling, to accelerate the convergence toward the optimal path. It optimizes the path by gradually shrinking the designed elliptical planning space around local states, which effectively narrows down the search space. The experimental results demonstrated that the proposed A-RRT* diminishes the initial solution search time by 71.00% and the sub-optimal solution search time by 82.86% in comparison to RRT*. The A-RRT* exhibits superior performance over RRT*, Informed-RRT*, P-RRT* and Quick-RRT* in terms of soundness and efficiency in narrow and intricate environments. This method could expedite efficient motion planning for drones and mobile robots in complex environments.

Keywords

• Path planning
• RRT*
• goal-biased strategy
• informed sampling
• complex environment