2024年5月9日发(作者：荀聪慧)

综述

《自动化技术与应用》2019年第38卷第6期

Survey

旋翼无人机智能航迹规划研究综述*

皇甫淑云,唐守锋,童敏明,张宝山,孙海波

(中国矿业大学信息与控制工程学院，江苏徐州221008）

摘要:无人机在军事和民用领域的广泛应用,使其成为全球范围的研究热点。智能航迹规划是旋翼无人机自主导航飞行的关键技

术保障,有着重大的应用前景和研究意义。本文对旋翼无人机智能航迹规划进行了研究综述，在旋翼无人机航迹规划模型

的基础上，分析了传统经典算法、现代智能算法等规划算法，指出了其优点与不足并讨论了智能算法的改进算法，最后展望

了无人机智能航迹规划的发展趋势。

关键词:旋翼无人机;飞行控制;航迹规划;智能算法

中图分类号：TP312文献标志码:A文章编号:1003-7241(2019)06-0001-05

ResearchonIntelligentTrackPlanningofRotorcraftUAV

HUANGFUShu-yun,TANGShou-feng,TONGMin-ming,ZHANGBao-shan,SUNHai-bo

(ChinaUniversityofMiningandTechnology,Xuzhou221008China)

Abstract:Thewiigenttrackplanningisakeytech-

nologyguaranteeoftheautonomousnavigationofrotorunmannedaerialvehicle,whichhassignificantapplicationpros-

paper,theresearchontheintelligenttrackplanningofrotorcraftUAVisreviewed.

Basedontherotorcraftdronetrackplanningmodel,thetraditionalclassicalalgorithm,modernintelligentalgorithmand

otherplanningalgorithmsareanalyzed,andtheadvantagesanddisadvantagesarepointedoutandtheimprovedintelli-

y,thedevelopmenttrendofintelligenttrackplanningforunmannedaerialvehicles

isprospected.

Keywords:rotorcraftUAV;flightcontrol;trackplanning;intelligentalgorithm

1引言

无人机(UnmannedAerialVehicle,UAV)是在20

世纪初作为靶机训练而出现的一种新型空中飞行器

[1]

。

近几十年来,随着科技与经济水平的快速发展,国内外学

者对无人机的导航飞行控制,自主着陆等方面取得了巨

大的成果,包括在无人机侦查、探测、救援等军事活动,摄

影测量以及农场作业等实际操作中,无人机因其成本相

对低廉、操作灵活、不惧伤亡等特点,在军事和民用领域

得到了广泛的应用。

智能航迹规划

[2]

（在舰艇、自主战车、机器人等领域一

般称为路径规划）是指在一些特定的约束条件下,为无人

机规划出满足某些性能指标的从起始点到目标点的最优

飞行航迹。本文将介绍旋翼无人机的航迹规划模型,在

此模型的基础上介绍航迹规划的多种智能算法,其中包

括传统经典算法、现代智能算法,并且针对不同算法的优

缺点进行阐述,并讨论相应的改进措施。

2旋翼无人机航迹规划问题建模

近年来,旋翼无人机受到人们的广泛关注。与固定

翼无人机相比,旋翼无人机具有垂直起降和点定悬停的

突出功能特点,适合在狭小的空间以及多障碍物的复杂

未知环境下飞行

[3]

。

旋翼无人机的航迹规划算法要考虑无人机的航迹倾

角、航向角变化和三维位置,并以前两者的导数为对应的

航迹控制量

[4]

。建立笛卡尔坐标系,以目标点为原点O,取

XOY平面为水平面,取Z轴垂直于水平面向上,并做以下

假设：1)忽略地面效应；2)将UAV看作质点,不考虑姿态

TechniquesofAutomation&Applications

*基金项目:国家重点研发计划(编号2016YFC0801800）

收稿日期:2018-05-07

1

《自动化技术与应用》2019年第38卷第6期

综述

大,航迹规划任务量大,需要大量的实验数据作为依据。

Survey

变化；3)UAV匀速飞行,控制量只改变UAV的飞行方向

[5]

。

故无人机三维笛卡尔坐标系下的质心运动方程为：

3.2最优控制法

最优控制法(OptimalControlMethod,OCM)是一

种基于控制论的优化算法,该方法用目标函数构造Hamilton

（1）

函数时,要求目标函数二阶可导

[8]

。最优控制法拥有严格

的数学理论基础,可以简化两端固定的问题,可用向量求

解,可以一端固定,但是约束条件严格,鲁棒性较差,容易

式(1)中,S

n

=[x

n

,y

n

,z

n

,θ

n

,ψ

n

],n

T

N为无人机n的

出现死锁,航迹规划时间长,仅适用于简单的地形

[9]

。

状态向量,U

n

=[u

θn

,u

ψn

]

T

为控制量；(x

n

,y

n

,z

n

)为无人机n

的坐标；V(n)表示飞行速度；θ

n

和ψ

n

分别为航迹倾角和

航向角,对应的控制量分别为u

θn

和u

ψn

