基于改进A*算法的航迹规划设计研究*

郑煜坤，王 瑛，吕茂隆，李正欣

（空军工程大学装备管理与安全工程学院，西安 710051）

0 引言

航迹规划是飞机在执行飞行任务前需要做的极其重要的一项工作。合理的航迹规划可提高飞机执行飞行任务的效率，缩短飞行航程，减少油耗代价，增强飞机安全性。我国空域存在大量“危险区”、“禁飞区”和“限制区”[1]，在航迹规划时，必须要考虑“三区”规避问题，减少飞行成本，降低飞行风险。

目前常用的航迹规划算法主要有遗传算法、蚁群算法和A*算法等。遗传算法能够解决复杂背景下的航迹规划问题，鲁棒性较强，但其编码难度大、搜索时间长。蚁群算法采用正反馈、分布式协作的策略，但其信息素的相关规则难以设定[2]。A*算法是一种启发式搜索算法，编码简洁，容易实现，能够解决民航航迹规划中的“三区”规避问题[3]。文献[4]采用离线航迹规划和在线航迹规划的思想，减少了算法在线运行时间，降低了A*算法的信息存储量。文献[5]采用双向A*算法提高搜索效率、减少搜索时间。文献[6]将飞行器的机动约束和燃油约束添加到代价函数中，减少了搜索的节点数，提高了算法运行效率。文献[7-8]提出了一种改进A*算法的无人机航迹规划方法，实现了变方向和变步长扩展节点。文献[9]针对侦察无人机航迹规划易陷入局部最优问题，引入“电势场”理论，将威胁源视为带电体，提出了一种改进的蚁群算法。

然而，上述文献多是针对复杂环境条件下的无人机航迹规划，其关注点主要是算法的运行时间和收敛速度。在民用航空领域，则更关注飞行安全和飞行成本，即在保证飞机运行稳定的条件下实现最优航迹规划。不同于无人飞行器，民用飞机具有体积大、飞行阻力大以及灵活性差等特点，因此，其转弯半径和过载要求更为严格[10]。利用传统A*算法得出的飞机飞行航迹均为“折线航迹”，未考虑大型民航客机的机动性和安全性，增大了转弯处飞行航程，增加了飞行成本，难以满足实际飞行需求。

结合导弹的目标指示型追踪方法，根据民航客机实际，忽略导弹追踪过程中的复杂机动动作和多维追踪曲线，仅采纳其追踪策略，本文提出了一种改进的A*算法，采用水平、竖直和斜向3种追踪模式，将“折线航迹”优化为“光滑曲线航迹”，保证了优化后航迹的平滑性和可实现性，减少了飞机飞行距离。

1 传统A＊算法基本原理

传统A*算法基于启发型搜索函数建立，具有快速、高效、准确的特点，在机器人路径寻优和路线规划等领域有着广泛的应用[11]。根据不同的搜索任务，可以采取有针对性的代价函数。在最短路径寻优过程中，A*算法的代价函数如式（1）所示：

其中，F（ni）表示当前节点i的代价总和，F（ni）的值越小，说明经过i点到达终点的代价越小，i点越有价值；G（ni）表示“既定代价”，指起始点到i点的已耗代价值；H（ni）表示“估算代价”，指自i点到达终点需要付出的可能代价值。

启发公式H（ni）是决定A*算法运算效率和精确性的关键函数，当H（ni）=0时，F（ni）=G（ni），该算法就会变成静态条件下的路径寻优问题。通常情况下，使用两点之间的距离表示代价函数[12]，其表达式如式（2）所示：

式中，a表示单位长度代价，即栅格的边长。D表示目的点，i表示路径上某点。

为详细说明传统A*算法的搜索流程，给出以下规范：搜索区域包括m个栅格，其中S点为起点，D点为终点，i为当前点；OPEN表用于存放未考察点，即当前点i的可达点，CLOSED表用于存放已考察点；F（ni）表示i点的代价函数。A*算法的具体流程如下：

1）令 S∈OPEN，CLOSED=φ；

2）判断OPEN表是否为空，若为空，则不存在最短路径；

3）若OPEN表不为空，则将OPEN表中第1个顶点n1移入CLOSED表；

4）判断n1是否为终点，若为终点，则搜索成功，按追溯法画出最优航迹；

5）若n1不为终点，则对n1周围邻节点nj（j≤m，j≠i）进行扩展，判断其是否存在于OPEN表和CLOSED表中，并计算F（nj）值；

① 若 nj∉（OPEN∪CLOSED），则令 nj∈OPEN，设置父节点为n1；

②若nj∈OPEN，则更新F（nj），取较小值并设置父节点为n1；

③若nj∈CLOSED或nj是障碍点则舍弃，返回步骤5）选择其他邻节点；

6）根据F（nj）大小对OPEN表中顶点进行升序排列，之后再返回步骤2）。流程图如下页图1所示。

2 基于“追踪”思想的改进A＊算法

