无人船全覆盖路径规划算法研究

2022-10-14邢博闻胡庆松王五桂

兵器装备工程学报 2022年9期

邢博闻，杨柳，胡庆松，王五桂

(1.上海海洋大学工程学院，上海 201306； 2.中国舰船研究设计中心，武汉 430064)

1 引言

近年来，随着我国在渤海综合治理、长江保护修复、水源地保护等水生态事业的持续推进，搭载相关传感器装置的无人船已经被越来越多的使用在水域监测领域。在这个过程中，针对指定水域的无人船监测路径规划的有效性与科学性已经成为了提升监测质量、降低监测成本的核心问题。为了实现对水域环境的完整监测，无人船往往需要执行经典搜索模式(平行线、蠕变线、方形、扇区和障碍巡逻等搜索模式)，即全覆盖路径规划(CCPP)任务。但其监测效率、数据实时性、可检测范围等方面都受到路径距离的限制与制约，如何在有限的时间内完成对相关水域的完整覆盖，已经成为了无人船CCPP任务策略设计的核心指标。

目前已经有很多基于全覆盖路径规划(CCPP)的研究。其中Howie Choset提出了精确的细胞分解方法用于覆盖目标地图。算法的主要工作是将整个工作空间按照障碍物的边界分割成一个个小的待覆盖区域，然后在整个工作空间中使用深度优先搜索的方法来遍历这些区域。Vatana等提出了一种为圆形移动机器人进行本地全覆盖路径规划的方法。该方法首先将目标区域划分为多个正三角形，然后根据多个正三角形的大小和感应范围，确定路径。Hassan等提出了一种新颖的自适应全覆盖路径规划算法，该方法设计了一个包含3个奖励的总奖励函数，其中第一个奖励受到捕食者与猎物关系的启发，第二个奖励与沿着直线方向的持续运动有关，第三个奖励则与覆盖的范围大小有关。

无人船在航行过程中时刻受到浪流影响需要不断改变速度、航行，这也降低了传统全覆盖路径规划算法无法在复杂环境中的有效性与可行性。为此，Koppaka Ganesh Sai Apuroop 和 Anh Vu Le以卷积神经网络(CNN)为基础，提出了可以使机器人最大化区域覆盖，同时最小化耗能的基于深度强化学习的框架，并使用演员-评论家经验回放算法(actor-critic experience replay)来训练神经网络的长期记忆库(LSTM)。然而基于传统神经网络方法，其全覆盖路径规划算法面临环境信息未知、缺乏先验知识和神经网络没有解搜索空间等等问题。

为此本文中提出了一种新的神经网络算法，通过改进后人工蜂群法进行无监督训练和学习完成无人船的全覆盖路径规划。该算法根据无人船是否满足障碍物约束、新区域探索效率等条件来构建了评价函数，利用改进后的人工蜂群法优化神经网络的参数，提高训练效率、提升训练效果，从而实现无人船在复杂环境下的自主探索的全覆盖路径规划。

2 环境建模与仿真平台

2.1 栅格地图模型

由于计算机不能直接处理环境信息，所以需要首先对环境进行建模，将现实的环境和路径规划问题转化为计算机可以理解的表达形式。

在栅格地图模型中，空白(白色)栅格代表可以通行的区域，黑色栅格代表障碍物所在区域。如果栅格中既有白色又有黑色，通过判断黑色部分的占比来判断该区域是否可以通行，如果黑色占整个栅格的10%以上则判定为此栅格不可通行，否则该区域可以正常通行。

2.2 仿真平台搭建

本文中根据栅格地图模型，基于Tkinter搭建了无人船全覆盖路径规划仿真环境平台，其效果如图1所示。图1中地图中的黑色区域为障碍物所在的区域，无人船只能在白色栅格中移动，如果无人船移动到黑色栅格中，则任务失败。红色方块代表无人船，规定无人船每一步移动都只能从当前栅格移动到相邻的白色栅格区域。无人船每覆盖一个栅格，栅格就会由白色变为深色，表示其已经被覆盖过。若无人船移动到地图边界以外或者移动到黑色栅格内，则任务失败。若除黑色栅格区域以外的栅格都变为深色，则代表所有非障碍物栅格都已经被覆盖，任务完成。