,如图1所示。

3.3单元格法

单元格法(CellDecompositionMethods,CDM)是

将空间划分为简单的单元,判断单元之间是否连通以寻

找可行的路径。按照划分形式,可以分为：网格法和四叉

树法

[10]

。按照单元格划分粒度,单元格法又分为：精确划

分、近似划分和自适应划分

[11]

。栅格分解法

[12]

和单元格法

的原理相同,将航迹规划的空间分解为多个栅格,并确定

障碍栅格和自由栅格,利用相关的搜索算法在自由栅格

上寻找无碰撞的规划路径。

3.4

图1

规避约束：

（2）

式中,R

se

为无人机间最小安全距离。

概率路标图算法

概率路标图(ProbabilisticRoadMap,PRM)算法

[13]

无人机航迹倾角和航向角定义

为了飞行的安全,在任意时刻,无人机间需满足碰撞

在1994年被提出,广泛应用于高维位姿空间中。概率路

标图是由路标法演变而来,路标法的示意图如图2所示,

其中黑色不规则区域为障碍物。算法分为两个阶段,预

处理阶段和查询阶段。预处理阶段是在位姿空间中基于

概率的随机取样,将通过检测的采样点添加到路标图中；

查询则是将初始点和目标点分别连接到路标图中,并利

用搜索算法找到两者之间的可行路径。概率路标图算法

简单实用,但算法的完备性较差,在狭窄的通路中采样率

极低。针对上述问题,提出了MAPRM算法

[14]

、OBPRM

算法

[15]

,另有分阶段混合采样这一策略思想

[16]

。

3传统经典算法

航迹规划算法是实现旋翼无人机自主导航飞行的技

术关键。按照规划决策,将航迹规划算法划分为传统经

典算法和现代智能算法

[6]

。传统经典算法包括统计归纳

法、最优控制法、单元格法、路标法、动态规划法、导数相

关法等。

3.1统计归纳算法

统计归纳算法(StatisticalInductionAlgorithm,

SIA)是基于概率论的全局优化算法。在某一阶段的优化

过程中,将指导向前搜索的信息按照先前的处理状态分

为两部分

[7]

：I)前面已经处理过的状态点的函数值情况；II)

事先已经假定或者已经知道的函数本身所具有的一些性

质。SIA根据具体问题中所给出的信息II,确定出如何从

I中提取有用信息来指导下一步的搜索。SIA具有并行

性,能根据优化问题灵活选取不同的统计项目,适合解决

工程上复杂的组合优化问题(如TSP问题),但其计算量

2

TechniquesofAutomation&Applications

图2路标法示意图

综

3.5动态规划法

动态规划法(DynamicProgramming,DP)是一种基

于几何学的枚举搜索算法,与D*算法同属于确定型搜索。

对于给定的输入集,动态规划算法的搜索行为可重复、可

预见,模型简单,能够保证全局最优解,但规划时间长,计

算量大,适合小范围的航迹规划

[17]

。

述

《自动化技术与应用》2019年第38卷第6期

Survey

应用流程如图3所示。

遗传算法的鲁棒性强,能够并行处理,搜索不需要连

续、可导的目标函数,通过模拟生物基因的复制、交叉和

变异解决航迹规划的优化问题,且不容易陷入局部最优

解,但优化时间长,需要的已知经验参数多,收敛过快,不

适合实时的航迹规划

[23]

。

4.3粒子群算法

