1. 引言

1.1. 问题背景

随着信息技术、自动化、计算机技术的飞速发展，现代智能飞行器技术已经发生了巨大的变化。智能飞行器起初是一种用在军事上，对敌方进行侦查、干扰以及一定必要破坏的工具。其原型类似于无人驾驶机，但智能飞行器整体更加小巧智能。智能飞行器的结构相对复杂多变，甚至最新的研究，已经向智能变体飞行器的方向发展，以适应多变的环境，提高其多约束条件下的适应性能，在未来作战中将发挥越来越重要的作用，将成为未来战场上的主要作战工具之一。智能飞行器的协同性更强，性能越来越高，但这也使得飞行器的操控与规划预定也越加复杂。飞行器的轨迹规划就是在综合考虑飞行器到达时间、油耗、角度及飞行区域等因素的前提下，以路径最短、用时最短或误差最小等为目标，为飞行器规划出最优或者是最满意的飞行轨迹，保证智能飞行器圆满地完成既定的飞行任务，是实现飞行器自动导航的一项关键技术[1]。航迹规划技术为提高作战效能，实施精确打击提供有效保障。目前，航迹规划技术，已经广泛应用于导弹制导、军用和民用的无人机的控制系统之中。但是随着现代战争进程的发展及战场情报体系的日益完善，航迹规划需要考虑的约束条件越来越多，对智能飞行器的航迹规划算法的求解效率和规划精度也提出了越来越高的要求[2]。

通常航迹规划问题是一个包含多个优化目标和多个多约束条件的非线性规划问题，其核心就是建立一个有效处理各种约束条件的目标函数的数学模型。由于所涉及的约束条件通常较多，所以常采用分层规划的思想进行分析。首先根据已知的环境信息任务、任务要求等规划处一条满足约束条件的全局最优参考路线。然后再进行局部航迹动态优化，以提高飞行器的飞行精度，更有利于应付突发威胁，恶劣天气等意外状况，确保航迹规划的有效性和实时性。

复杂环境下航迹快速规划是智能飞行器控制的一个重要课题。飞行器的飞行物理空间是指，从它的起飞点到目标点之间的区域。在实际生活中，航迹规划的空间都是提前设定好的。这个已经设定的区域就是要进行路径搜索的空间，常称为规划空间，即为路径的搜索范围，也是进行优化的函数定义域。由于智能飞行器系统的结构限制，这类飞行器在实际飞行时，其定位系统无法对自身进行精准定位，往往会随着时间的推移，产生一定的水平误差和垂直误差。一旦定位误差累计过大，就可能导致飞行器偏离事先规划的飞行路线，使飞行器无法正确地到达目标点位置，进而导致飞行任务失败。因此，在其飞行的过程中，实时地对系统的航迹规划进行校正，消除所产生的飞行误差，保证飞行器按照规划的路线飞行，是智能飞行器航迹规划中一项重要任务。本论文研究的就是在系统定位精度限制等多约束条件下，智能飞行器的航迹快速规划问题。

1.2. 问题重述

假设智能飞行器在一个三维空间坐标系中飞行，飞行器的出发点为点A (X₁, Y₁, Z₁)，目的地为点B (X₂, Y₂, Z₂)，其航迹约束条件如下：

(1) 飞行器在空间飞行过程中需要进行实时定位，其定位误差可简单划分为垂直误差和水平误差两种。飞行器在飞行的过程中每飞行1 m，垂直误差和水平误差将各增加δ个专业单位，即每段距离产生的误差大小与飞行的长度线性相关。到达终点时垂直误差和水平误差均应小于𝜃个单位，并且为简化问题，假设当垂直误差和水平误差均小于𝜃个单位时，飞行器仍能够按照规划路径飞行。

(2) 飞行器在飞行过程中需要对定位误差进行校正。飞行区域中存在一些安全位置(称之为校正点)可用于误差校正，当飞行器到达校正点即能够根据该位置的误差校正类型进行误差校正。校正垂直和水平误差的位置可根据地形在航迹规划前确定。可校正的飞行区域分布位置依赖于地形，无统一规律。若垂直误差、水平误差都能得到及时校正，则飞行器可以按照预定航线飞行，通过若干个校正点进行误差校正后最终到达目的地。