图1 仿真环境平台效果示意图Fig.1 Schematic diagram of simulation environment

2.3 评价函数

无人船需要使用尽量少的步长遍历整个环境同时自主躲避地图中的障碍物。为了分析算法的性能，本文中定义了以下评价函数。该评价函数分为3部分：

1) 覆盖率

2) 路径重复率

3) 事故惩罚

本文中设定当无人船进入障碍物所在的栅格或者地图边界以外则代表任务失败，从而在评价函数中减去固定的值作为惩罚，并且结束此次任务。然后开始新一轮的尝试。如果无人船顺利完成全覆盖路径规划任务，即覆盖了工作环境中所有未被障碍物覆盖的栅格并且过程中未碰撞到障碍物和地图边界，则加上固定的分数作为奖励。奖励记为。

3 人工蜂群法结合神经网络的全覆盖路径规划算法

3.1 人工蜂群法

人工蜂群法是2005年Karaboga小组为优化代数问题所提出的群智能算法，其模仿蜜蜂寻找蜜源和采集蜂蜜的过程。相较于常见的启发式算法，它的优势在于使用了比较少的控制参数，在每次迭代中都会搜索全局和局部的最优解方案，因此可以大大增加其寻找到最优解的概率，并且人工蜂群法具有很强的鲁棒性。

人工蜂群算法就是基于蜜蜂采蜜的过程而提出的新型智能优化算法，它由蜜源、雇佣蜂和非雇佣蜂3个部分组成。蜜源就是待优化问题的可行解，是人工蜂群算法需要处理的基本对象。蜜源的好坏由评价函数所决定。雇佣蜂与蜜源的位置是一一对应的，在人工蜂群算法中，蜜源的个数与雇佣蜂的个数是相等的。雇佣蜂的任务是发现蜜源并且以一定的概率与跟随蜂相分享，概率一般是以评价函数的值和轮盘赌法则来综合计算。非雇佣蜂则分为跟随蜂与侦察蜂。跟随蜂根据雇佣蜂发布的蜜源信息来选择探索的范围并且进行贪心选择搜索新的蜜源。如果一个蜜源在经过多次更新后仍未被更新，则此雇佣蜂变为侦察蜂。侦察蜂的作用是在蜂巢附近寻找新的食物源，也就是跳出局部最优解，寻找全局最优解。

人工蜂群法的算法原理如下。假设需要解决的问题的解空间的维数为，跟随蜂与侦察蜂的个数都为，蜜源的浓度相当于相应的解通过评价函数得到的值，也称为适应度。跟随蜂与蜜源是一一对应的，所以与第个蜜源相对应的第个跟随蜂寻找蜜源的公式如下：

(1)

其中，=1,2,3,…,，=1,2,3,…,,为[-1,1]区间上的随机数，并且≠。然后将新生成的解与原本的解比较并且采用贪婪策略选择保留较好的解。每一个观察蜂根据概率选择一个蜜源，概率为：

(2)

其中为解所对应评价函数的值。观察蜂根据概率公式搜寻新的可能解。当在给定的步骤内蜜源对应的评价函数值没有提高，则放弃该蜜源。而与该蜜源对应的雇佣蜂变为侦察蜂寻找新的蜜源，新蜜源为:

(3)

3.2 神经网络结构

无人船应该做到可以根据周围的环境和自身的状态来不断自动调节下一时刻的动作。在这一应用场景下，神经网络展现出了良好的效果。神经网络不仅可以通过周围环境的信息输入来决定下一时刻的控制指令，而且可以通过不断地学习提高自己的表现效果。但是由于在全覆盖路径规划中很难利用类似于梯度下降等的规律来优化神经网络参数进行学习，所以本文中只构建一个前向神经网络，优化参数时使用人工蜂群法代替神经网络的反向传播过程。

