1 引言（Introduction）

面对日益激烈的太空竞争，代表国家科技实力的火星探测^[1]、月面建造^[2]、在轨捕获^[3]以及深空自主导航^[4]等关键技术的突破与应用日益迫切^[5]，已成为大国博弈的焦点。近年来，多智能体机器人系统（MARS）^[6]不断发展与完善，为太空挑战提供了新的机遇与途径。其中，多机器人协同探索与地图构建作为该领域研究中的基础性关键技术，是多机器人实现自主定位、规划与导航、自主作业的技术前提，目前已成为能够真正实现多机器人在外太空中协同完成高度自治任务的重要标志^[7-9]。

为使得多机器人能够应对复杂多变的未知环境和满足探索任务需求，国内外诸多学者针对多机器人协同探索以及任务分配方法进行了大量研究。Yamauchi^[10-11]最早提出基于边界法的未知环境探索方法，利用图像处理中的边缘检测技术对已知区域和未知区域之间的边界进行检测和提取。然而，该算法需要对整个区域进行遍历搜索，因此相当耗费计算资源，极大限制了探索区域的空间尺寸。为了提高边界检测的效率，高环宇等^[12]在此基础上提出基于边界搜寻思想并适用于2维栅格地图的未知区域探索方法，以环境地图中边界上的出口区域为逻辑点，以节点距离成本为权重，建立待探索出口区域节点的动态探索树，并通过SLAM（同步定位与地图创建）算法引导机器人移动到未知区域内的探索目标点处。Umari等^[13]提出了一种基于快速扩展随机树（RRT）的改进边界探索方法，通过将RRT算法引入到全局/局部边界点检测器中来不断提取边界点，从而提高边界点的获取效率。Hu等^[14]提出了一种基于Voronoi图的多机器人自主探索方法，采用一种包含一个高级决策层和一个低级决策层的分层控制架构，为每个机器人分配不同的目标点，并在此基础上提出了一种基于深度强化学习的避障算法，从而提高机器人协同探索的自主性。Zhang等^[15]提出了一种基于改进RRT算法的优化地图探索方法，综合考虑机器人的运行时间和轨迹长度并建立了相应的评价指标。Mendonca等^[16]提出了一种使用动态模糊认知地图和蚁群算法的多机器人探索方法，设计并使用了3种模糊逻辑所构成的控制器，使得机器人能够以更短的行进距离完成未知区域探索任务。Clark等^[17]受行星探测的启发，通过构建分布式通信网络来管理多机器人目标，同时使用虚拟队列和排队论来约束和分析控制器系统，降低了机器人定位的不确定性并获得了更好的覆盖率。金毅康^[18]提出一种基于RRT—广度优先搜索（BFS）的边界探索算法，摒弃了RRT算法执行过程中的均值漂移聚类步骤，节省了计算资源。然而，以上关于多机协同探索算法的研究大多局限于边界探索效率和任务分配策略，较少考虑边界点检测的有效性与探索目标点收益的最大化问题。此外，大部分算法都采用随机采样方法进行边界检测，这将导致获取到的边界点存在随机性，继而导致多机器人在探索过程中的分散程度变高，并最终影响多机探索的效率和稳定性。

本文的主要研究目标是多机器人协同探索方法。通过提出改进的边界探索算法对环境地图中的边界点进行细化处理，提高探索目标点的最大收益。通过引入改进的任务分配算法对探索目标点进行动态分配，从而降低多机探索的耗时，提高多机探索的效率。本文的主要贡献包括：

(1) 构建多机器人协同探索系统，并以功能包方式对各模块进行组织和管理，实现各种类型的多机器人系统之间功能模块的快速部署与算法的快速移植。需要指出的是，该系统的优势不仅体现在软件仿真层面，在硬件样机层面上依然适用。

(2) 提出一种基于快速扩展随机树—贪婪边界搜索（RRT-GFE）的新型边界探索方法，利用划分形成的Thiessen多边形区域搜索环境边界，并提取连续边界域的形心作为探索目标点，实现探索目标点收益的最大化。