(3) 在出发地A点，飞行器的垂直和水平误差均为0。

(4) 飞行器在垂直误差校正点进行垂直误差校正后，其垂直误差将变为0，水平误差保持不变。

(5) 飞行器在水平误差校正点进行水平误差校正后，其水平误差将变为0，垂直误差保持不变。

(6) 当飞行器的垂直误差不大于个单位，水平误差不大于个单位时才能进行垂直误差校正。

(7) 当飞行器的垂直误差不大于个单位，水平误差不大于个单位时才能进行水平误差校正。

(8) 飞行器在转弯时受到结构和控制系统的限制，无法完成即时转弯(飞行器前进方向无法突然改变)，假设飞行器的最小转弯半径为200 m。

按照上述约束条件，本文主要解决如下问题。

问题1：针对数据集1和数据集2中的校正点的数据分别规划满足条件(1)~(7)时，飞行器的航迹，并且综合考虑以下优化目标：

(A) 航迹长度尽可能小；

(B) 经过校正区域进行校正的次数尽可能少。

并讨论算法的有效性和复杂度。

其中数据集1数据的参数为：

${\alpha }_1=25,{\alpha }_2=15,{\beta }_1=20,{\beta }_2=25,\theta =30,\delta =0.001$

数据集2中数据的参数为：

${\alpha }_1=20,{\alpha }_2=10,{\beta }_1=15,{\beta }_2=20,\theta =20,\delta =0.001$

分别绘出两个数据集的航迹规划路径，并将结果(即飞行器从起点出发经过的误差校正点编号及校正前误差)依次填入航迹规划结果表。

2. 模型假设与符号说明

2.1. 模型假设

为了方便问题的研究，本文对题目中的某些条件进行如下的简化及合理的假设：

假设1：若飞行器的水平误差和垂直误差在校正点处满足校正要求且能得到及时校正，飞行器按照预定的航线飞行。

假设2：在终点处，当垂直误差和水平误差均小于个单位时，飞行器仍能按照规划路径到达终点。

假设3：在出发点处(即A点)，飞行器的垂直和水平误差均为0。

假设4：问题1中，在校正点进行校正过程的中，由于飞行器校正的时间较短，为简化问题，校正所产生的位移忽略不计，即校正的过程实现即时转弯。

假设5：校正点的位置和校正类型，在智能飞行器出发前已知，并且不会随着时间而发生改变。

假设6：问题2中，由于结构和控制系统限制，无法完成即时转弯。并假设最小转弯半径为200 m。

假设7：问题3中飞行器到达校正点时即知道在该校正点处能否校正成功。

假设8：为简化问题，本文未考虑空间障碍物和禁飞区域等问题。

假设9：不考虑智能无人机飞行过程中，燃料的消耗对飞行状况产生的问题。

假设10：不考虑雷电，暴雨等突发天气情况对无人机飞行状况的影响。

2.2. 符号说明

3. 问题解答

3.1. 问题分析

相比常规的无人驾驶机和原始的载人侦察机，智能飞行器整体积更加小巧轻便，更加智能。不仅可以实现实时监测，精准打击等基本功能，还可以在飞行过程中自动校正，减少人为操作，协同性更强，飞行性能更好，甚至在向智能变体性飞行器的方向发展。在未来作战中将发挥越来越重要的作用，将成为未来战场上的主要作战工具之一。航迹规划是指在综合考虑智能飞行器到达目的地所使用的时间、速度、油耗及飞行区域等约束条件下，以路径最短、校正调整最少或到达目的地的误差最小等优化条件下，规划出一条最符合智能飞行器要求的航迹路线，以此提高智能飞行器的作战效能，快速精准地到达设定的目的地，实施监视侦查、战略干扰、打击破坏等战略要求，保证智能飞行器圆满地完成既定的战略飞行任务。

