钱金伟，戴晓强，高宏博，朱延栓

(江苏科技大学，江苏镇江 212003)

1 引言

随着海洋探索事业的不断发展，海洋资源开发及海洋探索搜救成为必需，但是由于水下环境未知，人类下潜深度有限及操作风险高等原因，需要水下机器人替代人类进行水下探索及搜救作业。水下机器人通过岸上操作台进行控制，通过自身搭载的声呐、深度计、加速度计及水下云台等传感器采集水下数据并实时传输至岸上操作台，从而达到观测水下环境，探索水下资源的功能。因此，对于水下机器人移动路径规划及避障的研究有利于推进海洋资源开发、海洋工程结构探伤及人员搜救方面的应用。

目前，水下机器人路径规划分为两种，一种是规划出一条从起点至目标点能够避开所有障碍物的最优路径，另一种是在已知水下环境信息的情况下，规划出一条能够遍历地图的全局路径。全局路径规划方法主要有人工势场法，但是人工势场法也存在着固有缺陷：局部极小值引起的陷阱区域问题；存在相近障碍物时难以发现移动路径；目标点附近存在障碍物时无法到达目标点；在障碍物前振荡[1]。随机路径规划方法是由Goodman和Heathcote提出在未知地图环境中的遍历路径规划方法[2]。该方法控制机器人以设定角度直线行走，直至到达规定时间或者触碰到障碍物后，随机选择角度旋转后继续直线行走。该方法简单易实现，但缺点是无法确保地图的完全遍历。通过重复执行随机算法可以提高地图的覆盖率，但也会浪费搜索时间及增加运行路径[3]。Simon X.Yang提出的一种基于生物激励的神经网络算法[4](BINN算法)，在未知地图环境信息时依旧可以遍历整个地图环境，遍历路径过程中不需要学习过程，也可解决存在动态障碍物情况下的路径规划。虽然该方法在全覆盖路径规划中有一定优势，但是也存在着一些不足，如当难以脱离死区，需要等待周围神经元活性值降低后才可逃脱死区，规划路径转弯次数太多，子区域之间的路径规划并非最短等。

本文在生物激励神经网络算法(BINN算法)的基础上，结合内螺旋覆盖算法与A*算法的优点，提出了基于内螺旋搜索的生物激励遍历路径规划算法，有效解决了重复覆盖率高、脱离死区时间长、分离区域路径规划不是最优的问题，优化了规划路径质量。

2 基于BINN的遍历路径规划算法

1952年，著名的生物物理学家Hodgkin和Huxley提出了神经细胞膜的著名电路模型和描述细胞膜的动力学方程(H-H模型[5])。Grossberg在H-H模型的基础上总结并开发了该模型，提出了分流模型，并将其应用于生物和机器视觉，传感和运动控制以及其它应用领域[6]。Yang和Meng于2001年根据Crossberg提出的神经动力学网络模型，将生物激励神经网络应用于移动机器人的地图环境建模和路径规划，实验结果显示取得了很好的效果[7]。

2.1 生物激励神经网络模型

在生物激励神经网络中，神经元的活性值大小决定机器人的运动路径。神经元初始值为0，神经元的变化值由分流方程(Shunting Equations)决定[8]

(1)

(2)

μ和r0都是正常数。每个神经元仅与半径为r0的圆内的神经元有直接联系，权系数ωij是对称的，生物激励神经网络模型如图1所示。

图1 二维生物激励神经网络结构

2.2 路径规划算法

Yang和Luo在移动机器人的全覆盖路径规划领域，针对静态已知环境与动态未知环境的情况下对生物激励神经网络进行了研究[9]。以下为路径规划算法。

机器人栅格地图的位置pc已知，下个时刻的位置表示为

pn⟸xpn=max{xj+cyj，j=1，2，…k}

(3)

c为一个正常数，k为以当前位置为圆心，设置长度为邻域半径内的神经元的总数。yj定义为

yj=1-Δθj/π

(4)

这里Δθj∈[0，π]，是指当前时刻和下个时刻的方向角改变的绝对值大小。Δθj定义如下

Δθj=|θj-θc|=atan 2(ypj-ypc，xpj-xpc)

-atan 2(ypc-ypp，xpc-xpp)

(5)

由上式可知yj是一个递减函数，Δθj越大，yj值越小。