粒子群优化算法(ParticleSwarmOptimization,

4现代智能算法

现代智能算法包括启发式寻优搜索算法(如A*算

法）、遗传算法、人工势场算法、模拟退火算法、神经网络

算法、蚁群算法、粒子群算法等,以上算法具有一个共同

优点——启发式寻优。

PSO)是对鸟群觅食行为模拟的全局优化进化算法

[24,25]

。

粒子群算法没有遗传算法的“交叉”、“变异”操作,从随机

解出发,通过迭代寻求最优解,并追随当前最优解寻求全

局最优。粒子群算法性能高效、形式简单,不需要调整很

多参数,适合于机载应用,但算法早熟收敛,容易陷入局

部最优

[26]

。粒子群优化算法还可以用于解决连续空间

函数优化、离散空间组合优化、训练神经网络、图像压缩

等问题

[27]

。

4.1A*算法

A*(A-Star)算法是一种求解最短路径最有效的经典

启发式搜索算法

[18]

。A*算法具有可接纳性、一致性,计算

简单,与一般的广度、深度有效搜索方法比较,搜索效率

更高,但由于搜索空间大,算法收敛时间长,在航迹规划

过程中出现组合爆炸问题

[19]

。近年来,一种将地形平滑技

术用于路径搜索的改进A*算法被提出

[20]

,使路径处理只

需满足飞行器过载限制。一种将三维航迹规划分为二维

平面规划和高度规划的改进A*算法被提出

[21]

,缩短了航

迹规划时间。

4.4蚁群算法

蚁群算法(AntColonyOptimization,ACO)是一种

在图中模拟蚂蚁觅食行为来寻找优化路径的随机型搜索

算法

[28]

,模拟蚁群从巢穴到食物地的觅食活动。蚁群算法

的本质是一种正反馈机制：当一条路径上的蚂蚁越多,蚂

蚁选择该路径的概率越大。蚁群算法主要包括状态转换

规则和生物信息激素修改准则,其鲁棒性好,并行性强,

适合分布式并行计算,但算法搜索时间长,易陷入停滞和

局部最优解

[29]

。求解旅行商（TSP）问题时,基本蚁群算法

完整的代码步骤为

[30]

：

（1）代码初始化,并将蚂蚁随机分布到的城市添加

进禁忌表中。

4.2遗传算法

遗传算法(GeneticAlgorithm,GA)是一种将遗传学

与进化论结合的随机型搜索方法

[22]

。遗传算法按照“适者

生存、优胜劣汰”的原则,完成遗传编码、设计适应度评价

函数、执行遗传算子和设计系统约束参数等一步步优化

后,输出当前最优值。旋翼无人机航迹规划的遗传算法

图3遗传算法应用流程图

TechniquesofAutomation&Applications

3

《自动化技术与应用》2019年第38卷第6期

综述

略的3个指标为：迭代代数、最优个体适应度差、种群标准

差,其中标准差的计算公式如下：

（3）

其中,sd为标准差,N为种群规模,为x

i

第i个粒子的

适应度值,x为N个粒子适应度的平均值。

Survey

（2）设定结束条件,运行结果不满足结束条件则继

续执行3、4循环。

（3）对蚂蚁k,1≤k≤n（n为蚂蚁总数）：如果本次循

环到达下一城市j,则记录到达下一城市j,否则记录本次

循环路径。

（4）更新信息素。

（5）输出结果,结束程序。

4.5遗传算法、粒子群算法和蚁群算法结合

为提高旋翼飞行器自主导航飞行的效率,根据算法

5结束语

目前,随着旋翼无人机航迹规划的研究发展,各种算

法已相对成熟,被用于实际的自主导航飞行中。每种算

法都有其优缺点：遗传算法不受搜索空间的限制,是一种

高效、并行的全局搜索算法,但不适合实时航迹规划；粒

子群算法易实现、精度高,不需要调整很多参数,但其搜

索精度低,早熟收敛；蚁群算法是一种采用正反馈机制的

新仿生类算法,其寻优性能好,但搜索时间长,容易陷入

局部最优解。因此,未来旋翼无人机航迹规划算法的研

究趋势主要有以下三个方面：（1）算法融合。单一的算法

不能满足无人机复杂的任务需求,根据不同任务需求选

择不同的算法,或将算法进行融合以实现自主飞行,是未

来无人机航迹规划的发展趋势。（2）创新性地提出某种算

法。未来可以在现有算法上进行创新,提出一种新算法,

用于无人机航迹规划任务。（3）多无人机协同航迹规划算

法的研究。国内外学者对于多无人机协同作战可以进行

深入研究,以提高多无人机航迹规划的效率。智能航迹

规划的优劣影响着无人机的飞行性能,以上算法的实现

是未来该领域的研究难点和热点。

各自具有的特点,有些研究者将多种智能算法融合在一

起提出了新的航迹规划算法,实现了算法互补和安全、可

靠的飞行,本小节将3种随机型搜索算法进行融合。

[31]

4.5.1遗传算法与蚁群算法结合

由于旋翼无人机航迹规划的复杂性和特殊性,将蚁

群算法和遗传算法融合在一起形成一种新的算法—遗传

蚁群算法(GA-ACO)

[32]

。GA-ACO算法的第一阶段采

用了遗传算法生成初始信息素来栅格序列分布,第二阶

段采用了蚁群算法在正确信息素指导下准确搜索出最优

解,将遗传算法的快速收敛性和蚁群算法的正反馈机制

有效地结合在一起,实现了算法的优势互补,实现了无人

机安全的飞行。

该算法是在栅格障碍环境下工作的,算法的基本结

构如图4所示。新算法的关键在于转入蚁群算法,即何时

停止遗传算法的迭代过程。另外,利用蚁群算法和遗传

算法也可产生基于性能较好的最大—最小蚁群系统

(Max-MinAntSystem,MMAS)算法

[33]

。

参考文献:

[1]何小九,李彦彬,朱枫,等.国外垂直起降无人机发展现

状及设计制造关键技术[J].飞航导弹,2016(6):22-27.

[2]贾阳阳.飞行器避障与航迹规划研究[D].北京：北京理

工大学,2015.

[3],l,navigationand

collisionavoidanceforanunmannedaerialvehicle[J].Sen-

图4GA-ACO算法结构

sorsandActuatorsA,2013(190):66-76.

[4]张煜,张万鹏,陈璟,等.基于Gauss伪谱法的UCAV对

地攻击武器投放轨迹规划[J].航空学报,2011,32(7):1240-1251.

[5]白瑞光,孙鑫,陈秋双,等.基于Gauss伪谱法的多UAV

协同航迹规划[J].宇航学报,2014,35(9):1022-1029.

[6]任耀庭.基于超声波测距与图像信息融合的旋翼无人机

避障算法研究[D].成都：电子科技大学,2016.

[7]刘志宏,施工,胡永明.一种新的全局优化算法——统计

4.5.2遗传算法与粒子群算法结合

[34]

针对路径规划问题,采用一种基于混沌粒子群和专

用遗传算法的结合方法,提出一种切换优化策略,前期

考虑到粒子群算法对初解质量要求不高的特点,使用混

沌粒子群进行全局搜索；后期利用遗传算法搜索速度快

的特点,使用专用遗传算法进行局部搜索。切换优化策

4

TechniquesofAutomation&Applications

综

归纳算法[J].清华大学学报(自然科学版),2002,42(5):580-583.

[8]otionplanningandautono-

mousobstacleavoidanceforunmannedvehicles[D].Monterey:

NavalPostgraduateSchool,2006.

[9]-dimensionalaircraftterrain-fol-

lowingviareal-timeoptimalcontrol[J].JournalofGuidance,

Control,andDynamics,2007,30(4):1201-1205.

[10]王维平,刘娟.无人飞行器航迹规划方法综述[J].飞行

力学,2010,28(2):6-15.

[11]张瑜.电力巡检多旋翼无人机避障技术研究[D].成都：

电子科技大学,2016.

[12]冯楠.自主移动机器人路径规划的RRT算法研究[D].

大连：大连理工大学,2014.

[13]LKAVRAKI,izedPrepro-

cessingofConfigurationSpaceforFastPathPlanning[C].

[14]WILMARTHS,AMATON,:

Aprobabilisticroadmapplannerwithsamplingonthe

medialaxisofthefreespace[C].IEEEInternationalConfer-

enceonRoboticsandAutomation,1999:1024-1031.

[15]NAMATO,OBAYAZIT,LDALE,CJones,DVallejo.

OBPRM:Anobstacle-basedPRMfor3Dworkspaces[C].Ro-

botics:Thealgorithmicperspective,1998:155-168.

[16]陈家照,张中位,徐福后.改进的概率路径图法[J].计算

机工程与应用,2009(10):54-55.

[17]张莹.动态规划算法综述[J].科技视界,2014(28):

157-158.

[18]许云红,周锐,夏洁,等.无人机自动防撞冲突检测与优

化控制方法[J].学术研究,2014(1):2-5.

[19]薛若宸.无人机飞行控制与航迹规划研究[D].北京：北

京理工大学,2016.

[20]任波,周焘,于雷.基于改进A*算法的飞行器三维航迹

规划算法[J].系统工程与电子技术,2008,30(2):324-326.

[21]刘莉,于成龙,王祝,等.小型无人机快速三维航迹规划

算法[J].系统工程与电子技术,2013,35(12):2521-2526.

[22]周佳,蒋玉明.遗传算法和动态规划综述[J].技术研发,

2009,16(12):18.

[23]辛贵州.无人飞行器航迹规划算法研究[D].哈尔滨：哈

尔滨工程大学,2010.

[24]KENNEDY,J.,EBERHART,leswarm

述

《自动化技术与应用》2019年第38卷第6期

Survey

规划[J].电子设计工程,2013,21(22):36-39.

[27]傅阳光.粒子群优化算法的改进及其在航迹规划中的

应用研究[D].武汉：华中科技大学,2011.

[28]李栋,曹义华,苏媛,等.基于改进蚁群算法的低空突防

航迹规划[J].北京航空航天大学学报,2006,32(3),258-261.

[29]杨丹.蚁群算法的改进及其在航迹规划中的应用研究

[D].哈尔滨:哈尔滨工业大学,2007.

[30]韩攀,陈谋,陈哨东,等.基于改进蚁群算法的无人机航

迹规划[J].吉林大学学报,2013,31(1):66-72.

[31]任子玉.智能车自主避障路径规划研究综述[J].软件导

刊,2017,16(10):209-212.

[32]何娟,涂中英,牛玉刚.一种遗传蚁群算法的机器人路

径规划方法[J].计算机仿真,2010,27(3):170-174.

[33]李晋.基于蚁群算法和遗传算法的机器人路径规划研

究[D].哈尔滨：哈尔滨工业大学,2012.

[34]张超,李擎,董冀媛,等.基于混沌粒子群—专用遗传算

法切换策略的移动机器人路径规划[J].北京科技大学学报,2013

(6):826-830.

optimization[C].inProceedingsofIEEEInternationalCon-

ferenceonNeuralNetworks,1995:1942-1948.

[25]KENNEDY,J.F.,EBERHART,R.C.,SHI,

Intelligence[M].SanFrancisco:MorganKaufmann,2001.

[26]陈攀峰,刘文军,王为.基于粒子群算法的无人机航迹

作者简介:皇甫淑云(1995-),女,硕士研究生,研究方向：飞行器

航迹规划。

TechniquesofAutomation&Applications

5

2024年5月9日发(作者：荀聪慧)

综述

《自动化技术与应用》2019年第38卷第6期

Survey

旋翼无人机智能航迹规划研究综述*

皇甫淑云,唐守锋,童敏明,张宝山,孙海波

(中国矿业大学信息与控制工程学院，江苏徐州221008）

摘要:无人机在军事和民用领域的广泛应用,使其成为全球范围的研究热点。智能航迹规划是旋翼无人机自主导航飞行的关键技

术保障,有着重大的应用前景和研究意义。本文对旋翼无人机智能航迹规划进行了研究综述，在旋翼无人机航迹规划模型

的基础上，分析了传统经典算法、现代智能算法等规划算法，指出了其优点与不足并讨论了智能算法的改进算法，最后展望

了无人机智能航迹规划的发展趋势。

关键词:旋翼无人机;飞行控制;航迹规划;智能算法

中图分类号：TP312文献标志码:A文章编号:1003-7241(2019)06-0001-05

ResearchonIntelligentTrackPlanningofRotorcraftUAV

HUANGFUShu-yun,TANGShou-feng,TONGMin-ming,ZHANGBao-shan,SUNHai-bo

(ChinaUniversityofMiningandTechnology,Xuzhou221008China)

Abstract:Thewiigenttrackplanningisakeytech-

nologyguaranteeoftheautonomousnavigationofrotorunmannedaerialvehicle,whichhassignificantapplicationpros-

paper,theresearchontheintelligenttrackplanningofrotorcraftUAVisreviewed.

Basedontherotorcraftdronetrackplanningmodel,thetraditionalclassicalalgorithm,modernintelligentalgorithmand

otherplanningalgorithmsareanalyzed,andtheadvantagesanddisadvantagesarepointedoutandtheimprovedintelli-

y,thedevelopmenttrendofintelligenttrackplanningforunmannedaerialvehicles

isprospected.

Keywords:rotorcraftUAV;flightcontrol;trackplanning;intelligentalgorithm

1引言

无人机(UnmannedAerialVehicle,UAV)是在20

世纪初作为靶机训练而出现的一种新型空中飞行器

[1]

。

近几十年来,随着科技与经济水平的快速发展,国内外学

者对无人机的导航飞行控制,自主着陆等方面取得了巨

大的成果,包括在无人机侦查、探测、救援等军事活动,摄

影测量以及农场作业等实际操作中,无人机因其成本相

对低廉、操作灵活、不惧伤亡等特点,在军事和民用领域

得到了广泛的应用。

智能航迹规划

[2]

（在舰艇、自主战车、机器人等领域一

般称为路径规划）是指在一些特定的约束条件下,为无人

机规划出满足某些性能指标的从起始点到目标点的最优

飞行航迹。本文将介绍旋翼无人机的航迹规划模型,在

此模型的基础上介绍航迹规划的多种智能算法,其中包

括传统经典算法、现代智能算法,并且针对不同算法的优

缺点进行阐述,并讨论相应的改进措施。

2旋翼无人机航迹规划问题建模

近年来,旋翼无人机受到人们的广泛关注。与固定

翼无人机相比,旋翼无人机具有垂直起降和点定悬停的

突出功能特点,适合在狭小的空间以及多障碍物的复杂

未知环境下飞行

[3]

。

旋翼无人机的航迹规划算法要考虑无人机的航迹倾

角、航向角变化和三维位置,并以前两者的导数为对应的

航迹控制量

[4]

。建立笛卡尔坐标系,以目标点为原点O,取

XOY平面为水平面,取Z轴垂直于水平面向上,并做以下

假设：1)忽略地面效应；2)将UAV看作质点,不考虑姿态

