基于生物启发神经网络的多AUV目标搜索∗

孙奥林 曹 翔 肖 旭 徐丽雯

（淮阴师范学院物理与电子电气工程学院 淮安 223300）

1 引言

水下机器人目标搜索是水下搜救、水下捕获等水下任务的重要组成部分［1～2］。由于自治水下机器人（Autonomous Underwater Vehicle，AUV）自身携带能量有限，单个AUV很难在复杂水域完成目标搜索任务。因此，多AUV目标搜索成为了当今水下机器人研究的一个重要方向［3～4］。与陆地和天空机器人相比，水下机器人起步较晚，由于其具有相关性，陆地和天空机器人的目标搜索算法可以借鉴。对于多机器人的目标搜索算法，国内外学者已取得了大量的研究成果。

在早期关于多机器人目标搜索问题的研究中，Ge和Fua在文献［5］中提出一种用于动态未知连通环境的全覆盖搜索方法，算法的思想是机器人在全覆盖搜索的同时尽可能地搜索障碍物与已搜索区域附近一些难以到达的区域，并充分考虑如何减少重复搜索和时间花费。但在障碍物间的路径宽度小于机器人搜索覆盖范围宽度的两倍时，可能出现重复搜索的现象。

为了增加多机器人之间的协作，Yamauchi［6］提出了一种基于边界的分布式多机器人目标搜索策略。该算法将“边界”定义为已知开阔区域与未搜索区域之间的分界线。其使用栅格占有率的方法来表征所探索的地图，多机器人之间分享各自的感知信息，维护独立的全局地图。处于搜索中的每个机器人不断地选择最近的边界点对环境进行搜索，直到所有可达的区域都被搜索完毕而完成任务。由于这种策略各个机器人之间协调信息很有限，可能导致某些机器人驶往同一边界造成碰撞以及重复搜索，搜索效率低下。

为了提高目标搜索的效率，市场经济算法常常应用于多机器人目标搜索任务中。Zolt等在文献［7］中提出一种基于市场经济机制的多机器人目标搜索算法。在该算法中各个机器人之间共享关于目标的信息，它们根据各自的局部地图计算出到达目标的花费，并且以此作为投标价格，再按照第一价格密封标价拍卖法将目标即“标的”分配给出价最低的机器人。此种机制是分布式的，具有鲁棒性、高效等特点。但机器人必须通过显式的通信有意图的协作，资源消耗较多，一旦通讯中断性能将明显下降。除此之外，但由于没有考虑各目标之间的距离关系，所以此算法对搜索效率没有太多提高。

对于未知环境中多机器人的目标协作搜索，Yoon和Qiao［8］提出一种基于同步的多AUV搜索算法，该算法能够实现大范围的目标搜索。AUV通过定时的相聚完成数据的交换，实现对目标的协作搜索。该算法还具有冗错能力，在部分AUV出现故障以后，同样能完成搜索任务。但是该算法只研究了二维的环境且将环境理想化，没有考虑环境中的障碍物，因此降低了该算法的实用性。Wagner等［9］提出了多机器人通过留下化学气味轨迹的方式进行相互间的交流和协作机制，这种化学气味能够随着时间变长而挥发，并且在机器人到达某一点后能够增强其上的化学气味。这种方法类似于Svennebring在文献［10］所提出的一种基于蚁群优化的目标搜索算法，其将地图划分为很多方形区域，并且机器人能够在其走过路径上留下轨迹。但是上述所有的方法都需要机器人能够在探索环境中留下一些符号，或者使用一片集中区域（例如：共享的内存区域）来记录机器人的移动路径，一旦搜索区域较大、机器人数量较多时，系统需要很大的存储空间。因此不适合大范围大规模的目标搜索任务。

综上所述，虽然已有许多关于多机器人目标搜索的研究，但是行为搜索策略效率较低，机器人之间基本无协作，违背了使用多机器人进行目标搜索的最初目的；基于边界的目标搜索策略要么某些机器人驶往同一边界造成碰撞以及重复搜索，搜索效率也不高，要么系统中存在有中央节点，如若损坏整个系统将崩溃；市场经济机制搜索策略由于计算量大的缺点，只适用于静态已知环境下的小规模的多机器人系统；基于信息素的方法需要大量存储空间存储机器人运动路径，机器人数量增加时会增加算法的负担，不适用于大范围大规模的搜索任务。并且，对于多AUV目标搜索的报道较少。因此，本文针对未知水下环境中目标搜索算法进行研究，引入生物启发神经网络，提出生物启发多AUV搜索算法。将水下栅格地图与生物启发神经网络相联系，神经网络中每一个神经元与水下栅格地图中的位置单元一一对应，根据该神经网络中神经元的在线活性输出值分布情况制定AUV的搜索路径规划模型。旨在提高多AUV目标搜索的效率，提高AUV之间的协作性。通过仿真实验证明生物启发神经网络在多AUV目标搜索中的有效性。

2 基于生物启发神经网络的多AUV目标搜索算法

图1 神经网络结构图