(3) 提出一种基于改进市场机制的多机器人任务分配方法，通过实时计算机器人与探索目标点之间的权重并动态调整虚拟机器人数量的方式，将探索目标点合理有效地分配给各个机器人，提高多机探索的效率。

2 多机器人协同探索系统（Multi-robot cooperative exploration system）

多机器人协同区域探索是指多台移动机器人以迅速覆盖整个探索区域为目标，依靠自身传感器感知周围环境并按照一定的协同策略自主完成导航、探测及地图构建^[19]。

2.1 移动机器人里程计模型

以多机器人未知环境下的协同探索方法为主要研究问题，选用3台典型的两轮差速移动机器人作为研究对象，简化的里程计模型如图 1所示。

图 1中，设机器人车身直径为$ d $，航向角为$ \theta $，左、右轮速度分别为$ v_{\rm l} $和$ v_{\rm r} $，角速度为$ \omega $，则机器人总体速度可用两轮连线中心点处的速度$ v $表示。当机器人移动时间间隔$ \Delta t $较短时，$ \theta $可表示为

$ \begin{align} \theta \approx \sin \theta =\frac{l}{d} \end{align} $

(1)

其中，$ l $为机器人$ \Delta t $时间间隔内驶过的距离，左、右轮驶过的距离可近似为直线距离$ v_{\rm l} \Delta t $、$ v_{\rm r} \Delta t $，且：

$ \begin{align} l=({v_{\rm r} -v_{\rm l}})\Delta t \end{align} $

(2)

此时，通过简单的数学推导即可得到两轮差速移动机器人的运动学方程，即机器人左、右轮轮速与线速度、角速度的关系为

$ \begin{align} \begin{bmatrix} {v_{\rm l}} \\ {v_{\rm r}} \end{bmatrix}= \begin{bmatrix} v-\dfrac{\omega l}{2} \\[6pt] v+\dfrac{\omega l}{2} \end{bmatrix} =\begin{bmatrix} 1 & -\dfrac{l}{2} \\[6pt] 1 & \dfrac{l}{2} \end{bmatrix} \begin{bmatrix} v \\ \omega \end{bmatrix} \end{align} $

(3)

其中，线速度$ v $和角速度$ \omega $可通过机器人操作系统（ROS）中的速度话题（cmd_vel）进行设定和发布，从而控制机器人左、右轮的速度。

2.2 多机器人协同探索系统构建

所设计的协同探索系统基于ROS构建并以功能包方式对各模块进行组织和管理，通过改进Umari等^[13]提出的rrt_exploration多机探索平台，建立了基于RRT-GFE探索方法的多机器人协同探索系统MRCES（multi-robot cooperative exploration system），其系统组成如图 2所示。该系统分别由多地图融合模块、全局/局部边界点检测模块、多机器人任务分配模块和机器人运动控制模块（包含路径规划器与SLAM模块^[19]）组成并协调工作。其中，多机器人地图融合算法部署在多地图融合模块中，基于RRT-GFE方法的边界探索算法部署在全局/局部边界点检测模块中，基于改进市场机制的多机器人任务分配方法则部署在多机器人任务分配模块中。

多机器人协同探索系统的工作原理为：探索任务启动后，SLAM模块首先从激光雷达和里程计中获取传感器数据，为机器人提供位姿和建图的相关信息，用于机器人自主定位与全局/局部地图构建；其次，全局/局部边界点检测模块通过话题通信的方式订阅实时发布的位姿信息，获取已知区域与未知区域的连续边界并提取其形心作为探索目标点；再次，多机器人任务分配模块基于改进市场机制算法实时计算机器人与探索目标点之间的权重，并将边界点合理有效地分配给各个机器人，同时运动控制模块根据所提供的边界点计算到达目标点的路线，并将线/角速度指令发送给相应的机器人；最后，多地图融合模块计算局部地图之间的重叠区域，并将多张局部地图融合为一张全局地图。

