文章推荐 | 一种用于渐近最优路径规划的相关性采样策略

内容摘要

基于随机采样的路径规划算法是解决高维空间内机器人路径规划问题的重要工具。传统方法一般通过非最优的正向搜索树计算节点的cost-to-come值，并使用欧几里得距离计算节点的cost-to-go值，这种方法取得的估计值与实际偏大很大，影响路径规划效率。本文创新性地提出在一个改进后的相关性区域内采样，通过带有replanning过程的正向搜索获取cost-to-come值，以及不进行碰撞检测的反向搜索获取cost-to-go值，以此计算出更准确的相关性区域，有效提高路径规划的求解速度或当前路径的质量。在二维和三维空间内的仿真实验验证了本文提出的相关性采样策略用于机器人路径规划的高效性。

图文导读

（一）算法的基本流程如图1所示。每次循环开始时，规划器会采样n个点，构成整个空间的抽象表达(图1(a))；规划器通过不带碰撞检测的反向搜索，构建反向搜索树，计算每个节点的cost-to-go值(图1(b))；根据得到的cost-to-go值增量式地生长正向搜索树，如图1(c)所示；由于反向搜索树未进行碰撞检测，会产生错误的引导性信息，导致正向搜索树在生长过程中会和障碍物发生碰撞，因此规划器通过在碰撞区域附近增加采样点数量并重新计算cost-to-go值，引导正向搜索树越过障碍物，如图1(d)所示。同时replanning过程也会优化正向搜索树，让正向搜索树的节点近似更优的cost-to-come值。

图1 渐进最优路径规划算法过程（二）具有自适应估计的相关性采样策略算法流程如Algorithm 1所示。通过删除缺少正反向搜索树父节点的节点，缩小采样点集合，提高查找最近节点等操作的效率；规划器会优先进行反向搜索，只有当反向搜索树无法提供更高质量的cost-to-go值时，规划器才会进行正向搜索过程；采样和搜索交替进行，直到规划器输出的解的质量达到任务要求或者到达规定时间。函数的采样过程如Algorithm 2和3所示。在每次采样过程中，算法一次性采集多个点，并确保这些采样点都位于free space内；评估正向搜索树中的各个节点，按照与求解问题所需扩展区域的相关性对其排序；规划器在优先级最高的一组节点的相关性区域内进行采样。为避免和反向搜索树中已经存在的采样点重合，规划器在采样过程中对距离和方位都增加了高斯噪声，用来提高采样过程的随机性。同时，为保证基于随机采样的路径规划算法的概率完整性，规划器也会通过均匀的随机采样采集一定比例的采样点，该比例属于根据经验调节的参数，一般在50%左右。

（三）在Open Motion Planning Library（OMPL）的BugTrap环境下，本文方法与RRT#、AIT*算法的性能对比如图3所示。图3(a-d)展示了RRT#算法的规划过程，可以明显看出其节点因为replanning过程而具备更优的cost-to-come值（搜索树内的节点通常连接到最优的父节点）。图3(e-h)展示了AIT*算法的规划过程，由于反向搜索过程提供了cost-to-go值，AIT*算法仅需要维持一棵较小的正向搜索树。在路径规划问题中最耗时的是碰撞检测，但AIT*算法的反向搜索树的构建过程不包含碰撞检测，所以即使AIT*算法维持一棵较大的反向搜索树，其整体表现仍然优于其他同类算法。图3(j-m)展示了本文方法的规划过程，可以看出在障碍物的拐角处是最容易发生碰撞的位置，这是由不做碰撞检测的反向搜索树提供的不准确引导信息导致的。本文方法在这一范围内的采样点更加密集，使得正向搜索过程更有可能通过障碍物。与AIT*算法相比，本文方法规划的路径更直，并删除了很多无效的节点。

图3 本文所述方法与RRT#，AIT*算法的对比（四）在OMPL平台的BugTrap、Maze、RandomPolygons环境中，BIT*、AIT*、Informed RRT*、ABIT*、RRT#、RRT*算法的对比结果如图4和图7所示，本文所述算法的初始解质量明显优于其他算法，并且在收敛速度等方面也取得不错的表现。图4 2D环境中的仿真实验结果 图7 3D环境中的仿真实验结果

【作者信息】

Chenming Li^a, Fei Meng^a, Han Ma^a, Jiankun Wang^b,*,  Max Q.-H. Meng^a,b,c,*a Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong 999077, Chinab Department of Electronic and Electrical Engineering, Southern University of Science and Technology, Shenzhen 518055, Chinac Shenzhen Research Institute of the Chinese University of Hong Kong, Shenzhen 518057, China* Author to whom correspondence should be addressed: [e-mail]，[e-mail]

【DOI】

https://doi.org/10.1016/j.birob.2023.100113

【全文链接】

关于本刊

Biomimetic Intelligence and Robotics（《仿生智能与机器人（英文）》，CN 37-1527/TP，ISSN 2667-3797）是由教育部主管，山东大学主办，山东大学科技期刊社与爱思唯尔（Elsevier）联合出版的国际学术期刊，2019年入选中国科技期刊卓越行动计划。目前已被Ei Compendex、Scopus和DOAJ等国际数据库收录。

Biomimetic Intelligence and Robotics聚焦仿生智能与机器人领域，主要发表高质量原创理论和应用研究成果。涉及领域包括但不限于：仿生设计、仿生材料、仿生驱动与感知、工业机器人、服务机器人、特种机器人、医疗机器人、微型和纳米机器人、软体机器人、外骨骼系统、机器学习、人机交互、运动学和动力学、运动规划与控制、自主系统、多机器人系统等。

期刊接收包括原创研究论文、综述、短篇通讯等多种类型的文章，目前对作者和读者均免费，平均审稿周期30天，诚邀广大学者将高质量的创新成果投稿至本刊。

其他推荐

【专题征稿】- 仿生软体机器人：驱动、感知与集成仿生杂谈 | 山高路险坑深 看我 α-WaLTR【本期目录】Vol‍ume 3 Issue 3 September 2023文章推荐 | 手术器械透明化：微创内镜手术中的遮挡去除喜讯！Biomimetic Intelligence and Robotics被Ei收录

点击“阅读原文”