智能优化算法在无人机航迹规划应用研究

雷 蕾

(海军装备研究院 北京 100073)

智能优化算法在无人机航迹规划应用研究

雷 蕾

(海军装备研究院 北京 100073)

智能优化算法具备计算效率高,适应性强的特点,通过对智能优化算法在无人机航迹规划的研究,分析无人机航迹规划模型,提出无人机航迹规划的约束条件,阐述了目前国内外应用和研究的几种航迹规划算法,并对无人机航迹规划算法的发展趋势进行了展望。

无人机; 航迹规划; 智能优化算法

Class Number TP391

1 引言

随着计算机、通信技术、自动化的发展,无人飞行器的种类更加丰富,具有协调性强、技术密集、系统复杂的特点,因此对无人飞行器航迹规划工作人员提出了愈来愈高的要求。同时,随着现代无人飞行器航迹规划难度、危险度以及要求的不断增加,通过操作人员手工操作成功完成复杂的飞行任务越来越困难。面对这种情况,无人机航迹规划技术成为一种有效的解决途径。

由于无人机面临的战场环境将是异常复杂辽阔,规划约束条件众多,模糊性大,各因素之间存在强耦合及其自身独特的控制和任务方式,航迹规划在处理这些因素时面临极大的挑战。许多学者已对航迹规划方法问题作了大量工作,就此作了不同程度的叙述。采用分层规划方法进行航迹规划,根据规划层次不同,可以将航迹规划算法分成两大类:任务级航迹规划和战术级航迹规划。任务级航迹规划可以采用较粗糙的数字地图和简化的性能模型,其目的是获得参考航迹,从而减少战术级航迹规划的搜索空间,任务级航迹舰划包括网络法、符号规划方法、试探法和知识推理法等方法。战术级航迹规划实质是个轨迹优化问题,可以运用最优控制理论求解战术级突防航迹问题,采用动态规划算法或A*算法得到优化航迹。另外,模拟退火算法和遗传算法也在航迹规划问题中得到广泛应用,而蚁群算法是这几年发展起来的一种新方法。对于规划无人机航迹的问题,需要协调许多约束条件,在理论上还没有一种通用的航迹规划算法。因此,在不同条件约束下,寻找航迹规划时间更短,寻优更好的航迹规划算法具有重要的现实意义。

2 无人机航迹规划问题分析

无人机在执行任务时,会受到如禁飞区、障碍物、险恶地形等复杂地理环境的限制,因此在航迹规划时,应尽量避开这些区域,可将这些区域在地图上标识为禁飞区域,以提升无人机工作效率。此外,飞行区域内的气象因素也将影响任务效率,应充分考虑大风、雨雪等复杂气象下的气象预测与应对机制。因此,无人机航迹规划技术需要考虑约束条件、飞行环境、突防安全等基本因素。

1) 飞行器的物理限制。在航迹规划过程中必须考虑无人机自身性能限制,否则无人机可能不能按照规划航迹飞行,无人机的自身性能对航迹规划的约束主要有:最大偏转角,它限制在生成扩展航迹时无人机水平面的偏转角度,生成的新航迹段偏转角只能小于或等于无人机限定的最大角度;最大俯仰角,它限制在生成扩展航迹时无人机在垂直平面上仰或俯冲的最大角度;最小航迹段长度,它用于限制无人机在改变飞行姿态之前飞出的最短距离;最低飞行高度,虽然飞行高度越低,被敌方发现的概率越低,但飞行越低无人机触底的概率也会增加,所以需要对最低高度进行限制。

2) 航迹距离约束。它限制规划的无人机航迹的长度必须不大于一个预先设置的最大飞行距离。最大飞行距离对应无人机所载燃料。

