将RRT-Connect扩展为可渐进优化的规划器,兼顾速度与解质量。
AORRTC: Almost-Surely Asymptotically Optimal Planning with RRT-Connect
- 基于AO-x元算法改进RRT-Connect,实现任意时间收敛
- 7/8自由度机械臂上初始解速率达RRT-Connect水平,优化更快
- 适合高自由度机器人实时规划,尤其擅长复杂场景
快速获取高质量路径是运动规划的重要目标,尤其对高自由度机器人而言。传统满意型规划器虽能快速找到可行解,但无法保证最优性;而几乎必然渐近最优(a.s.a.o.)规划器虽有概率收敛保证,但计算开销大。本文利用AO-x元算法,将满意型RRT-Connect扩展为渐近最优规划器(AORRTC)。该方法在类似RRT-Connect的速度下获得初始解,并在额外时间内以任意时间方式收敛至最优解。理论证明其具备概率完备性和a.s.a.o.性质。在Panda(7 DoF)和Fetch(8 DoF)机械臂上,基于MotionBenchMaker数据集的实验表明:AORRTC初始解速度与RRT-Connect相当,且优于所测主流a.s.a.o.算法;同时在更短时间内收敛到更优解。在高自由度难题中,其可在毫秒级完成求解,而其他a.s.a.o.算法在秒级仍无法稳定求解。该性能在启用或禁用SIMD加速下均得到验证。
原文摘要 · Abstract (English)
Finding high-quality solutions quickly is an important objective in motion planning. This is especially true for high-degree-of-freedom robots. Satisficing planners have traditionally found feasible solutions quickly but provide no guarantees on their optimality, while almost-surely asymptotically optimal (a.s.a.o.) planners have probabilistic guarantees on their convergence towards an optimal solution but are more computationally expensive. This paper uses the AO-x meta-algorithm to extend the satisficing RRT-Connect planner to optimal planning. The resulting Asymptotically Optimal RRT-Connect (AORRTC) finds initial solutions in similar times as RRT-Connect and uses any additional planning time to converge towards the optimal solution in an anytime manner. It is proven to be probabilistically complete and a.s.a.o. AORRTC was tested with the Panda (7 DoF) and Fetch (8 DoF) robotic arms on the MotionBenchMaker dataset. These experiments show that AORRTC finds initial solutions as fast as RRT-Connect and faster than the tested state-of-the-art a.s.a.o. algorithms while converging to better solutions faster. AORRTC finds solutions to difficult high-DoF planning problems in milliseconds where the other a.s.a.o. planners could not consistently find solutions in seconds. This performance was demonstrated both with and without single instruction/multiple data (SIMD) acceleration.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。