3 多机器人协同探索算法设计（Design of the multi-robot cooperative exploration algorithm） 3.1 基于Thiessen多边形的环境建模与划分方法

为实现多机器人对探索区域的持续覆盖，采用Thiessen多边形^[20]对已探索到的区域进行持续划分，并最终形成可用于多机器人自主导航的全局路径地图。在此过程中，Thiessen多边形的数量始终与机器人数量相同，且每个多边形中仅存在一个正在执行探索任务的机器人，其形状随着机器人位置的变化而变化。具体的数学描述如下：

$ \begin{align} V_{i} =\{p\in S, \; \| {{{\mathit{\boldsymbol{p}}}}-{{\mathit{\boldsymbol{r}}}}_{i}} \|\leqslant \| {{{\mathit{\boldsymbol{p}}}}-{{\mathit{\boldsymbol{r}}}}_{j}} \|, \; \forall i\ne j\} \end{align} $

(4)

其中，$ S $表示当前探索区域，$ p $表示探索区域内的任意离散点，且对应的位置坐标为$ ({x_{i}, y_{i}}) $，$ V_{i} $表示第$ i $个机器人所在的Thiessen多边形区域，$ r_{i} $表示第$ i $个机器人的当前位置，$ \| \cdot \| $表示探索区域内任意2个离散点之间的欧氏距离。

RRT边界探索算法是一种基于采样的搜索方法^[21]，具有快速扩展并迅速覆盖未知区域的特性，能够用于检测已知区域和未知区域的边界点。因此，本文将基于Thiessen多边形的环境建模与划分思想与RRT-GFE的细化搜索方法相结合，利用划分形成的多边形环境区域能更快找到边界并进一步细化搜索目标点。另外，当所有区域均被探索到之后，即可获得完整的环境区域地图$ A $，此时可以认为全局地图是一个尺度确定的几何平面。由此还可将$ A $划分成$ n $个相互邻接的多边形，并且每个多边形中有且只有一个离散点。生成的路径也被称作Voronoi路径^[22]。

综上所述，Thiessen多边形与Voronoi路径的生成步骤如下：

Step 1：根据RRT算法生成的树节点构建三角网，即构建Delaunay三角网，同时记录对应的离散节点和形成的三角形编号。

Step 2：计算并记录每个三角形所对应的外接圆圆心。

Step 3：遍历三角形链表，搜索与当前三角形三边共边的相邻三角形。

Step 4：若第3步找到了与之三边共边的相邻三角形，则将寻找到的三角形外心与其自身外心相连接，并存入Voronoi边链表中；若未找到，则求出其最外边的中垂线射线，并存入Voronoi边链表中。

Step 5：遍历结束，根据所找到的Voronoi边绘制Voronoi路径。

图 3与图 4展示了Voronoi路径生成的过程，以及基于Thiessen多边形的探索区域划分效果。其中，在树节点和边界给定的情况下，Thiessen多边形可将探索区域划分为多个多边形区域，且每个多边形与一个节点相关联。此时输入任意离散点坐标，均可通过Thiessen多边形确定与之最接近的树节点，生成用于机器人路径规划与导航的Voronoi路径。

3.2 基于RRT-GFE的全局/局部边界点探索算法

针对传统RRT边界探索算法存在探索目标点随机性较大且重复探索耗时久等问题，提出了一种基于RRT-GFE的边界探索方法，在保留RRT算法提取边界点速度快且不受空间维度限制等优势的同时，结合GFE算法对边界区域进行细化处理，提取连续边界域的形心作为探索目标点，从而消除RRT算法提取边界点的随机性并实现探索目标点的收益最大化。

