智能航迹规划算法研究现状与展望

谢凯利，杨海涛，谢海平

(航天工程大学， 北京 101416)

航迹规划是指在给定的约束条件下，基于某种性能指标求取运动物体从初始点到目标点的最优运动轨迹[1]。60年代，航迹规划的研究主要基于数学理论，经过几十年的发展，航迹规划算法已十分丰富，并逐步应用于无人机、导弹、机器人等领域[2-6]。目前，对航迹规划的研究主要由规划环境建模和优化搜索两部分组成。

在规划环境建模上，由于实际的空间环境比较复杂，为降低求解问题的规模，通常根据几何学原理，按照特定的规则对规划空间进行结构划分，常用的划分方法包括单元分解法、路标图法、势场法等。针对航迹规划存在约束条件多、复杂性强、时效性高、规划领域大、难以直接求解等特征，近年来国内外学者提出了许多不同的规划搜索方法[7]，大多数是转化为状态空间的路径搜索问题，利用搜索算法获得最优解。按照规划策略，可将航迹规划算法分为传统经典算法和智能优化算法。Dijkstra算法、人工势场法等传统算法已经发展成熟，对于小规模以及简单的空间环境，在获取最优航迹方面具有明显优势。但当空间环境规模增大时，传统算法的时间呈指数倍增长，而智能优化算法在提高航迹搜索效率方面有着较好表现。其中，遗传算法[8]、模拟退火算法[9]、粒子群算法[10]、神经网络算法[11]等，是航迹规划技术中较为常用的一些智能算法，对解决实际规划问题具有重要意义。

下面将从传统经典算法和智能规划算法两方面，对现有航迹规划算法进行综述，同时对未来航迹算法的研究重点和发展方向进行展望。

1 传统经典算法

传统的航迹规划算法有可视图法、自由空间法、栅格法、人工势场法、梯度方法、Dijkstra算法、模拟退火算法等，本节主要对以Dijkstra算法为代表的图搜索算法、人工势场法、模拟退火算法这几种常用的搜索算法进行分析[12]。

1.1 Dijkstra算法

Dijkstra算法[13]于1959年由狄克斯特拉提出，其核心是解决有权图中固定点之间的最短路径问题，在搜索过程中，处理边权为正的情况。采用贪心思想将有权图中起始顶点与各个顶点的距离保存在数组d[i]中，其中i代表顶点，从起始点开始，向周围节点进行遍历，选择与起点距离最短且没有被扩展过的顶点，将其保存在集合T中，以此循环，直至遍历到终点，其中集合T中的顶点为单源最短路径点。

Dijkstra算法进行航迹规划，将航迹规划问题转化为有权图求最短路径问题，其中有权图的顶点和边代表航迹点和可行航迹。Dijkstra算法在简单环境空间下获取最短路径的效率较高，由于工程应用中飞行器的规划区域较大，算法扩展节点数量增多，导致搜索时间增加，规划效率较低，因此在实际应用中需要对Dijkstra航迹规划算法进行改进[14-16]。文献[14]改进Dijkstra航迹规划算法，基于人工势场法建立新的威胁模型，在工程应用中，减少算法搜索时间，降低内存的占有率。文献[15]基于voronoi方法对威胁源建模，获得的航迹能够安全的躲避威胁物，采用Dijkstra算法搜索最优航迹。文献[16]Dijkstra算法基于可视图方法将多边形中的各个阻碍点表示为航迹点，加入航迹转角约束，得到最短航迹点，但规划的航迹紧贴障碍物，容易发生碰撞。

由上述可知，目前Dijkstra算法的应用多是在二维静态环境中，利用voronoi图、可视图或者是与其他航迹算法结合建立环境模型，在此基础上搜索最优航迹，但得到的航迹在安全性和有效性很难达到平衡。

1.2 人工势场法

人工势场法[17]的基本思想是将运动体所处的工作环境抽象为一个虚拟力场空间(如图1所示)，把障碍物和威胁看成排斥力，目标点当作吸引力，通过合力控制物体的运动，有效规避行进过程中障碍物的阻碍，使得规划出来的路径是平滑、安全的。