根据该路径规划方法，水下机器人的路径生成过程具体如下：首先从起始点开始，机器人朝着设定的方向行进，同时不断计算所在栅格神经元邻域内的其它神经元的活性值，若周围的其它神经元活性值相等，则机器人根据路径规划算法及生物激励神经网络算法的权值比较选择下一个位置的行进方向，默认行进方向直行，否则下一个位置为设置邻域范围内最大神经元的位置，当机器人触碰到障碍物时，机器人根据路径规划方法选择旋转的角度，当机器人陷入死区时，机器人计算当前栅格邻域内其它栅格的神经元活性值，若均小于等于所处位置的栅格神经元活性值，则机器人维持原状不动，否则机器人移动至活性值最大的位置，如此直到完成区域的全覆盖。

该路径规划方法能够应用在存在死角及障碍物多的情况，也能够运用在存在动态障碍物的情形，能够遍历地图内的所有空间。但是该路径规划方法缺点即路径重复，在从死区逃脱到下一个遍历区域的路径不是最短，搜索时间长，搜索效率低。

3 基于内螺旋搜索的生物激励遍历路径规划算法

3.1 内螺旋算法

内螺旋覆盖算法是由Butler等人提出来的[10]，该算法的覆盖流程具体如下：移动机器人按照设定的初始方向沿着顺时钟或者逆时针方向运行，当前方无障碍物时，机器人保持直线行驶，当遇到障碍物时，机器人按顺时针或者逆时针旋转90度后继续行驶，如此往复，完成整个区域的覆盖。覆盖路径图如图2所示。

图2 内螺旋覆盖算法路径示意图

3.2 A*算法

A*算法结合Dijkstra算法与传统BFS(广度优先搜索算法)算法[11]，通过求解当前节点到起点的路径代价与当前节点至目标点的路径代价之和，对周围的搜索位置进行评估，得到最好的位置，以此求解起点至终点的最短路径。其启发函数采用的代价计算公式如下

F(n)=G(n)+H(n)

(6)

式中：F(n)即为A*算法对于每个节点的评估函数[12]，包含两个子函数：G(n)是从起点到当前位置的n运行代价，即从起点至目前所在位置的移动距离长度；H(n)是从当前位置n至目标点的运行代价，即当前节点到目标点的移动距离长度。

A*算法的路径搜索过程还需要两个表：OPEN表和CLOSE表，OPEN表存储经过代价计算后F值最小的下一个节点，CLOSE存储已完成访问的节点。

H(n)是A*算法的距离估计值，A*算法需要一个距离评估函数来计算这个值。由于使用栅格地图法进行水下环境建模，曼哈顿距离函数较为合适，从数学上描述，曼哈顿距离是当前点至目标点在各个坐标轴上的距离差值的和，对于二维平面上的两个点(x1，y1)与(x2，y2)来说，其曼哈顿距离为

D=|x1-x2|+|y1-y2|

(7)

即欧氏平面几何距离为在直角坐标系中两个坐标轴上的投影距离之和。

3.3 改进算法

水下机器人运行生物激励神经网络算法遍历整个栅格地图，根据负值神经元活性值提取出障碍物的X、Y轴信息并存入ZHANGAI表中，需要进行覆盖的栅格神经元活性值逐渐增长，栅格信息存入DITU表中，已覆盖的栅格信息存入LUJING表中运行估计代价h存入DAIJIA表中。水下机器人运行基于BINN的路径规划算法，根据栅格地图的活性值进行地图覆盖，当机器人触碰到障碍物栅格或者已覆盖路径时，开始运行改进算法。

机器人旋转角度为

i=Δθ/π(Δθ∈{-π/2，π/2})

(8)

求得的i存入JIAODU表中，当i的值为-1/2时，表示机器人在当前行进方向上右转，1/2时表示机器人左转，本文中机器人根据当前所在位置选择旋转方向。如图3所示。

图3 (x，y)坐标周围信息

当机器人从下向上运行时，即从(x，y-1)向(x，y)方向运行，由(x-1，y+1)至(x+1，y+1)为障碍物，机器人通过神经元活性值选择向(x-1，y)或(x+1，y)行进；

当机器人从上向下运行时，即从(x，y+1)向(x，y)方向运行，由(x-1，y-1)至(x+1，y-1)为障碍物，机器人通过神经元活性值选择向(x-1，y)或(x+1，y)行进；

当机器人从左向右运行时，即从(x-1，y)向(x，y)方向运行，由(x+1，y-1)至(x+1，y+1)为障碍物，机器人通过神经元活性值选择向(x，y+1)或(x，y-1)行进；

