💻 computer science

Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration

本文提出了一种基于边界连通性的去中心化探索图扩展策略，旨在增强在间歇性通信条件下运行的多无人机系统的探索效率并保持鲁棒的区域划分。

原作者： Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard, David Filliat

发布于 2026-09-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard, David Filliat

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一支无人机小队被派往一个广阔且未知的洞穴系统进行测绘。他们的任务是尽可能快地覆盖整个空间，同时避免彼此碰撞或在重复路径上浪费时间。在现实世界中，这些机器无法依赖持续且完美的网络连接。厚重的岩壁、干扰以及距离都会切断它们之间的联系，使得每架无人机只能根据它所能看到的内容以及从经过的邻近无人机那里抓取到的微量信息来做出决策。机器人领域的挑战在于，如何设计一种系统，让这些处于孤立状态的机器即使在暂时失去联系时，仍能作为一个协调的团队行动，公平且高效地分配工作。

这是研究人员 Beatrice Garcia Cegarra、Elena Vanneaux、Quentin Picard 和 David Filliat 所解决的核心问题。他们解决了当通信不可靠时，一组自主无人机如何探索未知环境的问题。在他们的研究中，他们专注于一种特定的策略：将地图划分为不同的区域，以便每架无人机都知道自己应该探索哪个区域。难点在于地图是不完整的，且无人机无法通过相互通信来更新各自的计划。如果一架无人机失去了联系，它可能会误入已经分配给另一架无人机的区域，或者因为它不知道视野之外的布局而陷入死胡同。研究人员希望找到一种方法，即使在无人机断开连接且地图不断变化的情况下，也能保持团队计划的稳定性和有效性。

为了解决这个问题，该团队开发了一种让无人机利用环境“心理地图”来进行“预判”的新方法。无人机不再仅仅观察眼前的空旷空间，而是构建一个代表已探索区域边缘的点网络。然后，它们利用这个网络来预测下一个未探索区域可能出现的位置。研究人员引入了一种扩展这种心理地图的方法，即根据空间的结构化方式，添加与现有点逻辑相关的点。可以把这想象成一名徒步旅行者，当面对分叉路口时，他不仅仅是随机选择一个方向，而是会考虑路径的整体形状，以确保自己是朝着森林中新的、未曾造访的区域移动，而不是在原地打转。通过以尊重障碍物物理布局的方式将这些新点连接到现有地图中，即使在没有持续通信的情况下，无人机也能维持一个一致的行动计划。

研究人员在两种不同类型的环境中通过计算机模拟测试了这一想法：一个是复杂的迷宫，另一个是拥有蜿蜒通道和死胡同的地下洞穴系统。他们将这种新方法与现有的策略进行了对比，这些现有策略要么依赖完美的通信，要么使用更简单的猜测下一步去向的方法。在模拟中，他们使用了一支由三架无人机组成的队伍，飞行平均速度为每秒 1.1 米。无人机只有在距离 6 米以内时才能相互通信，这是一个非常短的范围，迫使它们在大多数时间内独立运行。目标是观察团队完成 95% 地图探索所需的时间以及每架无人机需要行驶的总距离。

结果显示，这种利用地图结构来扩展规划图的方法显著提升了性能，尤其是在更为复杂的洞穴环境中。当无人机具备这种拓扑感知能力时，它们探索洞穴的速度更快，且行驶的总距离更短。在洞穴模拟中，与不使用这种扩展功能的标准方法相比，新方法将完成任务所需的总时间减少了约 20 秒，并将每架无人机的平均行驶距离缩减了约 18 米。这种改进即便在无人机彼此接触非常有限的情况下依然有效。事实证明，该方法在保持团队任务分配的稳定性方面表现出色；即使在失去联系时，无人机也很少会突然变换目标或对该负责的区域产生困惑。

一个关键发现是，无人机划分工作的方式很大程度上取决于环境。在迷宫中，不同方法的表现相似，这表明简单的策略在开阔、较少杂物的空间中效果良好。然而，在拥有狭窄通道和死胡同的洞穴中，这种新的图扩展方法展现出了明显的优势。它帮助无人机避免了低效的回溯，并确保它们向着未知深处推进，而不是陷入循环。研究人员还发现，该方法有助于无人机达成更一致的计划。即使在断开连接时，它们的内部任务地图仍能保持一致，从而防止了因孤立个体做出冲突决策而导致的混乱。

