一种快速3维无人机航迹规划方法

李时东，艾 青，刘 嵩

(湖北民族学院 信息工程学院,湖北 恩施 445000)

无人机航迹规划是为了完成特定的飞行任务，在综合考虑飞行器的机动性能约束、飞行环境、油耗因素等一系列特定约束条件的基础上，自动规划从起始点到目标点的最优航迹或满足一定要求的航迹.无人机的种类繁多[1]，其中固定翼无人机由于约束众多，其航迹规划问题更为复杂.各种无人机航迹规划算法都不可避免要在巨大的规划空间中进行搜索，规划过程相当耗时，航迹规划精度与航迹规划时间往往是一对突出的矛盾，在保证航迹规划质量的情况下，如何提高航迹规划的速度以缩短规划时间是一个急需解决的问题.

对航迹规划算法的研究始于任务规划系统的研制，近三十年来积累了丰硕的成果，广大研究者提出的规划算法可分为三类：①轨迹优化类的方法基于最优控制理论，通过确定动态模型中的状态变量和控制变量, 以达到代价函数最优，典型算法有最速下降法、动态规划法、非线性规划法、最优控制法和奇异摄动法等；②基于概略图和单元分解的确定性搜索法通过将规划空间表示成由一维线段构成的网络图，或者将规划空间分解成简单网格单元，结合搜索算法寻找图或网格中的最优路径，典型搜索算法如A*搜索、Dijkstra搜索等，构图或分解的方法很多，如Voronoi图，Skeleton图等，其中随机路标图(PRM)和随机搜索树(RRT)更是得到广泛的应用；③基于模仿的方法借助仿生学或者物理学的概念对航迹规划问题进行转化，然后求解，被广泛研究的有遗传算法(GA)、粒子群优化(PSO)、神经网络(NN)、模拟退火(SA)、蚁群算法(AC)、人工免疫算法(AI)、人工势场法(APF)、水平集方法(LS)、人工蜂群算法(ABA)等.然而现有算法大多因为规划速度不够理想而难以实用，尤其是在无人机的三维航迹规划应用中，快速高效的航迹规划算法意义重大.本文采用二维平面规划结合高度规划的策略实现三维航迹规划，二维规划过程采用水平集方法，确保所得航迹具有良好的地形回避特性，高度规划采用稀疏A*实现快速性，实验表明，该方法整体规划速度快，所得到的三维航迹具有良好的避障能力和地形跟随能力.

1 航迹规划建模

1.1 问题描述

航迹规划问题本质上是一个多约束条件下的极值求解问题，定义距离函数：u:R2→R+，则航迹可通过求下列问题的最小值得到.

(1)

其中:xs和xg分别代表起始点和目标点的位形，ρ(τ)为某种距离测度，τ是测度的弧长参量.文献证明[2]该极小值问题与求解Eikonal方程(2)等效.

|u|=c

(2)

其中正定代价函数c与距离测度ρ(τ)之间的关系用式(3)来进行描述:

(3)

Cx,x′(s)表示位形x和x′之间的一条路径，s为C的弧长参数.

1.2 航迹规划约束

在不同的应用场景中，航迹规划存在着各种不同的约束[3]，可以分为两类：环境约束和本体约束.环境约束主要指来自无人机飞行空间的各类障碍和威胁源，诸如山峰、建筑、气象禁飞区、敌方雷达、导弹以及火炮等，无人机应该尽可能规避；本体约束指无人机由于机动能力的限制和支持技术(如导航方法)的限制而形成的，如转弯半径、过载等.航迹规划应在满足各类约束的前提下进行.

环境约束中，各种障碍按照其高度可折算为飞越代价，高度越高代价越大，通常威胁源在不同的方向上具有不同的威胁能力，可等效为具有不同长、短轴的椭球或者不同半径的球形区域，进行二维规划时它们投影成椭圆或圆，威胁源位于椭圆中心，它对无人机的威胁强度从椭圆中心沿轴向外视威胁种类不同按特定规律递减，规划出的航迹应尽可能远离威胁源，航迹与椭圆无交点意味着对应的威胁源不影响无人机飞行，航迹一旦与椭圆相交，处于椭圆内的航迹段对应的飞行代价将增加，从而增加航迹的整体飞行代价，威胁对应的整个椭圆形区域都不能通过的区域称之为禁飞区，规划航迹时要保证与禁飞区无交集.

机动约束很多，主要存在最大转弯角、最大爬升/俯冲角、最低飞行高度、最大航程、最大过载量、最短直飞航迹长度以及由导航技术决定的航迹修正间距等多个方面，全部考虑所有的机动约束是一件十分困难的问题，本文采用简化模型：在二维航迹规划过程，主要考虑最大转弯角和最短直飞航迹长度的限制，在高度规划过程中处理最大爬升/俯冲角、最低飞行高度约束.

2 三维航迹规划算法

2.1 二维规划

