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] 在考虑无人机动力学模型时将无人机看作质点, 与实际动力学模型有一定差异。总之, 对于极小值等问题, 前人提出的各种改进方法都在一定程度上弥补甚至消除了这些缺陷, 但对于障碍物附近抖动、 狭窄通道间频繁摆动这一缺陷的改善效果还有待提高。
