C²-Explorer: Contiguity-Driven Task Allocation with Connectivity-Aware Task Representation for Decentralized Multi-UAV Exploration¶

日期: 2026-03-08
arXiv: 2603.07699
代码: GitHub
领域: 机器人
关键词: multi-UAV, decentralized exploration, task allocation, CVRP, connectivity-aware

一句话总结¶

提出 C²-Explorer，去中心化多无人机探索框架——用连通性图（CCL 分割空间为独立任务单元）替代拓扑无关的均匀网格分解，并将任务分配建模为带图邻接连续性惩罚的 CVRP 问题，在 3 个场景中平均探索时间降低 43.1%、路径长度降低 33.3%（vs RACER/FAME），并在真实无人机上验证可行性。

研究背景与动机¶

领域现状: 多无人机协同探索是快速 3D 重建、搜救、结构检测等应用的基础。近年从两个方向推进：(a) 任务表示——frontier/viewpoint 类方法（RACER、FAME）需要实时全局一致的地图共享；区域类方法（Zhou et al.）用均匀网格分解避免全局共享依赖；(b) 任务分配——贪心方法逐步选最优目标、VRP 类方法求解全局路线。
现有痛点: (a) 任务表示缺乏拓扑感知——均匀网格分解会把空间上不连通的未知区域合并为一个任务（如被障碍物分隔的两块区域），导致不必要的跨区域绕行；同时保留不可达的封闭区域（被障碍物包围的未知区域仍被视为有效任务），造成无效分配。(b) 任务分配缺乏时空连续性——贪心方法忽略时间一致性导致频繁目标切换；VRP 方法虽考虑穿越成本但缺少显式的连续性正则化，仍可能将拓扑不相邻的任务分给同一架无人机，产生交错轨迹。
核心矛盾: 高效多机探索需要"连续性"——每架无人机的分配任务应在空间上连续、时间上一致，避免跨区域绕行和冗余覆盖，但现有方法在任务表示和分配两个层面都没有系统地保证这一点。
切入角度: 构建连通性图显式编码空间拓扑，将不连通区域分割为独立任务单元；在 CVRP 代价矩阵中引入图邻接惩罚核，惩罚非连续分配。

方法详解¶

整体框架¶

C²-Explorer 是去中心化框架，包含三个组件：(1) 连通性感知任务表示——每架无人机增量建图+维护拓扑连通性图，将未知空间分解为灵活的任务单元；(2) 连续性驱动任务分配——通信范围内的无人机由最低 ID 的临时主机求解带邻接惩罚的 CVRP，分派任务序列；(3) CP 引导的单机规划——每架无人机基于全局覆盖路径（CP）用 ATSP+局部 TSP+B-spline 轨迹生成做分层规划。

关键设计¶

连通性感知任务表示（Connectivity-Aware Task Representation）:
- 做什么：将未知空间分解为拓扑上独立的任务单元，消除传统均匀网格的拓扑歧义
- 核心思路：先粗粒度均匀划分网格 → 在每个网格内用 Connected Component Labeling (CCL) 分割不连通的自由/未知区域 → 构建增量连通性图 \(\mathcal{G} = (\mathcal{V}_f \cup \mathcal{V}_u, \mathcal{E}_f \cup \mathcal{E}_u \cup \mathcal{E}_p)\)，每个空间独立的未知区域作为一个任务单元。任务单元维护轻量信息结构：位置 \(\mathbf{p}_{u,i}\)、凸包 \(\mathcal{H}_i\)（或父网格 ID）、未知体素计数 \(\text{NUM}_i\)、归属无人机 ID。状态为 pending/completed/invalid（不可达区域标为 invalid 并排除）
- 设计动机：传统方法把同一网格内被障碍物分隔的两块未知区域当作一个任务，无人机需跨越障碍物往返；同时不可达的封闭区域浪费了分配资源。连通性图在这两个层面同时解决问题
连续性驱动 CVRP（Contiguity-Driven CVRP）:
- 做什么：在任务分配优化中显式惩罚非连续分配，鼓励每架无人机的任务序列在空间上连续
- 核心思路：构建 CVRP 代价矩阵 \(\mathbf{C}_{cvrp}\)，核心是任务间代价 \(\mathbf{C}_\mathcal{T}(i,j) = \psi(\rho_{ij}) \cdot l_{i,j}\)。其中 \(l_{i,j}\) 是混合 A* 求解的穿越距离，\(\rho_{ij} = l_{i,j}/({\lambda_c \cdot L_g})\) 是归一化邻接比，惩罚核 \(\psi(\rho) = 1\) 若 \(\rho \leq 1\)，\(\psi(\rho) = 1 + (\rho-1)^2\) 若 \(\rho > 1\)。工作负载平衡通过容量约束 \(\sum_i D_i x_{k,i} \leq \sigma_Q W / N_c\) 实现
- 设计动机：仅优化穿越代价无法保证空间连续性——CVRP 求解器可能把距离相近但拓扑不相邻的任务分给同一架无人机。平方增长的惩罚核对拓扑相邻的任务对不加额外代价，对距离超过连通半径 \(R_c\) 的任务对加速增长惩罚，自然促进连续分组
Commit-Style 任务分派协议:
- 做什么：在有损/乱序通信下保持任务状态一致性
- 核心思路：三阶段握手 Proposal→Commit→Finalize + Cancel 回滚。带版本号和时间戳，支持幂等处理重复/迟到消息，有界重试+退避防止频繁重分配的震荡
- 设计动机：去中心化系统中通信丢包和乱序是常态，简单的广播+应用模式会导致不同无人机的任务状态不一致
CP 引导的分层规划:
- 做什么：每架无人机基于分配的任务序列做全局-局部分层规划
- 核心思路：全局层——将任务单元间的遍历建模为 ATSP，用速度一致性惩罚替代纯路径长度作为边代价 \(T_{ij} = l_{ij}/v_m + \sum_k (\text{加减速代价} + \text{反向惩罚})\)；局部层——在当前任务单元内聚类 frontier → 采样 viewpoint → 用固定起终点的 TSP 求解局部巡回 → B-spline 生成平滑轨迹（含无人机间避碰约束）