图2 激光雷达的输入示意图Fig.2 Schematic diagram of Lidar input

除了障碍物信息，无人船为了更好地执行全覆盖路径规划任务，还需要了解已经覆盖完成的区域信息，所以神经网络地输入还要包含无人船5个方向的区域覆盖程度信息：

(4)

其中，为在第个方向上的输入，为无人船覆盖过第个方向上第个栅格的次数，为激光雷达的量程，为最大覆盖次数，本文中设定=15。当无人船覆盖该方向上栅格的平均次数大于15次，则该方向上的区域覆盖率恒为1。

因此，神经网络的输入应为{,,,,,,,,,}，其中为激光雷达输出的障碍物信息，为从地图获取的5个方向上的覆盖率信息。

神经网络的输出为无人船所做出的动作，即向上、向下、向左和向右4个动作。本文中的神经网络的隐藏层激活函数选择ReLU 函数，输出层的激活函数选取softmax函数，ReLU函数的表达式为()=max(0,)。

经大量实验发现，当隐藏层的层数为1，隐藏层的神经元个数为6时神经网络的性能最优。

3.3 人工蜂群法作为神经网络参数优化方法的全覆盖路径规划算法

神经网络的学习模式大致可以分为有监督学习和无监督学习，有监督学习需要提供大量的标注后的样本，通过输入样本之后输出的信息来调整神经网络的参数，从而拟合出样本与输出的关系。由于在无人船的全覆盖路径规划算法中，很难根据任务去设定每一种情况对应的最优动作的值，从而很难确定实际输出与理想输出之间的误差，即无法判断在某一环境下某一个动作是否为正确、高效的对全覆盖有利的动作，需要根据回合结束后的信息才能判断，所以无法确定该动作样本为正样本还是负样本，也无法利用损失值来进行梯度下降等方法来更新神经网络的参数。

本文中将神经网络的参数值作为待优化的部分，可以通过启发式算法来对其进行优化更新。由于人工蜂群法不需要了解问题的特殊信息，只需对生成的路径进行优劣比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值凸显出来，有着较快的收敛速度，所以本文中采用无监督学习结合人工蜂群法来优化神经网络参数。

一般来说，神经网络单步更新的效率更高，即无人船每走一步，神经网络的参数更新一次。但是由于无法根据无人船单步运动信息准确地判断这一步对于整体全覆盖路径规划的收益，所以本文中选择在无人船完成任务之后或者碰撞到障碍物和地图边界之后再整体评价神经网络所最终形成的路径，根据评价再进一步优化神经网络的参数，即按照回合制更新。

人工蜂群法可以基于任务来灵活地设计评价函数，从而评价和选择神经网络的参数，并且通过多次迭代得出全局近似最优解。由于人工蜂群法算法设计过程简单、参数少、能够跳出局部最优解、鲁棒性强等特点，所以本文中采取人工蜂群法来代替梯度下降法优化神经网络的参数。

初始情况下神经网络的参数是在极值区间中随机生成的，所以初始情况下神经网络所规划出的路径得分会较低。然后人工蜂群法一次生成多组神经网络参数，神经网络参数的组数即蜜源的个数，人工蜂群法求解空间的维数即神经网络参数的个数。然后在每一组神经网络的控制下无人船会在地图中生成各自的轨迹，轨迹可以通过速度的积分求出，也可以在地图中实时记录无人船每一步的位置信息。当轨迹碰撞到障碍物和地图边界或者覆盖率达到指定要求时，无人船停止运动并评估轨迹的得分。神经网络在初始学习阶段很容易出现无人船在相同的路径上转圈，此路径既不会碰撞到障碍物或者地图边界，也不会达到覆盖率大于预设值，此时程序陷入死循环，所以设定当无人船运动步长大于待覆盖栅格的3倍以上，则任务失败。无人船停止运动并且评估该轨迹得分。如果最高分满足要求，则算法结束。如果最高分不符合要求，则将该分值和参数值保存在列表中，供人工蜂群法之后的迭代使用。通过评价函数评价各个轨迹，挑选优秀的轨迹，并且侦察蜂会在整个解空间随机搜索新的蜜源，不断优化蜜源即神经网络参数的质量。