图1 人工势场航迹规划二维图

人工势场法作为传统算法，研究和发展较为成熟，算法简单、规划时间短，广泛应用于局部静态航迹规划。在实际应用中，规划环境复杂，目标点周围有障碍物出现的情况下，飞行器会受到明显的斥力作用，此时无法到达目标点；当飞行器在动态环境规划时，障碍物和目标点发生运动，容易造成局部震荡或与障碍物发生碰撞的现象。对此许多学者对人工势场算法进行研究并提出多种改进方法，文献[18]提出一种混沌理论的人工势场算法，解决航迹规划过程中，容易陷入局部较小值和在目标点徘徊的情况。文献[19]加入最大转角约束，解决了传统人工势场法存在的局部最小值和震荡问题。文献[20]在威胁指标确定的情况下，引入相对速度斥力势场和斥力增益模糊控制器，有效地解决人工势场法的动态规避障碍物和陷入局部极小值的问题。

针对上述所述，国内外学者提出的多种改进方法，可以有效的解决人工势场算法容易陷入局部最小的缺陷，而对于动态规划环境下，局部震荡和与障碍物发生碰撞的改善效果明显不足，是其未来研究的方向。

1.3 模拟退火算法

模拟退火算法[21](Simulated Annealing,SA)是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法，应用于规模较大的组合优化问题。基于固体物质的退火原理，设定较高的初始温度，随着温度的降低，为避免陷入局部最优，结合概率突跳特性，进行随机搜索，寻找全局最优解。

在模拟的过程中，设置初始温度T和初始解x，将温度T作为控制参数，对当前解采用metropolis准测，不断进行“产生新解—判断—接受或舍弃”迭代，当参数T逐渐减少直至零时，算法结束，当前即为航迹最优解。通过冷却进度表控制T和每个T值的迭代次数、产生新解过程的计算增量Δt。

模拟退火算法在航迹搜索过程中，不依赖于初始状态，具有通用性，应用广泛，同时具有较好的全局收敛性，适合求解多数组合优化问题，例如二维航迹规划中的TSP问题[22]。但算法对当前解的求解方法和冷却进度表的依赖性较强，在实际应用中，问题规模过大，容易影响最优解的质量。目前对模拟退火算法的主要研究和应用，将模拟退火算法与容易陷入局部最优的航迹算法结合，即克服了局部最优的不足又提高算法搜索效率和精度[23]。

1.4 算法小结

传统的航迹规划算法发展成熟，采用一定的搜索技术可以获得最优路径，但是，在路径搜索效率和航迹优化等方面存在不足，需要进一步完善。传统算法间的对比分析如表1所示。

表1 传统算法间的对比分析

2 智能优化算法

本节将智能航迹规划算法分为两类；一类是确定型搜索算法，如确定性计算方法的最小化原理和确定性状态的空间搜索方法，包括以A*算法为代表的图搜索算法和动态规划法等；另一类为随机型搜索算法，如遗传算法、蚁群算法和神经网络算法等，以随机搜索为特征的优化算法。智能航迹规划算法分类如图2所示。

图2 智能航迹规划算法分类框图

2.1 确定型搜索算法

2.1.1A*算法

A*算法[24]在20世纪60年代由Hart等提出，以Dijkstra算法为基础，采用启发式思想，引入当前结点的估价函数，对扩展节点的代价值进行评估和比较，选择代价值最小的节点作为最优节点进行下一步扩展，直到搜索到终点。A*算法搜索时使用OPEN和CLOSE表进实现节点的扩展和最优节点的选取，其中，扩展节点按照估价值大小的顺序保存在OPEN表中，CLOSE表存储估价值最小的扩展节点，这些节点的连线组成最优航迹。

其中，当前结点的估价函数定义为:

f*(n)=g*(n)+h*(n)

(1)

