用于异构团队搜索救援的多机器人任务分配框架
用于异构团队搜索救援的多机器人任务分配框架
在灾害发生后，高效的搜索和救援行动需要机器人和人类之间的协作。现有的规划方法侧重于特定方面，但忽视了信息收集、任务分配和规划等关键要素。本文提出了一种全面的框架——多阶段多机器人任务分配（MSMRTA），集成了侦察、任务分配和路径规划阶段，根据机器人能力、受害者需求和过去的机器人表现优化任务分配。实验结果表明，与最先进的基线相比，该框架在四张地图上的评估性能显著提高了97%。
一、引言
机器人技术的进步使其能够协助执行危险的人类回避搜索和救援任务。此类操作通常需要多个机器人和人类的协调，但这带来了各种挑战。这些挑战涵盖了具有限制的不同环境中的不同任务，强调了有效的多机器人任务分配框架的重要性。现有框架缺乏对信息收集、分配和规划的全面包容，而且随着机器人多样性的增加，优化它们变得更加复杂。为了解决这些问题，我们提出了一个用于搜索和救援的侦察集成框架，包括多阶段多机器人任务分配（MSMRTA）和路径规划。我们的框架优化了不同功能机器人对特定任务的分配。任务分配采用优化和基于市场的技术，增强了实用性。对各种地图复杂性的实证评估表明，与基线 (MRGA) 相比，规划时间显著减少 (97%)，随着机器人受害者实例的增长，规划时间略有增加 (61.2%)。
二、相关工作
作为人道主义研究领域，用于搜索和救援行动的机器人技术的发展仍然是一个重要的研究领域。为了提高多机器人搜救效率，Quattrini Li等人引入了语义线索，而Liu等人采用了分层强化学习。为了进一步提高系统的整体性能，我们通过二进制向量集成了与机器人的能力和需求相关的语义。
多机器人任务分配（MRTA）对于高效的搜索和救援任务至关重要，分为集中式方法、分散式方法和混合方法。例如，赵等人采用集中式方法使用异构机器人来定位幸存者，而我们的方法则利用侦察队来加速搜索。去中心化方法，以 Mouradian 等人为例，利用机器人间通信的多目标优化。相比之下，我们的框架采用独立于通信的蚁群算法来进行有效的侦察。混合方法，如 Liu 等人，将自主性和人工干预结合起来，而混合框架将任务建模为多个旅行商问题。我们独特的方法独立采用A算法*进行不同的计算。 MRTA 的进一步分类涉及基于优化的和基于市场的 方法。两者都有优点和缺点。在我们的论文中，我们提出了多阶段多机器人任务分配（MSMRTA）算法，集成了这两种技术以提高效率。
三、问题描述
在将受害者需求分配给救援队之前，必须使用一组制服机器人通过侦察会议收集包括位置和需求在内的基本信息。这些机器人可以初步了解救援行动的各个方面，例如受害者人数、位置和需求。本研究解决的主要问题是在建筑物中执行搜救任务的异构机器人团队的任务分配。所提出的解决方案适用于同质和异构机器人组，适应不同需求的任务。引入的多阶段多机器人任务分配 (MSMRTA) 框架结合了优化驱动和基于市场的规划阶段。一个关键方面是算法 2 中概述的需求分析，其中 MSMRTA（包括用于导航建筑物障碍物的 A* 路径规划算法）将受害者需求分配给具有适当能力的机器人。该框架的核心流程如算法 1 所示，分配结果存储在指定变量（B2、B3、B4）中。通过实现代码的开源可用性，促进了结果的可重复性。
A.侦察
在灾后紧急情况下，迅速评估环境提供的至关重要的受害者分发数据。我们采用一个2D网格仿真模型的建筑布局和属性。
我们的 "侦察 "功能（算法 1）使用环境地图来获取受害者信息–ID、位置和要求。机器人采用蚁群网格搜索算法，模仿蚂蚁搜索策略，并通过搜索表防止冗余覆盖。侦察兵拥有可调整的视场深度（VFD），用于检测受害者，并根据障碍物进行调整。侦察兵可识别 VFD 附近的受害者（图 2），并提取细节。智能体们通过在网格中向前、向后、向右或向左移动来导航。
B. 任务分配
受文献的启发，我们以异构机器人机群为背景来解决任务分配问题。在本文中，我们交替使用 "任务 "和 "受害者 "来指代同一个实体。机器人可以完全满足受害者的要求，也可以满足部分要求，这取决于它们的感知和执行能力。根据提出的论点，我们提出了一个混合多阶段任务分配框架，其中集成了优化和基于市场的方法。建议的框架遵循文献中的分类法，通过将任务分配给多任务（MT）机器人的延时分配（TA），为一组单机器人任务（SR）找到解决方案。为了更好地描述我们的系统，我们为机器人和受害者创建了一个能力/要求列表。对于机器人，我们用二进制向量来表示这些能力，指出每个机器人所具备的能力。同样，我们也为受害者创建了一个二进制向量来表示他们的个人需求。
- 受害者需求和机器人能力分析： 需求分析（算法 2 和算法 1 中的第 4 行）侧重于通过计算确定三组关键信息。这三组信息包括：特定机器人可完全满足受害者要求的信息（L full）、特定机器人可部分满足受害者要求的信息（Lparticial），以及可满足受害者要求的潜在机器人信息（Lpotencial）。如果机器人满足了受害者的所有要求，则受害者 ID 将被包含在 Lfull中。如果机器人只能满足受害者要求的一个子集，则相应的受害者 ID 会被添加到机器人的 Lparticial中。反之，有能力满足受害者要求的机器人会将其 ID 加入该要求的Lpotencial集合中。通过以矩阵形式表示受害者要求q）和机器人能力p），系统执行矩阵运算（算法 2，第 3 行），将结果与包含所有要求的更大向量（S）进行比较。这些二进制向量表示代理拥有每个属性。该算法的输入是包含信息的矩阵 Q = [q0 ⊤, … ,qM-1 ⊤] ⊤ 和 P = [ p0, … , pN-1] ⊤，以矩阵形式呈现以降低时间复杂度。
利用 L potential 中的数据，MissingCap 功能（算法 1，第 5 行）可识别没有合适机器人满足特定要求的情况。随后，它会将相关的受害者 ID 和要求添加到 L unavailable 中，以弥补能力的不足。
- 受害者聚类和将受害者聚类分配给机器人： 为了方便任务分配过程，使用聚类功能，采用 K-means 算法，根据受害者在地图上的位置将其分组。这些簇群的数量与机器人的数量相等（K = N），因此可以高效地为邻近的受害者分配机器人与受害者之间的簇群。 机器人-集群匹配采用线性分配法，我们的分配公式（等式 1）包含两个分配权重：w f rc（表示集群 c 中的机器人 r 完全满足的受害者要求集）和 wrc（表示集群 c 中的机器人 r 满足的受害者总要求），适用于 N 个机器人和 K 个集群。
重要性系数ψ∈[0, 1]平衡了完全满足与部分满足受害者要求之间的关系。ψ越高，机器人在完全满足一个或多个受害者要求的集群中的优先级就越高，而ψ越低，机器人在部分满足更多受害者要求的集群中的优先级就越高。二进制变量 xrc 决定机器人在集群中的分配。等式的第二行确保一个集群最多分配给一个机器人。 一旦机器人加入集群，它们就会移动到集群中心，而集群中心是根据受害者的位置平均值计算出来的。从中心到受害者的曼哈顿距离可指导簇内的优先级排序。 ClstrAsgn 函数（算法 1 第 7 行）计算了这一距离，并将结果存储在 B2 中。
仅仅依靠位置的聚类方法可能是不够的，因为它可能无法考虑环境中的障碍物。例如，位于墙壁两侧的受害者可能会被归入同一聚类，从而导致机器人的行进时间达不到最佳状态。为了解决这个问题，我们设计了一种方法，通过比较从集群中心到每个受害者的曼哈顿距离和空旷环境的曼哈顿距离，来检查每个集群是否存在障碍物。如果空旷环境中的距离大于有障碍物（墙壁）环境中的距离，则表明存在障碍物，受害者将被排除在外，直到下一阶段。
机器人性能和可靠性分析： 机器人在指定群组中的表现涉及与受害者的单独互动，要么成功，要么失败。 可靠性的评估依赖于分析成功（T success rv）和失败（T failure rv）任务的时间分配。计算机器人可靠性时，要尽量减少这两类时间，从而提高整体可靠性。这种优化方法采用线性分配，利用公式 2 管理 N 个机器人和 M 个受害者的忙碌时间。二进制变量 xrv 确保了受害者对机器人的排他性分配。 系数 β∈ [0, 1] 用于平衡时间成本的权衡。使用 PerfAnalysis 函数计算成功和失败时间（算法 1 第 8 行）。随后，VictimAssign（算法 1 第 9 行）利用这些数据将剩余的受害者分配给机器人，并存储为变量 B3。
基于距离的竞价： 我们利用 ReqmentAnalysis 函数中的潜在机器人列表（L potential），将无人值守受害者的要求与最近的机器人进行匹配。距离是通过计算潜在机器人之间的曼哈顿距离来确定的。这种方法采用密封出价方案，机器人在拍卖结束前提交隐藏出价。出价最高者即为获胜者，在此情况下，获胜者就是距离受害者最近的机器人。结果（记为 B4）通过机器人分配函数（算法 1，第 10 行）计算，确保全面满足受害者的要求。此外，我们还会对 L 进行全面验证，以防止重复。具体来说，如果一个机器人能够满足受害者的所有要求，那么就不应该将该受害者分配给其他机器人。
C. 路径规划
算法 1 第 11 行中的路径规划功能使用 A∗ 搜索算法，这是一种广泛使用的路径规划算法，尤其适用于网格环境。A∗ 算法通过考虑已走过的距离和到目标的估计距离（也称为启发式成本），计算出从机器人初始位置到指定受害者地址的最短路径。在我们的系统中，我们使用曼哈顿距离作为启发式成本。A∗ 算法可确保机器人路径的效率，同时还能避开障碍物，确保导航安全。然后，机器人利用计算出的路径导航到指定的受害者处。
四、结果与讨论
本节将介绍我们提出的框架在地图 2 上的实验结果。十名受害者的要求各不相同（表一），他们被分配给四台能力各异的机器人（表二）。分配前，侦察小组采用了蚁群算法进行环境覆盖。所有十名受害者都被成功找到，并收集和记录了相关数据，如 ID、位置和要求，以便分配任务（表 I）。 表 I 中的群组 ID 表示聚类结果（算法 1，第 6 行），而 L potential 表示需求/能力分析输出（算法 1，第 4 行）。其余各栏展示了侦察小组获得的受害者信息。
表 I：受害者的位置、要求和满足要求的潜在机器人，以及每个受害者对应的群组 ID 汇总
该表示法表明，受害者 0 的要求包括能力/要求列表中的第二项和第三项，而机器人 0 和机器人 1 分别是满足这些要求的潜在候选者。此外，受害者 0 位于位置（16，7），属于群组 C0。
表 II：救援机器人的位置和能力。每个机器人可完全或部分满足要求的受害者 ID 列表，以及在任务分配过程的每个阶段分配给每个机器人的受害者 ID 的结果。
表 II 显示了机器人 0 的能力和任务。 受害者 2 和 5 的需求不可用 L unavailable 表示。图 2 用颜色标示了任务分配阶段。机器人 2 在 B2 中缺少集群，但在竞标中获得了任务。最初，机器人 0 被分配给受害者 8，后来根据空间限制进行了调整。除了最近的合格机器人外，B4 中的冗余最小。
我们的 MSMRTA 算法与 Carreno 等人的 MRGA 算法在 2 到 10 个机器人、10 到 100 个受害者和 4 幅地图上进行了对比评估。 MSMRTA 显著缩短了规划时间： 97.70%、97.00%、96.93% 和 97.34%。规划时间随着机器人和受害者的增加而增加：92.26%、31.80%、80.85% 和 39.89%。图 3 描述了这些结果，凸显了 MSMRTA 在提高搜救效率方面的潜力。
图3 左边是提出的算法(MSM RTA)平均规划的时间，右边是基线算法(MRGA)上。
五、结论与未来工作
本文介绍了一种集侦察、多阶段多机器人任务分配和路径规划于一体的新型搜救框架。该框架在侦查过程中充分利用了机器人的能力和受害者的要求，并根据这些数据和机器人过去的表现优化了任务分配。 值得注意的是，它还能让不同的机器人执行多项任务，以满足所有要求。通过模拟验证了该框架的有效性，结果表明计划时间平均缩短了 97%，整体性能也得到了提升。未来的工作包括完善聚类技术、分析环境地图、探索影响因素，以及通过不同机器人队的实际实验来验证该算法。
本文原文来自CSDN