问题1的实质是研究在多约束条件下的智能飞行器轨迹规划的优化问题。在满足约束条件(1)~(7)的前提下，建立目标函数，其目的是使得智能飞行器在顺利到达目标点的前提下航迹尽可能最短，并且在飞行过程中，经过校正区域进行校正的次数尽可能少。在此过程的基础上，采用分层规划的思想，通过将约束条件进行融合设计优化算法，分别利用数据集1和数据集2中的数据进行问题求解，即找出在相应数据集下，智能飞行器的最佳规划路径，与此同时本文讨论了优化模型的有效性及计算复杂度。

该航迹规划的目的是使得飞行器在航迹尽可能短的同时，经过校正点的次数尽可能少，故此为一种动态规划问题。本文共给出两个固定数据集：数据集1和数据集2。数据集1中包含613个节点(1个出发点、1个目标点和611个校正区域)及相应位置坐标。数据集2中包含327个节点(1个出发点、1个目标点和325个校正区域)及相应位置坐标。所以，根据各数据集所给的点位置坐标，空间内的任意两点之间的距离，都可以通过欧氏距离公式来进行计算。这就将飞行区域的空间三维问题，转化为了求解最小路径的平面二维带有约束的优化问题。

此外，本题中的飞行器校正点又分为水平校正点和垂直校正点，分别对飞行器进行水平校正处理和垂直校正处理。而对于不同类型的校正点，智能飞行器需要进入该校正点进行校正，由于飞行器存在实时状态误差，因此需要在不同的校正点上建立不同的误差约束。此外，本文还利用一定的限制条件进行权重处理，将距离矩阵转换为邻接矩阵，来表示各点之间的关系，在相应的限制条件的基础上，构建了问题的代价函数，并利用图论Dijkstra智能最短路径算法对上述带有约束的目标函数进行求解。在此期间，本文还对Dijkstra算法进行改进，将约束条件融合在算法之中，从而使得求出的最优航迹规划更加符合实际情况。最后根据算法迭代过程，分析并讨论了改进算法的有效性和时间计算复杂度。

3.2. 模型建立

3.2.1. 飞行器的航迹表示

通常情况下，飞行器的航迹标识号方法有两种[3]：一种是基于飞行器运动学、动力学描述的连续平滑轨迹；另一种是用航迹点表示，相邻航迹点用直线段连接几何折线航迹。相比第一种方法，第二种方法可以将复杂的航迹规划问题，分解为一组同一形式的小规模子问题，对于每个问题只关心一个点的坐标，从而将考察航迹是否可行转变为考虑一个点和一个线段是否满足要求的问题，可以有效地将复杂的实际问题进行合理简化。本题使用第二种表示方法对飞行器的航迹进行描述，便于合理有效地对航迹的动态规划问题进行分析处理。

3.2.2. 欧式距离(Euclidean Metric)

在实际问题中，欧几里得距离(也称欧式距离)是一种通常采用的距离定义。用来描述一个M维空间中向量的自然长度，或两点之间的真实距离。在M = 2和M = 3时，欧氏距离就是表示二维和三维条件下，两点之间的真实距离，相应的公式如下：

二维空间中的欧氏距离：

$d=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}$ (1)

三维空间中的欧氏距离：

$d=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2+{\left(z_1-z_2\right)}^2}$ (2)

3.2.3. 0-1规划

0-1规划是决策变量取值仅为0或1的一类特殊的整体规划。在处理经济管理和某些规划问题中，广泛应用。该方法可将问题中的决策变量，转换为0-1变量(二级制变量)，即决策变量，可以数量化地描述诸多如留与弃，开与关等反映逻辑关系、顺序关系以及互斥关系的约束条件。

本文中，为简化问题的复杂度，对于校正点的类型问题进行0-1规划，具体定义如公式(3)所示：

$q1\{\begin{array}{c}1,该点为垂直校正点\\ 0,该点为水平校正点\end{array}$ (3)

3.2.4. 数据处理

1) 为了更好地便于后面利用算法对问题的处理，在此本文将校正点的校正状态进行数字化表示：