3) 实时性要求。实时性要求主要针对在线航迹规划,由于飞行现场环境复杂多变,不可能规划出满足突发状况的航迹,这样就要求无人机具有实时规划能力。实际的地形和敌情信息与事先获得的信息总会有出入,一般认为这种差异的影响不大,可以通过保留一定的安全裕度来解决。对于无人机,航迹规划往往由地面规划员在起飞前做好,存储在机载计算机内。无人机起飞之后,就按预定的航迹飞行。从长远来看,无人机需要具有自主控制的能力,有部分的人工智能,因而往往还需要根据战场实际情况进行实时航迹规划,这是由未来无人机所执行的任务复杂性决定的。在这种情况下,无人机需要利用机载传感器及我方的侦察通信系统实时探测敌方防御区域的各种信息,通过实时航迹规划来消除规划轨迹的偏差。由于机载传感器的探测距离有限,实时航迹规划往往只能局部修正规划航迹。

航迹规划的另一难点是进行自适应航迹规划。自适应航迹规划是提高飞行器生存能力的重要方法。自适应航迹规划包括无人机在飞向目标途中接受和分析近实时的威胁数据,以致能改变预先规划的航迹,达到减少受机动威胁攻击的目的。自适应航迹规划甚至可以改变飞行器的任务内容,使得作战任务更具灵活性。飞行器自适应航迹修改需要得到实时信息,这种实时信息应该具有某种标准格式和协议。航迹规划算法中也应具备一定的标准模式,以便快速响应所输入的信息。整个自适应航迹规划程序应有一定的智能,目前这方面的研究还处于起步阶段。

3 无人机航迹规划方法研究

由于无人机所处的战场环境异常复杂辽阔,规划约束条件众多,各因素之间又存在强耦合,再加上无人机自身独特的控制方式,航迹规划在处理这些因素时面临极大挑战。航迹规划问题是一个NP问题,具有约束条件多、复杂性强、时效性要求高、规划范围大、直接求解比较困难的特点,近年来国内外学者已提出了许多不同的规划方法。

其中,采用智能优化算法求解无人机航迹规划问题一般分为两类,一类是确定型搜索算法,如:基于极小值原理的确定性计算方法和基于动态规划或A*算法的确定性状态空间搜索方法;一类是不确定型搜索算法,如以随机搜索为特征的模拟退火算法、遗传算法和蚁群算法等优化算法,由于这些算法模拟了自然界的物质变化以及生物活动和进化的过程,具有一定的优点和特点,因而在航迹规划应用中得到了越来越多的重视。特别是遗传算法由于不受搜索空间限制性假设约束,不要求优化函数具备连续、可导等假设,并隐含并行性,对于航迹规划这种含有大量模糊信息、可以适应威胁环境的变化,多约束的优化问题来说,具有特别重要的意义。

3.1 A*算法

基于A*算法的航迹规划是目前国内外应用较多的规划算法,属于一种经典启发式搜索算法,被许多学者应用于无人机二维航迹规划中。

A*算法基本思想:通过设定启发函数来评估搜索到的扩展航迹点代价值,通过比较选择代价值最优的航迹点,直到到达目标航迹点后完成航迹规划。基于A*算法的无人机航迹规划从起始航迹点出发,通过不断寻找最小代价值的下一个扩展航迹点,从而产生一组航迹点集,完成整个航迹规划过程。A*算法的核心实际就是下一航迹点扩展的过程,通过这一特点,可以找到代价值最优的飞行航迹。在确定最优飞行航迹后,需要计算该航迹是否满足航迹规划时对燃油、航程、速度或时间等条件的约束。如果不能满足航迹规划约束条件,规划航迹失败,必须重新规划并对参数适当的修改。

基于A*算法航迹规划过程中建立open表和close表,其中open表用于记录可行当时没有被采用的次优航迹点,close表用于存放已扩展的代价值最小的航迹点。在航迹点扩展过程中,也从open表中找出代价值最小的航迹点,进行扩展并进行分析,根据分析结果修改open表和close表,选择最合适的航迹点。

