一种混合优化的全局路径规划算法

韩新洁，李欣然，范云生，孙晓界

(大连海事大学 船舶电气工程学院，辽宁 大连 116026)

0 引 言

智能化的发展首先体现在水下无人机器人、无人机、无人车的出现，随着智能化研究的深入无人水面艇随之而来并飞速进步，在军事领域技术已经较为成熟[1]。无人水面艇作为军事领域的重要研究对象，其在航行过程中的路径规划也十分关键，一般可分为2种类型：一种是全局路径规划，另一种是局部路径规划[2]。二者之间的主要区别是已知信息量的范围，全局路径规划是已知整个航行环境信息而局部路径规划则是只能根据传感器探测得到周围的环境信息[3]。传统的路径规划方法主要有人工势场法[4]、蚁群算法[5]、栅格法[6]等。智能化算法主要有模糊逻辑算法、神经网络、遗传算法以及混合算法等[7]。由于工作环境以及需要的不同，传统算法无法满足路径规划的需要因而许多研究者对算法进行了组合和改进。张玉奎[8]利用遗传算法和人工势场法对多种复杂的障碍物环境进行规划。王燕龙等[9]提出了一种基于航行安全权重，导频量和路径曲线平滑的改进A*算法。曹璐[10]针对多变因素和即时重要需求约束提出了一种基于Voronoi图和改进遗传算法的快速路径规划方法。陈超等[11]改进人工势场法来解决最小点问题。

本文在前人研究成果的基础上，以无人水面艇为例提出一种混合算法优化的全局路径规划方法，对环境中的可行区域使用A*算法预处理后使用遗传算法进行路径规划并对结果进行平滑处理获得适合快速安全行进的路线，并给出一种评价体系对规划结果进行定量的避障评价，评价结果显示通过混合优化算法规划出的路径更安全和平滑。

1 问题描述

在全局路径规划中，无人艇航行环境已知，并且确定无人艇的位置[12]，需要根据要求如耗时短、耗能少、路线距离小等[13]搜索出一条最适合当前要求的能够到达目标点的路径。本文在进行全局路径规划过程中选取使用的算法为能够对静态障碍物进行全局路径规划的遗传算法，但基本的遗传算法存在着早熟、收敛速度慢等问题[14]，因此在基本的遗传算法上进行一定的改进，在规划出路线的同时进行一定的优化，并给出避障能力的评价指标。

1.1 应用平台

“蓝信”号USV作为一种具有全自主和半自主控制的多功能智能化无人水面机器人由大连海事大学自主研发[15]。

船长7.02 m、型宽2.60 m、配备5.0 L排量191.1 kW的推进器、该船最大载荷1 000 kg、航速最高可达35 kn、可持续航行180 n mile。艇上搭载有红外热成像系统、4G波段连续波导航雷达、前扫防碰撞声纳、海事卫星链路终端、多路差分GPS/BDS、姿态方位组合导航、高清视频和音频、VHF通信等多种传感器；配备自主研发的自主动态避碰控制器、自主导航运动控制器、多信息网络控制器和推进控制器等[16]；“蓝信”号USV能够通过地面站设备操控无人船以较高的航行速度实现多种功能。

1.2 全局路径规划的快速平滑安全性问题

随着现有各种算法的不断发展，采用单一方法虽然也能够实现路径规划，但是每种方法也都存在着一些不足和待解决的问题，因而不断出现各种改进及优化使得基础算法不断完善，得到更快更好的路径规划结果。遗传算法以其并行性和良好的全局寻优能力而著称，但由于算法中早熟和收敛速度慢等不足，因此需要对其进行改进优化。本文主要以遗传算法为主，同时使用A*算法进行搜索范围预处理，并对其规划出来的路线给出适当的评价函数，通过评价函数更直观的了解规划出的路线的避障能力。

2 全局路径规划算法介绍

2.1 A＊算法

A*算法作为智能化算法一种是典型的启发式算法，能够灵活方便解决问题[17]。A*算法主要是将搜索空间看作是一系列位置节点和连接它们的边，针对不同边长赋予相应的路径价值，通过搜索到达目标节点价值最小的节点序列来得到最短路径[18]。