式中：f*(n)为起始节点到目标节点的估计代价；g*(n)为起始节点到当前节点n的实际代价；h*(n)为当前节点n到目标点的估计代价。h*(n)作为启发函数可选用欧氏距离、曼哈顿距离、对角线距离三种公式计算，常用曼哈顿距离公式计算h*(n)，有:

h*(n)=D*(abs(n.x-goal.x)+abs(n.y-goal.y))

(2)

式中：D表示移动代价；abs表示绝对值；x、y分别表示横坐标和纵坐标。

A*算法相比于其他算法来说简单，代码容易实现，其中航迹最优解的获取以及算法搜索效率的提高，与h*(n)的选择、OPEN表的维护有着直接的关系以及规划空间的规模，适应于二维静态规划环境。提高搜索算法效率的同时获取最优航迹，是当前A*算法在航迹规划中主要的研究方向[25-28]。文献[25]将动态加权A*算法应用于无人机航迹规划，减少了航迹代价，提高了算法的航行速度。文献[26]对广义搜索A*算法增加约束条件，将改进的A*算法应用到动态规划环境中，解决了A*算法搜索空间大的复杂问题，具有较强的工程实用性。文献[27]结合无人机的性能和任务约束改进的A*算法，同时对OPEN表的管理方式进行优化解决三维环境下空间搜索节点数量增多和内存消耗较大的问题，提高了算法搜索的时间。

由于规划环境的复杂性，学者们通过各种改进的方法提高了A*算法的搜索效率，但选择合适的启发函数，平衡算法搜索效率和搜索精度，仍然是A*算法重点考虑的问题。

2.1.2D*算法

D*算法[29]是动态的A*算法，由Stentz[29]提出，是火星探测器的寻路算法。D*算法的核心思想：在Dijkstra和A*算法的基础上，从目标G向起始点进行反向搜索，建立一个“路径场”，搜索过程中将节点信息保存在OPEN和CLOSE中。当路径环境发生变化或者路径上的节点遇到阻碍时，通过建立的“路径场”信息，避免二次规划，减少运算量，提高搜索效率。文献[30]提出有向D*算法，在提高搜索方面引入导向函数以控制单次搜索的节点搜索范围。

D*算法进行路径寻优时，能够很好的感知到当前节点或者临近节点的信息变化，但D*算法不能很好解决环境中较远节点信息发生改变的状况。

2.2 随机型搜索算法

2.2.1基于采样算法

快速扩展随机树(Rapidly-Exploring Random Tree，RRT)算法[31]，于1998年由S.M.LaValle首次提出，如图3所示为RRT算法的发展时间轴。RRT算法是典型的基于随机采样的算法，在搜索空间中快速扩张，生成一颗连接根节点和目标点的搜索树。其中路径起点做为扩展树的根节点，采用随机采样方法进行叶子节点的扩展，直到终点或者终点所在的区域包含在叶子节点中。

图3 RRT的发展时间轴框图

该算法与其他算法相比，计算简单，能够结合当前环境状况进行快速有效地搜索，其搜索速率在空间维度较高的情况下尤为明显，广泛应用于不具备完整系统的航迹规划[32]。同时RRT算法具有较为明显的缺点，使得后续算法的应用受到限制：没有对航迹代价进行综合考虑，造成较大的损耗代价；节点选择的随机性太强，不能够得出最优或者接近最优的航迹。

面对上述算法存在的不足，国内外专家对算法进行通过大量的研究和改进，在简单的规划环境下，保证了算法在实际应用中的可行性和高效性[33-36]。其中，文献[33]对算法节点的采样和扩展方式进行改进和优化，解决算法节点随机性较强而无法获取最优航迹的问题，减少了扩展节点数量，提高算法航迹搜索的效率；文献[34]针对算法节点随机性强、不能够得到最优航迹等缺点，通过改变随机树的生长方向的角度对RRT算法进行改进和优化，降低了规划时间，规划航迹接近最优；文献[35]结合A*算法的启发思想，改变RRT中扩展节点的方式，建立满足航迹规划的约束条件，减少巡航时间，降低航迹代价的损耗，易于工程的实现。然而在约束条件较多的复杂规划环境，对RRT算法性能有着更高的要求。