2) 坐标数据处理：附件中给出的是各节点的坐标数据，将坐标数据转化为连通轨迹的距离数据：

$d_{ij}=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2+{\left(z_1-z_2\right)}^2}$ (4)

其中$i,j$ 分别表示不同的校正节点。

3) 空间距离邻接矩阵是表示空间散点之间相邻距离关系的矩阵，本题中的校正点具有空间特性，而空间中，点与点之间距离最短，所以对附件中的校正点坐标建立邻接矩阵D。

以附件1为例构建空间距离邻接矩阵。空间区域共有613个坐标点，包括起始点A、终点B和611个校正点，用W表示邻接矩阵，权值w由相应两点i和j的欧式距离给出，具体表达如公式(5)所示：

$w_{ij}=\{\begin{array}{c}{d}_{ij}；当节点i到节点j之间满足最大校正误差距离\\ \infty ；当节点i到节点j之间不满足最大校正误差距离\end{array}$ (5)

3.2.5. 常用的航迹规划算法

A*搜寻算法[4]俗称A星算法，是一种启发式图搜索算法，是一类求出最低通过成本的算法。该算法广泛地用于路径优化领域。它的特点是检查最短路径的过程中，对每个可能的节点同时引入了全局信息，可以在全局有限的条件中，对当前节点距终点的距离做出合理的估计，作为评价该节点处于最短路线上的可能性判断度量，并保证全局最优解的收敛性，在处理航路规划类问题时，可以较好地满足各类限制条件。具有可采纳性、单调性、信息型的特点。

A*算法的核心思想是建立一个启发函数，如公式(6)所示：

$f\left(n\right)=g\left(n\right)+h\left(n\right)$ (6)

式中：$g\left(n\right)$ 是从起始点到当前节点n的实际代价值，$h\left(n\right)$ 是从当前节点n到目标点的估计值。两者相加得到的就是当前节点的总估计值$f\left(n\right)$ ，然后再对$f\left(n\right)$ 的大小做出比较，选取$f\left(n\right)$ 最小的节点n作为有效节点。

A*算法的实现步骤如下：

步骤1：把起始点作为第一个路径节点，将周围与之相邻的节点作为候选节点，并储存。

步骤2：分别计算步骤1中的候选点对应的启发函数值，再找出启发函数值最小时所对应的节点，把该点作为有效点，并记录该点。

步骤3：判断步骤2中得到的有效点是否满足终止条件，若满足，结束算法；若不满足，则跳转回步骤2，将下一点作为新的起始点继续搜索，直到满足条件为止。

步骤4：将所有有效点进行连线，获得最优路径。

虽然A*算法是比较常用的一种航迹规划算法，但在每一次扩展时，均需对范围内所有节点进行判断，将所有满足要求的节点加入到扩展列表中，循环处理。这就导致了算法计算量过大，大大降低了规划路径的效率，无法满足本题中的快速规划要求，降低算法的时效性。其次，A*算法每一步的最佳搜索方向并不是朝着目标点的方向的，因此得到的路径通常不是最优，或者规划出的路径有一定的曲折，并非最短。所以判断该方法并不适用本文要求，需考虑其它算法处理本题。

3.2.6. 改进的最短路径算法

经典Dijkstra算法

最短路径分析是网络分析最基本的功能之一。迪杰斯特拉算法(Dijkstra)算法是荷兰计算机科学家Dijkstra提出的一种最短路径算法。迪杰斯特拉算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。常用于搜索从某一固定起点到其余各点的最短路径，适合解决静态道路规划问题，是目前公认的较好的最短路径算法。最短路径不仅仅指一般意义上的距离最短，诸如时间、费用都可被引申为最短路径。相应地，最短路径问题就成为最快路径问题、最低费用问题等[5]。

经典Dijkstra算法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点。网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点。每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。

算法的基本思想基于以下原理：两结点间的最短路径包含了其内部其它的最短路径，而算法实现的主要技术是松弛技术，而这种技术的实质是反复减小每个结点实际路径权值的上限，直到该上限等于最短路径的权值[6]为止。即若序列$\left\{v_0,v_1,\cdots ,v_{n-1},v_n\right\}$ 是$v_0$ 到$v_n$ 的最短路线，则序列$\left\{v_0,v_1,\cdots ,v_{n-1}\right\}$ 必为$v_0$ 到$v_{n-1}$ 的最短路线。

定义两种标号：临时标号V和永久标号U。若给$v{}_i$ 点一个U标号，表示从$v_0$ 到$v{}_i$ 点的最短路径，$v{}_i$ 的标号不再改变。若给$v{}_i$ 点一个V标号，表示从$v_0$ 到$v{}_i$ 点的估计最短路径的上界，是一种临时标号，凡没有得到U标号的点，在终点$v_{n-1}$ 得到U标号之前，保持计算。

计算步骤如下：

步骤1：给起始点$v_0$ 以标号U，令U(0) ={$v_0$ }，余下的点全部标号V，对于$i\ne 0$ ，则给定$\text{l}\left(v{}_i\right)=+\infty$ 。

步骤2：如果$v{}_i$ 为刚刚获得U标号的点，则考虑V标号的点$v_j$ ，对于$v_j$ 的V标号进行更改：$l\left(v_j\right)=\min \left[l\left(v_i\right),l\left(v_i\right)+d_{ij}\right]$ 。

步骤3：比较所有具有V标号的点$v_j$ ，把最小者V标号的点改为P标号，即$\min \left[V\left(v{}_j\right)\cup U_i\right]=U_{i+1}$ 。

步骤4：若终点得到U标号，则计算结束，所有获得的U标记点即为所算出的最短路径。否则代替$v{}_i$ 转回步骤2。

改进的Dijkstra算法

由于本文针对的是三维空间中的散点，所以对于本文所要解决的问题，我们做出了如下的算法思想改进：

1) 行器每飞行1 m，垂直误差和水平误差将各增加0.001个单位。以下以距离简称两点之间的飞行路程，距离与飞行误差成比例；

