基于地形的直升机路径规划算法研究

石璐璐，徐金明

(中国直升机设计研究所，江西 景德镇 333001)

0 引言

军用直升机的作战飞行空间主要集中在低空或超低空。在此空间内，直升机易受到低空障碍物和地形的干扰。基于地形的路径规划是直升机低空飞行路径规划技术的基础，利用任务区域的高程地图数据，规划出满足任务约束条件和直升机平台性能约束的全局规划航路，为直升机在山地、丘陵等复杂地形环境下安全飞行提供路径作为参考，从而降低飞行员的负担，提高直升机飞行的安全性。

Dijkstra算法是最经典的最短路径搜索算法，属于遍历搜索，以起始点为中心向外层层扩展，直到扩展到终点为止。A*算法是在Dijkstra算法的基础上，加入启发式函数，用来决定下一步应该优先扩展哪个节点。很多外国学者提出了A*算法的各种改进和优化，如IDA*算法、LPA*算法、BidirectionalA*算法等。经过改进和优化后的A*算法在求解准确性和算法效率上都有了极大的提高，A*算法是直升机路径规划领域目前研究较为成熟、应用较多的一种算法。文献[6]便是基于A*搜索算法，提出了救援直升机二维航迹规划方法，在满足安全间隔的前提下，求解可行最短飞行路径。因此，文本选择A*算法进行基于地形的直升机路径规划研究。

1 标准A*算法

A*算法是一种启发式搜索算法，通过设定合适的代价函数，全面评估每个待扩展节点的实际代价值和预估代价值，通过比较所有待扩展节点的代价值大小，选择代价最小的节点进行扩展，直到找到目标节点位置。相比Dijkstra算法，A*算法引入了启发函数

h

(

m

)来估计当前节点到目标点的代价，从而引导搜索方向，达到减少搜索范围、提高搜索效率的目的。

标准A*算法的代价函数形式为：

f

(

m

)=

g

(

m

)+

h

(

m

)

(1)

其中，

f

(

m

)表示当前节点

m

的代价值，

g

(

m

)表示从起始位置点到当前节点

m

的实际代价值，启发函数

h

(

m

)表示从当前节点

m

到目标点的预估代价值。在标准A*算法中，

g

(

m

)一般设为实际的路径长度，

h

(

m

)一般设为当前节点到目标点的欧式距离。已经证明，只要启发函数满足可接纳性条件，即

h

(

m

)小于等于节点

m

到目标点的真实代价

h

(

m

)，且状态空间中存在可行解，则A*算法可以保证找到最优解。当

h

(

m

)=0时，A*算法就变成了Dijkstra算法。

在实际应用中，标准A*算法还存在一些问题，比如算法收敛时间较长、规划路径不满足直升机飞行性能要求等。针对这些问题，本文对标准A*算法进行了实用性改进。

2 标准A*算法的改进

2.1 代价函数的设计

A*算法的核心部分是代价函数的设计，包括实际代价值

g

(

m

)和启发函数

h

(

m

)。首先需要确定实际代价值

g

(

m

)的求解公式：

g

(

m

)=

k

∑

D

(

i

)+

k

∑

A

(

i

)+

k

∑

S

(

i

)

(2)

式中，

D

(

i

)为节点

i

与节点

i

-1之间航路段的水平距离；

A

(

i

)为节点

i

与节点

i

-1之间航路段的地形高度差值；

S

(

i

)为节点

i

与节点

i

-1之间的航路段及上一个航路段之间的角度值；

k

、

k

、

k

分别为各项的加权系数。相比传统三维A*算法中直接通过空间距离确定的实际代价值，本文将实际代价值

g

(

m

)拆分成三项，并通过设置合适的加权系数，最终规划出综合航程较短、爬升

/

下降较少、转弯次数较少的期望路径。启发函数通常使用当前节点与目标节点之间的欧式距离来表示，以保证

h

(

m

)≤

h

(

m

)。本文为了使启发函数更接近实际代价值，提高算法效率，设计

h

(

m

)求解公式为：

h

(

m

)=

a

(

k

D

(

m

)+

k

A

(

m

))

(3)

式中，

D

(

m

)为节点

m

、目标点之间的水平距离，

A

(

m

)为节点

m

、目标点之间的地形高度差，

k

、

k

