第2章 无人飞行器航迹规划建模

2.1 规划空间表示方法

在进行航迹搜索之前，首先必须将飞行环境中与航迹规划相关的要素（如地形、威胁、气候等）表示成符号信息，便于计算机理解。UAV航迹规划是在三维空间中进行搜索。设（x, y, z）为规划空间某一点的坐标，其中 x，y 表示经纬度，z 表示海拔高度，则航迹规划空间可以表示为集合{(x,y,z)|0≤x≤maxX , 0≤y≤maxY, 0≤z≤maxZ}，它代表了一个空间区域。在实际规划过程中，还需要将该空间区域离散化，即将x,y,z分别按不同的分辨率进行划分，从而得到离散化的规划空间。离散化所采用的分辨率越高，规划结果的精度就越高，但所需要的运算量就越大；分辨率越低，规划结果的精度就越低。

在大多数军事应用中，规划空间都分布着各种各样的敌方威胁。这些威胁可能不断变化，因此事先很难获得有关规划空间中威胁的准确个数，以及每个威胁的类型、位置、覆盖范围、威胁强度（对UAV的杀伤力）等的信息。另一方面，即使是同一威胁，它对UAV的杀伤力还会因为所接收到预警信号的不同而变化，如图2-1所示。假定在战场区域中有两个威胁X和Y（图2-1中圆形的灰色部分表示威胁覆盖范围，黑色的三角形表示威胁中心）。UAV需要飞过该区域，有A，B，C三条航迹供选择。假设在没有预警的情况下，UAV可以安全地飞过任何一个威胁区（航迹A和C）。因为当UAV只经过一个威胁区时，敌方防御系统不能及时捕获和跟踪UAV，或者虽然能够捕获却还来不及拦截，UAV已经越过敌防御系统的拦截范围。而当UAV经过两个威胁区时（航迹 B），尽管威胁 X 可能来不及拦截UAV，但它可以为威胁 Y 提供预警，使 Y 可以提前做好准备，对UAV成功实施拦截。由此可以看出，如果几个威胁可以相互通信，它们联合在一起的杀伤力远大于它们各自的杀伤力之和。Szczerba将这些相互间可以相互通信的多个威胁的组合称之为威胁网[72]。

图2-1 同一威胁对不同的航迹具有不同的威胁指数

除敌方威胁以外，在规划环境中需要考虑的还有地形、障碍、天气等因素。对于同一个战区来说，除了地形一般不会改变以外，其他因素都是不断变化的。因此，一种好的规划空间表示方法不但要能够合理地表示所有这些与航迹规划有关的战区环境信息，而且当其中某些要素发生改变时能够实时地进行更新。

由于航迹规划需要的数字地形高程数据（Digital Terrain Elevation Data，DTED）都是以栅格的形式保存，因此许多军用UAV航迹规划算法都采用数字化栅格的方法表示规划空间[72，84，85]。这种方法为每一栅格单元分配一代价值，对应于UAV经过战区空间相应区域的代价。这里的代价可以包括多种不同的因素如地形特征、威胁、天气条件等。为了简单起见，我们这里只在二维空间进行讨论，它可以很容易地推广到高维空间中去。设某一战区的所有栅格单元的代价构成一个大小为 M×N 的矩阵，称之为地图代价（Map Cost，MC）[1, 14]。根据MC矩阵可生成最佳代价（Best Cost，BC）矩阵。每一栅格单元的最佳代价表示从当前单元到目标单元代价最小航迹的累计代价（假定UAV可以从一个栅格单元到达与其相邻的任何栅格单元）。很多规划算法采用这种方式生成最小代价航迹：从起始单元开始，依次向其BC矩阵中代价最小的邻域移动，最后到达目标单元。利用MC矩阵生成BC矩阵的方法可参见文献[1，3，86]，这里不再详述。图2-2显示了利用MC计算BC的结果（其中阴影部分表示起始点到目标点的最小代价航迹）。

图2-2 网格模型中的MC和BC

这种基于栅格的表示方法主要存在如下几个方面的问题：第一，难以将各种航迹约束条件与栅格结合起来；第二，对于三维航迹规划来说，其规划区域很大，这种表示法所需要的存储空间在实际应用中是难以实现的；第三，不能表示同一威胁对不同航迹的不同杀伤力，例如高炮阵地对先经过预警雷达探测区的航迹具有较大的威胁；第四，生成三维空间的MC和BC矩阵需要大量时间，而规划环境中的威胁、障碍、天气等因素是不断变化的。一旦战场环境发生变化（例如，发现新的威胁），MC和BC矩阵必须更新，这一过程将耗费大量时间，因而这种方法不能用于机上实时航迹规划。

基于以上的分析我们知道，一种好的规划状态空间表示法应能满足如下要求：

（1）状态空间应能合理地反映战区环境的各种信息，以利于航迹搜索。

（2）当战区环境中的某些要素发生变化时能够实时地进行更新，以满足实时应用的要求。

（3）能够根据航迹的不同动态地反映威胁代价的变化。例如，若UAV先经过预警雷达的探测区域，然后飞经高炮阵地，则高炮阵地的威胁概率将更大。

（4）可以满足航迹的各种约束条件，包括最大距离约束、最小航迹段长度、最大拐弯角、最大爬升/俯冲角和最低飞行高度等。

为此，设计一种新的规划空间表示方法，采用不同的数据结构表示不同环境信息。对于地形高程数据，由于原始的数字地形高程数据一般都以栅格形式存储，而且对于同一战区来说，其地形高程数据一般不发生变化，因此直接采用二维栅格结构表示；对于规划环境中的其他要素，如威胁、障碍、天气等，由于它们经常发生变化，因此将它们记录在一个环境要素查找（Environment Attributes Look-Up，EALU）表中，一旦发生变化，便于及时更新。EALU表中的威胁信息应包括威胁的位置、类型、覆盖范围、信息传输能力（例如预警雷达能否将探测到的信息传送到下一个高炮阵地）等内容。

在第1 章中提到，构建搜索图是传统规划算法耗时的两个主要方面之一。利用上面描述的表示方法，通过采用不同的数据结构表示不同的环境要素，避免了传统规划算法构建搜索图的计算量。当战区环境发生变化时可以及时更新规划环境信息，保证满足实时应用的要求。同时，通过利用数字地形高程数据，我们的算法生成的航迹可以自动进行地形回避并利用地形进行威胁回避。