動的環境における効率的な運動計画のための漸近最適な遅延生涯サンプリングベースアルゴリズム
Asymptotically Optimal Lazy Lifelong Sampling-based Algorithm for Efficient Motion Planning in Dynamic Environments
動的環境でエッジ評価が高コストな場合に、生涯計画と遅延探索を組み合わせて最適解を効率的に再計画するサンプリングベース運動計画法を提案し、ロボットシステムでの有効性を示した。
著者: Lu Huang, Jingwen Yu, Jiankun Wang, Xingjian Jing
分類: cs.RO
原文アブストラクト
The paper introduces an asymptotically optimal lifelong sampling-based path planning algorithm that combines the merits of lifelong planning algorithms and lazy search algorithms for rapid replanning in dynamic environments where edge evaluation is expensive. By evaluating only sub-path candidates for the optimal solution, the algorithm saves considerable evaluation time and thereby reduces the overall planning cost. It employs a novel informed rewiring cascade to efficiently repair the search tree when the underlying search graph changes. Theoretical analysis indicates that the proposed algorithm converges to the optimal solution as long as sufficient planning time is given. Planning results on robotic systems with $\mathbb{SE}(3)$ and $\mathbb{R}^7$ state spaces in challenging environments highlight the superior performance of the proposed algorithm over various state-of-the-art sampling-based planners in both static and dynamic motion planning tasks. The experiment of planning for a Turtlebot 4 operating in a dynamic environment with several moving pedestrians further verifies the feasibility and advantages of the proposed algorithm.
