2.1 传统经典算法
近年来常用于航迹规划的传统经典算法有Dijkstra算法、 人工势场法(APF：Artificial Potential Field)和模拟退火算法(SAA: Simulated Annealing Algorithm)。Dijkstra算法是图论中求解最短路径的经典算法, 适用于每条边的权数为非负的情况, 能得到从指定顶点到其他任意顶点的最短路径。使用Dijkstra算法进行航迹规划, 构建的赋权图的顶点代表航迹点, 赋权图的边代表所有可行航迹, Dijkstra算法的作用就是在这些可行航迹里找到最优航迹。Dijkstra算法实现简单, 但其运算时间和所用内存与搜索空间中节点个数平方成正比, 在大范围高维空间中搜索时间长, 对内存要求也很高, 因此多用于二维静态航迹规划[12,13] 。由于航迹规划空间范围大, 对于Dijkstra算法在航迹规划中的应用, 如何选取有效航迹点, 减少航迹点数量, 缩短规划时间是问题的关键。文献[12] 在Voronoi图的基础上使用Dijkstra算法寻找最优航迹, 将威胁看作一个点, 选取各威胁点之间连线的中垂线的交点为航迹点。这种方法能保证航迹最大化避开各个威胁, 安全性高, 但航迹较长。并且没有考虑无人机最大转弯角约束, 航迹不一定可飞。文献[13] 在可视图的基础上使用Dijkstra算法寻找最短航迹, 将多边形障碍的各个顶点看作航迹点, 并建立转弯角约束机制。这种方法得到的航迹短, 满足无人机最大转弯角约束, 但由于航迹贴近障碍物, 安全性较低。此外, 可视图不能表达物体运动的方向性约束的缺陷导致Dijkstra算法在搜索时可能找不到路径。虽然Dijkstra算法多用于二维航迹规划, 但也有学者将其应用于三维航迹规划。文献[14] 将飞行空间映射到由若干个四面体组成的三维Delaunay三角网中, 四面体的顶点对应威胁的位置, 四面体内切球的中心作为航迹点, 所有相邻四面体内切球中心点的连线构成一个三维网络, 这个三维网络就是所有可行航迹。然后用Dijkstra算法在这个三维网络上寻找最短航迹。最后用人工势场法对初始航迹进行优化, 获得平滑可飞的航迹。该方法与Voronoi图法类似, 规划出的航迹能最大化避开威胁, 安全性高, 但航迹相对较长。目前使用Dijkstra算法进行航迹规划多是利用Voronoi图、 概率地图或可视图描述规划环境, 然后在此基础上利用Dijkstra算法寻找最短航迹, 但得到的航迹若安全性高则航迹长, 若航迹短则安全性低, 没有在航迹长度与安全性之间寻找到一个好的平衡。
人工势场法是一种模拟电势场分布的规划方法, 任务区域内的目标点产生引力场, 威胁源产生斥力场, 无人机在引力和斥力的共同作用下向目标点运动。传统人工势场法定义如下。
航迹点X的引力势函数和斥力势函数分别为
(3)
(4)
其中Katt和Krep分别为引力和斥力增益系数, 且均为正常数； ρ(X,XG)为航迹点X与目标点XG之间的距离； ρ(X,XO)为航迹点X与威胁源XO之间的距离； ρO为威胁源最大影响距离。
无人机在X处受到的引力和斥力分别是相应势函数的负梯度
Fatt=- Uatt(X)=-Kattρ(X,XG)(5)
Frep=- (6)
总势场力为目标点产生的引力和各个威胁源产生的斥力的矢量和
Ftotal=Fatt+∑Frep(7)
人工势场法的优点是算法简明、 实时性好、 规划速度快, 在局部规划和实时规划领域应用广泛。缺点是当无人机离目标点比较远, Fatt≫Frep时, 合力方向更趋近目标点方向, 无人机可能会进入威胁区；当目标点附近有威胁源时, 斥力将会非常大, 而引力相对较小, 无人机将很难到达目标点；在复杂环境中, 容易产生局部极小值, 使算法停滞或震动；在障碍物附近有抖动现象, 在狭窄通道间频繁摆动；在动态环境下规划效果减弱；计算势场负梯度的方法因为没有优化变量, 将航迹规划问题转换成了非优化问题, 因此缺乏评价指标衡量航迹的优劣, 势场的建立直接决定了航迹的质量, 相同的环境下, 不同的势场形式也可能得到不同的航迹。针对该问题, 学者们结合无人机航迹规划的特点提出了多种改进方法。文献[15] 在斥力势函数中加入无人机与目标点的距离, 减小斥力, 改善障碍物在目标附近时, 目标不可达的问题。设置引导点为无人机提供方向随机的势场力, 解决局部极小值和震荡问题。文献[16] 在人工势场法搜索陷入威胁区时, 构造惩罚势函数替代斥力势函数, 并使用模拟退火算法取代虚拟力引导的方法搜索逃离位置, 有效避免了局部极小值和抖动现象, 得到的航迹能成功避开威胁, 但增大了计算量, 降低了人工势场法的实时性。文献[17] 通过引入相对速度斥力势场和斥力增益模糊控制器实现人工势场法的动态避障, 避免局部极小值。文献[18] 通过增加高度调节引力势函数以增强人工势场法在三维航迹规划中对高度的控制, 同时引入飞行器的动力学约束条件, 使航迹更具可飞性, 并改善了人工势场法的局部极小值、 障碍物附近抖动、 狭窄通道间频繁摆动等缺点。然而文献[15-18] 中均未衡量航迹优劣的评价指标, 对此文献[19] 引入附加控制力作为优化变量, 通过优化出适当的附加控制力, 使无人机在满足各种物理约束的条件下, 规划出的航迹可使代价指标最优, 降低了势场建立的任意性对航迹结果的影响。但文献[19] 在考虑无人机动力学模型时将无人机看作质点, 与实际动力学模型有一定差异。总之, 对于极小值等问题, 前人提出的各种改进方法都在一定程度上弥补甚至消除了这些缺陷, 但对于障碍物附近抖动、 狭窄通道间频繁摆动这一缺陷的改善效果还有待提高。
模拟退火算法是基于蒙特卡罗迭代求解法的一种启发式随机搜索算法。它模拟固体物质的退火过程, 在某一初始温度下, 伴随温度控制参数按照降温函数不断下降, 结合概率的突跳特性在解空间中随机寻找目标函数的全局最优解, 即能概率性地跳出局部最优解并最终趋于全局最优解。退火过程由冷却进度表(Cooling Schedule)控制, 包括温度控制参数的初值t及其衰减因子Δ t、 每个t值时的迭代次数和终止条件。模拟退火算法的优点是算法求得的解与初始解状态无关, 具有渐近收敛性, 是一种以概率1收敛于全局最优解的全局优化算法。缺点是解的质量依赖于当前解产生新解的变换方法和冷却进度表的设计。在航迹规划中, 模拟退火算法的一个解代表一条航迹, 目标函数则是代价函数, 常用于求解二维航迹规划中的TSP问题[20] , 但该算法多数没有考虑无人机的机动性能约束, 得到的航迹可飞性不高。模拟退火算法也可与易陷入局部最优解的算法相结合帮助其跳出局部最优找到全局最优解, 如遗传模拟退火算法[21] , 在交叉和变异过程中使用Metropolis准则判断是否接受新解, 当然, 这会增大原算法的计算量。
2.2 现代智能算法
相较于传统经典算法, 现代智能算法的应用更为广泛。在航迹规划中常用的现代智能算法有A*算法、 遗传算法(GA：Genetic Algorithm)、 蚁群优化(ACO：Ant Colony Optimization)算法和粒子群优化(PSO：Particle Swarm Optimization)算法。
A*算法是一种智能启发式搜索算法, 它将搜索空间表示为网格的形式, 以网格的中心点或顶点作为航迹点, 通过搜索邻域内代价函数值最小的航迹点, 从起始点逐步搜索到目标点, 最后逆向回溯当前节点的父节点生成最优航迹, 其中待扩展航迹节点存放在OPEN表中, 已扩展节点存放在CLOSE表中。代价函数的表达式如下所示
f(x)=g(x)+h(x)(8)
其中g(x)表示从起始点到当前节点的实际代价, h(x)称为启发函数, 表示从当前节点到目标点的估算代价, 常用的启发函数可选用欧氏距离、 曼哈顿距离、 对角线距离等。启发函数是A*算法的核心, 它能在搜索效率和最优解之间权衡。若h(x)小于从当前节点到目标点的实际代价, 则搜索得到最优路径, 但这时搜索节点增多, 搜索效率降低；若h(x)一直等于从当前节点到目标点的实际代价, 此时A*严格按照最优路径搜索, 搜索效率最高；若h(x)大于从当前节点到目标点的实际代价, 则搜索结果可能不是最优路径, 但搜索效率会提高。此外, OPEN表的维护方式也会影响A*算法的搜索效率, 当路径很长时, 这种影响会更明显。总之, 启发函数的选择决定了A*算法是否能找到最优解, OPEN表的维护方式和搜索节点数量决定了A*算法的运行速度。随着搜索空间增大, A*算法的计算量会呈指数增长, 导致规划时间过长, 一般用于静态航迹规划。在航迹规划中, 如何提高A*算法的运行速度并得到最优航迹是学者们重点考虑的问题。文献[7] 采用结构体式最小二叉堆和三层嵌套的二叉堆技术分别维护管理OPEN表和CLOSE表, 相比较于传统的数组式最小二叉堆维护OPEN表和单向链表管理CLOSE表的方式, 提高了最优节点的提取速度, 克服了数组二叉堆的容量可能导致OPEN表溢出的问题, 有效解决了动态二叉树易出现的极度不平衡问题, 保证了节点查找的高效率, 较大幅度提高了A*算法的规划效率。文献[22] 提出使用2.5维网格模型描述三维规划空间, 每个网格点包含经度、 纬度和高程信息, 此方法计算效率要远大于三维网格划分方式。文献[23] 将三维航迹规划分解为二维规划和高度规划, 使用动态时间规整(DTW: Dynamic Time Warping)距离作为A*算法的启发函数进行二维规划, 再由二维航迹结合高程数字地图, 利用粒子沉降法赋予每个航迹点高度信息, 生成三维航迹。这种方法有效地将三维空间的搜索节点删减至二维, 大大减少了搜索节点数量, 缩短了规划时间。使用DTW距离作为启发函数得到的航迹也要优于常用的欧氏距离、 曼哈顿距离和对角线距离, 但仍不是最优航迹。由于航迹规划问题的复杂性, 虽然学者们通过各种改进方法提高了A*算法的搜索效率, 但仍没有找到值恒等于从当前节点到目标点真实代价的启发函数, 实现A*算法的高效最优搜索。