当机器人从右向左运行时，即从(x+1，y)向(x，y)方向运行，由(x-1，y-1)至(x-1，y+1)为障碍物，机器人通过神经元活性值选择向(x，y+1)或(x，y-1)行进；

上述机器人旋转后的角度i存入JIAODU表中，在机器人完成矩形区域遍历陷入死区前，下一步的旋转方向均为角度i。

机器人陷入死区时进行脱困运行A*算法，算法具体实现如下：

Step1：初始化建立一个OPEN表与CLOSE表，将当前节点作为起点S加入OPEN表中，搜索建立的DITU表与LUJING表，寻找DITU表中未完成覆盖且距离当前节点最近的点，将该节点作为目标点G，估计代价起点S至目标点G的距离，估计函数选择曼哈顿距离函数，左、右、上、下的栅格估计代价均为栅格距离1，左上、右上、左下、右下的栅格估计代价为栅格距离2，估计代价函数h(n)=length(n，G)，n表示当前节点，当前节点计算完成后，将当前节点n加入到CLOSE表中，选择周围F值最小的栅格n+1作为子节点加入到OPEN表中；

Step2：判断OPEN表是否为空，是则转移到Step5，否则继续执行；

Step3：判断n+1节点是否为目标点G，是则转到Step5，否则转到Step4；

Step4：计算n+1节点至G的估计代价h(n+1)=length(n+1，G)，取n+1节点周围估计代价最小的节点n+2作为子节点加入到OPEN表中，将n+1节点加入到CLOSE表中，转到Step2；

Step5：从G点搜索子节点链直至S点，最优路径搜索完成，算法结束。

机器人脱困后，继续运行基于BINN的路径规划算法，并通过内螺旋算法与A*算法完成局部遍历脱困，如此完成整个栅格地图的覆盖。

4 仿真及分析

在MATLAB仿真环境下，设置水下环境为30×20的二维栅格地图(如下图4所示)，环境中的障碍物信息已知，水下机器人起始位置是(1，20)，考虑到水下环境中会出现U形区域，栅格地图设置了U形障碍及不规则障碍物。水下机器人的任务是从起点出发，按照最小重复覆盖率完成对整个栅格地图的遍历，同时运行路径尽可能短。生物激励神经网络参数设置为：A=10，B=1，D=1，μ=0.05，权值占比c=0.5，神经元邻域半径r0=1.5，能够覆盖周围8个神经元，即k=8(Willms and Yang 2006)[13]。设置神经元活性值最大为0.9，障碍物活性值最低为-0.9。

图4 水下环境栅格地图

图5是采用改进路径规划算法后内螺旋算法覆盖部分与脱困示意图，机器人在运行至(7，28)时，开始运行内螺旋覆盖算法，完成矩形区域的遍历后，机器人运行A*算法脱困，如图6所示。

图5 运行内螺旋覆盖算法

图6 运行A*算法脱困

图7是按照生物激励神经网络算法运行后的重复路径图，其中，绿色圆形为起点，蓝色正方形为重复覆盖栅格，白色正方形表示机器人经过生物激励神经网络无法搜索到的未知区域，黑色正方形表示障碍物，红色三角形为已覆盖的栅格，比较图8内螺旋搜索重复路径图，可以看出两种算法均完成了100%的遍历覆盖率，但是内螺旋搜索在重复覆盖率上相比较原生物激励神经网络算法有很大的降低。

图7 生物激励重复覆盖路径

图8 内螺旋搜索重复覆盖路径图

图9 生物激励算法路径图

图10 内螺旋搜索算法路径图

图9为机器人运行生物激励神经网络生成的运动路径图，图10为机器人基于内螺旋搜索的生物激励遍历路径规划算法的运动路径图，从图中可以看出，相比较传统基于生物激励神经网络的路径规划，基于内螺旋搜索的生物激励神经网络遍历路径规划在运行路径长度上要更短。表1列出了两种算法在相同条件下的各种性能指标上的差异。

表1 两种算法参数比较图

5 结束语

本文提出的基于内螺旋搜索的生物激励神经网络遍历路径规划算法能优先解决基于生物激励的全覆盖路径规划算法的重复覆盖率高、分离区域间路径规划不是最优、脱离死区时间长的问题。在相同仿真条件下，及遍历覆盖率是100%的基础上，相对于基于生物激励神经网络路径规划算法，本文提出的算法在重复覆盖率、运行时间、路径长度指标上均有明显提高，表示该方法具有一定的优越性和有效性。