RRT边界点检测算法与RRT-GFE边界点检测算法的工作原理分别如图 5、6所示。其中，红色方框表示机器人当前所处位置，蓝色方框表示提取出的初始边界点，绿色和粉色方框分别为RRT算法和RRT-GFE算法处理后得到的探索目标点，红色圆圈表示聚类算法预先设定的作用范围，黄色曲线表示移动机器人的全局路径。对比图 5、6可知，传统RRT算法在边界点处理上存在随机性问题，而这种随机性将会导致探索目标点的分散程度变大甚至存在边界点遗漏等风险，直接影响机器人的探索效率。如图 5所示，经RRT边界点检测算法处理后得到的探索目标点分别为标号2、3、4、5、6的绿色方框，当机器人启动探索程序后，会优先驶向2号方框，此时若机器人所配备的激光雷达扫描范围较小，则机器人在抵达2号方框时，其雷达扫描范围无法完全覆盖左上方的3号和4号方框，因此机器人至少需要经历2次探索过程才能够实现此边界区域的全覆盖，这无疑将增加探索过程的耗时。图 6中采用改进的RRT-GFE算法对整个连续边界域进行求解，同时提取各个边界域的形心作为探索目标点（标号2、3、4、5的粉色方框），此时机器人在启动探索程序后将直接驶向2号方框，从而降低无效探索过程的耗时，提高机器人的探索效率。

RRT-GFE算法的伪代码如算法1和算法2所示，且分别运行于图 2蓝色方框内的全局/局部边界点检测模块中。其中，局部边界检测模块运行在各个机器人平台上，且在检测到有效边界点后，其内部的随机树会重置并以当前位置为新的初始点重新生长。全局边界检测模块则运行在主机中，该模块会在初始化阶段为每台机器人添加一棵固定的随机树，该树不会随机器人移动而改变或重置。当多棵随机树的顶点相遇时会合并为一棵全局树，并以提高计算负载为代价，增强检测模块对远离机器人区域边界点的检测。

算法的主要流程如下：

Step 1：初始化顶点$ x_{\rm{init}} $和边缘集$ \phi $，同时SampleFree函数在预先设定的空间区域内随机采样一个初始点$ x_{\rm{rand}} $及最接近$ x_{\rm{rand}} $的第1个顶点$ x_{\rm{nearest}} \subset V $，通过Steer转向函数计算并生成$ x_{\rm{new}} $点。

算法1：RRT-GFE全局边界点检测算法

1: V ← xinit; E ← ϕ; 2: while True do 3:   xrand ← SampleFree; 4:   xnearest ← Nearest(G(V; E); xrand; ξ); 5:   xnew ← Steer(xnearest; xrand); 6:   if GridCheck(Map; xnearest; xnew) = −1 then 7:     PublishPoint(xnew); 8:     xfrontier ← xnew; 9:     Qlist ← ϕ; Qfp ← xfrontier; 10:     PushBack(Qlist; Qfp); 11:     while Qlist非空集do 12:       Point ← GetFrontier(Qlist); 13:       for每一个边界点及其周围近邻点do 14:         if存在有效边界点then 15:           PushBack(Qlist; Qneighbor); 16:         Qfp ← Qfp ∪Qneighbor; 17:       end if 18:     end for 19:     end while 20:     Centroid ← GetCentroid(Qfp); 21:     PublishCentroid(Centroid); 22:     Qfc ← Centroid; 23:   else if GridCheck(Map; xnearest; xnew) = 1 then 24:     V ← V ∪ {xnew}; E← E ∪ {xnearest; xnew}; 25:   end if 26:   if {xnew} ∩Vi ∈= ϕ then 27:     V ← Vi ∪ {xnew}; 28:   end if 29: end while 30: return Qfc

算法2：RRT-GFE局部边界点检测算法
1: V ← xinit; E ← ϕ; 2: while True do 3:   xrand ← SampleFree; 4:   xnearest ← Nearest(G(V; E); xrand); 5:   xnew ← Steer(xnearest; xrand); 6:   if GridCheck(xnearest; xnew) = −1 then 7:     PublishPoint(xnew); 8:     V ← xcurrent; E ← ϕ; 9:   else if GridCheck(xnearest; xnew) = 1 then 10:     V ← V ∪ {xnew}; E ← E ∪ {xnearest; xnew}; 11:   end if 12: end while