基于A*搜索算法的航迹规划计算简单、易实现,理论上可以实现全局最优解收敛,同时也大大提高了搜索效率。但随着搜索空间的扩展,A*搜索算法的航迹规划计算量也呈指数形式增长,收敛时间变长,尤其在三维航迹规划中常常出现组合爆炸问题,同时航迹规划效果对启发函数有太强依赖性,得出的最优航迹只是在该启发函数下的最优,较好的启发函数是通过试凑方法得出的,在遇到未知障碍物陷阱时可能会导致搜索失败。基于以上A*搜索算法航迹规划特点一般用于二维空间的全局航迹规划。

3.2 Voronoi图法

Voronoi图作为计算几何中非常重要的几何图形之一,被广泛应用许多领域中,具有简单直观的优点。尤其在解决要求无人机离障碍物、威胁源的距离越远越好的问题,Voronoi图方法具有很大的优势。

Voronoi图法基本思想:首先根据无人机飞行环境威胁源和障碍物的分布情况,以威胁源和障碍物的中心点为基础构建出Voronoi图的威胁模型;其次基于Voronoi图计算出加权无向图,并采用最短路径搜索算法如Dijkstra算法搜索初始最短路径。Voronoi图法主要缺点在于存在不可行的尖角,主要是通过三次样条插值法或B样条法优化路径,把路径中尖角剔除生成可行的最优轨迹。

最优轨迹的精度取决于构建Voronoi图的精度,当威胁源或障碍物位置发生变化时,需要再次构建Voronoi图并重新计算。Voronoi图法可用于二维航迹规划任务。

3.3 遗传算法

遗传算法(Genetic Algorithm，GA)是在20世纪70年代初期被Holland等提出的,它是将生物自然选择与基因遗传学机理与计算机结合起来的一种随机搜索算法。

遗传算法基本原理:按照某种编码方式对个体编码,采用选择、交叉和变异三种遗传因子模拟自然界中生物族群遗传变异的现象,以适应度值作为迭代过程中选取父代繁殖、交叉、变异的评价依据,不断向好的方向发展,最终产生最优个体解决问题。

遗传算法具有不易陷入局部最优解,鲁棒性好,不受搜索空间限制,不受假设约束,不要求优化函数具备特殊特性以及隐含并行性等特点。

3.4 粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是由美国心理学家Eberhart博士、电子信息工程师Kennedy博士提出的一种模仿鸟群捕食行为的算法,是一个群体智能模型。

粒子群算法基本原理:首先,随机初始化粒子,之后在粒子迭代时,通过跟踪两个最优值不断的进化自身找到最优解,两个最优值一个是粒子本身找到的最优解,另一种是全局粒子的最优解。该算法类似遗传算法,也是一种采用迭代的方法不断优化的算法。

粒子群算法的优点在于简单容易实现、通用性较强、搜索能力全面,缺点在于容易陷入局部最优解、对参数的要求比较高。

3.5 蚁群算法

蚁群算法(Ant Colony Algorithm，ACA)是1991年由意大利学者M. Dorigo等提出的一种新兴的启发式搜索算法。该算法也是一种模拟算法,源于对自然界蚂蚁觅食时最短路径行为的研究。

蚁群算法基本原理:首先网格图中信息素矩阵初始化,蚂蚁根据状态转移规则,形成一条从起始点到目标点的可行航迹,计算各蚂蚁航迹的目标函数得出最优航迹,然后根据目标函数和一定的信息素调整规则对网格图中各点的信息素进行调整,经过数次迭代产生全局最优航迹。

蚁群算法是一种很好的通用型算法,具有很好的鲁棒性和全局并行计算能力,缺点在于搜索时间长,收敛后期易陷入局部最优。

4 方法分析

本文综合考虑国内外学者研究航迹规划算法经验的基础上,针对两种类型算法特点,对不同算法的分析如下:

1) 不确定型搜索算法是有方向性的自适应搜索,在适应度函数的驱使下,通过各种引导信息,如遗传算法的交叉、变异,粒子群算法的速度和位置更新等手段,每次信息引导过程中的操作产生新个体,从而不断扩大搜索范围,不断向目标方向逐步优化,最终达到近似最优解。因此,算法搜索范围广,易找到全局最优解。不确定型搜索算法具有不受搜索空间限制,不受假设约束,不要求优化函数具备特殊特性以及隐含并行性等特点,因此,遗传算法通用性和鲁棒性强。