TechniquesofAutomation&Applications

*基金项目:国家重点研发计划(编号2016YFC0801800）

收稿日期:2018-05-07

1

《自动化技术与应用》2019年第38卷第6期

综述

大,航迹规划任务量大,需要大量的实验数据作为依据。

Survey

变化；3)UAV匀速飞行,控制量只改变UAV的飞行方向

[5]

。

故无人机三维笛卡尔坐标系下的质心运动方程为：

3.2最优控制法

最优控制法(OptimalControlMethod,OCM)是一

种基于控制论的优化算法,该方法用目标函数构造Hamilton

（1）

函数时,要求目标函数二阶可导

[8]

。最优控制法拥有严格

的数学理论基础,可以简化两端固定的问题,可用向量求

解,可以一端固定,但是约束条件严格,鲁棒性较差,容易

式(1)中,S

n

=[x

n

,y

n

,z

n

,θ

n

,ψ

n

],n

T

N为无人机n的

出现死锁,航迹规划时间长,仅适用于简单的地形

[9]

。

状态向量,U

n

=[u

θn

,u

ψn

]

T

为控制量；(x

n

,y

n

,z

n

)为无人机n

的坐标；V(n)表示飞行速度；θ

n

和ψ

n

分别为航迹倾角和

航向角,对应的控制量分别为u