2) 空间两点之间距离超出最大校正误差要求，则视作不能直接到达；

3) 由于存在误差累计，在已确定的垂直(或水平)误差点，对于下一个点的选取，则考虑选取满足现有误差值裕量的点来校正，降低水平(或垂直)误差以便选取下一个点；

4) 再结合Dijkstra算法，寻出一条最短路径。

Figure 1. Flowchart of the improved Dijkstra’s algorithm

图1. 改进后Dijkstra算法的流程图

计算步骤如下：

步骤1：初始化label()为inf。给起始点$v_0$ 以标号U，令U = {$v_0$ }，余下的点全部标号V。以二分法思想，在考虑校正点类型的情况下，计算初始点到各顶点的距离，并计算飞行误差是否满足对应校正点对误差的约束条件。label(v)为起始点到点v的距离。在满足的飞行误差前提下更新label(v)。

步骤2：选取最小的label(v)，将当前的V标号替换给U标号。

步骤3：如果$v_i$ 为刚刚获得U标号的点，则考虑V标号的点，且$d_{ij}$ 是否满足距离限定要求，对于$v_i$ 的V的标号进行更改；$l\left(v_j\right)=\min \left[l\left(v_i\right),l\left(v_i\right)+d_{ij}\right]$ 。

步骤4：对$v_j$ 进行误差校正，若超出校正误差，则该点不选用，重复步骤2。

步骤5：比较所有具有V标号的点$v_j$ ，把最小者V标号的点改为U标号，即$\min \left[V\left(v{}_j\right)\cup U_i\right]=U_{i+1}$ 。

步骤6：若终点得到U标号，则计算结束，所有获得的U标记点即为所算出的最短路径。否则代替$v_i$ 转回步骤3。

改进后Dijkstra算法的流程图如图1所示。

3.2.7. 代价函数(Cost Function)

代价函数(又称损失函数) [7] [8]，是将随机事件或其有关随机变量的取值映射为非负实数以表示该随机事件的“风险”或“损失”的函数。在应用中，损失函数通常作为学习准则与优化问题相联系，即通过最小损失函数求解和评估模型，通常处理分类问题和回归问题等，是最优控制领域中一个基础的判定方式。

