Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

技术摘要：无人机动态去中心化 3D 城市覆盖与巡逻

问题定义
本文解决了协调无人机（UAV）集群在自然或人为灾害（如火灾、洪水、地震）发生后的 3D 城市环境中进行协作式、周期性覆盖与巡逻的挑战。环境被建模为由直棱柱表示的建筑物集合，目标是覆盖所有垂直立面和屋顶表面，并满足特定目标检测的图像质量约束。

关键约束与假设包括：

• 资源有限： 智能体数量不足以提供持续覆盖；因此，系统必须提供“周期性”覆盖。
• 3D 复杂性： 智能体必须绕过障碍物（建筑物本身）进行导航，并管理相机俯仰角（pitch）以观测立面和屋顶。
• 系统要求： 解决方案必须是去中心化的（无中央控制器）、可扩展的、对智能体失效具有鲁棒性、能够适应动态变化，并能够在通信带宽和范围有限（周期性连接）的情况下运行。
• 目标： 最小化最大“空闲时间”（$i_v$），即任何特定建筑表面视点之间连续访问的时间间隔。

方法论
作者提出了一个模块化的去中心化框架，将问题分解为四个不同阶段：视点生成、任务生成、任务分配和巡逻策略。

1. 视点生成：
   建筑物的 3D 表面（立面和屋顶）被离散化为一组视点（$V$）。每个视点代表一个特定的 3D 位置和朝向，无人机可以在该处捕捉一个矩形区域，其大小匹配摄像头的视场角（FOV）以及特定的距离（$c_d$），以确保满足目标检测的最佳分辨率。

2. 任务生成：
   与单个建筑物相关的视点被连接成一条闭合路径（$H_j$）。路径生成被建模为 3D 旅行商问题（TSP）。为了避免 NP-hard 的复杂度，作者采用了 Christofides 算法，这是一种保证路径长度在最优解 1.5 倍以内的启发式算法。该路径利用 3D 可视性图（visibility graphs）考虑了避障（例如不穿过建筑物本身）。每栋建筑物构成一个“任务”，并具有定义的容量（$c_j$），即支持的智能体数量。

3. 任务分配：
   智能体使用基于共识的束集法（CBBA）及其扩展——基于共识的分组算法（CBGA）被分配到任务（建筑物）。这种基于拍卖的去中心化方法允许智能体根据评分函数对任务进行竞标。评分综合考虑了到建筑物的平方距离和优先级因子（$p_j$），从而实现异构任务处理（例如，优先处理高重要性建筑或为动态跟踪任务重新分配智能体）。这确保了在不需要全连接通信图的情况下实现可扩展性和容错性。

4. 巡逻策略：
   一旦被分配到闭合路径，智能体便执行一种极简的去中心化巡逻策略。

• 移动： 智能体从距离其最近的视点进入路径，并沿随机方向（顺时针或逆时针）移动。
• 交互： 智能体仅在通信范围内交换局部状态信息（位置、当前视点索引、最后服务的视点及方向）。
• “反弹”机制： 当智能体相遇（无论是在同一个视点还是彼此经过）时，它们应用特定规则反转方向（“反弹”）。
  • 如果两个智能体正朝着同一个视点反向移动，较近的智能体服务该视点并反转，而较远的智能体立即反转。
  • 如果朝同一方向移动，较远的智能体反转以防止超越。
  • 如果智能体经过了彼此最后服务的视点，则两者均反转。
• 涌现行为： 这种局部交互导致了一种涌现的振荡，使智能体动态地划分路径。系统并不旨在实现路径的等分，而是确保所有视点都能被定期访问。

核心贡献

• 模块化框架： 论文引入了一个结构化的方法，将覆盖路径规划与巡逻策略分离，允许独立优化或修改各个组件。
• 极简巡逻策略： 不同于以往依赖全局共识或复杂协调来划分连续周界的工作，该方法利用简单的局部规则（“反弹”）在离散的 3D 闭合路径上实现周期性覆盖。
• 3D 离散化： 该方法通过生成涵盖立面和屋顶的视点，显式处理了城市环境的 3D 特性，并考虑了相机俯仰角和避障。
• 资源效率： 该策略最小化了计算和通信开销，使其适用于在通信受限环境下运行的资源受限平台。

仿真结果
作者使用包含 7 栋建筑和 401 个视点的场景，通过 Swarm 研究模拟器验证了该框架。

• 设置： 100 架无人机被分配到 7 栋建筑中。智能体以 2 m/s 的速度移动，并在每个视点停留 3 秒。
• 性能： 系统实现了实时运行（分配/巡逻逻辑为 1 Hz，无人机动力学为 10 Hz）。Christofides 算法平均每栋建筑耗时 3 ms，巡逻算法每名智能体耗时不到 2 ms。
• 覆盖率： 在 10 次实验运行（每次 1800 秒）中，集群成功实现了所有视点的完整覆盖。
• 空闲时间： 视点的最大空闲时间是有界的且随时间收敛。结果表明，极简策略有效地约束了空闲时间的上界，并在无需全局协调的情况下确保了周期性覆盖。

意义与主张
论文声称，所提出的方法通过利用源自简单局部规则的涌现行为，成功解决了多智能体 3D 城市覆盖问题。其意义在于权衡：系统牺牲了等分路径的最优性（这需要全局共识），以换取在高扩展性、鲁棒性和适应动态通信受限环境方面的优势。作者断言，这种极简策略特别适用于通信信号可能受限或零星存在的灾害响应场景，且即使单个智能体失效或丢失，系统仍能保持功能。未来的工作确定为改进视点生成以处理异构相机和复杂的遮挡问题，但目前的贡献侧重于在结构化 3D 城市环境下实现去中心化巡逻机制的可行性。