本节对多AUV目标搜索算法进行研究，提出适合多AUV目标搜索的三维神经网络模型。将生物启发神经网络模型的神经元在空间中排列成三维的结构分布，如图1所示。每个神经元与其周边相邻的神经元（最多26个）互相连接，构成三维的神经网络结构。图1显示了一个3×3×3的三维神经网络结构（为直观起见，仅显示中心神经元的所有连接，其他神经元的连接省略）。

神经网络中神经元活性变化规律如下方程表示［11］：

其中，uk为神经网络中k位置处的神经元活性值；ul是与神经元k相邻（具有连接）的神经元l的活性值；参数A，B和D为正常数，-A反映了神经元k的活性值uk的衰减速率；B和D分别是uk的上下限值，即uk∈[-D，B]；Ik表示神经元k的外部输入信号，Ik＞0表示激励信号，Ik＜0表示抑制信号。

wkl表示神经元k与l之间的神经元连接权系数，定义为［12］

其中，|kl|表示在三维神经网络空间中神经元k与神经元l之间的距离，μ为常系数，一般定义在范围（0，1）内。

三维搜索路径规划模型是将AUV的搜索路径规划问题演变为寻找出AUV的下一个航行位置，只有准确找出了该位置，才能使AUV能够快速地发现未知目标，且不会与障碍物发生碰撞。对此，必须把具体的动态环境和AUV前后时刻的航行位置联系起来综合决策出AUV的下一个航行位置。用建立的三维生物启发神经网络模型来表示AUV的三维工作环境，并且神经网络中的每一个神经元与栅格地图中的位置单元一一对应，就可以根据神经网络中每一个神经元的活性输出值分布情况来规划AUV的搜索路径。由此把AUV搜索路径规划的研究转换为对神经网络结构中神经元活性输出值的研究，通过神经元活性输出值的分布情况来决策出AUV下一时刻的航行位置。首先计算出所有与当前神经元相邻的神经元的活性输出值，然后找出最大活性值的神经元，最后AUV向着最大活性输出值对应的位置航行。当出现多个相邻节点神经元活性值为最大值的情况时，AUV会随机选取其中一个神经元的位置作为它的下一步航行的位置，这样的路径决策并不会影响整个搜索路径规划的过程。

在三维生物启发神经网络结构中，外部输入信号包括激励信号和抑制信号。其中目标作为激励信号吸引搜索AUV向其靠近，而障碍物作为抑制信号排斥AUV使其不能靠近，避免发生碰撞。在神经网络中外部信号对应神经元的活性定义为

将外部信号的值代入式（1），计算输出神经网络中每个神经元的活性值。AUV根据神经元的活性值选择下一个航行位置Pn，其具体搜索路径规划模型为［13］

式中，Path是AUV的路经集合；Pc，Pp，Pn分别表示AUV的当前位置、前一时刻位置和下一时刻位置；uk是当前神经元的活性值；ul是周边神经元的活性值；|kl|是当前神经元与周边神经元之间的欧氏距离。

式（4）表明，当AUV开始寻找下一时刻的航行路径时，会将当前所处神经元周边的神经元的活性值进行比较，选取活性值最大的神经元所在的位置作为下一步的航行位置，此过程不断地重复，直到AUV发现未知目标。因为目标所在的神经元具有最大的活性值，起着激励作用，一直引领AUV不断靠近直至被发现；而障碍物所在的神经元具有最小的活性值，起着抑制作用，因此AUV不会选择此处神经元所在的位置作为下一步的路径，由此成功地规避障碍物。

3 三维水下环境中多AUV目标搜索仿真及分析

本节将验证该算法的有效性，对静态和动态情况下的三维多AUV目标搜索进行仿真研究，仿真在Matlab R2011a上实现。仿真实验设置水下工作空间的大小为100×100×100，其中随机的分布着各种形状的障碍物。每个AUV和目标都视为质点，不考虑其形状。同时假设AUV是可以全方位运动的，它的观察范围为3×3×3。通过搜索静态和动态未知目标的仿真实验，考察本文提及的算法是否能够快速地完成搜索任务，是否能自动避开障碍物。另外通过和其他算法的比较，考察本文所提及算法的性能。本节中算法的控制参数设置如表1所示。

表1 控制参数表

3.1 三维环境中未知静态目标搜索

图2 三维环境中未知静态目标搜索仿真

首先测试本文提及算法在三维环境中对多个静态目标搜索的能力。仿真实验的初始位置如图2（a）所示，搜索空间大小为一个100×100×100的立方体空间，空间中随机的分布着4个AUV，4个位置未知的静态目标，还有一些形状各异的障碍物。而AUV 初始位置坐标分别为（10，80，20），（60，100，90），（90，10，50）和（90，90，10）。AUV对区域中目标搜索采用生物启发神经网络的方式。根据算法的原理，针对栅格地图构建100×100×100的拓扑神经网络。目标作为激励输入在神经网络中对应神经元的活性值为1，而障碍物作为抑制输入在神经网络中对应的神经元活性值为-1。搜索任务开始以后，根据搜索路径的规划模型，AUV比较相邻栅格的神经元活性值，选择神经元活性值最大的栅格作为下一步的航行位置。所以AUV总是向着神经元活性值最大的位置搜索，对应到地图上就是向着目标的位置航行。同时在搜索过程中障碍物对应的神经元活性值是最低的，所以根据算法原理AUV能够自动的躲避障碍物。当目标进入任何一个AUV的观察范围以后，目标被发现。所有的目标都被发现以后搜索任务结束。图2（b）显示4个未知静态目标被发现时各个AUV的最终搜索轨迹，静态目标T1，T2，T3和 T4分别被AUV R1，R3，R4和R2发现。从图中可见AUV不仅搜索到了目标，而且在搜索过程中自动躲避障碍物，没有对已搜索区域重复搜索。可见本文提及的算法对未知静态目标的搜索是非常有效的。

