基于稀疏A*算法的无人机航路规划方法

陈慧杰

（92419部队,辽宁兴城，125106）

基于稀疏A*算法的无人机航路规划方法

陈慧杰

（92419部队,辽宁兴城，125106）

针对多约束条件下三维空间航路规划问题，分析了三维规划空间的划分方法，综合考虑航程代价、爬升代价和威胁代价等因素,针对航路规划任务对各种指标的偏重程度，引入指标的权重系数，设计了代价函数，并编制了稀疏A*算法流程，对算法的有效性进行了仿真验证。验证结果表明：采用稀疏A*算法能够有效地解决多约束条件下的三维空间航路规划问题。

无人机；航路规划；稀疏A*算法

0 引言

航路规划涉及的约束条件众多，主要包括飞行环境约束、无人机物理性能约束、飞行任务与战术目标约束三种主要约束条件[1]。飞行环境约束主要包括地形威胁、雷达探测威胁、复杂气象区威胁等；无人机物理性能约束主要包括最小航路段长度、最大偏航角、最大爬升/下滑角、最大航程约束等；飞行任务与战术目标约束主要包括飞行高度限制、目标任务区进入方向、战术目标约束等，而且这些约束条件往往相互耦合，航路规划中需要根据任务的类型，合理的考虑和处理约束条件并建立威胁模型，以保证所规划航路的安全性，提高无人机的生存能力；另外，航路规划的空间范围比较大，规划中需要处理的信息量大，在三维空间中实现对航路的合理规划更是增加了规划难度，采用稀疏A*算法能够有效解决三维空间下航路规划问题[2]。

1 稀疏A＊算法及其特性

稀疏A*算法（Sparse A*Search，SAS）是由Robert J.Szczerba等提出了一种改进的A*算法。具有普通A*搜索算法一些性质：（1）只要存在到达目标的路径，在规划网格不是特别大的前提下，SAS算法保证终止于到达目标的一条最小代价路径。（2）只要启发式函数满足容许条件，适当增大启发式函数值，可以加速搜索进程。（3）只要启发式函数满足一致性条件，那么当它扩展到某一节点时，它已经找了从起始点到达该节点的一条最优路径。（4）平均搜索时间短。将SAS应用到三维空间中去，在扩展节点时把最小航路段长度、最大拐弯角、最大爬升/俯冲角、航路距离约束、飞行高度限制、固定目标进入方向等航路约束条件结合到搜索算法中去[3-4]，能够有效地减小搜索空间，缩短了搜索时间。

2 规划空间的划分

为了简化空间划分和空间搜索的难度，将三维规划空间中每个网格取为一个小立方体。其中，水平剖面以满足最小步长和最大拐弯角的限制为准则，取为正方形，最小步长为其边长。当无人机从一个网格节点进入相邻网格节点时，可在最大拐弯角的范围内选择下一个可行航向[5]。同理，在高度剖面考虑到最大爬升/俯冲角的限制，假设取为30°，可把网格的垂直剖面取为长方形，长方形的长是最小步长，宽为最小步长的1/4。当无人机从一个网格节点进入相邻网格节点时，垂直方向的下一可行航向的范围也至多包括3个相邻网格，同样，如果需要增加精度，可以进一步细化网格，增加扩展节点个数。网格的划分与具体任务对精度的要求以及所提供的数字地形图的精度有关，因此可以综合考虑两者的关系，对网格进行适当划分。当无人机进入下一个网格时，只需考虑固定的网格，从而减少了搜索时间，进而减少整个规划的时间和存储空间。

3 代价函数设计

规划航路中的撞地概率、被探测概率、被击毁概率与无人机的状态（如飞行高度、速度、地面跟踪等）之间的关系比较难定义，因此，在规划中可以简化代价函数的计算公式，主要考虑航程代价、燃油代价、爬升代价、威胁代价等。

通过缩短航程可以减少无人机在敌方区域的飞行时间，一方面降低了无人机的危险系数，另一方面也可以减少油耗；通过适当的限制无人机爬升降低无人机的飞行高度，可以提高航路的隐蔽性；燃油代价指油耗情况，可以归并到航程代价和爬升代价之中；威胁代价主要是指通过雷达探测威胁区域和敌方防空区域等，无人机尽量远离威胁区域或通过威胁较小的区域。

式中的启发函数可以表示为无人机在地图当前点到目标点之间的欧式距离，即：

由以上两式，无人机航路规划的代价函数可以确定。但是考虑到无人机在执行具体任务时对航路的指标要求，如航程长短、时间长短、油耗大小，是否最大程度避开威胁等[6]。因此，针对航路规划任务对各种指标的偏重程度，引入指标的权重系数w，则无人机航路规划的代价函数为：

4 稀疏A＊算法流程

稀疏A*算法首先需要对规划空间进行合理的划分，然后按照设计的评价函数扩展节点。在规划空间中进行搜索，其中的节点在搜索过程中可分为三类：