这项研究并未声称已经解决了所有机器人探索的问题。模拟表明，虽然新方法具有鲁棒性，但它仍然依赖于无人机拥有准确的局部地图以及探测障碍物的能力。研究人员指出，在数据非常稀疏的环境中（例如路径较少的区域），这种方法的益处并不那么显著。他们还观察到，虽然该方法提高了效率，但并未完全消除对通信的需求；当无人机偶然相遇时，它们仍然能从信息更新中获益。这项工作表明，通过赋予机器人理解空间的“形状”而非仅仅是点与点之间距离的能力，团队可以在现实世界中常见的断续、不可预测的条件下更有效地运作。

最终，这项研究为必须在野外工作的自主系统提供了一个务实的进步。通过教导无人机去关注已知与未知之间的“连接性”，而非仅仅关注眼前的环境，该团队创建了一个对现实世界的干扰更具韧性的系统。研究结果表明，对于在困难且面临通信挑战的环境中运行的多机器人团队而言，一种尊重地图拓扑结构的策略是维持秩序和效率的强大工具。随着这些技术从模拟走向现实，此类方法可以让无人机群在探索灾区、深邃洞穴或其他危险区域时，展现出一种以往在没有中央指令持续链接的情况下无法实现的协调水平。

技术摘要：面向去中心化多机器人探索的连通性感知图扩展

问题陈述

在未知环境中利用多架无人飞行器（UAV）进行探索面临着一个根本性的挑战：如何在快速、协同的行为与间歇性且有限的通信现实之间取得平衡。在许多场景中，无人机的通信受限于通信范围、障碍物和干扰，使得持续连通成为一种例外而非常态。

目前的多机器人探索（MRE）系统通常依赖于集中式决策或假设通信可靠，这在去中心化设置中会失效。当通信丢失时，智能体可能会在任务分配上产生分歧，导致效率低下的重复访问、工作量不平衡或探索碎片化。本文解决的核心问题是：如何在通信不可靠（即无法实现连续、可靠通信）的无人机集群中，通过利用结构化的部分信息来对齐决策，从而维持一致的任务分配和高效的探索策略。

方法论

作者提出了一种去中心化框架，每个无人机都维护一个关于环境的共享、部分观测的拓扑图。该系统运行在一个涉及图维护、扩展、划分和局部规划的分层规划流水线之上。

1. 图表示与维护

环境被离散化为网格探索子区域（GES）。每个无人机维护一个包含三种节点类型的图 $G_m = (V_m, E_m)$ ：

边界节点 ( $v_F$ )： 已发现但尚未探索的 GES。
历史节点 ( $v_H$ )： 此前访问过的稀疏路标点。
无人机节点 ( $v_M$ )： 智能体的当前位置（被视为移动的 $v_H$ ）。

边基于考虑障碍物的连通性通过 Dijkstra 算法建立。无人机在通信半径 $r_c$ 内进行机会性数据交换，共享位置、目标和 GES 状态，但边权重是在本地计算的。

2. 核心贡献：连通性感知图扩展

主要贡献是一种新型的图扩展方法，旨在预判探索需求并稳定任务分配。与在无人机局部窗口内添加节点的采样法不同，该方法基于拓扑父集连通性在全球范围内扩展图。

机制： 对于每个边界节点 $v_F$ ，算法识别地理相邻的未探索 GES 候选对象 ( $v_{adj}^N$ )。
连通性准则： 算法检查这些候选对象的“祖先”关系。它收集 $v_F$ 的父节点集合 ( $P_F$ ) 及其对应的 $v_H$ 祖先集合 ( $P_H$ )。
决策规则： 仅当一个相邻候选对象的所有父集合都属于同一个最大连通分量（LCC）时，该候选对象才会被添加到扩展图 ( $G_m^{ext}$ ) 中，并与其父节点连接。
原理： 这防止了在由障碍物分隔的拓扑距离较远的区域之间创建“伪捷径”（这会扭曲划分结果），同时强化了那些共享共同结构路径的区域之间的连接。

3. 任务分配与规划