Step 2：定义占据栅格地图中落在未知区域内的单元格为1，当机器人执行探索任务时，Nearest函数搜索到$ x_{\rm{rand}} $的最近邻点$ x_{\rm{nearest}} $，GridCheck函数读取各个单元格值并将环境分为未知区域、已知区域和障碍区域，同时判断$ x_{\rm{new}} $是否为有效边界点（判断$ x_{\rm{new}} $和$ x_{\rm{nearest}} $的连接线上的任意点是否处于未知区域内）。

Step 3：Steer转向函数按步长$ \xi $依次求出$ x_{\rm{new}} $，如式(5) 所示，并将计算得到的$ x_{\rm{new}} $保存到队列$ Q_{\rm{list}} $中。同时调用GetFrontier函数判断队列$ Q_{\rm{list}} $中的边界点$ x_{\rm{frontier}} $及其周围近邻点是否为有效边界点。若条件为真，则更新队列$ Q_{\rm{fp}} $；若条件为假，则结束边界搜索，程序返回连续边界域内所有边界点的集合$ Q_{\rm{fp}} $。

$ \begin{align} {{\mathit{\boldsymbol{x}}}}_{\rm{new}} ={{\mathit{\boldsymbol{x}}}}_{\rm{nearest}} +\frac{{{\mathit{\boldsymbol{x}}}}_{\rm{rand}}} {\| {{{\mathit{\boldsymbol{x}}}}_{\rm{rand}} -{{\mathit{\boldsymbol{x}}}}_{\rm{nearest}}} \|}\xi \end{align} $

(5)

Step 4：在Step 3的基础上，调用GetCentroid函数计算边界点集合$ Q_{\rm{fp}} $的形心并保存到队列$ Q_{\rm{fc}} $中，利用PublishCentroid函数发布探索目标点并显示在Rviz软件中的地图上。

由于全局边界检测器中的随机树不会随着机器人的移动而改变或重置，因此，随着树的不断生长与扩展，其顶点数量会越来越多，探索区域内的Thiessen多边形也会越来越密集，此时全局边界点的检测速度变慢，求解耗时增加，导致探测效率下降。为了兼顾全局探测精度与整体探索效率，需要采用局部边界检测器来加快边界点的检测速度。算法的核心伪代码如算法2所示。

局部边界点检测算法与全局边界点检测算法的整体思路类似，但局部边界点检测算法中的GridCheck函数仅判断$ x_{\rm{new}} $以及$ x_{\rm{new}} $与$ x_{\rm{nearest}} $连接线上的单元格，其目的在于加快局部边界点的检测速度。当探索程序执行后，全局边界点检测模块与局部边界点检测模块相互配合，优势互补，确保环境区域能够被完全探索和感知。

3.3 基于改进市场机制的多机器人任务分配方法

与3.2节所提到的全局/局部边界点检测算法相比，多机器人协同探索过程中所涉及的任务分配算法同样是一项有待进一步研究的关键技术。在3.2节得到的探索目标点的基础上，采用基于改进市场机制的多机器人任务分配方法，确保机器人能够获得合理的探索目标点，从而显著减少重复探索过程的耗时。

其算法的主要思想为：假设由$ n $个机器人组成的多机器人系统协同执行区域探索任务，由3.2节可知，此时队列$ Q_{\rm{fc}} $记录了各个连续边界域上的形心。定义各个探索目标点与机器人之间的权重$ W_{i, j} $为距离成本函数$ f_{\rm C} $、效用函数$ f_{\rm U} $和惩罚函数$ f_{\rm P} $的函数。其中，距离成本函数$ f_{\rm C} $采用机器人位置$ p_{\rm{robot\_}i} $与探索目标点$ p_{\rm{fc\_}j} $之间的欧氏距离表示：