1）已被扩展的节点，又成为封闭节点，存放在CLOSED表中；2）当前节点的可行子节点等待扩展的节点，在搜索过程中存放在OPEN表中；3）尚未产生的节点。

采用稀疏A*算法规划航路，步骤如下：

步骤1 将起始节点插入OPEN表中，将CLOSE表置为空。

步骤2 如果OPEN表为空，算法搜索失败。调整算法参数（将规划空间的网格精度调高，或调整启发函数保证其满足可接纳性），重新运行搜索。

步骤3 从OPEN表中移出代价最小的节点作为当前节点，并将其放入到CLOSE表中。

步骤4 如果当前节点与目标节点之间的距离小于最小步长，则将目标点的父节点指针指向当前节点，航路搜索结束，算法搜索成功。从目标点开始向上回溯到起始位置，得到从起始点到目标点的最小代价航路。

步骤5 扩展当前节点。根据当前节点划分规划空间，并判断后继节点是否满足最小飞行高度和航程的约束，若满足，则作为有效后继节点，否则舍弃。将有效后继节点的父指针指向当前节点。

步骤6 返回步骤2。

5 仿真验证

设计数字地图，其中威胁区（如雷达）用坐标为(500,120)和(900,850)，半径分别为80和75的两个圆表示。按照最大拐弯角为45°，最大爬升/俯冲角为30°，最小步长为2km，对规划空间进行划分，代价函数采用式（6）。选择无人机起点网格坐标为（0，0，0），目标点网格坐标（1000，1000，15）。

取启发函数权重为wh=0.4，并取实际代价函数g( n)中航程代价、爬升代价、威胁代价权重相等，即wL=0.2，wC=0.2，wT=0.2。采用稀疏A*算法得到的航路规划等高线图见图1。采用该算法规划的航路可以避开雷达和山峰的威胁，能够实现三维范围内的航路规划功能。但由图1可以看出该航路的航程较长，在紧急任务或航路航程限制严格时可能不满足实际要求。

可以调整实际代价函数g( n)中各参数的权重来实现航程最短[7]。在启发函数和雷达威胁权重不变的情况下，通过调高航程代价并降低爬升代价，即wL=0.3，wC=0.1，wT=0.2，wh=0.4，得到三维航程最优仿真得到的航路规划等高线图如图2所示。由航程最优航路仿真图可以看出，航路在满足威胁规避的情况下，在损失了局部爬升代价的情况下，明显的缩短了航程。

6 结论

通过分析无人机在多约束条件下的三维空间航路规划问题，采用稀疏A*算法的航路规划方法，研究了航路规划空间的划分方法，针对航路规划任务对各种指标的偏重程度，引入指标的权重系数w，得到无人机航路规划的代价函数。在启发函数和雷达威胁权重不变的情况下，通过调整实际代价函数中各参数的权重来实现航程最短。

图1 采用等权重的航路规划等高线图

图2 航程最优航路等高线图

仿真结果表明该方法能够较好地解决多约束条件下的航路最优规划问题，实际应用后的效果进一步验证了该方法的有效性。

[1]李素娟，肖前贵．多约束条件下无人机航路规划动态评价方法[J]．指挥控制与仿真，2012，34（2）：40-44．

[2]刘希，朱凡等．一种改进的快速航路规划方法[J]．飞行力学，2011，29（1）：89-92．[3]丁吉．未知环境中无人机侦察机动态航路规划[J]．四川兵工学报，2012，33（5）：28-31．

[4]张书宇，张金雨，李雪梅．多方向饱和攻击时反舰导弹航路规划方法[J]．指挥控制与仿真，2012，31（11）：6-9．

[5]刘海桥，马东立．无人机三维航迹规划与可视化仿真[J]．火力与指挥控制，2011，36（7）：72-74．

[6]吴剑，喻玉华等．无人机航路规划中的变步长A*算法[J]．光电与控制，2011，18（5）：1-5．

[7]席庆彪，苏鹏，刘慧霞．基于A*算法的无人机航路规划[J]．指挥控制与仿真，2013，38（11）：5-9．

Method of Unmanned Aerial Vehicle Path Planning Based on Sparse A* Algorithm

Chen Huijie
（No.92419 Unit of PLA，Xingcheng，125106）

Aiming at the path planning of three dimensional space under constraint condition，analyzed the dividing method of three dimensional space, comprehensive consideration of voyage cost, cost to climb and threat to the price and other factors, tasks on the degree of lay particular stress on various indicators for path planning, the introduction of the index weight coefficient, designed the cost function, compiled the algorithm process, simulation is conducted on the effectiveness of the algorithm. The result shows that, using spare A* algorithm can effectively solve the constraint conditions of path planning problem in three dimensional space.

unmanned air vehicle；path Planning；sparse A* algorithm

陈慧杰（1983—），男，汉，山西忻州人，硕士研究生，主要研究方向为无人机总体设计。