2) 相比确定型搜索算法,不确定型搜索算法在具有这些优秀能力的同时也存在一些问题,如影响寻优效率的初始种群质量问题等。

因此,对无人机航迹规划问题可采用两种算法结合的方式进行改进,例如通过A*结合遗传算法,在遗传算法的基础上,采用稀疏A*算法搜索新航迹点的方法,产生初始种群进而提高航迹规划寻优性能。稀疏A*算法由于计算比较简单、易实现,通过结合约束条件随机选取航迹点的方式缩小了搜索空间,提高了搜索效率,减少搜索时间。同时,由于稀疏A*算法仅需要为遗传算法提供初始种群,不需要得到最优航迹,所以大大降低了稀疏A*算法对启发函数的依赖性,提高了算法的性能。

5 结语

无人机航迹规划有多种算法,既有适于小范围的规划算法,可在无人机上进行动态修改;又有适于大范围的规划算法,可在已知信息下求得全局最优解;既能进行人为的智能规划,又能在一定范围内进行模型的自动求解。应在具体问题具体分析基础上,发展高效的无人机航迹规划方法。

随着无人机所要执行的任务越来越复杂,加上环境的不确定性,对航迹规划的要求也将越来越高。未知威胁信息环境下的实时航迹规划将是未来研究的重点,高效的全局搜索方法和局部搜索方法混合使用将是无人机航迹规划的一种趋势。

[1] Zhonghua Hu, Min Zhao, Min Yao. Cooperative attack path planning for unmanned air vehicles Swarm based On grid model and bi-level programming[J]. Journal of Information & Compumdonal Science,2011,8(4):671-679.

[2] J. F. Gilmore. Autonomous vehicle planning analysis methodology[C]//The Proceeding of American Control Conference, Kluwer. Boston, MA,1991.

[3] C. Zheng, M. ding, C Zhou. Real-time route planning for unmanned air vehicle with an evolutionary algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence,2003,17(1):63-81.

[4] S. A. Bortoff. Path planning for UAVs[C]//the Proceedings of the American Control Conference, Chicago, USA,2000:364-368.

[5] 雷兴明,邢昌风,吴玲,等.基于分布式约束优化的多平台导弹协同航路规划[J].电子学报,2012,40(10):2068-2072.

[6] 张同法,于雷,鲁艺.多架无人机协同作战的路径规划[J].火力与指挥控制,2009,34(2):143-145.

[7] 马培蓓,纪军.3种多导弹航迹规划算法的比较[J].电光与控制,2010,17(10):28-32.

[8] 张同法,于雷,鲁艺.多架无人机协同作战的路径规划[J].火力与指挥控制,2009,34(2):143-145.

[9] W Zhang, Z Xing, G Wang, et al. Distributed stochastic search and distributed breakout: properties, comparison and applications to constrains optimization problems in sensor networks[J]. Artificial Intelligence,2005,161(1-2):55-87.

[10] 胡中华,赵敏.无人机任务规划系统研究及发展[J].航天电子对抗,2009,25(4):49-52.

Application of Intelligent Optimization Algorithm in UAV Path Planning

LEI Lei

(Navy Equipment Research Institute, Beijing 100073)

Intelligent optimization algorithm has the characteristics of high computational efficiency and abaptability. By analyzing the intelligent optimization algorithm in the UAV route planning, the UAV route planning model is researched. And the restrictions of UAV trajectory planning are proposed. This paper describes several trajectory planning algorithms applied and researched at home and abroad. And the development trend of UAV flight path planning algorithms is prospected.

UAV, route planning, intelligent optimization algorithm

2016年8月13日,

2016年9月29日

雷蕾,女,硕士研究生,工程师，研究方向:软件工程。

TP391

10.3969/j.issn.1672-9730.2017.02.009