$ \begin{align} f_{\rm C} (i, j)=\| {{{\mathit{\boldsymbol{p}}}}_{\rm{robot\_}i} -{{\mathit{\boldsymbol{p}}}}_{\rm{fc\_}j}} \| \end{align} $

(6)

效用函数$ f_{\rm U} $采用机器人到达探索目标点所能覆盖的未知区域面积$ S(p_{\rm{fc\_}i}) $表示，其中$ S(p_{\rm{fc\_}i}) $表示以探索目标点$ p_{\rm{fc\_}i} $为圆心，激光雷达扫描半径为效用半径的未知区域栅格面积，且效用值越大，表明该探索目标点对机器人的吸引程度越大。同时，为了提高探索目标点分配的合理性，避免同一个探索目标点被重复分配给多台机器人，需引入惩罚函数$ f_{\rm P} $对其进行重新评估，具体原理如图 7所示，其中图 7(a)表示存在重叠区域，图 7(b)则表示不存在重叠区域。当探索目标点$ p_{\rm{fc\_}1} $分配给机器人1后，其附近$ p_{\rm{fc\_}2} $的效用值将会下降，且下降值为重叠区域的面积$ S_{\rm{overlap}} $，如式(7) 所示。当两者完全重合时，其效用值与惩罚值将相互抵消，此时该目标点不存在任何效用价值。

$ \begin{align} f_{\rm P} (i, j) =\begin{cases} S_{\rm{overlap}}, & \| {{\mathit{\boldsymbol{p}}}}_{\rm{fc\_}i} -{{\mathit{\boldsymbol{p}}}}_{\rm{fc\_}j} \|<d_{\rm{fc}} \\ 0, & \rm{其他} \end{cases} \end{align} $

(7)

其中$ d_{\rm{fc}} $为效用直径，且数值是激光雷达扫描半径的2倍。

此时能够得到各个探索目标点与机器人之间的权重$ W_{i, j} $：

$ \begin{align} W_{i, j} =\lambda \times ({f_{\rm U} (i)-f_{\rm P} (i, j)})-f_{\rm C} (i, j) \end{align} $

(8)

其中$ \lambda $为确保效用函数值与距离成本量级一致性的缩放因子，其具体取值通常由实验确定。

此时的权重矩阵$ \mathit{\boldsymbol{W}} $可表示为$ n\times n $方阵，如式(9) 所示，并等效为指派问题中的指派矩阵，从而作为Hungarian算法^[23]的输入参数。

$ \begin{align} {\mathit{\boldsymbol{W}}} =\begin{bmatrix} {W_{1, 1}} & \cdots & {W_{1, n}} \\ \vdots & \ddots & \vdots \\ {W_{n, 1}} & \cdots & {W_{n, n}} \end{bmatrix} \end{align} $

(9)

其中，为提高分配效率，在实际任务分配过程中添加虚拟机器人，使得机器人的数量与探索目标点的数量保持相同，且虚拟机器人的数量在任务分配和协同探索的过程中动态调整，确保探索过程能够有序进行。形成的任务分配算法的伪代码如算法3所示。

算法3：多机器人任务分配算法

输入: 连续边界域上的形心队列Qfc、机器人数量N 输出: 每个机器人j所分配到的探索边界点pfc_i 1: while True do 2:   nfc ← length(Qfc); nrobots ← length(N); 3:   for i = 1 : nfc do 4:     for j = 1 : nrobots do 5:       fC[i][j] ← norm(pfc[i]; probots[j]); 6:       fU[i] ← GetUtilityValue(Qfc[i]); 7:       if norm(pfc[i]; pfc[j]) < dfc then 8:         fP[i][j] ← overlap(i; j); 9:       else 10:         fP[i][j] ← 0; 11:       end if 12:     end for 13:   end for 14:   W[i][j] ← λ ×(fU[i]− fP[i][j])− fC[i][j]; 15:   W ← W[i][j]; 16:   iindex ← Hungarian Algorithm(W); 17:   assign(robotWithID = (N[iindex]; Qfc[iindex])); 18: end while