θn

和u

ψn

,如图1所示。

3.3单元格法

单元格法(CellDecompositionMethods,CDM)是

将空间划分为简单的单元,判断单元之间是否连通以寻

找可行的路径。按照划分形式,可以分为：网格法和四叉

树法

[10]

。按照单元格划分粒度,单元格法又分为：精确划

分、近似划分和自适应划分

[11]

。栅格分解法

[12]

和单元格法

的原理相同,将航迹规划的空间分解为多个栅格,并确定

障碍栅格和自由栅格,利用相关的搜索算法在自由栅格

上寻找无碰撞的规划路径。

3.4

图1

规避约束：

（2）

式中,R

se

为无人机间最小安全距离。

概率路标图算法

概率路标图(ProbabilisticRoadMap,PRM)算法

[13]

无人机航迹倾角和航向角定义

为了飞行的安全,在任意时刻,无人机间需满足碰撞

在1994年被提出,广泛应用于高维位姿空间中。概率路

标图是由路标法演变而来,路标法的示意图如图2所示,

其中黑色不规则区域为障碍物。算法分为两个阶段,预

处理阶段和查询阶段。预处理阶段是在位姿空间中基于

概率的随机取样,将通过检测的采样点添加到路标图中；

查询则是将初始点和目标点分别连接到路标图中,并利

