多无人机任务分配/航迹规划的一体化求解方法

Integrated Solution Method for Multi-UAV Task Assignment and Trajectory Planning

针对多异构无人机任务分配和航迹规划存在的强耦合特性,为解决串行求解仅能获得局部最优解的问题,提出了一种基于图论的一体化求解框架,采用三维Dubins模型,通过对无人机航向角进行离散化,将路径规划问题和任务分配问题建立为离散图模型。为了实现该混合整数规划问题的快速求解,建立了基于并行化处理的遗传算法策略;为避免执行时序约束任务存在的死锁问题,引入深度优先算法(DFS),通过检测时序任务图环路状态判断任务规划结果的可行性,从而剔除规划结果中的不可行解。仿真结果表明,相比于解耦方法,一体化求解方法能明显提高规划结果的品质;相比于集中式遗传算法,分布式遗传算法能显著提高算法的收敛速度。

In view of the strong coupling characteristics of task assignment and flight trajectory planning of multi UAVs,in order to solve the problem that only local optimal solutions can be obtained by serial solving,an integrated solution framework is proposed based on the graph theory.By using three-dimensional Dubins model and discretizing the heading angle of UAVs,the multi-UAV task assignment and trajectory planning problem are established as discrete graph models.In order to solve the mixed integer programming problem quickly,a parallel strategy is proposed for genetic algorithm.In order to avoid the deadlock problem of executing time-constrained tasks,the depth-first search(DFS) algorithm is introduced to judge the feasibility of the task planning results by detecting the cycle state of the precedence task graph,so as to eliminate the infeasible solutions in the planning results.The simulation results show that compared with the decoupling method,the integrated solution methods can significantly improve the quality of planning results,distributed genetic algorithm can significantly improve the convergence performance compared with centralized genetic algorithm.