李泓波，白劲波，程顺，杨高明，黄少伟

（1.肇庆学院计算机学院软件学院，肇庆 526061；2.肇庆学院经济管理学院，肇庆 526061；3.安徽理工大学计算机科学与工程学院，淮南　232001）

航迹规划研究趋势分析

李泓波1，白劲波2，程顺1，杨高明3，黄少伟1

（1.肇庆学院计算机学院软件学院，肇庆 526061；2.肇庆学院经济管理学院，肇庆 526061；3.安徽理工大学计算机科学与工程学院，淮南232001）

0　引言

我国拥有三百多万平方公里的海洋国土，长达一万八千公里的海岸线。如果将岛屿也计算在内，则我国海岸线长度达到三万两千多公里［1］。在海空协同条件下，基于突然性和隐蔽性等多方面的考虑，为飞行器提供自适应飞行提供支持的航迹规划问题已经成为学术界研究的热点问题。

1　航迹规划算法分类

航迹规划研究经历了几十年的发展历程。上世纪六十年代，航迹规划主要采用纯数学的微积分方法进行研究。在其后的几十年中，航迹规划问题历经了基于机器人技术、自主机动机器人技术等几个阶段。

发展至今，航迹规划算法已经十分丰富，大致可以分为两大类：一类是纯数学的方法，典型的如参数优化法、能量状态法、牛顿法、穷举法，动态规划方法、整数规划、梯度法以及奇异摄动法等［8］。这类算法的缺点是计算量大，计算时间长，而且在约束条件比较多时很难或不能获得最优航迹解。另一类是启发式方法，典型的如遗传算法、神经网络、模拟退火算法、蚁群算法、粒子群算法等［8］。相比较而言，由于具有许多优良的特性，第二类算法越来越受到研究者的重视，并且这类算法也已广泛应用于航迹规划实践中［8-15］。

2　启发式航迹规划算法比较分析

在启发式航迹规划算法中，前述几种算法各有优缺点。

从优良特性方面来说，遗传算法具有较好的鲁棒性，变异机制使其能及时跳出局部最优解，对于目标函数没有严格要求；蚁群算法具有良好的并行性，对目标函数也没有严格的约束要求，无需设定前提假设；神经网络算法也具有良好的并行性，不易出现不符实际情况的规划结果；模拟退火算法最大优势在于对于解空间形状无约束，对于目标函数无需满足光滑、最优解唯一等要求；粒子群算法具有较好的实时性，可以获得全局最优解。

从存在的缺点方面来说，遗传算法的取得满意解往往需要进行多代进化，时间成本较大，并且由于遗传变异的振荡现象的存在，收敛速度有时会很慢；蚁群算法由于理论研究相对滞后，信息素挥发率等参数的设定带有试验性性质，往往会限入局部最优；神经网络算法计算开销较大，不易满足实时性要求；模拟退火算法虽然从理论上来说可以获得全局最优解，但往往需要较长的时间成本；粒子群算法需要设定的参数虽然较少，但设定的学习因子等参数也带有试验性性质。

3　启发式航迹规划算法的新发展

从前述分析来看，几种启发式算法各有千秋，适应范围存在较大差异。为克服现有算法的不足，目前研究者的主要方法是引入新机制、新技术与已有算法进行混合，提出新算法。

例如，为克服遗传算法效率不高、遗传算子不好选择等缺点，学者们引入了协同进化航迹规划算法。协同进化航迹规划算法既保持了遗传算法的优点，又通过种间斗争提高了算法效率。基于协同进化的航迹规划算法，比较典型的有多飞行器协调航迹规划方法CCRP算法（Coevolutionary Coordinative Route Planner），该方法快速有效，可用于机上实时规划系统中。该方法的一个主要特点是不同飞行器的“潜在航迹”个体形成自己的子种群 （相对于所有飞行器的全部航迹个体形成的种群而言），而且只在各自的子种群内部进化。飞行器间的协调与合作由个体适应函数的定义来反映。CCRP设计了一种有效的规划环境表示方法，当战场环境发生变化时可以及时更新环境信息，同时还可以有效地利用地形高程数据，使生成的航迹能够有效地进行地形回避和威胁回避［9］。

目前，混合算法研究保持着强大势头，量子遗传算法，量子粒子群、竞争粒子群、病毒粒子群、模拟退火、A*等航迹规划混合算法相继被提出［16-20］。虽然不断有新的混合算法被提出，但这些算法尚不完善，存在着一些局限性。例如，CCRP等算法在实时性和鲁棒性等方面尚有较大的改进空间。

4　研究趋势分析

从航迹规划算法来看，当前的研究还主要集中在单机航迹规划算法上。考虑到目前面临的严峻的周边局势，为打破岛链封锁，我国迫切需要多机协同航迹规划研究，特别是协同突防等领域的多机协同航迹规划研究。

多机的协同突防较之单机的突防在协同感应、协同干扰、协同攻击等许多方面都具有优势。例如：在协同感应方面，单机上的无源雷达只能提供目标的方位角信息，而多机（三架或三架以上的飞机）则可以通过协同感应（如使用三角测量法对目标进行测量）准确地获取目标的位置信息。在协同干扰方面，单机只能干扰敌方部分雷达辐射面，而多机协同飞行路线和干扰信号则能够干扰敌方雷达的整个辐射面。在协同攻击方面，单机的生存率和攻击成功率都比较低，而多机则可以通过协调行动而大幅度地提高生存率和攻击成功率。

