← 返回论文列表

最优UGV-UAV协作最短路径划分与巡检
Optimal UGV-UAV Cooperative Partitioning and Inspection of Shortest Paths

作者: Ninh Nguyen, Srinivas Akella
arXiv: 2604.25284v1
分类: cs.RO
📝 论文摘要
我们研究了在存在未知道路阻塞的环境中，由无人机（UAV）辅助的地面无人车（UGV）的协作最短路径规划问题。这些阻塞只有在机器人到达受损点时才会被发现。该问题推广了经典加拿大旅行者问题（CTP），CTP假设仅有一辆地面车辆，且当到达某个顶点时才会揭示所有相邻边的通行状态。我们首先分析了起点和终点由k条不相交路径连接的情况，并证明单辆UGV的最坏情况竞争比ρ为2k-1。在无人机辅助下，且假设无人机初始通行和空驶成本可忽略时，该比率改进为ρ=2v_G/(v_A+v_G)k-1，其中v_G和v_A分别表示UGV和无人机速度。针对一般图以及不可忽略的无人机初始通行和空驶成本，我们提出了一种最优路径划分策略，将路径前缀检查分配给UGV，后缀检查分配给无人机，并证明了该无人机检查策略在一般图上的最优性。我们采用全球50个人口最多城市的道路网络进行实验，设置随机阻塞，结果表明所提方法可将UGV行驶时间减少高达30%。

📊 核心分析

🎯 研究动机
- 解决**无人地面车辆(UGV) ** 在未知道路阻塞环境中的协作最短路径规划问题，阻塞只有到达受损点才能发现 - 推广了经典的** 加拿大旅行者问题(Canadian Traveller Problem, CTP)** ，原问题假设单地面车辆且到达顶点时获知所有关联边的可通行状态 - 现有方法缺乏对无人机(UAV)辅助下路径分割与检查的优化分析，尤其是一般图和非忽略的UAV初始通行与空驶成本
🔧 核心方法
- 提出**最优路径分区策略(optimal path partitioning strategy)** ，将路径前缀检查分配给UGV，后缀检查分配给UAV - 理论分析：在k条不相交路径情况下，单UGV最坏竞争比ρ=2k-1；引入UAV辅助且假设忽略UAV初始通行与空驶成本时，ρ=2(v_G/(v_A+v_G))k-1，其中v_G和v_A分别为UGV和UAV速度 - 针对一般图和非忽略成本，证明了UAV检查策略的最优性 - 在世界50个最人口稠密城市的道路网络上进行实验，随机化阻塞，验证方法有效性
💡 核心创新
- **首次将CTP推广到UGV-UAV协作场景** ，考虑更现实的阻塞发现机制（仅到达受损点） - ** 理论层面**：给出了k条不相交路径下含UAV辅助的竞争比上界，并证明了一般图上UAV检查策略的最优性 - ** 实践创新**：提出路径前缀/后缀分区分配策略，优化UAV的侦查与空驶成本，实现高达30%的UGV旅行时间减少 - 区别于仅关注单车辆或完全信息假设的现有工作，该方法在部分可观察环境下实现有效协同
🏆 总体贡献
- 为**UGV-UAV协同路径规划** 领域提供了理论竞争比分析与最优检查策略 - 提出了一种通用且可证明最优的路径分区框架，适用于一般图结构及非忽略UAV成本 - 大规模实验验证（覆盖全球50大城市路网）表明方法能显著降低UGV行驶时间（最高30%），具有实际应用价值 - 扩展了**加拿大旅行者问题** 的理论边界，为未来多机器人部分可观测路径规划研究奠定基础