无人机编队队形变换

1.1无人机编队队形变换

1.1.1队形变换问题描述

图4.1给出了队形变化的示意图，图中红色飞机代表长机，其他飞机代表僚机，无人机编队由原三角形队形p “ R变换到目标矩阵队形R' N R。队形变换选择的路线和目标队形的位置是影响队形变换效率的两个主要因素。当目标队形确定时，选择不同的对应路线，其

效率是不一致的。本章队形变换问题主要研究如何选取最优的对应路线。定义队形变化的最优效率为由原队形变换到期望队形的时间最短。

F2 R P'

—韦

|| I

图4.1队形变换示意图

假设编队中有n架飞机，各飞机i变化前的位置为R，期望队形的位置为R'，飞机i从R到R 的变换效率为i，经过的时间为t i，走过的路程为s。则一次变换中的能量效率为：

n

W tran i 件1)

i 0

队形变换的时间和总的路程为：

T tran maX(l, t? , 1, t n ) (4.2)

n

S tran S (4・3)

i 0

则队形变换的最优解问题转换为求取当T tran最小时的各飞机间的对应关系。由第三章编

队保持阶段可以知道，本文的僚机跟踪过程需要根据纵向X轴的距离不断调整自己的速度。

只要保证距离期望点的位置距离最近，根据僚机纵向编队跟踪的串级RID控制系统，僚机

就能以最快的时间到达。则问题可以进一步转化为求取当Sran最小时的各飞机间的对应关

系。假设队形变换在无障碍物情况下进行变换，则R到R'时的直线路径最短，最后可以将

队形变化最优解问题简化为指派问题。编队中有n架飞机，则共有n n中对应关系。若最

优的对应方法为J( R, R )。则其数学表达式为：

J(R,R') mi n(S；an,S2an,|||,S n an n) (4.4) 1.1.2匈牙利算法的应用

匈牙利算法又名为Munkres分配算法，该算法最早由匈牙利数学家D e nes K?nig和Jen?

P i

，长机还是作为目标编队中的

长机。这样只需将 Egerv d r 提出

［59］

。该算法可以用于解决指派问题，最坏情况下运行的时间复杂度为

O n 3

匈牙利算法的问题描述为：有

n 工人和n 任务，每个任务只能分配给一个工人，每个

工人去执行不同任务所需的费用不一样。如何分配使得总费用最小。

匈牙利算法的输入为效益矩阵 A n n ，输入矩阵必须为方阵。 该算法包括以下四个步骤。 前两个步骤执行一次，而步骤 3和步骤4重复执行，直到找到最佳分配：

步骤1遍历矩阵中的所有行，找到每一行的最小值，然后在对应行中将所有元素减去 对应的最小值。

步骤2:遍历矩阵中的所有列，找到每一列的最小值，然后在对应列中将所有元素减 去对应的最小值。

步骤3：使用尽可能少的标记线覆盖效益矩阵中的全部零元素。如果需要 n 行，则零元

素表示最佳分配的对应元素。算法停止。如果需要少于

n 行，请继续执行步骤 4。

步骤4:在步骤3中找到一条线未覆盖的最小元素 （称为k ）。从所有未发现的元素中减 去k ，并将k 添加到所有覆盖两次的兀素中。返回步骤

3。

从上述的分析知道，只要能构造出效益矩阵，便能运行上面四个步骤求解到最优的分配 序列。现将该算法应用到实际的编队队形变换中，

定义最大效益为让编队在执行队形变换前

后，各无人机飞行的路径总和最短。假设在原编队中第 i 架飞机与期望编队队形中第 j 架飞

机的距离为可。则效率矩阵可以表示为：

S ln

:

（4.

5）

考虑到编队队形保持阶段， 所有僚机都以长机作为基点且长机处于自动模式。 如果原队 形中的长机分配到目标队形中的僚机，

可能会造成编队队形很长时间才能收敛，

而且涉及到

编队内飞机之间的模式和角色切换， 增加了编队稳定飞行的难度。 因此本文决定，长机之间

的指派方式固定，以图 4.1为例，长机的对应关系为 P

n-1僚机之间构成效益矩阵即可。式

（4.5）变成:

A(n-1) (n-1)

(4.6

)