基于正六边形建模的无人水面艇路径规划

程 杰，陈姚节,3

(1.武汉科技大学 计算机科学与技术学院，湖北 武汉 430065; 2.智能信息处理与实时工业系统湖北省重点实验室，湖北 武汉 430065; 3.冶金工业过程国家级虚拟仿真实验教学中心，湖北 武汉 430065)

0 引 言

无人水面艇(unmanned surface vehicle，USV)是指采用遥控方式或自主方式在水面航行的无人化、智能化平台[1]，是船舶智能的一个典型应用领域，在军事和民用都有广阔的应用前景。路径规划是船舶智能诱导的重要组成部分，其主要目的是在已知船舶准确船位以及周围静态和动态障碍物区域并存的环境信息中，寻找一条从起点到终点的满足一定要求的航行路径，使船舶在航行过程中能够安全可靠地避开所有障碍区域并且使路径尽可能的短[2]。目前已有多种算法应用到了路径规划研究中，主要有A*算法、遗传算法[3-4]、蚁群算法[5-6]等，A*算法被认为是在静态环境中求解最短路径最有效的直接搜索算法[7]。

传统A*算法仅考虑路径距离导致规划所得路径转弯次数较多，为了得到更优的路径，国内外学者在不同方面对其进行改进优化。文献[8]采用双向搜索的方式,对传统A*算法加以改进,该算法在路径规划过程中,可同时进行正反向路径搜索,同时采用正反向搜索交替机制,保证了最终目标节点搜索在连线中点区域内相遇,从而缩短了寻路计算时间。文献[9]提出了一种基于权重的改进A*算法航线规划方法，根据风浪网格数据，筛选出危险点集，利用基于权重的改进A*算法快速寻找安全航行路径。文献[10]对估价函数进行指数衰减的方式加权，使得A*算法在离目标点较远时能够很快地向目标点靠近，在离目标点较近时能够局部细致搜索保证目标点附近障碍物较多时可到达目标。文献[11]在传统A*算法的基础上，引入角度计算模块拓展目标点方向可搜索邻域，使路径点不局限于栅格中且转折角度不限制为π/4的整数倍，再对求出的路径进行二次平滑处理，消除路径点中的冗余节点。以上文献对A*算法的改进提高了A*算法的性能，但均使用栅格法建立环境模型使得路径规划受到正方形网格几何性质的约束，同时也忽略了实体与障碍物之间的距离容易导致规划出的路径存在与障碍物相邻的部分。

为了提高规划路径的真实性和安全性，该文通过解析电子海图数据，采用正六边形网格划分建立海洋环境模型，引入“引导量”对A*算法启发函数进行改进，优化算法搜索效率，分析不同扩展邻域下A*算法的搜索效率以及规划路径的性能。

1 海洋环境模型的建立

为利用真实的海洋环境实现USV全局路径规划，采用正六边形网格划分建立基于电子海图的海洋环境模型。首先解析电子海图，提取其中的海域地理信息和障碍物信息，然后利用正六边形网格划分进行网格化，建立由可航行网格和不可航行网格组成的环境模型，通过正六边形网格划分对电子海图的海洋环境信息进行简化可以提高路径规划算法的效率。

1.1 电子海图数据提取

电子海图可以提供详细而准确的全局海洋环境信息，S-57电子海图是按照ISO/IEC 8211国际标准封装的不可见格式[12]，为了将电子海图应用到USV路径规划当中，需要对电子海图进行解析、读取和存储。S-57电子海图文件里的记录主要包含特征记录和空间记录，利用ISO 8211 lib库对电子海图进行解析，读取电子海图文件中的每条记录，使用vector容器存储特征记录，map容器存储空间记录，提取出海洋环境模型所需的内容[13]。

1.2 正六边形网格划分建立环境模型

通过解析电子海图提取的海洋环境信息是由复杂几何图形组成的，使得多数路径搜索算法不能直接被利用，因此需要对海洋环境信息进行网格划分，转换成几何关系简单的环境模型，以提高路径搜索算法的效率[13]。从电子海图中获取海洋环境信息后，通过正六边形网格划分的方法把海图区域划分为若干块大小相等的正六边形网格，根据电子海图中提取的海洋地理信息，可以判断一个网格是否包含大陆、岛屿、半岛等障碍物。如果网格中有障碍物，则标记为不可航行，否则，网格被标记为可航行[14]。图1是该文使用正六边形网格划分建立的环境模型，浅色区域为可航行区域，深色区域为不可航行区域，网格数为143*159，建立以水平向右为x轴，垂直向下为y轴的笛卡尔坐标系，对每一个网格编号，从(0,0)到(142,158)，一个网格即为一个节点。

图1 正六边形网格划分建立的环境模型

引入立方体坐标系对正六边形网格坐标进行转换可以简化坐标运算，在笛卡尔坐标系中的(x,y)对应立方体坐标系中的(q,r,s)，转换关系如下。

由笛卡尔坐标转换为立方体坐标：

(1)

由立方体坐标转换为笛卡尔坐标：

(2)

经过立方体坐标转换后的正六边形网格坐标示意图如图2所示。

海洋环境信息经正六边形网格划分后被转化成网格环境模型，正六边形网格的一致性和统一性简化环境模型，将全局路径规划问题转化为在网格环境中寻找两个网格节点之间的最优路径问题。

2 路径规划方法

2.1 A*算法

首先采用A*算法实现全局路径规划，寻找无约束条件的最优路径。A*算法是全局路径规划中一种启发式搜索算法，其估价函数表示为：

f(i)=g(i)+h(i)

(3)