分别为各项的加权系数，与实际代价值求解公式中的系数相同，

a

为启发函数预估代价值的权值参数。角度差代价

S

(

i

)项是航段之间的夹角，难以准确预估，因此与实际代价值

g

(

m

)相比，

h

(

m

)少了角度差代价项，仅有水平距离代价

D

(

m

)、高度差代价

A

(

m

)。此外，还增加了权值参数

a

，用以调节算法运行速度。

2.2 节点扩展改进

传统二维A*算法在进行栅格扩展时可以向8个方向进行扩展，每次选择待扩展子节点中代价函数值最小的节点作为下一个搜索节点，直至最终到达目标点。普通A*算法是全方向的扩展搜索，并未考虑直升机本身的性能约束，使得算法的效率低下。此处考虑采用改进A*算法，结合直升机的约束条件排除无效节点，减少节点的扩展方向，从而有效减少搜索空间，提高搜索的效率。

考虑到直升机的飞行性能等因素，在飞行速度不为零的情况下，直升机无法原地掉头；在直升机转弯半径的限制以及规划路径平滑度要求下，排除短距离大角度转弯的极限操作。因此，根据直升机实际飞行方向限制，将8个节点扩展方向缩减为3个。如图1所示，在节点m处只能向其路径方向水平投影的正前方、左前方、右前方的备选节点扩展，

m

-1为节点

m

的父节点，即

m

-1—

m

为当前节点

m

的路径方向。

图1 改进A*算法节点扩展方向示意图

此外，为了使最终得到的路径满足直升机转弯半径限制，地图栅格距离即搜索步长应满足一定的约束条件：

length

_

step

>

R

(4)

式中，

length

_

step

为栅格距离

/

算法的搜索步长距离值，

R

为直升机的最小转弯半径。

2.3 搜索步骤优化

本文的改进A*算法的搜索步骤与传统A*算法大体相同，仅增加了子节点的判断步骤和子节点是否满足直升机性能约束的判断步骤。改进A*算法的搜索步骤如图2所示。

图2中步骤(1)为改进算法的新增步骤—子节点的判断。2.2节中介绍了节点扩展方向由8个改进为3个，但是起始点不存在父节点，因此无法将子节点缩减为3个。与其他节点不同，起始点的子节点仍然有8个。具体操作为：

1)如果

m

点是起始点，则节点

m

存在8个子节点，步骤结束；2)如果

m

点不是起始点，计算节点

m

与节点

m

-1的相对位置(Δ

x

,Δ

y

)，其中Δ

x

=

x

-

x

-1,Δ

y

=

y

-

y

-1;3)根据相对位置(Δ

x

,Δ

y

)，获得当前节点处的路径方向，确定3个子节点的位置，步骤结束。

图2中步骤(2)为改进算法应用的新增步骤—子节点是否满足直升机性能约束的判断。为了使规划路径满足直升机实际飞行性能要求，且安全可行，需要在节点扩展过程中对子节点是否满足直升机性能约束进行判断，不满足的子节点则直接跳过。具体操作为：

图2 改进A*算法流程图

1)为子节点赋予满足离地高度约束的高度值，计算当前节点与子节点高度差和水平投影距离的比值，判断计算结果是否满足直升机爬升梯度

/

下降梯度的限制，若不满足则直接跳过该节点；

2)计算子节点水平安全范围内，是否有地形障碍物，若有地形障碍物，则直接跳过该节点。

3 算法性能分析

本文选择了范围15km×15km、精度25m的高程地图，通过MATLAB进行改进A*算法的仿真分析。

影响算法性能的参数有：

1)

k

(代价函数—水平距离加权系数)；2)

k

(代价函数—地形高度差加权系数)；3)

k

(代价函数—角度加权系数)；4)

a

(启发函数的权值参数)；5)

length

_

step

(搜索步长)等。本文选择其中的

k

、

k

、

k

、

a

四个参数进行影响分析。为了不影响对参数影响的分析，为搜索步长设置合适的数值。取直升机飞行速度为200km/h。该速度下直升机的最小转弯半径为180m，因此要求

length

_

step

>180m。由于地图精度为25m，为了满足

length

_

step

>180m的要求，

length

_

step

应该≥8个地图坐标，即200m。从仿真试验角度来说，搜索步长越小，仿真结果越可靠。因此本文仿真试验中，取