损失函数 / 训练策略¶

本文不涉及学习，核心是组合优化。CVRP 和 TSP 用 Lin-Kernighan-Helsgaun (LKH) 求解器求解。

实验关键数据¶

主实验¶

场景	无人机数	C²-Explorer 时间(s)	RACER 时间(s)	FAME 时间(s)	时间提升	路径提升
Cubicle Office	2	73.1±4.9	128.1±24.1	142.6±11.0	-42.9%	-32.1%
Cubicle Office	4	50.9±4.2	90.7±11.1	100.8±20.0	-43.9%	-32.3%
Open-plan Office	2	67.3±6.7	125.7±28.9	169.9±19.1	-46.5%	-32.8%
Open-plan Office	4	43.0±2.0	89.3±27.5	102.1±13.3	-51.8%	-34.5%
Octa Maze	2	89.5±2.7	140.7±20.3	163.7±15.8	-36.4%	-32.7%
Octa Maze	4	52.8±7.1	83.7±14.3	96.3±13.3	-36.9%	-34.5%

三个场景平均：探索时间降低 43.1%，路径长度降低 33.3%。C²-Explorer 标准差也最低，稳定性最好。

消融实验¶

配置	探索时间(s)	路径长度(m)	说明
C²-Explorer（完整）	43.0	243.9	完整模型
No-Con（去掉连续性惩罚）	51.7	329.6	时间+20.2%，路径+35.1%
No-Graph（去掉整个连通性图）	90.1	391.4	退化为均匀网格，性能最差

关键发现¶

连通性图贡献最大：去掉后探索时间翻倍（43.0→90.1），因为回到了拓扑无关的均匀网格分解
连续性惩罚锦上添花：在连通性图基础上进一步降低 20% 时间和 35% 路径，证明显式惩罚非连续分配的必要性
可扩展性好：2→4 架无人机时 C²-Explorer 路径长度仅增长 15.9%（RACER 18.0%，FAME 22.6%），说明冗余穿越被有效抑制
通信范围影响：\(r_{comm}\) 从 5m 扩大到 ∞ 探索时间进一步降低 30.2%，说明通信改善能带来额外收益
真实飞行验证：3 架四旋翼在室外树林（69s）和教学楼（52s）完成探索，证明系统可行性

亮点与洞察¶

连通性图 + CVRP 的组合很自然：用拓扑图编码空间连通性，再用图邻接信息作为 CVRP 代价矩阵的正则化，两者在数据结构层面天然兼容，不像 frontier 方法需要额外的全局地图共享
惩罚核设计简洁有效：\(\psi(\rho)\) 在邻域内不加惩罚、邻域外平方增长，只需一个参数 \(\lambda_c\)，避免了复杂的约束设定
速度一致性边代价：ATSP 中不仅考虑路径长度还加入加减速和反向惩罚，使全局规划更贴近实际飞行时间

局限性 / 可改进方向¶

被动通信：无人机不主动维护通信连通性，只在碰巧进入通信范围时协调。未来可引入主动连通性维护，权衡探索进度和协调质量
定位和地图漂移：假设完美定位（基于 FAST-LIO2），长时间飞行的定位漂移可能导致地图不一致和任务分配错误
任务类型单一：只考虑覆盖式探索，未涉及目标搜索、结构检测等更复杂的任务目标
CVRP 求解时间：随任务单元数增长，LKH 求解时间可能成为瓶颈（尽管论文中规模较小未成问题）

评分¶

新颖性: ⭐⭐⭐⭐ 连通性图驱动的任务表示+邻接惩罚 CVRP 是有意义的组合创新，但各组件（CCL、CVRP、A*）都是成熟技术
实验充分度: ⭐⭐⭐⭐⭐ 3个场景×3种无人机数量+完整消融+通信范围消融+真实飞行，实验设计全面
写作质量: ⭐⭐⭐⭐ 公式严谨，图示清晰（Fig.2 的对比图直观展示了连通性感知 vs 传统方法的差异）
价值: ⭐⭐⭐⭐ 为有限通信下的多无人机协作探索提供了实用框架，代码开源