3.4 多机器人地图融合方法

地图构建是多机器人协同探索过程中不可或缺的环节，由于本文的研究重点主要集中在多机器人协同探索方面，因此本节将采用Hörner^[24]提出的开源算法map-merging在仿真与样机实验中进行地图融合。该算法基于图像拼接方法设计，是一种间接地图融合方法。由于该算法基于机器视觉的方式实现，并基于随机采样一致性来提高位姿估计的准确性，使用概率模型来表示估计变换的可信度，因此，在硬件设备允许的范围内，该算法理论上能够实现无限张地图的合并。为了确保多机器人协同探索过程中地图融合的准确性，将多机器人之间相对位姿已知作为初始化条件进行探索与地图融合。算法的执行步骤如下：

Step 1：对每个占据栅格地图进行特征提取。

Step 2：基于提取得到的特征对栅格地图进行相互匹配，并记录匹配数目。

Step 3：判断匹配数是否小于设定阈值。若小于设定阈值，则令信任值为0；若满足设定阈值，则对特征点间的变换关系进行求解。

Step 4：根据Step 3求解出的变换关系建立坐标系之间的最大连通子图。

Step 5：根据Step 4得到的连通子图求解每个占据栅格地图中的最大生成树，并根据树节点之间关系依次求解各个子地图之间的变换关系。

图 8展示了该算法的地图融合效果。其中，图 8(a)~(c)分别为3台移动机器人所构建的局部地图，图 8(d)为融合后的全局地图。

4 实验与分析（Experiments and analysis）

为验证所提出的RRT-GFE算法的有效性和实用性，基于ROS搭建多机器人协同探索算法测试平台，并分别在Gazebo仿真场景和实际样机场景中对其进行验证。其中，涉及到的多机器人任务分配和地图融合方法均采用3.3节和3.4节中所提的方法。用于实验测试的3台移动机器人样机如图 9所示，同时，为降低外界环境及机器人传感器精度对实验测试的影响，将3台机器人样机的线速度/角速度、雷达扫描半径和位置测定频率设置为相同值，其型号与主要技术参数如表 1所示。受场地条件限制，实验测试均在一块4 m$ \times $10 m的矩形场地中展开，如图 10所示。此外，所有对比实验的软硬件配置设置相同（主机的硬件配置为：Intel i7-10750H @2.6 GHz处理器，16 GB RAM，GTX 1650Ti显卡，主机与3台移动机器人样机中所安装的软件版本均为：Ubuntu 18.04 LTS $ + $ ROS melodic）。

仿真和样机实验均选用机器人的探索距离与总耗时作为评价指标，考虑到实验过程中存在的偶然性，每组仿真/样机实验重复测试10次并记录相应的平均值和标准差作为最终实验结果。图 11、12展示了Gazebo仿真场景下的多机器人协同探索测试结果与建图效果。其中，图 12中地图里的灰色区域为已知区域，黑色为环境障碍，墨绿色则表示未知区域。机器人由红、蓝、绿3个空心方框表示。黄色方框为RRT-GFE算法处理后的边界形心点。将Umari等^[13]提出的RRT边界探索算法、金毅康^[18]提出的RRT-BFS边界探索算法以及本文提出的RRT-GFE算法进行对比实验，得到的仿真实验测试结果如图 13~15和表 2、3所示。其中，图 13(a)~(c)分别为3台移动机器人各自的探索距离，图 13(d)为探索总距离。对比表 2中3种算法的测试结果可以发现，RRT-GFE算法在Gazebo仿真场景下的探索平均耗时相较RRT和RRT-BFS算法分别减少约41% 和28.7%，探索总距离分别减少约39% 和30.9%，由此可见，RRT-GFE算法的优化效果明显，探索效率显著提高。

