1.1 无人机编队队形变换1.1.1 队形变换问题描述图 4.1 给出了队形变化的示意图，图中红色飞机代表长机，其他飞机代表僚机，无人机编队由原三角形队形16PP 变换到目标矩阵队形''16PP 。队形变换选择的路线和目标队形的位置是影响队形变换效率的两个主要因素。当目标队形确定时，选择不同的对应路线，其效率是不一致的。 本章队形变换问题主要研究如何选取最优的对应路线。定义队形变化的最优效率为由原队形变换到期望队形的时间最短。1P4P5P2P3P6P'1P'2P'4P'3P'6P'5P图 4.1 队形变换示意图假设编队中有n 架飞机，各飞机 i 变化前的位置为iP ，期望队形的位置为'iP ，飞机 i 从iP 到'iP 的变换效率为i ，经过的时间为it ，走过的路程为is 。则一次变换中的能量效率为：0ntraniiW(4.1)队形变换的时间和总的路程为：12max( ,,,)trannTt tt(4.2)0ntraniiSs(4.3)则队形变换的最优解问题转换为求取当tranT最小时的各飞机间的对应关系。由第三章编队保持阶段可以知道，本文的僚机跟踪过程需要根据纵向x 轴的距离不断调整自己的速度。只要保证距离期望点的位置距离最近，根据僚机纵向编队跟踪的串级PID 控制系统，僚机就能以最快的时间到达。则问题可以进一步转化为求取当tranS最小时的各飞机间的对应关系。假设队形变换在无障碍物情况下进行变换，则iP 到'iP 时的直线路径最短，最后可以将队形变化最优解问题简化为指派问题。编队中有n 架飞机，则共有nn中对应关系。若最优的对应方法为'(,)iiJ P P。则其数学表达式为：'12(,)min(,,,)n niitrantrantranJ P PSSS(4.4)1.1.2 匈牙利算法的应用匈牙利算法又名为Munkres 分配算法， 该算法最早由匈牙利数学家Dé nes K?nig 和 Jen? Egerv á ry提出[59]。该算法可以用于解决指派问题，最坏情况下运行的时间复杂度为3O n。匈牙利算法的问题描述为：有n 工人和 n 任务，每个任务只能分配给一个工人，每个工人去执行不同任务所需的费用不一样。如何分配使得总费用最小。匈牙利算法的输入为效益矩阵n nA，输入矩阵必须为方阵。该算法包括以下四个步骤。前两个步骤执行一次，而步骤3 和步骤 4 重复执行，直到找到最佳分配：步骤 1：遍历矩阵中的所有行，找到每一行的最小值，然后在对应行中将所有元素减去对应的最小值。步骤 2： 遍历矩阵中的所有列，找到每一列的最小值，然后在对应列中将所有元素减去对应的最小值。步骤 3：使用尽可能少的标记线覆盖效益...