针对传统A*算法的弊端，引入导弹追踪模型对折线路径进行优化并使用栅格法表示出来。栅格法是指用尺寸相同的正方形栅格将飞行空域分解为一系列网格单元[13]，并将网格与平面坐标系结合，构成栅格坐标网。

2.1 建立追踪数学模型

导弹追踪模型采用目标指示追踪方式，在追踪过程中自动导航系统指引导弹时刻瞄准目标[14]。在飞机航迹规划问题中，为将“折线航迹”优化为“曲线航迹”，可以在折线处将飞机类比为导弹，将栅格中心点类比为目标，并作出以下基本假设。

1）飞机始终以速度v1匀速飞行；

2）飞行全程高度保持不变，忽略起飞降落阶段带来的高度变化；

3）飞机具有自动导航系统和较强的运算能力。

此外，为确保飞行航迹能最终指向目的地，需提出以下追踪策略：

1）利用传统A*算法得出初始航迹并在栅格坐标网中表示；

2）对于初始航迹中方向变化的栅格采用追踪模型。栅格的中心点，即航迹转折点为假定动态目标，飞机驶入该栅格后，其速度方向时刻指向该动态目标，并在动态目标驶出该栅格时追上目标；

3）当飞机到达航迹方向变化的栅格时，激活栅格中心点，此时该动态目标将以速度vi（i=A，B，C，D）沿初始航迹匀速向下一个栅格前进，并在即将驶出栅格时被飞机追上，此时飞机的转弯航迹是一条光滑的追踪曲线。

按照目标点移动方向与坐标轴的关系将追踪模型分为水平追踪、斜向追踪和竖直追踪3种模型，如图2所示。

根据以上基本假设和追踪策略，以水平追踪为例构建如下模型：

飞机进入新的栅格时与其边界交于C（a1-a/2，a2-a/2），此时目标 D（a1，a2）以匀速 vD向 E（a1+a/2，a2）移动。假设 t时刻，飞机行驶至（x，y）点，此点轨迹切线与 DE 交于点 F（a1+v0t，a2），如图 3 所示。

根据假设可知：

此外，（x，y）点切线满足以下斜率：

结合式（4）和式（5）可得：

联立式（4）～式（6）可得到飞机飞行航迹方程为：

化简式（8），可得飞行航迹的解析表达式如下所示：

2.2 改进A＊算法的基本流程

传统A*算法采用追溯法获取飞行航迹[15]，如图1虚线框所示。但是，由于子节点只能向着8个方向拓展，因此，转向角只能是45°或90°，与实际航迹不符且增大航程。改进A*算法针对追溯法缺陷，提出基于追踪模型的航迹生成规则。其具体流程如下：

1）根据传统A*算法求得完整CLOSED表；

2）令指针指向CLOSED表当前节点；

3）连接当前节点与下一节点；

4）判断航迹方向是否发生变化，若变化，则采取相应的追踪模型优化航迹，然后移动指针令其指向下一节点；

5）若未发生变化，则直接移动指针到下一节点；

6）判断指针是否指向终点。若是，则航迹优化结束；

7）若没有指向终点，则返回步骤3）。

改进A*算法主要镶嵌到航迹生成模块，其相应流程图如图4所示。

3 仿真分析

中国航路网络结构复杂，网络内部存在大量“三区”，为了保证民航飞行的安全顺畅，需对“三区”空域进行避让[1]。与文献[3，14]一样，为验证改进A*算法的优越性将飞机模型作为质点来处理，忽略其微观飞行姿态。以“成都-北京”航班航迹为例进行仿真，选择1 210 km×1 110 km的区域，设置栅格边长为50.45 km，则得到24×22的栅格网，仿真结果如图5所示。

其中黑色方框代表障碍区域，蓝色实线代表传统A*算法得到的初始航迹，红色曲线代表转弯处改进航迹。可以看出改进A*算法对飞行航迹作了优化处理，经计算改进航迹比初始航迹节省航程约18.69 km，占初始航迹航程的1.15%。

进一步以“西安-上海”、“重庆-济南”、“郑州 - 杭州”、“昆明 - 合肥”、“南京 - 北京”、“广州 -上海”6条航线的航班为例进行仿真，其结果如下页图6所示。

由图6可以看出对于跨越“三区”密集分布且航程较远的航班，改进A*算法能有效优化其初始航迹，缩短飞机飞行距离，规避禁飞区域，实现了二维准确快速航迹规划，各航班仿真结果如表1所示。

表1 各组仿真结果

由表1可知改进A*算法相对于传统A*算法的运行时间更少，规划航程更短，提高了远距航班的飞行安全和效率。

4 结论

本文对民航飞行航迹进行研究，针对传统A*算法难以规划出符合实际转弯需求的飞行航迹问题，提出了一种基于“追踪”思想的改进A*算法，该算法有效缩短了飞行航程，同时能够对飞行过程中所遇威胁进行规避，实现二维准确快速航迹规划。最后，对“北京-成都”等7条航线的航班进行仿真，验证了所提方法的有效性，为我国民用航空航迹规划提供了一种重要参考。