目前，虽然对多机协同规划算法有所涉及，但研究数量相对较少，且远未达到实际应用水平。因此，为应对我国万里海疆上存在着的客观的和潜在的威胁、保护海上石油等自然资源的开发、促进祖国统一，充分展开多机协同航迹规划研究，特别是掠海突防等多机协同航迹规划研究将是未来研究的新方向和新热点。

5　结语

航迹规划算法先后经历了基于数学的纯数学方法和基于人工智能的启发式两大阶段。启发式航迹规划算法不断得到发展和完善，融合多种技术的新一代启发式算法——混合航迹规划算法正在蓬勃发展。依据前述分析，多机协同航迹规划将是未来的研究方向。

［1］杜朝平.岛链对中国海军的影响有多大［J］.中国海军，2004（5）：37-40.

［2］王羽纶.冲破太平洋三大岛链［J］.大科技，2007（6）：42-44.

［3］李杰.捆绑中国的“岛链”［J］.现代船舶，2001（7）：35-37.

［4］李济然.美暗布“第一岛链预警带”［J］.当代军事文摘，2006（7）：35-37.

［5］李泉.美国旧“岛链战略”指向新目标［J］.社会观察，2012（8）：36-37.

［6］海盾.三重岛链做长缨 妄想缚住中国龙——中国周边的美国航母基地［J］.舰载武器，2004（10）：44-45.

［7］于开金，李光所，曹永恒.岛链浅析［J］.船舶，2006（5）：13-15.

［8］屈耀红.小型无人机航迹规划及组合导航关键技术研究［D］.西北工业大学博士论文，2006.

［9］郑昌文，丁明跃，周成平，等.一种飞行器在线航迹重规划算法［J］.华中科技大学学报（自然科学版），2003（2）：90-92，113.

［10］M.B.Pellazar.Vehicle route planning with constraints using genetic algorithms［C］.Proceedings of the IEEE 1994 National Aerospace and Electronic Conference，1994：111-119.

［11］王栋.低空突防航迹规划、航迹控制的工程实现［D］.南京航空航天大学博士论文，1999.

［12］李春华.一种三维航迹快速搜索方法［J］.宇航学报，2002（3）：13-17.

［13］Robert J Szczerba.Robust algorithm for real-time route planning［J］.IEEE Transactions on Aerospace and Electronic Systems，2000 （3）：869-878.

［14］胡昱，高金源.应用模糊变权的启发式搜索进行飞行轨迹优化［J］.飞行力学，1998（2）：46-50.

［15］Scott A.Bortoff.Path-planning for unmanned air vehicles［C］.Proceedings of the American Control Conference，2000：364-368.

［16］李婷，张金生，王仕成，等.量子粒子群算法在地磁匹配航迹规划中的应用［J］.电光与控制，2015（7）：43-47.

［17］吴天爱，吴云玉，别晓峰.采用病毒粒子群优化算法的飞行器航迹规划［J］.电光与控制，2014（8）：102-105.

［18］严浙平，邓超，孙海涛.竞争粒子群算法及其在UUV航迹规划中的应用［J］.北京理工大学学报，2014（8）：813-818.

［19］王瑞，白晓涛，等.基于A*算法的无人机跟踪目标的航迹规划［J］.计算机仿真，2015（1）：153-156.

［20］张玉广，谢文俊，赵晓林.基于改进粒子群算法的无人作战飞机航迹规划［J］.现代计算机（专业版），2015（3）：14-18.

Route Planning；Research Trend

Research Trend Analysis of Route Planning
LI Hong-bo1，BAI Jin-bo2，CHENG Shui1，YANG Gao-ming3，HUANG Shao-wei1

（1.School of Computer/School of Software，Zhaoqing University，Zhaoqing 526161；
2.College of Economics&Management，Zhaoqing University，Zhaoqing 526161；3.College of Computer Science and Engineering，Anhui University of Science&Technology，Huainan 232001）

安徽省高校自然科学基金（No.KJ2014A061）、安徽省博士后基金（No.2014B021）、中国民航信息技术科研基地开放课题基金（No.CAAC-ITRB-201404）、创新强校专项基金（No.504-20000112）、基于物联网技术的信息化协同中心（No.CQ2014013）

1007-1423（2015）31-0049-03

10.3969/j.issn.1007-1423.2015.31.013

李泓波（1971-），男，辽宁法库人，博士，讲师，研究方向为社会计算、数据挖掘等

白劲波（1971-），女，博士，副教授，研究领域为群体智能等，E-mail：hljbjb@126.com

程顺（1968-），男，博士，副教授，研究方向为自动化控制、大数据等

杨高明（1974-），男，博士，副教授，研究方向为隐私保护、机器学习等

黄少伟（1979-），男，博士，副教授，研究方向为数据挖掘、移动电子商务等

2015-09-29

2015-10-20

航迹规划是指在一定约束条件下，寻找运动体从初始点到目标点满足某种性能指标最优的运动轨迹。在对现有航迹规划算法进行分类、比较和阐释其新近研究动向的基础上，结合我国面临的实际情况，分析航迹规划研究的趋势和方向。

航迹规划；研究趋势

Route planning is pointed in a certain constraint conditions，looks for body moving optimal trajectory from the initial point to the target point to meet a certain performance index.On the basis of classifying and comparing of the existing route planning algorithms，and interpreting the new status of them，combining the actual situation that China is facing，analyzes the research trends of route planning.