图 15和表 3分别展示了3台机器人在仿真实验中的探索距离以及任务分配结果。其中，表 3中的平均探索距离表示理想情况下各个机器人的探索距离，其数值上等于表 2中的总距离$ D $除以机器人总数。任务分配均匀程度则由机器人在仿真或样机场景下的实际探索距离的标准差来表征。通过对比表 3中的3组测试结果可以发现，当基于改进市场机制的多机器人任务分配算法与RRT-GFE边界探索算法相结合时，任务分配均匀程度最优，相较于第1、2组提升了约52.8% 和10.1%。由此可见，该任务分配算法优化效果明显，合理性提高显著。

图 16和图 17分别展示了实际样机场景下多机器人协同探索测试结果和建图效果。其中，图 17(a)~(c)分别为3台移动机器人所构建的局部地图，图 17(d)为融合后的全局地图。由于受通信时延、传感器精度误差以及车轮打滑等影响，实际样机实验的测试结果相比Gazebo仿真实验的测试结果较差，例如：图 17(d)所示的全局地图中存在部分噪点及重叠现象，与表 4中样机实验数据相比，表 2中的仿真数据同样存在部分差异（其中，RRT-GFE算法在样机实验中的探索平均耗时与总距离相比仿真实验增加约31.6% 和23.3%）。但总体来看，RRT-GFE算法仍然具有良好的探索表现，从图 18、图 19和表 4中不难发现，RRT-GFE算法在实际样机测试下的探索平均耗时相较RRT和RRT-BFS算法分别减少约46.8% 和31.3%，探索总距离分别减少约34.1% 和23.8%。此外，其探索总距离的标准差小于等于0.75 m，探索总耗时的标准差小于等于2.5 s。由此可见，RRT-GFE算法的优化效果明显，探索效率与鲁棒性提高显著。

图 20和表 5分别展示了3台机器人在样机实验中的探索距离以及任务分配结果。通过对比表 5中3种算法的测试结果可以发现，当基于改进市场机制的多机器人任务分配算法与RRT-GFE边界探索算法相结合时，任务分配均匀程度最优，相较于第1、2组提升了约47.2% 和18.7%。综合仿真与样机实验结果能够证明基于改进市场机制的多机器人任务分配算法具有良好的适用性。

5 结论（Conclusion）

以多机器人协同空间探索方法为主要研究内容，提出了一种基于RRT-GFE的多机器人协同空间探索方法，并通过仿真和样机实验验证其有效性和鲁棒性。结合仿真与样机实验测试结果得到以下结论：

1) 对于Gazebo仿真实验，RRT-GFE算法的探索平均耗时相较RRT和RRT-BFS算法减少约41% 和28.7%，探索总距离分别减少约39% 和30.9%。仿真结果表明，RRT-GFE算法相较RRT和RRT-BFS算法具有更高效省时的探索效果。

2) 对于实际样机实验，受通信时延、传感器误差以及车轮打滑等影响，其测试结果与仿真结果不一致，但总体来看，RRT-GFE算法仍然具有良好的探索表现，其探索平均耗时相较RRT和RRT-BFS算法分别减少约46.8% 和31.3%，探索总距离分别减少约34.1% 和23.8%。

3) RRT-GFE算法在仿真和样机实验中的探索总耗时标准差分别为2.3595 s和2.4161 s，探索总距离标准差分别为0.5563 m和0.7321 m。仿真与样机实验结果表明，RRT-GFE算法具有较好的稳定性和实用性。

4) 通过一系列仿真与样机实验测试后发现，当基于改进市场机制的多机器人任务分配算法与RRT-GFE边界探索算法相结合时，任务分配均匀程度最优，且优化效果明显。然而，3台移动机器人的最终探索距离始终存在一定差异，说明任务分配算法还需进一步优化完善。

针对多机器人协同空间探索方法仍存在诸多有待深入研究的问题，后续将从多机器人任务分配的合理性、边界点提取的有效性以及地图融合的去噪处理等方面作进一步研究。