本题的多约束条件下的航迹规划问题实质是一个动态规划的问题，目的是在多约束条件下，寻找出符合要求的最优路径。因此，本文引入代价函数，对优化效果综合地进行定量评定分析。并通过代价函数的引用，将多个约束条件进行归一处理，简化了问题的复杂性，并有利于改进模型。代价函数的表达式如公式(7)所示：

$f={\displaystyle \sum _{i=1}^n\left({\alpha }_{1i}{l}_i+{\alpha }_{2i}{k}_i+{\alpha }_{3i}{r}_i\right)}$ (7)

其中，${\alpha }_{ji}$ 代表不同点处，几个约束条件的权重参数，可通过人为给定；

$l_i$ 代表路径上第i个点的路径长度；

$k_i$ 代表经过第i点时，所经历的校正次数；

$r_i$ 代表第i个点处，进行校正的误差限制条件。

3.3. 模型的求解与分析

根据前面所述建立的模型与搭构算法框架，在此利用题目中给出的真实数据进行模型求解，具体结果如下所示：

3.3.1. 数据集1

处理数据集1时，利用题中所给的参数即：垂直校正点、水平校正点以及飞行器能够按规划轨迹正常飞行的参数，如下所示：

${\alpha }_1=25,{\alpha }_2=15,{\beta }_1=20,{\beta }_2=25,\theta =30,\delta =0.001$

经过利用上文所提的改进的Dijkstra算法处理后，可得到了满足题目要求的最优规划路径，以及在校正点处的智能飞行器校正状态。数据集1的航迹规划结果表如表1所示。在该航迹中，飞行器共经过11个校正点，飞行路径总长度约为106,802.676米，路径的三维效果图如图2所示。

Table 1. Table of trajectory planning results for dataset 1

表1. 数据集1的航迹规划结果表

Figure 2. Shortest path of the trajectory for dataset 1

图2. 数据集1的航迹最短路径

该部分获取最优路径的坐标如表2所示。

3.3.2. 数据集2

处理数据集2时，垂直校正点、水平校正点以及飞行器能够按规划轨迹正常飞行的参数要求如下：

${\alpha }_1=20,{\alpha }_2=10,{\beta }_1=15,{\beta }_2=20,\theta =20,\delta =0.001$

经过我们航迹规划算法处理后，我们得到了满足题目要求的最优规划路径。最优路径的相关参数如表3所示。共经过13个校正点，路径长度为约118730.0358米。路径的三维效果图如图3所示。

Table 2. Coordinates of the optimal path

表2. 最优路径的坐标

Table 3. Table of trajectory planning results for dataset 2

表3. 数据集2的航迹规划结果表

Figure 3. Shortest path of the trajectory for dataset 2

图3. 数据集2的航迹最短路径

4. 结论

根据算法复杂性理论，评价一个算法质量的优劣，主要从算法的时间复杂度或空间复杂性来考虑[9]。算法的时间复杂度是指，执行该算法所消耗的时间代价。在本文所提出的算法中，借鉴经典的Dijkstra最短路径算法的思想，在此基础上进行了改进，来解决多约束条件下的航迹规划问题。并通过对数据集内，各校正点的预处理，计算各点之间的欧氏距离。根据题中限定的“飞行器每飞行1 m，垂直误差和水平误差将各增加个专用单位”，以及各校正点完成校正的误差限制条件，优先对邻接矩阵进行筛选处理，大大减少了备选参考点。通过这样处理大大减少了算法迭代次数以及计算时间。并通过权重设定代价函数，在算法中进一步筛选划分，缩小航迹规划中的预选范围。从而有效地提高了算法的计算效率，减少了算法的计算复杂度。同时，相比于传统的A星算法，使用本文所提出的改进算法，进行航迹规划，可以在更短的时间内，得到航迹长度更短，经理校正点的次数更少计算效果，更符合题所设定的优化目标，有效地提高了优化效果。进一步证明了本文提出的算法模型具有更低的复杂度和更有效的优化能力。

参考文献