中国指挥与控制学会会刊 
1 概述
随着“斯巴达侦察兵”等水面无人艇(Unmanned Surface Vessel,简称USV)正式装备美海军,同时在2003年的伊拉克战争中被划到战区进行相关实验以来,水面无人艇已经被公认必将在未来的海战中扮演重要的角色,可执行扫雷、反潜、电子战等多种作战任务。因此,深入研究水面无人艇技术,尽早装备我军,对提高战斗力有重要意义。智能化是水面无人艇研发的重要方向之一,智能化意味着在复杂的海洋环境中无人艇可以和外部海洋环境进行自主交互,自适应海洋环境的变化,这种交互的一个重要方面就体现在无人艇的轨迹规划上。
路径规划是这一领域发展的基本阶段。此时,无人艇简化为一个质点,没有运动学和动力学特性。这一阶段,无人艇的外形和尺寸也不对路径规划产生影响,规划路径最短、消耗资源最少、耗时最短是规划的目标和限制条件。基于路线图的规划方法、基于网格的搜索算法以及各种具有优化目标的进化算法和启发式算法,均属于这一阶段的规划方法。然而,通过这种方法规划出的路径,与无人艇的实际路径之间存在着较大差距。在实际海上任务中,无人艇很难执行这些路径。在路径规划中加入无人艇运动学限制,催生了第二个阶段——轨迹规划。这一阶段,无人艇不作为质点出现,而是具有合理假设的外形和尺寸。位置的一阶导数包括平动速度、旋转角速度,甚至二阶导数包括平动加速度、角加速度等要素,限制了生成的可行轨迹集的规模。路径的安全性、消耗少、平滑和可执行性成为运动规划的新目标,吸引大量学者展开了对动态路径生成、速度窗口、路径平滑等课题的研究。速度障碍法、动态窗口法以及各种曲线平滑算法被提出来。第三个阶段是运动规划,考虑规划的路径是否可以被控制系统执行。此时,NGC(Navigation-Guidance-Control)系统的概念受到了关注。导航系统提供无人艇的位置、航向、航速信息,制导模块规划出可行的航迹,控制系统按照一定的算法跟踪所规划的算法。这一阶段,研究的重点是轨迹跟踪算法和稳定的航行控制方法。
本文在前人资料的基础上,重点研究了无人艇的全局路径规划算法。规划算法实质是,在给定的起始点和目的地之间设计一条轨迹,使得无人艇安全平稳到达目的地。路径规划算法分为全局规划算法和局部规划算法,二者没有本质上的区别,局部规划的目标是局部的子目的地而全局规划的目标是最终的目的地。全局路径规划利用静态环境数据,进行大范围离线路径规划,由于传感器精度和动态环境限制,只提供宏观的路径指导,即一系列离散的子路径的组合。在进行路径规划之前,需要根据使用的方法对环境进行建模。一般有两种方式:1)基于可视图法或单元分解的方法,将环境地图转化为行车路线图或者栅格。在此基础上,利用搜索算法得到最优路径;2)基于“场”的概念,将环境地图转化为势能场或者向量场,在建立的场中进行轨迹规划。
2 基于可视图法和单元分解的搜索规划
2.1 环境建模方法
2.1.1 基于道路图的可视图法
可视图法对环境变化的适应性较弱。起始点和终点改变,或者障碍物改变,都会导致可视点的变化,导致全局路径需要完全重新规划。文献[6]针对算法不适应动态环境的缺陷,设计了一种基于相交判断的改进算法,但是不能处理凹形障碍物的情况。可视图法的另一个缺陷是实际路径巡航中一旦产生位置误差,极易发生碰撞。可视图法的计算复杂度依赖于工作空间总的障碍物,当环境中存在密集障碍物,后续的搜索算法很可能找不到最优路径甚至搜索失败。文献[7]利用膨胀法,将膨胀轮廓的顶点作为连接的顶点,降低了碰撞危险。同时仅考虑以起终点连线为对角线的矩形内部的障碍物,降低了算法的计算规模,但忽略矩形外部障碍物也可能导致只能得到次优路径。文献[8-9]明确了可视图法中内可视点和外可视点的概念,通过模拟现实人寻路的思想,引入凸点法提高了可视图法的计算效率。
2.1.2 环境地图的单元分解方法
栅格法是由W.E.Howden于1968年提出,他在进行路径规划时采用栅格表示地图,规划空间被分解为一系列具有二值信息的网络单元。每个网格的规格参考规划对象的尺寸以及单步规划步长来确定。栅格地图中存在自由栅格和障碍栅格,障碍栅格是环境中障碍物经过膨胀或者腐蚀处理后填充到栅格中形成的,自由栅格是可以自由行走的栅格。栅格位置可以使用序号法和直角坐标法两种方法来表示[13]。
运用最优搜索算法进行搜索,可以得到从起始点到目的地的无碰路径。栅格法描述简单且易于实现,可应用于不同的算法,同时可以表示不同的障碍物,实现大规模的并行处理[14-15]。同时栅格法存在以下缺陷:1)分辨率难以确定。分辨率过高,增加搜索算法的运算量;分辨率过小会导致路径规划结果粗糙,在极端情况下会造成本来分开的障碍物连通,最终得不到有效路径。2)栅格在被选入路径后需要加入禁忌表,即该栅格不能再次被选入路径中,这样当遇到一些U型障碍物等复杂环境会迅速地生成有效路径。文献[16]参考可视图法和人工势场思想,提出了基于有效顶点的栅格编码方法,使得算法计算规模不再依赖于分辨率的设置,只与障碍物的个数相关;文献[17]给出了四叉树的方法,四叉树只需要记录叶子节点的编码而不用记录中间的节点和层次关系,减少了储存空间,但是计算过程引入了邻域查找算法,增加了算法的复杂性。文献[18]设计了一种扇形栅格,改进后的栅格法更加适合处理传感器数据。
2.2 启发式路径搜索算法
启发式算法一般用来解决“NP-Hard”问题,借助某种直观判断或试探的方法,以求得问题的次优解或以一定概率求得最优解。在规划环境稀疏时,使用深度优先搜索(DFS)、广度优先搜索(BFS)、Dijkstra[19]算法等精确算法,可以在离散的路径中准确高效地找到全局最短路径。而随着规划环境的规模和复杂度增大,求解全局最优路径的计算量会急剧增加。此时精确算法难以在要求的时间内得到满意解,启发式算法牺牲求解质量换取求解速度,可以以一定概率在较短时间内得到最优解。用在路径规划领域的启发式算法,主要包括A*算法及其变种算法[20⇓⇓⇓⇓⇓⇓⇓-28]、快速进行法(FM)[22]、随机路图法(PRM)[29]、快速扩展随机树法(RRT)[30⇓⇓⇓⇓⇓⇓⇓⇓-39]等。
A*算法是比较经典的启发式寻路算法,是在Dijkstra算法基础演化而来。Dijkstra算法在搜索下一个路径点时,仅仅考虑了该路径点到起点的路径最短,直到遍历整个路径网络,属于盲目、遍历式的搜索。A*算法加入了目标点到当前路径点的距离估价代价,综合考虑从起点到当前路径点的距离G以及经过该路径点到达终点的距离H,以此来决定搜索的方向。A*算法中最关键部分是当前路径点到终点的距离估价代价函数H的设置,由于当前路径点到终点的路径是未知的,因此该距离估计是有误差的。当H小于实际距离时,A*算法可以通过搜索找到问题最优解,但是会搜索较多无用的节点,H为0时类似于BPS算法;当H大于实际距离时,A*算法可以快速找到可行解,但有可能不是最优解。A*算法的路径寻优能力和收敛速度是相互矛盾的。A*算法主要用于静态栅格地图的最优路径搜索,其改进主要集中在两个方面:提高搜索速度以及提高规划路径的可行性。目前提高搜索速度的方法有:使用曼哈顿距离和对角线距离作为代价函数H,引入决胜法来处理评价值相等的情况,以采样的方式进行跳跃点搜索,引入权值到距离估价函数,双向搜索等提高了搜索速度。
部分学者给出了很多代价函数H的设置方法,使用动态加权方法,为代价函数H设置一个权值,当不断接近目标位置时,权值也不断降低,这样路径实际代价的重要性相对提高,启发式函数的不确定性相对降低。还有部分专家学者引入带宽搜索的概念,限定了评价值的取值范围,当搜索点的评价值超出该取值范围,那么该搜索点一定不在最优路径上,这样加快了算法的搜索速度。文献[20]设计了双向搜索的A*算法,通过计算正向搜索点的G值、反向搜索点的G值以及两个方向搜索点的距离估值H的和,可以确定最佳的搜索方向,直至两个方向的搜索在中途相遇,即评价值不再增加。A*搜索算法一般和栅格法结合运用,常见的A*算法变体在四宫格、九宫格或者十六宫格内进行搜索,路径的平滑度和使用的搜索宫格的格子数量相关,格子越多,搜索出来的路径就越平滑。文献[27]提出了Theta*算法,和原始的A*算法中顶点的父节点必须是相邻顶点不同,它允许顶点的父节点是任意顶点,从而摆脱了搜索宫格对路线平滑度的限制。Theta*算法需要完成大量的顶点是否相互可视的检查工作,降低了搜索效率,后来部分学者又提出了Lazy Theta*算法,减少了顶点相互可视的检查次数。由于动态地图环境建模导致节点发生变化,A*算法一般用于静态地图的搜索。基于A*算法的改进动态搜索算法D*算法[24]可以适应动态变化的地图,进一步地终身规划A*算法可以重复利用之前的A*计算来产生新的路径,但是两种算法需要一定的计算储存空间的支持。
快速扩展随机树法应用也较为广泛,是一种常见的用于运动规划的方法,由LaValle在1998年提出[30-31]。其基本原理是在工作空间中存在一个起始点,先在工作空间中随机选定一个点并连接起始点和随机点,若连线与障碍物不相交,那么该连线确定一个可行方向,机动平台可以沿着该方向前进一步,到达一个新的位置点。那么,这个新的位置点和初始点以及其连线构成了一棵简单的树。在这棵树的基础上,继续在工作空间中随机选定一个点,然后在已经确定的树上找到距离该随机点最近的点并将二者连线。若连线不与障碍物相交,那么该连线确定了下一步的可行方向,机动平台沿着可行方向到达新的位置,该位置可以被添加到已经确定的树上,以此类推,直到目标点被添加到树上。
随机性和运算的复杂性是制约该算法应用的两个主要问题。工作空间中选点的随机性导致相同环境下规划结果的不同。该算法是概率完备的,但是由于选点是随机的,在起点和目标点之间确定一条可行路线的时间是不确定的,这给算法的实际应用带来困难。影响RRT算法性能的主要因素有:随机节点个数,树扩展的轨迹段长度,随机节点产生的概率分布扩展树的个数。已经有专家学者对算法进行改进,形成了一些改进版本的RRT算法。文献[32-33]提出了带有目标偏向思想的RRT算法,通过随机函数加参数来生成局部目标点,以一定概率用目标点作为牵引点,解决原始RRT算法中扩展节点方式过于平均、随机性大的问题。文献[34]提出了双向搜索的改进RRT算法,分别以初始点和目标点作为根节点进行扩展,直到两棵树连接在一起,提高了搜索效率。文献[35]和文献[36]分别通过限制采样概率和采样节点提高工作空间中采点的质量。文献[37]将RRT算法和Parti-game方法结合起来,在例如障碍物附件等需要的地方细化搜索,以便能更快速地给出规划方案。文献[38]则将Theta*算法和RRT算法结合,使用路径优化和智能采样相结合的方式来加快RRT算法的收敛速率。文献[39]则将A*算法和RRT算法相结合,在第一层使用A*算法进行大尺度的规划,然后在第二层使用RRT算法进行小尺度规划,将启发式思想引入到RRT算法中改善规划的效果。
2.3 智能搜索算法
智能算法是在自然规律的启发下,根据其原理模拟求解问题的算法,也称元启发式算法。元启发式算法结合了启发式算法和随机算法,其解决问题的思路一般是:1)生成一组候选解;2)设置适应性函数计算这些候选解的适应度;3)根据适应度阈值保留符合条件的候选解;4)对保留的候选解进行操作以生成一组新的候选解。这方面内容有很多,如禁忌搜索算法、模拟退火算法、人工免疫算法、人工神经网络、遗传算法、蚁群算法、粒子群算法、人工鱼群、人工蜂群等。由于具有全局寻优能力,这些智能算法被广泛用于路径规划领域。
遗传算法是应用最广泛的智能搜索算法,算法将候选解看作染色体,对染色体进行交叉、变异、选择等操作,经过有限次的遗传得到符合条件的染色体,即问题的解。粒子群算法[40]同遗传算法类似,初始化粒子群随机解,通过迭代寻找最优值,但是没有交叉变异等操作,而是在解空间中追寻最优解。同时,粒子群算法由于不像遗传染色体那样粒子之间共享信息,只有全局最优粒子发布信息给其他粒子,因此收敛速度要优于遗传算法。
遗传算法的优点是具有强大的自组织学习能力、容错能力以及隐含的并行性,遗传进程以适应度为导向,对问题的依赖性较弱[41]。同时,遗传算法存在运算规模大、前期易陷入局部极小,后期收敛速度慢等问题[42]。遗传算法的改进一般着眼于种群初始化、染色体编码方式、适应度函数结构、遗传算子结构等四个方面。刘佳男[43]使用浮点数编码代替常用的二进制编码,提高了运算精度和效率。针对传统遗传算法随机初始化种群导致路径质量不高的问题,文献[41]引入势场力的思想为遗传算法初始化种群,文献[43-44]采用了启发式方法降低种群初始化的随机性。文献[45]在种群初始化时,事先将障碍物从规划空间中剔除,提高了算法的全局收敛速度。赵媛[45]根据动静态路径规划的不同分别设计了动态和静态适应度函数,张毅等[46]在设计适应度函数考虑了路径最短和障碍物规避两个要求,文献[44,47]进一步考虑了路径平滑度这一因素。遗传算子的改进倾向于自适应函数的设计,使其能和种群适应度交互,降低陷入局部极小的概率,提高全局收敛能力。文献[43,45-46]在传统遗传算子的基础上引入了删除、平滑和插入(修复)算子,文献[41]则提出了种群熵的概念以及染色体自适应度排序分组的策略,设计了自适应的选择、交叉和变异算子,提高了规划路径的质量。
另一种比较常用的智能算法是蚁群算法,它模拟蚂蚁觅食的过程,是一个群体性行为。蚂蚁在寻找食物时,会在道路上释放一种信息素,而且可以感受到其余蚂蚁释放的信息素。信息素浓度大小代表着距离的远近,信息素浓度越高,表示距离越近。通常蚂蚁以较大的概率优先选择信息素浓度较大的路径,并且释放信息素以提高该路径上的信息素浓度,由此形成一个正反馈。最终,蚂蚁找到一条从巢穴到食物的最短路径。将蚁群思想应用于路径规划,即用蚂蚁的行走路径作为待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。按照蚂蚁觅食的思想,最终得到一条从起始点到目的地的最短路径。蚁群算法的缺陷是:1)前期各条路径上信息素分布为固定值,导致搜索具有盲目性;2)后期各条路径上信息索的积累,导致后续搜索路径不一定是全局最优路径。文献[48]将势场概念引入信息素扩散模型,提高了算法的动态规划能力。文献[49-50]对比了遗传算法和蚁群算法的收敛性,利用遗传算法初始种群随机性强的特点,为蚁群算法的生成初始信息素分布,降低蚁群算法前期搜索的盲目性。文献[50-51]将遗传算子引入蚁群算法,抑制蚁群算法后期陷入局部极小。
3 基于场建模的轨迹规划
3.1 人工势场法
基于场建模的轨迹规划是将无人艇工作空间的障碍物转化为“场”,一般通过研究无人艇在这些场中的受力情况来规划航向。Khatib在1986年提出了人工势场法[55],它的基本思想是在机器人周围设计一种类似于电场的势场,机器人的运动依靠势场力进行驱动。障碍物对机器人产生“斥力”,目标对机器人产生“引力”,障碍物斥力和目标引力的矢量和是机器人所受的合力,合力的方向即机器人下一步的运动方向。该方法由于数学原理简单、计算速度快、硬件要求低,被广泛应用于移动机器人路径规划。
人工势场法将局部环境转化为势场,虽然势场函数是连续的,但是由于环境中障碍物的不确定性,无人艇受到的势场力变化是不连续的。同时由于势场中引力和斥力同时作用于无人艇,势场中可能存在受力平衡点,此时算法无法给出无人艇的下一步规划航向。因此人工势场法主要存在以下四方面缺陷。
1)受力平衡问题
当无人艇靠近障碍物时,受到障碍物斥力势场的作用,且距离障碍物越近受到的势场斥力越大。同时,无人艇还受到目标点的引力作用,且距离目标点越远,受到的引力越强。当引斥力的合力与引力的夹角为斥角时,无人艇规划的航向有较大角度的变化。当引力和斥力二者共线且合力为0时,无人艇所在位置称为全局极小点,在该点处算法无法给出规划航向,无人艇提前停车或者航向“震荡”。
针对全局极小问题,前面的研究者给出了很多改进方法[56⇓⇓⇓-60]。第一类方法是从算法层面进行改进,基本原理是根据全局极小点的特征判定无人艇陷入全局极小,然后利用其他方法引导无人艇离开全局极小点,当判定无人艇已经脱离全局极小点后继续利用人工势场法进行规划。无人艇随机行走、目标点在一定范围内随机生成、水流法、斥力偏转、沿墙走、和其他方法结合设置子目标点(VFH、A*、遗传算法、随机路图法PRM、快速扩展随机树法RRT等)。显然,这些方法仅仅是在局部层面上进行算法的改进,其应用范围是有限的。系统输入的信息规模没有改变,当无人艇遇到的障碍物尺寸大于无人艇局部工作空间的尺寸时,这些算法不能给出有效的解决方案。第二类方法是引入全局信息,改变系统输入的信息规模。相比局部规划的实时性,全局规划时生成路径的安全性和最优性是首要考虑的目标。因此将人工势场法应用于无人艇任务起点和终点之间的矩形区域,可以提前确定全局极小点的位置并进行规避。在进行局部规划时,根据全局规划信息的指导,无人艇可以成功避开这些全局极小点。
2)目标不可达问题
目标不可达问题实质上也是一类受力平衡问题[58]。当目标点周围有障碍物时,障碍物处的斥力势场值较高,而目标点处的引力势场值较低,经过势场叠加后在目标点周围存在势场值高点。无人艇需要跨越这些势场高点才能到达目标点。按照势场梯度下降的规划原理,无人艇无法到达目标点。
针对目标不可达问题,比较常见的改进方法是修改势场函数。部分专家学者将无人艇和目标点的距离引入到斥力势场函数中,斥力随着机器人到目标点距离缩小而减小,同时增加了一个由机器人指向目标点的分力,该模型理论上可以解决目标点不可达的问题。
3)狭窄通道内航向抖动问题
当无人艇在较为狭窄的通道内航行时,周围障碍物和无人艇的距离较近,因此斥力的方向变化对障碍物的位置改变比较敏感。尤其是在狭窄通道内侧边缘不平滑的情况下,无人艇受到的势场斥力的方向变化较为剧烈,导致最终规划的航向抖动比较明显。显然,这种频繁大角度变化的规划航向,对机动性相对较差的无人平台而言,是难以执行的[60]。
针对狭窄通道内航向抖动的问题,可以对算法规划的航向进行滤波,减小算法输出的航向抖动的幅度;部分学者将人工势场法和向量场直方图法结合,当无人艇当前航向被障碍物遮挡时调整航向至可行方向,当无人艇当前航向不受障碍物遮挡时减小航向的调整幅度。还有的学者从障碍物入手,在进行障碍物建模的时候利用图形学,使狭窄通道内侧更平滑,有利于算法输出小幅度变化的航向。
4)复杂环境中不能确定有效通道问题
人工势场法计算无人艇受到的总斥力时,考虑到每个障碍物与无人艇之间的距离信息以及障碍物与无人艇之间的相对位置关系。但是在计算总斥力时,算法给出的只是障碍物的一般趋向,即障碍物少的方向,这个趋向程度是由斥力增益系数决定的。当环境中的障碍物分布较为复杂时,尤其是有效通道较为狭窄且隐藏在障碍物群中时,人工势场法通常不能发现有效通道[61]。
针对复杂环境中寻找有限通道的问题,部分学者使用了启发式的算法,如A*、Theta*等算法来搜索可行路径;部分学者利用快速扩展随机树法(RRT)来寻找有效路径,该方法不需要进行环境建模,且搜索的速度较快。
3.2 流函数法
将流体力学中的理想流体概念引入路径规划中的流函数法,是近些年出现的新算法。流函数法是基于流函数给出一条平滑的规划航线,和人工势场法类似,也是基于障碍物位置的规划方法。在无人艇的工作空间中引入某种流场,根据流体力学的知识可以得到其势函数,之后在初始流场中加入障碍物,通过建立障碍物的流场并与原势场叠加即可得到总的流场,对势函数求导即得流场中各处的流速,对流速积分所得流体的流线就是为无人艇规划出的航路,如图1 所示。
4 轨迹规划未来发展方向
路径规划领域的一些主流算法提出时间如表1 所示。
表1 算法发展脉络 |
| 算法 | 提出时间 | 算法 | 提出时间 |
|---|---|---|---|
| Dijkstra算法 | 1959 | 随机路图法 | 1996 |
| 栅格法 | 1968 | 快速扩展随机树 | 1998 |
| A*算法 | 1968 | 人工鱼群 | 2002 |
| 遗传算法 | 1975 | 细菌觅食算法 | 2002 |
| 可视图法 | 1979 | 人工蜂群算法 | 2005 |
| 人工免疫算法 | 1986 | 布谷鸟搜索 | 2009 |
| 蚁群算法 | 1992 | Theta*算法 | 2010 |
| D*算法 | 1994 | 狼群算法 | 2011 |
| 粒子群算法 | 1994 | 鸟群算法 | 2014 |
| 差分进化 | 1995 |
可以看出,自从遗传算法提出以来,对于群智能算法的探索从未停止,这些算法大都受到自然界的生物群繁衍的启发。这些新的算法在解决问题的维度、求解效率、解的完备性等方面不断改进。对于启发式算法A*算法和RRT算法的探测和改进也从未停止,由于启发式算法能够牺牲较小的时间消耗快速得到较优解,对于解决大型复杂静态问题效果会更加突出。
综合前面专家学者的研究,解决轨迹规划问题的最新方向如下。
1)全局路径规划和局部路径规划相结合
全局路径规划提供粗线条的规划,局部路径规划提供更为精确的避碰规划,一定程度上降低了全局规划的计算复杂度,同时解决了局部规划固有的局部极小问题。
2)多种智能算法的融合
根据前文分析可知,每一种算法的基本模型都是在一定的假设情况下提出的,随着应用环境的改变,算法的不足就会凸显出来。单一算法很难使解决问题的某一项指标有质的变化,而多种算法之间却可以扬长避短、优势互补,最终达到理想的效果。
3)规划路径时,考虑环境信息的影响
目前对于轨迹规划的研究,大多仍停留在算法阶段,能否经得起实际平台的检验是未知的。因此在研究无人艇路径规划时,有必要同时研究海上环境信息的变化。风、浪、流等天气气候信息的变化规律,以及它们是如何影响船的航向航速的,这都是需要深入探讨的问题。
4)从控制的角度,研究规划路径的可行性,形成反馈
同第三点类似,现在的算法规划出的路线过于理想,实际海上航行时这些路线很可能无法被无人艇执行,导致规划失败。根本原因是,算法并未将无人艇的机动性能和控制系统调节能力考虑进去,算法如何和控制系统联结起来并形成反馈控制也需要深入研究。
5 结束语
轨迹规划问题的研究,是无人艇海上平台研究的一个重要课题,对于无人艇的智能无人驾驶至关重要。本文从基于可视图法和单元分解的搜索规划、基于场建模的轨迹规划两大方面,对应用到轨迹规划问题中的算法技术以及其未来的发展进行了系统的总结和评价,对当前无人艇海上航行路径规划的研究与发展具有一定的参考价值。