2.2.2遗传算法

1975年，美国John Holland教授基于“物竞天择，适者生存”理论提出遗传算法[37](Genetic Algorithms,GA)，其算法原理基于基因重组和自然进化选择，如图4所示，在航迹搜索过程中，将待求解问题进行编码(基因)，若干基因组成一个染色体，每一个染色体代表一条可行性航迹，通过对染色体进行自然选择、交叉和变异操作得到新的个体，并不断地循环迭代，直到产生最优的个体。

图4 遗传算法原理示意图

遗传算法是当代人工智能科学研究的一个重要分支，遗传算法具有自身迭代的优势，适用全局航迹搜索，易与其他算法相结合，鲁棒性强，能够很好地应用到三维航迹规划空间。对该算法进行改进是目前研究的热点，通过引入量子，改进适应度函数参数和遗传算子等方面，弥补算法规划后期收敛速度慢、容易陷入局部最优等不足。文献[38]进入差分进化变异策略，增加算法变异的多样性，改进的算法在全局搜索后期加快了收敛速度，抑制了算法的早熟，防止陷入局部最优；文献[39]提出改进量子遗传算法，针对量子遗传算法初始种群的单一性，引入关于概率划分的小生境协同进化策略，并对各种群采用动态量子旋转角，并借鉴狼群分配原则对种群进行更新，改进后的算法提高了算法的精度和稳定性。

改进后的遗传算法能够有效平衡全局搜索精度和搜索速度，但单一的遗传算法应用于实时航迹规划中效果不佳，需要与其他的智能航迹优化算法进行结合，如文献[40]针对 GA 算法早熟问题改进适应度函数，构造一种随进化代数动态调整的非线性适应度函数，提高算法的收敛速度，同时与稀疏A*算法结合，应用于三维在线航迹规划问题，具有一定的工程意义。

2.2.3蚁群算法

蚁群算法[41]基于蚂蚁觅食的群体思想，是群体智能算法的一种，1992年Marco Dorigo在他的学术论文中第一次提出了该算法，并用该算法解决了实际问题。

算法思想是基于蚂蚁觅食方式，在寻找食物的过程中，蚂蚁会释放一种称为信息素的分泌物，所经过的地方会留下前继蚂蚁的信息素，后继蚂蚁通过信息素获取路径信息，并通过状态转移概率以大概率选择其中信息素浓度较高的一条路径，同时也会留下自身的信息素，使得该条路径上的信息素浓度逐渐加深，信息素的浓度和路径长度成反比，最终信息素浓度较高的路径为最优路径。该算法采用正反馈机制，加快搜索速度，在分享和寻找信息素之间能够达到很好的动态平衡，具有较强的抗干扰性、全局计算能力。

与其他搜索算法相比，蚁群算法的收敛速度相对较慢，搜索空间较大时容易出现滞留现象，容易陷入局部最优。针对上述算法的缺点，许多学者针对算法的不足进行改进。文献[42]通过对参数进行自适应调节，使蚁群的搜索能力和个体之间的交互能力有所提高，解决传统算法存在易陷入局部最优的问题。文献[43]引入伪随机状态转移规则对基本蚁群算法进行改进，克服基本蚁群算法容易陷入局部最优和迭代停滞的现象。文献[44]设计一种分层模型，使改进的蚁群算法更能够应用到复杂的三维航迹空间，并对相关的算法模型进行优化，提高三维空间下航迹规划的适应性和安全性。

目前，对蚁群算法的改进大多针对算法陷入局部最优问题，对算法的搜索精度优化的研究较少。同时利用蚁群算法的鲁棒性强的优点，与其他智能算法相融合也是其未来主要的研究方向。

2.2.4神经网络算法