length

_

step

=8×25m。

3.1 加权系数的影响分析

根据算法原理来看，加权系数不是通过自身的数值，而是通过三个加权系数之间的比值关系来对算法性能产生影响的。因此，为了便于分析，将

k

设为1。1)

k

的影响分析在分析

k

值影响的仿真试验中，将

k

、

a

四个参数均设为1，

k

取0，通过调整

k

的数值来得到不同的规划路径(图3)。

图3 路径规划结果(k1=1，k3=0，a=1)

比较图3中4条路径可知：当

k

=0时，直升机完全进行贴地直线飞行，当地形起伏较大时，飞行操作难度大，不满足实际的飞行需求；在

k

一定的情况下，

k

值越大，算法越趋近于地形规避，即避开高海拔区域，尽量在地形平坦区域飞行。但是

k

值过大会导致算法敏感度增加，在不影响整体路径的基础上，路径中的拐点会增加，路径平滑度下降。因此，为了获得合适的路径，

k

的取值应该根据任务区域地形特点、飞行任务需求等进行综合考虑。具体取值需要在大量样本下进行对比分析，最终给出建议值，本文在此不做更多讨论。在本文所用地图中，当

k

/k

=5时的路径结果最接近期望路径，因此后面的仿真中，

k

值设定为5。2)

k

的影响分析在分析

k

值影响的仿真试验中，将

k

、

a

三个参数均设为1，

k

设为5，通过调整

k

的数值来得到不同的规划路径(图4)。比较图4中几条路径可以看出：随着

k

值的增加，规划路径中会在不影响整体路径的基础上拐点逐渐减少，即路径的平滑度逐渐增加；然而，当

k

值从500开始，整体路径受到影响，此时，在本地图中，路径角度对算法的影响开始超越地形高度差的影响；当

k

=2000时，路径角度对算法的影响远远大于超越地形高度差的影响，规划路径变为一条连接起点、终点的直线。

图4 路径规划结果(k1=1，k2=5，a=1)

在不同地图中，

k

与

k

的比值对路径的影响有所不同。在本文所用地图中，当

k

/k

=20时，实现在低海拔区域的路径平滑效果；当

k

/k

=100时，路径角度和地形高度差对规划路径的影响趋于平衡。

3.2 权值参数a的影响分析

启发函数的权值参数

a

是用来调整算法的搜索效率的。从算法原理来看，

a

值越大，算法越快地趋向终点，搜索效率越高。基于前文的仿真结果，为了便于分析，本文中将

k

设为1，

k

设为5，

k

设为100。不同

a

值下的算法搜索步数如图5所示。可以明显地看出，随着

a

值的增加，算法的搜索效率也在增加。当

a

值为0时，算法几乎遍历了地图上所有的节点；

a

值从0增长至2的过程中，算法的搜索步数在大幅减少；当

a

值大于2后，随着

a

值的增长，算法搜索步数的增加幅度有着显著的降低，且两者之间几乎呈线性关系。选取其中一部分

a

值下的规划路径图进行对比分析，如图6所示。结合图5中的算法搜索步数与

a

值关系以及图6中的路径规划结果，可知：当

a

<2时，启发函数的权值比重仍然比实际代价值小，规划结果受实际代价值影响更大；当

a

>2时，启发函数的权值比重逐渐超过实际代价值。

图5 算法搜索步数与a值关系图(k1=1，k2=5，k3=100)

图6 路径规划结果(k1=1、k2=5、k3=100)

从兼顾算法搜索效率和规划路径效果的出发点来考虑，

a

值应该小于图5中图线转折点对应的

a

值，在本文的地图和参数设置条件下，即为

a

<2。

4 总结

针对直升机在山地、丘陵等复杂地形环境下的低空飞行需求，本文设计一种基于地形的路径规划算法，在代价函数、节点扩展方向、约束条件等方面对A*算法进行了改进，为直升机路径规划算法提供设计思路和算法改进的方向；通过仿真试验，分析了算法参数值对算法性能的影响，并给出参数选取原则，为改进A*算法在基于地形的直升机路径规划中的实际应用奠定基础。

然而本文的算法性能分析是基于选定地图进行的，下一步，将利用大量不同环境下的地图数据研究算法参数值的自适应选择方法，以解决不同任务环境中的直升机路径规划问题。