3.2 三维环境中未知动态目标搜索

在实际的搜索任务中，时常需要对位置未知的动态目标进行搜索。这无疑增加了搜索的难度。但是本文提及的算法能够克服这个困难。根据算法的定义，目标为激励输入对应的神经元活性值是最大的，AUV搜索路径规划策略是始终向着神经元活性值大的位置搜索。根据生物启发神经网络的传递性，当目标运动以后，AUV相邻神经元的活性值将随之发生变化。因此移动目标运动的位置信息将通过神经网络传递给每一个AUV。AUV根据实时获取的神经活性值信息调整搜索的路径，到达对未知动态目标搜索的目的。

如图3显示了AUV搜索到未知动态目标的过程。图3（a）显示了第一个动态目标被发现时的搜索过程。图3（b）显示了第二个动态目标被发现时各个AUV的搜索轨迹。从图中可见不管目标怎么运动，AUV的搜索路径总能随之作出调整，向着目标的方向搜索。可见本文提及的算法不仅能够搜索到未知的静态目标，同样对未知动态目标的搜索也是非常有效。

3.3 三维环境中部分AUV出现故障情况下的未知目标搜索

如果在搜索过程中部分AUV出现故障，将对多AUV系统的容错性是一个极大的考验。本节将检验本文提及的多AUV系统的容错能力，对系统中部分AUV出现故障的情况进行仿真。首先对一个AUV出现故障的情况进行仿真，实验中4个AUV对4个未知静态目标进行搜索。

图3 三维环境中未知动态目标搜索仿真

图4一个AUV出现故障的未知目标搜索仿真

目标和AUV的初始位置和3.1节未知静态目标搜索实验相同。开始搜索的初期，4个AUV都是正常工作的。搜索了一段时间，R4出现了故障不能继续工作，其余的机器人继续搜索目标（如图4（a）所示）。由于多AUV系统采用分布式的体系结构，一个AUV出现故障不会使整个系统发生瘫痪。剩余正常的AUV将继续搜索工作。当R3发现目标T3后，由于目标T4的吸引，R3继续向着目标T4搜索。图4（b）所示R3最终发现了目标T4，搜索任务结束。通过上述仿真实验可见即使有AUV出现故障，本文提及的算法仍然能完成搜索任务，证明该算法有很强的容错能力和多AUV的协作能力。

图5 两个AUV出现故障的未知目标搜索仿真

仿真实验进一步验证当不止一个AUV出现故障时，本文提及的算法是否还能完成搜索任务。图5显示了2个AUV出现故障时的目标搜索仿真结果。仿真实验是4个AUV对2个未知静态目标进行搜索。开始搜索的初期4个AUV都能正常工作。经过10s的搜索后，AUV R4出现故障，停止搜索（如图5（a）所示），其他的AUV继续搜索。当搜索进行了20s时，另一个机器人R1又出现故障（如图5（b）所示）。由于系统采用分布式的结构体系，剩余的两个AUV继续搜索目标。最终AUV R2和R3发现了目标T1和T2（如图5（c）所示）。虽然在搜索过程中两个AUV出现了故障，但是在没有对算法做任何参数修改的情况下剩余的AUV仍然完成了搜索任务，可见本文的算法有很好的容错性，并且对于不同的工作环境不需要对算法的参数进行修改，证明该算法有很强的适应性。

4 结语

本文对三维水下环境中的多AUV目标搜索算法进行了研究。针对水下环境中未知目标搜索，将生物启发神经网络应用到搜索算法中，分别选择目标和障碍物作为生物启发神经网络的激励输入和抑制输入，通过神经元活性函数计算出神经网络中每个神经元的活性值，AUV比较邻近神经元活性值大小确定下一步搜索的位置，从而规划出一条有效的搜索路径。从不同情况下的多AUV目标搜索仿真实验可知，在三维的水下环境中本文提及的算法都能成功搜索到未知的静态和动态目标。同时还通过实验证明了多AUV系统中有部分AUV出现故障时仍然能完成搜索任务。本文最后对不同目标搜索算法进行了比较，从比较结果可知本文提及的算法缩短了搜索时间，降低了搜索路径的重复率。虽然本文提及的算法有上述优点，但是仍然存在一些不足，如环境模型较为简单，并未考虑水流对目标搜索的影响；另外，将AUV假设为一个质点，未考虑AUV的动力学和运动学模型，这些不足将在进一步的研究中解决。