评价函数作为算法的核心，表达式为：

式中：n为当前搜索到的节点位置；f(n)为估价函数，其中估价是指从起始位置经过节点n以最优路径到目标位置的价值；g(n)表示从初始位置以实际的最短路径到节点n的价值，如果n为起始位置，则g(n)=0；h(n)是“估算”节点n以最优路径到目标位置的价值。

2.2 遗传算法

遗传算法由美国J.Holland教授在1975年提出，是一种模拟生物进化过程寻找最优解的智能搜索算法[19]。它以初始种群为基础，其中初始种群是某一随机产生的或是特定的，种群由若干经过基因编码的个体组成。按照适者生存和优胜劣汰的原则经过选择、复制、交叉、变异等操作并根据个体的适应度不断迭代计算从而引导种群的基因向最优解逼近[20]。迭代结束后，将最优个体的基因经过解码得到最优解或近似最优解[21]。遗传算法简单易用，容易得到满意结果，且适用于并行分布处理，在科学研究和工程领域得到普遍认可[22]。

遗传算法是基于染色体群的并行搜索，带有猜测性质的选择操作、交叉操作和变异操作，并且能够同时处理群体中的多个个体，能够减少陷入局部最优解的可能，此外具有自组织、自适应和自学习性，利用进化过程获得的信息自行组织搜索时适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。但是遗传算法通常的效率比其他传统的优化方法低，易过早收敛，而且对精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

2.3 人工势场法

Khatib[23]针对配置空间提出了势场的概念。人工势场是将被控对象看作一个质点，其所在环境为二维欧式空间，对环境空间模拟潜在的引力场和斥力场，其中目标位置周围为吸引力场，障碍物周围为排斥力场[24]，环境中被控对象的运动虚拟为在受力场中的运动，障碍物产生斥力，目标则为引力，2种力产生的合力控制运动方向[25]。

3 全局路径规划的混合优化

3.1 全局路径规划的优化

遗传算法之所以能被大量使用是因其并行性和良好的全局寻优能力等，但也饱受早熟和收敛速度慢等问题的困扰。收敛速度慢的原因有很多，例如随着搜索范围的不断扩大，生成的随机初始种群的可能性也越来越多，有些位置可能会出现在初始种群中，但在路径规划时，这些位置最终不会出现在可行路径，排除这些可行区域中的不通行区域，能够减少不必要的计算量。

选择A*算法进行预处理是因为A*算法从当前节点出发向周围8个方向进行节点扩展，如图1所示。

图1 A*算法扩展节点方向图Fig.1 A* algorithm extended node pattern

8个节点选取“估算”价值最小的节点作为路径节点序列中第2个节点，然后对第2个节点进行相同操作直到目标节点，搜索出最短路径[26]。A*算法在规划过程中会有许多可行点作为规划结果而导致最终路径过于冗余，也会出现一些大角度的转折，因此在使用A*算法作为路径规划算法时需要对其进行改进优化，综上考虑选取A*算法作为预处理方法保证非全覆盖搜索后搜索到的可行栅格内包含最优路径。

A*算法对海图进行预处理主要是对给定的海图以及起始点和目标点进行搜索区域计算，栅格大小选取为海图的一个像素点，通过预处理缩小可行区域范围，并将搜索区域的范围读取出来作为遗传算法的初始种群范围。图2是以天津港的海图作为无人艇的航行环境，给定的起始点和目标点位置在图中以绿色点的形式显示，使用A*算法对环境进行预处理，红色区域为使用A*算法预处理后得到的可行区域范围，其中经过预处理后的可行区域约占整个海图可行区域的40%，减少了遗传算法的规划范围，提高了遗传算法全局路径规划效率。

由于采用不同的海图以及设置的起始点和目标点存在差异，因此预处理过程搜索出的可行区域相对于原环境的海图来说能够减少一定的可行区域面积，但是具体减少的面积比例要根据实验环境中的可行区域以及对起始点和目标点的设定的不同而存在差异。

