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

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.