标题：HMS-RRT: A novel hybrid multi-strategy rapidly-exploring random tree algorithm for multi-robot collaborative exploration in unknown environments
单位：School of Mechano-Electronic Engineering, Xidian University, Xi’an, China；School of Informatics, The University of Edinburgh, Edinburgh, United Kingdom
1、研究背景：
1、提出了一种基于混合多策略RRT（HMS-RRT）的边界检测算法，该算法考虑了获取的边界点的有效性，显著提高了探索效率。
2、提出了一种基于改进市场机制的多机器人任务分配策略，该策略可以实时计算机器人与探索目标点之间的权重，并将探索任务动态分配给每个机器人。
3、研究方法：
本文的多机器人探索系统框架如下图1所示：
图1 多机器人协同探索框架
框架包含多地图合并模块、任务分配模块、局部和全局边界检测模块以及机器人运动控制模块（包括路径规划器和SLAM模块）这四个模块。本文提出的HMS-RRT算法位于局部和全局边界检测模块，多机器人分配机制位于任务分配模块中。
HMS-RRT算法包含三种策略：自适应增量距离策略、子区域采样策略和基于贪婪边界的探索策略。
首先，在传统的基于RRT的边界检测算法中增量距离
图2 传统的基于RRT的边界检测算法的示意图
（a） RRT在简单环境中的性能（b） RRT的节点扩展示意图
图3 Voronoi多边形生成的示意图
其次，基于随机采样的传统RRT算法可以根据Voronoi图在初始扩展过程中快速偏向未探索的部分。然而，当已探索部分的比例增加时，RRT探索未探索部分的速率急剧降低。为了克服这一限制，确保算法能够快速覆盖未探索的区域，提出了基于高斯分布的子区域采样策略。即根据子区域
图5 机器人探索示意图
（a） 基于RRT的边界检测算法（b）基于贪婪边界的探索策略。
从而，本文提出的HMS-RRT算法完整流程如图6所示。其中，(a)机器人正在未知环境中执行探索任务。(b)Voronoi图用于在未知环境中对已探索区域进行连续划分。(c) HMS-RRT算法根据子区域的障碍物密度计算自适应增量距离，并根据环境中障碍物的密度动态调整扩展速率。(d)机器人基于HMS-RRT算法生成的无碰撞路径导航到边界区域。(e)从初始计算中获得的边界点。(f)使用基于贪婪边界的探索策略来细化搜索结果，并为机器人导航生成新的路径。
图6 HMS-RRT算法的设计流程
为了进一步提高多机器人协同探索的效率，本节提出了一种新的多机器人任务分配策略，该策略通过实时计算机器人与探索目标点之间的权重，并动态地将任务分配给每个机器人，从而最大限度地提高多机器人协作探索的效益。
假设一个多机器人系统由
图7 惩罚函数的示意图
最后，得到所有权重值组成的权重矩阵，并作为匈牙利算法的输入参数获得机器人与边界点的最优匹配解。
在实验部分，首先将HMS-RRT算法与M-RRT、ID-RRT、RRT-GFB、E-RRT以及RRT-BFS这5个算法对比，对比结果如图8所示。验证了HMS-RT算法在复杂环境中能够避免被困在局部极小值中，并且减少无效迭代次数，有效地克服了障碍效应。从而比其他五种算法具有更好的环境探索效率和鲁棒性。
其次，在多机器人协同探索实验中，通过在三种不同场景对比6个算法，实验结果如图9。结果表明所提出的多机器人协同探索方法可以显著提高多机器人任务分配的有效性和合理性。
表1 六个算法在三种不同场景下的实验结果
图10 提出的多机器人协同探索方法在不同场景下的仿真结果
4、结论：