用搜索算法找到两者之间的可行路径。概率路标图算法

简单实用,但算法的完备性较差,在狭窄的通路中采样率

极低。针对上述问题,提出了MAPRM算法

[14]

、OBPRM

算法

[15]

,另有分阶段混合采样这一策略思想

[16]

。

3传统经典算法

航迹规划算法是实现旋翼无人机自主导航飞行的技

术关键。按照规划决策,将航迹规划算法划分为传统经

典算法和现代智能算法

[6]

。传统经典算法包括统计归纳

法、最优控制法、单元格法、路标法、动态规划法、导数相

关法等。

3.1统计归纳算法

统计归纳算法(StatisticalInductionAlgorithm,

SIA)是基于概率论的全局优化算法。在某一阶段的优化

过程中,将指导向前搜索的信息按照先前的处理状态分

为两部分

[7]

：I)前面已经处理过的状态点的函数值情况；II)

事先已经假定或者已经知道的函数本身所具有的一些性

质。SIA根据具体问题中所给出的信息II,确定出如何从

I中提取有用信息来指导下一步的搜索。SIA具有并行

性,能根据优化问题灵活选取不同的统计项目,适合解决

工程上复杂的组合优化问题(如TSP问题),但其计算量

2

TechniquesofAutomation&Applications

图2路标法示意图

综

3.5动态规划法

动态规划法(DynamicProgramming,DP)是一种基

于几何学的枚举搜索算法,与D*算法同属于确定型搜索。

对于给定的输入集,动态规划算法的搜索行为可重复、可

预见,模型简单,能够保证全局最优解,但规划时间长,计

算量大,适合小范围的航迹规划

[17]

。

述

《自动化技术与应用》2019年第38卷第6期

Survey

应用流程如图3所示。

遗传算法的鲁棒性强,能够并行处理,搜索不需要连

续、可导的目标函数,通过模拟生物基因的复制、交叉和

变异解决航迹规划的优化问题,且不容易陷入局部最优

解,但优化时间长,需要的已知经验参数多,收敛过快,不

适合实时的航迹规划

[23]

。

4.3粒子群算法