神经网络算法作为目前应用较为广泛的一种人工智能算法，其雏形由心理学家W.MeCulloch和数学家W.Pitts[45]提出，通过模仿人类大脑的神经结构处理问题的方式建立算法的计算模型。人工神经网络作为非线性动态系统，引入能量函数的概念，其在航迹规划过程中，通过不断调整神经网络中的各项权值，使能量达到一个稳定的状态，基于此获取航迹最优解。

人工神经网络算法在结构、实现原理和功能各方面都模拟生物神经网络，因此具有较强的并行处理能力和自主学习能力，容错性和鲁棒性较强，神经网络作为重要学科，引起众多学者的广泛关注[46-48]。目前，对神经网络的研究还在探索阶段，在实际应用中，航迹搜索环境的复杂化和空间区域范围广，使得选取合适的权值较为困难，增加了规划时间。

2.3 算法小结

通过分析上述两种类型算法的适用性和优缺点可知(如表2所示)，随机型搜索算法具有方向性自适应搜索的优点。在适应度函数的推动下，依据各种引导信息，如遗传算法的交叉、变异等，产生新的个体，不断扩大搜索范围，向目标方向逐步优化，易找到全局最优解。

表2 智能优化算法间对比分析

随机型搜索算法与确定型搜索算法相比，搜索空间不受限制，假设条件不受约束，对于优化函数不要求其特殊性，并且可以并行性，但在搜索精度和规划时间等方面不如确定型搜索算法。

3 总结与展望

现代高技术信息化的发展对航迹规划技术的要求不断提高，静态环境下的航迹规划算法已经无法满足复杂作战任务和多样化规划环境的需求，例如：城市环境中建筑物的复杂性和多样性、战场环境所面临的敌方防御系统和未知环境下障碍物的动态变化等。这些更为复杂和多约束规划环境下，提高航迹规划技术的实时性，是航迹规划算法未来发展的主要方向，其算法的改进和创新也是未来研究的重点与难点，下面对其发展趋势进行深入分析。

1) 实时航迹规划技术的发展不仅对计算机的性能和硬性条件有要求，也对算法在时间和空间复杂度方面提出更高的需求。航迹规划技术实时性的提高，目前主要考虑航迹规划过程中的突发威胁，引入知识集成和模型预测控制对复杂环境中的威胁物进行处理。未来，为满足实时航迹规划技术，航迹规划算法在求解优化问题方面需要具备更高的搜索效率和较短的规划时间，是智能航迹规划算法未来的发展趋势。

2) 智能航迹规划算法存在规划时间长、范围广的缺点，因此不断完善算法自身的缺陷，提高算法的搜索效率和准确度，是目前算法改进的主要目的。然而在实际应用中，面对交叉学科的新问题时，单一的规划算法存在局限性，无法得出问题的最优解。因此，未来航迹规划算法的研究方向趋向于将两种或多种算法结合。同时，多种算法的融合需要考虑其算法在工程中的应用效果，需要学者对融合算法的性能进一步研究。

3) 同时，原有的航迹规划智能算法的不足依旧存在，例如：RRT算法不适应高纬度、复杂化的战场环境，神经网络算法训练结果的准确性和可靠性无法得到保证，遗传算法、蚁群算法的收敛速度慢等缺点，在2014年Mirjalili 等人提出的一种新的智能化航迹算法-灰狼优化算法，具有参数少、容易实现和收敛性能高等优点，弥补了其他智能算法的部分缺陷，与该算法进行融合在性能上也有明显的优势。因此，新的智能航迹算法的提出是必要的，也是未来航迹规划算法研究的难点和发展方向。

4 结论

航迹规划算法的发展，在机器人系统、无人驾驶系统和多飞行器系统等导航方面的发展具有一定的价值。人工智能技术在航迹规划领域的发展、规划环境的复杂性和约束条件的多样性，对智能化航迹算法有着更高的要求。在航迹规划算法发展的基础上不断改进和优化，将航迹规划智能算法的研究重点放在实时在线航迹规划技术和算法创新与改进方面，是广大学者主要研究的方向。