全覆盖路径规划算法需要无人船能够在未知区域中进行全覆盖路径规划并且自主避障，所以路径的评价函数必须包含地图的覆盖率、路径的重复率和路径的事故率，所以评价函数应该取：

(5)

由于在仿真地图中可以很轻易地实时获得无人船的动作信息，所以在仿真中取：

(6)

本文中选取的蜜源数为8，雇佣蜂个数与蜜源相等。首先随机生成蜜源，根据各个蜜源生成对应的神经网络，通过评价函数来评估依据神经网络输出生成的路径。之后通过雇佣蜂和跟随蜂的搜寻寻找更优的蜜源，不断迭代，迭代终止条件为迭代次数达到设定的最大值或者评价函数的值高于预设值。同时侦察蜂在整个解空间搜寻蜜源，实现跳出局部最优解，达到全局最优解。算法流程如图3所示。

图3 算法流程框图Fig.3 Algorithm flowchart

4 仿真分析

本次仿真实验环境为一张10*10的栅格地图，其中有一些随机障碍物，网格边长为1 m。仿真系统通过离线学习功能实现自主避障和全覆盖路径规划任务的神经网络参数优化。当一代无人船完成全覆盖路径规划任务或与障碍物碰撞时，它们会根据路径覆盖、重复率和事故率进行评分。人工蜂群算法选择得分较高的路径进行迭代，优化神经网络参数进行全覆盖路径规划。优化结果如图4所示。纵坐标cost采取路径分数的倒数，横坐标代表迭代次数。随着迭代次数的不断增加，前200次的cost迅速降低，说明之前的训练可以非常有效。快速提升神经网络的效果，后面的分数趋于收敛，此时得到的路径接近最优路径。图5为使用神经网络结合遗传算法进行全覆盖路径规划的训练得分曲线。通过大量的实验表明，在地图大小小于7*7时遗传算法可以很快收敛到最优路径，但是当地图大小大于9*9之后，遗传算法的收敛速度变得非常缓慢。图5为遗传算法在10*10的栅格地图中进行全覆盖路径规划的训练得分曲线。图6表示采用传统的牛耕法全覆盖路径规划，此时的覆盖率为100%，重复率为20%。图7表示全覆盖路径规划神经网络训练之后生成的路径。此路径的覆盖率为100%，重复率为2%。如表1所示，本文中所提出的算法的路径重复率大大小于传统的牛耕法，虽然算法耗时要大于牛耕法的时间，但是也在接受范围之内。而且其算法可以积累之前的经验，在新的地图中可以吸取之前地图的全覆盖路径规划经验，从而更加迅速地收敛于最优路径。理论上，使用足够多的地图对其算法进行训练，训练完成之后，此算法可以直接在任意陌生地图中使用而不需要再次训练。此时只需要相应的传感器提供数据，从而满足路径规划过程中实时性的需求。

图4 神经网络训练优化曲线Fig.4 Neural network training optimization diagram

图5 遗传算法训练得分曲线Fig.5 Genetic algorithm training score graph

图6 牛耕法全覆盖路径规划示意图Fig.6 The full coverage path planning diagram of cattle farming method

图7 全覆盖路径规划路径示意图Fig.7 The map of full coverage path planning path

表1 算法结果Table 1 The result of the algorithm

由上文可得本文中设计的神经网络结合人工蜂群的全覆盖路径规划算法经过较少的迭代次数就能收敛，得到较高的评价即较优的全覆盖路径，且路径不会与障碍物和地图边界相撞。同时通过降低迭代结束标准，程序迭代的时间也会大大缩短，即牺牲一部分区域的探索可以换得更短的步长覆盖尽量多的区域，当全覆盖路径规划的路径重复率的要求比较低时时可以通过适当调低覆盖率来实现快速收敛，使得算法执行效率更高。