图2 A*预处理结果Fig.2 A* preprocessing results

遗传算法中着重考虑的是适应度函数，在本文中选取的是最小路径代价、平均拐角值代价和碰撞威胁代价得到综合最小解[27,28]。综合最小解Value(P*)为Value(P*)=min[f1(P),f2(P),f3(P)]，其中，目标函数f1(P),f2(P),f3(P)代表无人艇路径的平滑性、经济性和安全性。路径光滑性平均拐角值代价(li-2)+mi×C2；经济性主要考虑的是路径长度及最小路径代价，其中路径长度f2(P)为{Length(Pi)}，最小路径代价Length(Pi)为：Length(Pi)=安全性{danger(Pi)}，其中danger(di)=1/di。

由于无人艇实际航行轨迹应为一条连续平滑的曲线，而进化遗传算法得到的可行路径是由浮点数所连接而成的折线段组成，因此要对结果进行平滑处理使其能够作为无人艇的航行路线。通过采用贝塞尔数学优化方法，可以将折线路径进行曲线优化[29]。

贝塞尔曲线普遍应用为矢量曲线，一般化的n阶贝塞尔曲线表达式为:

其中，B(t)表示由点P0，P1，···，Pn所决定的贝塞尔曲线，t∈(0,1]。

路径优化采用高阶贝塞尔曲线，阶数选取依据可行路径的浮点个数，从而得到光滑的连续路径。

本文提出的混合优化算法主要是对遗传算法的初始种群进行优化，对生成初始种群的范围进行缩小，在不影响最终路线的情况下，缩小搜索范围，使得混合优化后的算法能够快速有效的规划出适合无人水面艇安全航行的全局路线。

3.2 评价函数的优化

本文提出一种对避障能力进行评价的方法，利用人工势场法的思想，将无人艇行进过程中的陆地岛屿等不可行区域看作斥力影响，目标点则看作引力影响，给出引力和斥力对无人艇的影响函数，最终得到评价函数。其中无人艇受到的斥力由当前行进的位置点到左右两侧的最近障碍点的斥力值之差来确定，斥力值需要分别计算左右两侧，通过下式计算得到：

式中：h为行驶到当前规划路线时所在点(x0,y0)与最近障碍点(xb,yb)的距离

最终该位置点的斥力fr由式（3）分别计算出左侧障碍物的斥力值frel和右侧障碍物的斥力值frer，取两者之差的绝对值作为该点的斥力

无人艇受到的引力主要是目标点对当前行进的位置点的吸引，当前位置点离目标点越近，受到的引力值越大，受到的引力fa通过下式计算得到：

式中：H为行驶到当前规划路线时所在点(x0,y0)到目标点(xa,ya)的距离。

评价函数作为无人艇受到的合力值，是整个规划的路线中每一个位置点的引力和斥力值之和后取平均值，而斥力在评价函数中是作为负值出现的，因此引入的评价函数为：

其中：n为规划出的路线上所有点的个数。

评价函数评价的路径为经过混合算法得到的路径点使用贝塞尔曲线平滑处理后的路径，若经过平滑处理后的路线经过障碍物及其他不可行区域则重新进行全局路径规划。评价函数的值越高，说明经过平滑处理得到的可行路径能够保证在整个行进的过程中无人艇距离周围陆地及暗礁岛屿的距离都很充裕，能够较好地使用算法获得最优路径。

4 实验验证及结果分析

4.1 实验环境搭建

本文在Matlab环境中基于天津港的海图针对无人艇进行了全局路径规划。首先对获取的电子海图进行加载，用Matlab读取电子海图的像素点信息，将彩色的海图进行图像处理，分离障碍物与可行进区域，设置起始点和目标点的位置，使用A*算法对规划路线区域进行预处理，缩小生成初始种群的范围。对缩小后的可行区域范围使用遗传算法进行路径规划并对规划后的路线进行平滑处理从而使规划出来的路线更符合船舶运动特性。最后对规划出来的路线进行避障评价，采用基于人工势场法的评价函数对规划路线的避障能力予以评价分析，以便更加显著地看出使用混合算法优化的路线具有更好地避障能力，具体流程如图3所示。