对于方程Eikonal(2)，如果T(x) 作为距离函数代表从起始点到当前点x的到达时间测度，可以得到用T(x)来表示的Eikonal方程形式[4]:

(4)

其中:Ω表示规划空间，∂Ω为其边界；F为规划空间中的速度场,它代表距离函数(在水平集理论中叫做水平集函数)在规划空间中各点的演化速度，该求解Eikonal方程的方法[5]为Fast Marching Method(FMM).

在将规划空间离散化的前提下，两点之间的距离记作Ti,j=T(xi,j)，假定笛卡尔坐标中网格的宽度为h，对方程(4)定义下面的算子以进行一阶数值近似：

|

(5)

其中代价函数ci,j=c(xi,j)=1/Fij.

图1 二维航迹拟合过程示意图

图2 稀疏A*高度规划示意图

2.2 高度规划

经过二维规划得到的航迹只能保证满足无人机的水平机动约束，以此为基础，进行高度规划产生三维航迹与直接在三维空间搜索航迹相比，规划空间得到有效压缩，规划速度得到提高.本文结合所得到的二维航迹和相应的地形高程信息，采用稀疏A*搜索法进行.如图2，在二维航迹的直飞段，以当前点A为参考点，OA为参考基线，由无人机的最大爬升角、最大俯冲角构成扇形搜索区域，并对扇形区域进行离散化，以当前点到目标点的欧式距离作为A*搜索的启发函数在扇形区域开始搜索，新的扩展节点必须满足两个约束：①最短距离约束；②与空间障碍的碰撞检测约束.对新节点重复上述扩展过程，直至的目标点包含其中，高度规划结束.

3 应用算例

仿真实验用地形高程图数据来自http://gisweb.ciat.cgiar.org/sig/90m_data_tropics.htm，其分辨率为90 m，规划范围为600 km×600 km，仿真所用到的参数设置如下：

1)无人机最低飞行高度为100 m；

2)最短直飞距离为4 km；

3)巡航速度为音速的0.8倍，即0.8 Ma；

4)最小转弯半径为6 km；

5)最大爬升/俯冲角为30°.

图3显示了一个完整的航迹规划过程， 在图3(a)中，采用文中所述方法产生一条长度为450km的航迹，小红旗所在位置为起始点，蓝色三角对应目标点，其中设置两类威胁源，藏青色区域表示普通威胁区，红色区域表示禁飞区，航迹上藏青点为航迹水平转弯点，橙色点为高度变化点.图3(b)是对所获得的二维航迹，结合飞行器的垂直机动能力、最小离地高度和地形高程信息进行高度规划所得的航迹剖面效果，其中红色线条为航迹高度，线条上的黄点为高度变化点，藏青点为航迹转弯点，蓝色曲线为地表.经过高度规划以后的航迹就是一条在三维空间可飞的航迹.

(a)二维航迹规划结果 (b) 高度规划

图4 三维航迹示例(离地高度设为50 m，最小直飞距离设为500 m，转弯半径设为2 km)

为了清楚地显示三维航迹的效果，图4为在512×512大小地图上，采用本文的方法所获得的三维航迹效果，图中所示的两条航迹分别对应于从相同的起点出发到达不同目标点的最优航迹.由于地图变小，为了显示效果明显，将航迹离地高度、最小直飞距离和最小转弯半径等规划参数都作了相应改变.所得的三维航迹具有良好的地形跟随能力.

4 结语

本文利用地形高程信息结合威胁简化模型，采用FMM方法进行二维平面航迹规划，并在此基础上进行曲线拟合以满足无人机水平机动约束，实现了航迹的直线段加圆弧的表示；然后结合稀疏A*搜索进行高度规划，满足无人机垂直机动约束条件，从而实现了无人机的三维航迹规划.仿真实验表明：该方法所得到的航迹具有良好的障碍/威胁回避性能，并具有很好的地形跟随能力，同时由于该方法只在二维航迹所对应的空间进行高度规划，极大地压缩了搜索空间，因此规划效率很高.

[1] 诺曼·弗里德曼.全球作战无人机[M].聂春明译.北京:中国市场出版社,2011.

[2] Rouy E,Tourin A.A viscosity solutions approach to shape-from-shading[J].SIAM Journal on Numerical Analysis,1992,29(3):867-884.

[3] 熊丹君,蔡满意,刘宇坤.多约束条件下飞行器航路规划[J].弹箭与制导学报,2009,29(2):289-292.

[4] Sethian J A.Level set methods and fast marching methods:evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science[M]. 2nd. Cambridge: Cambridge University Press,1999.

[5] Sethian J.Fast marching methods[J]. SIAM review,1999,41(2):199-235.

[6] 李时东,蔡超,丁明跃.一种航迹约束演化新模型及其FMM实现[J].系统仿真学报,2011,23(5):925-929.

[7] Yang K,Sukkarieh S.An Analytical Continuous-Curvature Path-Smoothing Algorithm Robotics[J].IEEE Transactions on,2010,26(3):561-568.