多约束下动态实时多无人机协同任务规划方法

《Drones》：Dynamic Real-Time Multi-UAV Cooperative Mission Planning Method Under Multiple Constraints Chenglou Liu, Yufeng Lu, Fangfang Xie, Tingwei Ji and Yao Zheng

　　

随着无人机（UAV）的普及，其相关的任务规划问题也日益增多。经典规划方法面临着任务分配与路径规划解耦、实时性和可扩展性差以及适应性有限这三大难题。针对这些挑战，本文提出了一种基于无人机状态的多无人机实时协同任务规划方法。首先，采用的杜宾斯（Dubins）路径准确表征了任务之间的距离，并在无需平滑处理的情况下满足了曲率约束，从而实现了任务分配与路径规划的耦合求解。随后，应用了一系列加速技术以保证方法的实时性能，包括通过任务聚类来减少决策空间、采用低迭代次数的分配策略以及高效的距离成本计算方法。为了增强鲁棒性和适应性，该方法妥善处理了新任务的实时分配以及因可用无人机减少而导致的任务重新分配。最后，仿真结果表明，与基准方法相比，所提方法仅增加了9.57%的路径长度，同时实现了规划速度提升4至5个数量级，单次任务规划时间约为0.0003秒。此外，该方法能够轻松扩展至大规模场景（在1000架无人机和25000个任务的情况下，规划时间为0.0029秒）。

研究背景

如今，无人机（Unmanned Aerial Vehicles, UAVs）已广泛应用于军事和民用领域，其中固定翼无人机因其续航时间长、载荷能力大等优势备受学者关注。然而，单架固定翼无人机已无法有效适应日益复杂的任务环境，无人机集群成为极具前景的解决方案。多无人机协同任务规划是成功实现多无人机协作的前提，包含协同任务分配和多无人机协调路径规划两个组成部分。尽管已有广泛研究，但该领域仍面临挑战：现有方法通常将任务分配与路径规划解耦，导致航向角和运动约束无法在早期整合，降低了求解效率和质量；多数研究侧重于静态环境下的任务预规划，缺乏基于无人机当前位置和姿态的即时规划能力；随着任务复杂度和数量的增加，大规模无人机集群需要更高效的实时规划；此外，针对新任务、无人机失效及多重突发事件的综合应对策略尚不完善，限制了无人机的适应性和鲁棒性。

关键技术方法

为解决上述问题，研究人员开展了基于无人机状态的实时协同任务规划研究。核心技术方法包括：采用杜宾斯（Dubins）路径距离作为决策成本，将任务分配与路径规划耦合；利用K-means算法进行任务聚类预处理以减少决策空间；应用贪婪算法等低复杂度分配策略；引入基于解析几何的高效CS型和CSC型Dubins路径生成方法；设计分布式决策框架，根据无人机的空闲（idle）、途中（in-transit）、忙碌（busy）和失效（disabled）四种状态进行状态机管理；建立考虑异构任务和航向角约束的整数规划模型；制定新任务插入和失效无人机任务重新分配的应急机制。

研究结果

1. 引言

明确了多无人机协同任务规划的重要性，指出当前主流方法在解耦、实时性及适应性方面的不足。提出了基于无人机状态的实时规划框架，将无人机状态划分为空闲、途中和忙碌，并考虑了失效这一特殊状态。核心贡献在于实现了任务分配与路径规划的耦合、通过加速技术保证实时性，以及增强了应对突发事件的适应能力。

2. 相关工作

综述了多无人机协同任务规划的常用数学模型（如多旅行商问题MTSP、车辆路径问题VRP等）和求解算法（确定性算法如匈牙利算法，启发式算法如模拟退火、遗传算法等）。指出现有研究多将任务分配与路径规划解耦，且多集中于静态环境下的预分配，难以满足动态环境和大规模场景下的实时响应需求。

3. 预备知识与问题建模

将固定翼无人机建模为平面非完整车辆，假设其在不同高度飞行以避免碰撞，并以恒定速度飞行。定义了无人机属性（位置、航向角、状态）和任务属性（位置、状态、类型）。将任务分为点目标、线目标、圆目标和区域目标四类，并详细推导了Dubins路径距离成本的计算方法，包括CSC型和简化的CS型路径构造几何直觉。建立了基于MTSP的整数线性规划模型，目标函数为最小化各无人机移动的总路径长度，并列出了一系列约束条件（如访问一次、MTZ消圈约束、航向角约束、曲率约束等）。

4. 基于无人机状态的实时协同任务规划

详细阐述了算法的七个步骤：初始化、任务聚类、任务完成与无人机状态评估、空闲状态决策、途中状态决策、忙碌状态决策和无人机返航。分析了算法的时间复杂度，指出任务聚类将复杂度由O(N^2)降低，总复杂度为O(N·K + N^2/K)。仿真结果显示，与基准方法相比，所提方法在路径长度仅增加9.57%的情况下，单次规划时间达到约0.0003秒，且在1000架无人机和25000个任务的大规模场景下仅需0.0029秒。

5. 紧急情况

探讨了三种紧急场景的应对策略：新任务出现时，根据其位置与初始聚类中心的距离将其分配给最近的无人机集群；无人机失效时，释放其未完成任务并按就近原则重新分配给可用无人机；当新任务与无人机失效同时发生时，通过调整新任务聚类处理流程来适应可用无人机数量的变化。

6. 仿真结果与讨论

通过对比实验验证了方法的有效性。在空间维度，基于Dubins距离的成本计算影响了任务分配方案，且带有聚类的PRBDDG方法能实现接近最优解的差异化任务分配。在时间维度，PRBDDG展现了显著的实时优势。可扩展性实验证明了其在大规模场景下的快速规划能力。紧急场景实验验证了其在动态环境下的鲁棒性和适应性。

讨论与结论

论文发表于《Drones》。研究结论表明，该动态实时多无人机协同任务规划方法具有四个显著特点：起飞前无预定义任务序列和路径的实时规划、基于邻近准则的任务聚类预处理、采用Dubins路径距离成本以及替代性的低复杂度任务分配策略。这些技术特征使得算法能够在异构任务、非完整运动学约束、时间限制和紧急情况等多种约束下，实现任务分配与路径规划的实时耦合求解，并使总距离尽可能缩短。实验证实，不同距离成本会导致不同的分配方案；所提方法能获得次优解并实现近优解机制；具备高度可扩展性；且在紧急场景下表现出优异的鲁棒性和适应性。未来工作将致力于解决同高度无人机的避障与防撞问题，考虑无人机有效载荷、航程和速度差异，以及引入强化学习等智能规划方法。