高效动态环境路径规划新算法，省时且渐近最优。
Asymptotically Optimal Lazy Lifelong Sampling-based Algorithm for Efficient Motion Planning in Dynamic Environments
- 仅评估子路径候选，大幅减少计算开销。
- 在复杂环境中比现有方法更快收敛到最优解。
- 适合机器人实时重规划，尤其适合移动障碍场景。
本文提出一种渐近最优的终身采样规划算法，融合终身规划与懒惰搜索的优点，适用于边评估成本高的动态环境中的快速重规划。该算法仅对最优解的子路径候选进行评估，显著节省评估时间，降低整体规划成本。通过一种新型有信息量的重布线级联机制，可在搜索图变化时高效修复搜索树。理论分析表明，在足够规划时间内，算法能收敛至最优解。在具有SE(3)和R^7状态空间的机器人系统上，于复杂环境中进行的规划实验显示，该算法在静态与动态任务中均优于多种先进采样规划器。对搭载Turtlebot 4的机器人在多人移动环境中的规划实验进一步验证了该算法的可行性与优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。