图3 混合算法流程图Fig.3 Hybrid algorithm flowchart

4.2 仿真平台搭建

本文在Matlab上使用混合算法进行路径规划的同时，搭建了能够加载海图显示相关参数的QT平台。该平台能够加载典型航行区域的电子海图，并可以针对每个加载的海图设置相应的起点和终点经纬度，选择相应的算法进行路径规划。

4.3 实验结果及分析

本文在Matlab上对天津港的海图进行了模拟仿

真，仿真主要是以天津港为背景，结合天津港周围的海况以及暗礁岛屿绘制出天津港的环境，通过对周围的岛屿及陆地等无人艇不可能行驶的区域进行提取后，

分别使用A*算法和混合算法对无人艇进行路径规划，使无人艇能够避开障碍物从设定的起始点到达目标点。本文首先使用了路径规划较为广泛的A*算法对天津港的周围区域进行全局路径规划，设定起始位置和目标位置后使用A*算法进行规划并对规划出来的折线结果进行相同的贝塞尔曲线平滑处理，对最终的路径点进行避障结果评价。在进行平滑处理后得到的曲线会穿过障碍物致使无人艇无法航行，使用A*算法规划并进行平滑处理后得到的仿真结果如图4所示。

图4 使用A*算法仿真图Fig.4 Simulation diagram using A* algorithm

在使用A*算法进行路径规划的同时，本文也使用了混合优化算法对天津港附近海域进行了同样的路径规划，设定相同的起始点和目标点，得到的仿真结果如图5所示。由于起点和终点都位于不可行区域附近，结合仿真结果和评价值，说明规划出的路径能够正确避开障碍物及不可行区域抵达目标点。

图5 使用混合算法仿真图Fig.5 Simulation diagram using a hybrid algorithm

A*算法和混合算法都能够将电子海图给出的附近区域中的障碍物和可行区域信息提取出来，在设定起始点和目标点之后通过算法得到一条无碰撞航线，但是经过贝塞尔曲线平滑处理后，2种算法得到的路线有一些不同之处，依据避障评价函数对2种算法进行评价的结果如表1所示。其中安全距离为无人艇与周围障碍物之间的最小距离，避障评价为衡量算法规划出的路径对于无人艇平稳安全通过的能力。

表1 A＊算法与混合算法的对比Tab.1 Comparison of A* algorithm and hybrid algorithm

通过评价结果可以看到当确定无人艇航行环境以及起始点和目标点时，A*算法的规划路径穿越障碍物区域，这种路径是不能被采用的，本文所提出的混合算法可以规划出一条足够安全的路径。同时本文通过所提出的评价函数对不同算法规划出来的路线进行避障能力的评价，用数值直观地给出评价结果。通过以上仿真及评价函数的结果可以显著地看出使用混合优化算法比用A*算法规划的路线具有更好的避障能力，其生成的路径能够与周围障碍物保持相对较远的安全距离，使得船只能够更安全的通过障碍物区域抵达目标点。

5 结 语

本文将A*算法应用到遗传算法中提出混合路径规划算法，首先A*算法预处理从起点到目标点进行大致范围搜索，减少遗传算法中计算的范围，然后使用遗传算法对起点到目标点的路线进行规划生成能够行进的路线，最后引入评价函数对规划出来的路线进行评价，评价函数的值越高，该路线的避障能力越强，最后选择最为合适的路线作为最优路线。在仿真过程中，使用能够提供周围障碍的图像并给出起始点和目标点，使用Matlab进行路径规划，并对规划出的路线进行评价，最终得到较为合适且便捷的行进路线。同时使用QT搭建界面显示的平台，加载相应的环境进行路径的设置和显示。在接下来的研究中路径规划算法不仅需要考虑行驶的天气性因素，还要对行驶中的其他各种干扰情况进行考虑。