粒子群优化算法(ParticleSwarmOptimization,

4现代智能算法

现代智能算法包括启发式寻优搜索算法(如A*算

法）、遗传算法、人工势场算法、模拟退火算法、神经网络

算法、蚁群算法、粒子群算法等,以上算法具有一个共同

优点——启发式寻优。

PSO)是对鸟群觅食行为模拟的全局优化进化算法

[24,25]

。

粒子群算法没有遗传算法的“交叉”、“变异”操作,从随机

解出发,通过迭代寻求最优解,并追随当前最优解寻求全

局最优。粒子群算法性能高效、形式简单,不需要调整很

多参数,适合于机载应用,但算法早熟收敛,容易陷入局

部最优

[26]

。粒子群优化算法还可以用于解决连续空间

函数优化、离散空间组合优化、训练神经网络、图像压缩

等问题

[27]

。

4.1A*算法

A*(A-Star)算法是一种求解最短路径最有效的经典

启发式搜索算法

[18]

。A*算法具有可接纳性、一致性,计算

简单,与一般的广度、深度有效搜索方法比较,搜索效率

更高,但由于搜索空间大,算法收敛时间长,在航迹规划

过程中出现组合爆炸问题

[19]

。近年来,一种将地形平滑技

术用于路径搜索的改进A*算法被提出

[20]

,使路径处理只

需满足飞行器过载限制。一种将三维航迹规划分为二维

平面规划和高度规划的改进A*算法被提出

[21]

,缩短了航

迹规划时间。

4.4蚁群算法

蚁群算法(AntColonyOptimization,ACO)是一种

在图中模拟蚂蚁觅食行为来寻找优化路径的随机型搜索

算法

[28]

,模拟蚁群从巢穴到食物地的觅食活动。蚁群算法

的本质是一种正反馈机制：当一条路径上的蚂蚁越多,蚂

蚁选择该路径的概率越大。蚁群算法主要包括状态转换

规则和生物信息激素修改准则,其鲁棒性好,并行性强,

适合分布式并行计算,但算法搜索时间长,易陷入停滞和

局部最优解

[29]

。求解旅行商（TSP）问题时,基本蚁群算法

完整的代码步骤为

[30]

：

（1）代码初始化,并将蚂蚁随机分布到的城市添加

进禁忌表中。

4.2遗传算法

遗传算法(GeneticAlgorithm,GA)是一种将遗传学

与进化论结合的随机型搜索方法

[22]

。遗传算法按照“适者

生存、优胜劣汰”的原则,完成遗传编码、设计适应度评价

函数、执行遗传算子和设计系统约束参数等一步步优化

后,输出当前最优值。旋翼无人机航迹规划的遗传算法

图3遗传算法应用流程图

TechniquesofAutomation&Applications

3

《自动化技术与应用》2019年第38卷第6期

综述

略的3个指标为：迭代代数、最优个体适应度差、种群标准

差,其中标准差的计算公式如下：

（3）

其中,sd为标准差,N为种群规模,为x

i

第i个粒子的

适应度值,x为N个粒子适应度的平均值。

Survey

（2）设定结束条件,运行结果不满足结束条件则继

续执行3、4循环。

（3）对蚂蚁k,1≤k≤n（n为蚂蚁总数）：如果本次循

环到达下一城市j,则记录到达下一城市j,否则记录本次

循环路径。

（4）更新信息素。

（5）输出结果,结束程序。

4.5遗传算法、粒子群算法和蚁群算法结合

为提高旋翼飞行器自主导航飞行的效率,根据算法

5结束语

目前,随着旋翼无人机航迹规划的研究发展,各种算

法已相对成熟,被用于实际的自主导航飞行中。每种算

法都有其优缺点：遗传算法不受搜索空间的限制,是一种

高效、并行的全局搜索算法,但不适合实时航迹规划；粒

子群算法易实现、精度高,不需要调整很多参数,但其搜

索精度低,早熟收敛；蚁群算法是一种采用正反馈机制的

新仿生类算法,其寻优性能好,但搜索时间长,容易陷入

局部最优解。因此,未来旋翼无人机航迹规划算法的研

究趋势主要有以下三个方面：（1）算法融合。单一的算法

不能满足无人机复杂的任务需求,根据不同任务需求选

择不同的算法,或将算法进行融合以实现自主飞行,是未

来无人机航迹规划的发展趋势。（2）创新性地提出某种算

法。未来可以在现有算法上进行创新,提出一种新算法,

用于无人机航迹规划任务。（3）多无人机协同航迹规划算

法的研究。国内外学者对于多无人机协同作战可以进行

深入研究,以提高多无人机航迹规划的效率。智能航迹

规划的优劣影响着无人机的飞行性能,以上算法的实现

是未来该领域的研究难点和热点。

各自具有的特点,有些研究者将多种智能算法融合在一

起提出了新的航迹规划算法,实现了算法互补和安全、可

靠的飞行,本小节将3种随机型搜索算法进行融合。

[31]

4.5.1遗传算法与蚁群算法结合

由于旋翼无人机航迹规划的复杂性和特殊性,将蚁

群算法和遗传算法融合在一起形成一种新的算法—遗传

蚁群算法(GA-ACO)

[32]

。GA-ACO算法的第一阶段采

用了遗传算法生成初始信息素来栅格序列分布,第二阶

段采用了蚁群算法在正确信息素指导下准确搜索出最优

解,将遗传算法的快速收敛性和蚁群算法的正反馈机制

有效地结合在一起,实现了算法的优势互补,实现了无人

机安全的飞行。

该算法是在栅格障碍环境下工作的,算法的基本结

构如图4所示。新算法的关键在于转入蚁群算法,即何时

停止遗传算法的迭代过程。另外,利用蚁群算法和遗传

算法也可产生基于性能较好的最大—最小蚁群系统

(Max-MinAntSystem,MMAS)算法

[33]

。

参考文献:

[1]何小九,李彦彬,朱枫,等.国外垂直起降无人机发展现

状及设计制造关键技术[J].飞航导弹,2016(6):22-27.

[2]贾阳阳.飞行器避障与航迹规划研究[D].北京：北京理

工大学,2015.

[3],l,navigationand

collisionavoidanceforanunmannedaerialvehicle[J].Sen-

图4GA-ACO算法结构

sorsandActuatorsA,2013(190):66-76.

[4]张煜,张万鹏,陈璟,等.基于Gauss伪谱法的UCAV对

地攻击武器投放轨迹规划[J].航空学报,2011,32(7):1240-1251.

[5]白瑞光,孙鑫,陈秋双,等.基于Gauss伪谱法的多UAV

协同航迹规划[J].宇航学报,2014,35(9):1022-1029.

[6]任耀庭.基于超声波测距与图像信息融合的旋翼无人机

避障算法研究[D].成都：电子科技大学,2016.

[7]刘志宏,施工,胡永明.一种新的全局优化算法——统计

4.5.2遗传算法与粒子群算法结合

[34]

针对路径规划问题,采用一种基于混沌粒子群和专

用遗传算法的结合方法,提出一种切换优化策略,前期

考虑到粒子群算法对初解质量要求不高的特点,使用混

沌粒子群进行全局搜索；后期利用遗传算法搜索速度快

的特点,使用专用遗传算法进行局部搜索。切换优化策

4

TechniquesofAutomation&Applications

综

归纳算法[J].清华大学学报(自然科学版),2002,42(5):580-583.

[8]otionplanningandautono-

mousobstacleavoidanceforunmannedvehicles[D].Monterey:

NavalPostgraduateSchool,2006.

[9]-dimensionalaircraftterrain-fol-

lowingviareal-timeoptimalcontrol[J].JournalofGuidance,

Control,andDynamics,2007,30(4):1201-1205.

[10]王维平,刘娟.无人飞行器航迹规划方法综述[J].飞行

力学,2010,28(2):6-15.

[11]张瑜.电力巡检多旋翼无人机避障技术研究[D].成都：

电子科技大学,2016.

[12]冯楠.自主移动机器人路径规划的RRT算法研究[D].

大连：大连理工大学,2014.

[13]LKAVRAKI,izedPrepro-

cessingofConfigurationSpaceforFastPathPlanning[C].

[14]WILMARTHS,AMATON,:

Aprobabilisticroadmapplannerwithsamplingonthe

medialaxisofthefreespace[C].IEEEInternationalConfer-

enceonRoboticsandAutomation,1999:1024-1031.

[15]NAMATO,OBAYAZIT,LDALE,CJones,DVallejo.

OBPRM:Anobstacle-basedPRMfor3Dworkspaces[C].Ro-

botics:Thealgorithmicperspective,1998:155-168.

[16]陈家照,张中位,徐福后.改进的概率路径图法[J].计算

机工程与应用,2009(10):54-55.

[17]张莹.动态规划算法综述[J].科技视界,2014(28):

157-158.

[18]许云红,周锐,夏洁,等.无人机自动防撞冲突检测与优

化控制方法[J].学术研究,2014(1):2-5.

[19]薛若宸.无人机飞行控制与航迹规划研究[D].北京：北

京理工大学,2016.

[20]任波,周焘,于雷.基于改进A*算法的飞行器三维航迹

规划算法[J].系统工程与电子技术,2008,30(2):324-326.

[21]刘莉,于成龙,王祝,等.小型无人机快速三维航迹规划

算法[J].系统工程与电子技术,2013,35(12):2521-2526.

[22]周佳,蒋玉明.遗传算法和动态规划综述[J].技术研发,

2009,16(12):18.

[23]辛贵州.无人飞行器航迹规划算法研究[D].哈尔滨：哈

尔滨工程大学,2010.

[24]KENNEDY,J.,EBERHART,leswarm

述

《自动化技术与应用》2019年第38卷第6期

Survey

规划[J].电子设计工程,2013,21(22):36-39.

[27]傅阳光.粒子群优化算法的改进及其在航迹规划中的

应用研究[D].武汉：华中科技大学,2011.

[28]李栋,曹义华,苏媛,等.基于改进蚁群算法的低空突防

航迹规划[J].北京航空航天大学学报,2006,32(3),258-261.

[29]杨丹.蚁群算法的改进及其在航迹规划中的应用研究

[D].哈尔滨:哈尔滨工业大学,2007.

[30]韩攀,陈谋,陈哨东,等.基于改进蚁群算法的无人机航

迹规划[J].吉林大学学报,2013,31(1):66-72.

[31]任子玉.智能车自主避障路径规划研究综述[J].软件导

刊,2017,16(10):209-212.

[32]何娟,涂中英,牛玉刚.一种遗传蚁群算法的机器人路

径规划方法[J].计算机仿真,2010,27(3):170-174.

[33]李晋.基于蚁群算法和遗传算法的机器人路径规划研

究[D].哈尔滨：哈尔滨工业大学,2012.

[34]张超,李擎,董冀媛,等.基于混沌粒子群—专用遗传算

法切换策略的移动机器人路径规划[J].北京科技大学学报,2013

(6):826-830.

optimization[C].inProceedingsofIEEEInternationalCon-

ferenceonNeuralNetworks,1995:1942-1948.

[25]KENNEDY,J.F.,EBERHART,R.C.,SHI,

Intelligence[M].SanFrancisco:MorganKaufmann,2001.

[26]陈攀峰,刘文军,王为.基于粒子群算法的无人机航迹

作者简介:皇甫淑云(1995-),女,硕士研究生,研究方向：飞行器

航迹规划。

TechniquesofAutomation&Applications

5