Adaptive Informed RRT*: Asymptotically Optimal Path Planning With Elliptical Sampling Pools in Narrow Passages

다국어 초록 (Multilingual Abstract)

The rapidly exploring random tree star (RRT*) is a conventional algorithm for path planning that aims to establish a collision-free path for robots from a starting point to a goal by constructing an exploration tree using randomly generated samples. However, inefficient sampling strategies and inadequate scales of searching trees increase the burden of calculation. Moreover, the necessity of sufficient trees has a significant impact on computation time, which is rarely investigated in previous research. To address the challenges of optimal path planning in narrow passages, we propose the adaptive informed RRT* (AI-RRT*), which not only asymptotically converges to an optimal solution but also achieves this with reduced computational time and a shorter path length. An attempt to identify accessible narrow passages is executed in advance to satisfy the traversability of robots. Also, a hybrid sampler is constructed to generate samples efficiently using the prior knowledge of narrow passages. Significantly, an adaptive tree growth strategy is introduced to evaluate the necessity of a third tree. After finding an initial solution, a local optimization method based on elliptical sampling pools is devised to enhance existing solutions. The mathematical proof demonstrates the asymptotic optimization of the sampling pool method within a limited number of iterations. Finally, the simulation results confirm that the AI-RRT* algorithm outperforms other sampling-based path planners in obtaining both an initial solution and an optimal solution in narrow passages. This is evidenced by its faster computation time, shorter path length, higher travelability, and more stable performance of the algorithm.