扩展后的图 $G_m^{ext}$ 通过两种最先进的方法进行划分，以向智能体分配区域：

广义沃罗诺伊图 (GVD)： 基于测地距离进行空间划分，使用无人机位置作为中值点。
K-中心点聚类 (K-medoids Clustering)： 基于图拓扑（使用紧密中心度）而非欧几里得距离进行划分。中值点使用 K-means++ 策略进行初始化，以选择距离较远的节点，从而降低方差。

一旦完成划分，每架无人机都会规划一条轨迹，前往其分配簇内最近的 GES 进行探索。如果某个划分被耗尽，无人机会重新规划路径，前往其他划分中的最近 GES。

关键贡献

新型扩展策略： 一种确定性的图扩展方法，通过基于拓扑父集交集的节点添加方式，确保扩展图与环境的障碍物结构保持一致。
对断连的鲁棒性： 该方法旨在即使在通信间歇的情况下，也能维持稳定的区域划分和一致的任务分配，避免划分形状发生剧烈变化。
与划分算法的集成： 该方法通过结合 Voronoi 和 K-medoids 两种划分策略进行了评估，展示了在不同分配算法下的适应性。
去中心化框架： 系统无需中央协调器即可运行，依赖于机会性数据交换和局部图维护。

实验结果

作者在 ROS 和 Gazebo 环境下，在“迷宫”（办公类）和“地下”（SubT，具有复杂走廊和死胡同）两种环境下进行了仿真评估。对比对象包括标准图方法和一种基于采样的扩展方法 [3]，分别在全局（全范围）和局部（有限范围）通信条件下进行测试。

在 SubT 环境中的表现： 在复杂的 SubT 环境中，所提出的拓扑扩展在有限通信条件下显著提升了性能。
- 对于 Voronoi，在局部设置下，该扩展相比标准基准方法减少了约 20 秒的总探索时间 ( $T_{tot}$ ) 和每架无人机约 20 米的平均行驶距离 ( $D_{avg}$ )。
- 对于 K-medoids，基于采样的扩展在全局通信设置下提高了稳定性，并减少了 $T_{tot}$ 和 $D_{avg}$ 约 15%。在局部设置下，拓扑扩展维持了 K-medoids 的性能，而基于采样的扩展对 K-medoids 几乎没有收益，尽管两种扩展都提升了 Voronoi 的表现。
效率： 拓扑扩展在 Voronoi 方面比基于采样的扩展具有更高的探索效率，特别是在减少不必要的行驶和保持一致的簇分配方面。
通信韧性： 虽然全局通信通常能带来最好的结果，但所提出的方法允许集群即使在通信受限的情况下也能收敛到相似的策略，表明在特定拓扑结构下，划分过程对通信半径约束具有鲁棒性。
指标改进： 该方法降低了行驶距离的标准差 ( $D_{std}$ )，表明智能体之间的负载更加均衡。同时，它在保持性能的同时减少了总数据交换量 ( $B_{tot}$ )，表明信息使用更加高效。

意义与主张

本文声称，所提出的连通性感知图扩展提供了一种鲁棒的机制，用于去中心化多机器人探索，特别解决了由间歇性通信引起的稳定性问题。

稳定性： 该方法确保了任务分配随时间及跨智能体的一致性，即使在它们失去联系时也是如此。它防止了当智能体仅依赖局部、过时信息时经常出现的探索计划“碎片化”问题。
拓扑感知： 通过考虑图的结构连通性（祖先关系）而非仅仅是几何邻近性，该方法避免了创建误导性的捷径，从而防止智能体进入低效的探索路径或孤立区域。
适用性： 该方法特别适用于受限环境（如地下环境），在这些环境中，欧几里得距离无法很好地代表可通行性。它使集群能够维持“更深层”的探索策略，并减少智能体推断区域之间的重叠。

作者总结道，虽然基于欧几里得距离的划分（Voronoi）在某些情况下可能优于拓扑度量，但在低通信速率下，利用拓扑连通性来丰富探索图对于维持性能至关重要。该研究工作建议，未来的改进可以侧重于精炼深度探索与横向区域完成之间的权衡决策准则，以及开发恢复策略（例如定期会合）以进一步增强共享知识。