其中，g(i)表示从初始节点到节点i的代价，启发式函数h(i)表示从节点i到目标点的估计代价。

A*算法包含两个数据集合：open表和closed表，open表保存已生成而未考察的节点，closed表保存已访问过的节点，算法基本流程如下[15]：

(1)把起点加入open表。

(2)遍历open表,找到f值最小的节点，把它作为当前节点来处理，如果当前节点为终点，搜索结束，否则，把该节点加入closed表。

(3)遍历当前节点的8个相邻节点，如果相邻节点可行并且不在open表。

(4)计算相邻节点的g值，如果相邻节点不在closed表或者g值更小。

(5)更新相邻节点的g值，将当前节点设置为相邻节点的父节点，计算f值，将相邻节点加入open表，转至(2)。

传统的A*算法规划路径无约束条件导致计算时间较长以及转折次数过多。因此，提出了一种改进的A*算法，从启发函数和搜索策略两方面对A*算法进行优化。

2.2 启发函数的改进

正六边形网格之间的实际距离为立方体坐标系中距离的一半，因此节点u(q,r,s)和节点v(q,r,s)的曼哈顿距离D(u,v)表示为：

D(u,v)=

(4)

在A*算法搜索流程中，可能会有多个具有相同估价值的网格被搜索，但只想选择靠近从起点到目标点直线的网格，通过“引导量”对启发函数进行改进，可以减少具有相同估价值的网格数量，选择期望的最优路径。

假设起点S到目标点E的直线为L1，节点i到目标点E的直线为L2。

起点S到目标点E的欧氏距离为：

(5)

节点i到目标点E的欧氏距离为：

(6)

L1和L2之间的夹角θ的计算方法如下：

θ=

(7)

节点i的引导量p(i)可表示为：

(8)

假设从起点S到节点i的规划路径为S→n0→n1→…→ni，则g(i)和h(i)可表示为：

(9)

h(i)=D(i,E)·p(i)

(10)

2.3 搜索策略的改进

在正六边形网格模型中，传统的A*算法搜索下一个节点采用6邻域方式，每个搜索方向之间夹角为π/3，此时规划路径可能不是最短且因转折点较多不够平滑。为优化这个问题，对搜索邻域进行层级扩展，向外扩展一层可将当前节点n周围第一层和第二层总计18个节点纳入算法下一步待扩展节点，向外扩展两层可将当前节点n周围第一层、第二层和第三层总计36个节点纳入算法下一步待扩展节点。

A*算法的可扩展节点数与可搜索层级成正比，设x表示当前节点n搜索下一节点的可搜索层级，Nx表示可扩展节点数，则：

(11)

其中，x≥1,x∈Z。

由此得到与x取值对应的不同Nx的值，如表1所示。

表1 可扩展节点数与可搜索层级的对应关系

3 实验及结果分析

为验证正六边形网格化模型的合理性和A*算法优化方法的可行性，对已解析的电子海图分别使用栅格法和正六边形网格进行划分，其中使用栅格法划分的网格左右相邻的单位代价与使用正六边形网格划分的单位代价相同。假设单位代价为1，设定起点S位置为(112.521 000°E，21.635 000°N)，在栅格法划分的环境模型下的笛卡尔坐标为(99，6)，在正六边形网格划分的环境模型下的笛卡尔坐标为(114，5)，立方体坐标为(-15，-62，114)，终点E位置为(112.901 000°E，21.669 000°N)，在栅格法划分的环境模型下的笛卡尔坐标为(89，115)，在正六边形网格划分的环境模型下的笛卡尔坐标为(103，115)，立方体坐标为(63，-166，103)，使用A*算法进行仿真实验。

3.1 正六边形网格与栅格法划分实验

对基于栅格法划分和基于正六边形网格划分的电子海图模型进行路径规划，仿真实验结果分别如图3和图4所示。

图3 栅格法划分实验

图4 正六边形网格划分实验

统计两次仿真实验的路径参数数据可以更加直观地看出两次实验的区别，统计表如表2所示。

表2 正六边形网格与栅格法划分实验对比

由表2可以看出，基于正六边形网格划分模型相比栅格法划分模型优势在于算法的遍历点数减少27.93%，搜索时间减少49.76%，虽然转弯次数和路径总长有所增加，但是曲线的平滑度更好。综合来看，基于正六边形网格划分模型的算法性能更好，但是依然存在转弯次数较多的问题。

3.2 邻域层级扩展实验

在基于正六边形网格划分模型的基础上，对A*算法的搜索策略进行邻域层级扩展，图5和图6分别是双层18邻域扩展、三层36邻域扩展仿真实验结果。

图5 18邻域扩展实验

图6 36邻域扩展实验

统计6邻域扩展、18邻域扩展、36邻域扩展三次仿真实验的路径参数数据，统计表如表3所示。

表3 邻域层级扩展实验数据对比

由表3可以看出，随着可扩展邻域层级的增大，算法搜索时间增加，路径总长减少，转弯次数和转角总和减少。本组实验中，基于正六边形网格划分模型并使用18邻域扩展搜索的路径相比栅格法建模搜索的路径，转弯次数和转角总和显著减少且搜索时间更短。

4 结束语

以无人水面艇路径规划为背景，针对A*算法规划路径的安全问题，提出基于正六边形网格建模的方法和一种A*算法的优化方法，通过仿真实验得到以下结论：

(1)基于正六边形网格建模相比栅格法建模可以提升算法搜索性能以及规划路径的平滑度；

(2)在保证算法搜索时间的前提下可以尽量增加邻域扩展层级以减少转弯次数得到更优的路径。