基于鱼群算法的智能机器人全覆盖路径规划

邓 红，孙 栩

(黑龙江工程学院，哈尔滨 150050)

0 引言

随着社会的发展，人们对生活品质的需求也在不断增高，对于环境也有了更高的清洁度需求。因此移动智能扫地机器人被研究出来，成为了清扫工作的代替者[1]。为保证道路上所有区域的干净整洁，需要保证智能机器人可以做到全方位的路径覆盖，且在同样的区域内，行走路径需要尽量减少，路径重复率尽量降低[2-3]。

在现有的研究中，文献[4]为获取肉眼不可见区域的图像信息，设计了一种针对图像监测的路径规划算法。该方法可以基于生物启发神经网络模型，将结果直接指向活性增益趋势，并获取连续的图像信息。对比原有的算法，该路径规划方法的准确率和效率均有一定程度的提高。但是，该方法路径规划重复率有待验证。文献[5]使用无人机技术，在凸划分优化方法的基础上，提出了一种针对复杂障碍物的路径规划方法，该方法可以准确绘制复杂地块的边界轮廓，标记凹凸点信息，并在随机路标算法的基础上，寻找最短路径。但是，该方法在计算算力方面有待进一步提高。文献[6]提出了一种基于高校模版与动态窗口法的路径规划算法，结合全局路径与位置的障碍物，在窗口栅格地图中，对路径的覆盖率进行规划分析。实验结果显示，该算法可以提高机器人在全覆盖路径中的工作效率和工作精度，具备较高的使用价值。但是，该方法在复杂环境下的路径覆盖率需要提升。

鱼群算法是一种根据鱼群觅食行为完成最优数值计算的方式，使聚集区域内鱼群数目达到特定比例，其具有实现简单、鲁棒性强、使用灵活等优点，且对初值要求不高，对参数选择不敏感，只需获取其目标函数值即可[7]。通过鱼群算法执行追尾和聚群行为，降低遍历重叠度，减少路径冗余，在确保高收敛效率的基础上降低时延，提升复杂环境下的路径规划精准度，实现数值处理和智能规划的高覆盖、低重复、强算力。基于此，结合上述文献资料，本文基于鱼群算法设计了一种智能机器人全覆盖路径规划方法。根据机器人位姿关系计算目标区域旋转角，构建智能机器人死区脱困模型，描述栅格周边状态，获取未被覆盖的栅格区域。在描述不同目标鱼个体之间距离的基础上，依托三维坐标系获取移动目标元素的坐标向量，求解目标点代价完成全路径覆盖的判定。运用鱼群算法判断机器人当前位置是否为死区，获取路径规划的全局最优解，实现智能机器人的全覆盖路径规划。在保证100%覆盖率的基础上，进一步优化机器人路径的重复率和路径长度，以期提升机器人对复杂环境的适应性。

1 建立智能机器人死区脱困模型

在选择智能机器人的目标轨迹时，需要以活性值作为依据。每一个神经元均存在感知域的响应机制，因此可以结合智能机器人周边的活性值获取位姿关系[8-9]。在栅格地图下，其自身的活性可以表示为：

(1)

式中，p(x，y)表示某目标点的活性值；km表示目标点与障碍物的覆盖状态，当km=0时表示未覆盖，当km=1时表示已覆盖；fd表示目标点是否已经被叠加，当fd=1时表示已被叠加，当fd=0时表示未被叠加[10]。在自身的活性影响范围之外，还存在运动方向对旋转角度的影响，因此可以规定机器人在目标区域的旋转角度：

(2)

式中，h(x，y)表示智能机器人的旋转角度对活性值影响；dj表示旋转角度。通过上述两个公式，可以对正常路线下以及前方出现障碍物情况下的智能机器人行走进行规划与分析[11-12]。但是很多时候，如果障碍物较为密集，智能机器人很容易走入死区。通常将智能机器人周边没有未被覆盖栅格的情况成为机器人陷入死区。死区与未被覆盖区域的距离越远，逃离死去的路径就越长，智能机器人在全覆盖路径规划过程中陷入死区的次数越多，其覆盖重复率就越高。此时需要对整体地图环境下的栅格数量进行计算：

(3)

式中，Nk表示该地图环境的栅格总数；sd表示单位栅格的长度；Lh和Wh则分别表示该栅格地图模型的长与宽、同时使用函数描述栅格地图的状态：

(4)

式中，Wsta表示某一栅格周边所拥有的未被覆盖区域的数量[13]；uij表示未被覆盖栅格数量，在该状态函数中，uij={0，1，2，3，4}，即表示单一栅格周边可以有0～4个未被标记的栅格。

当智能机器人在某一活栅格中被逐渐引导到死区时，其想要脱困时的行驶角度差可以表示为：

(5)

式中，Δβdead表示智能机器人行走在死区时的角度差；β则表示方向引导角度[14-15]。通过该角度公式，可以得知智能机器人脱离死区的方法，只要朝着这个方向一直前进，就能够以最短的距离进入未被覆盖的栅格区域。

2 基于鱼群算法的全路径覆盖判定

在该路径规划方法中，除尽快促进智能机器人脱离死区以外，还需要保证机器人的路径覆盖率达到100%，以实现全路径覆盖。制定需要一个判定机制，避免机器人在未完全覆盖所有路径时即停止运行[16]。在这个搜索空间中，可以假设存在一个人工鱼群，该鱼群内包含N个个体，则可以对不同鱼之间的距离进行描述：

(6)

式中，dij表示第i条鱼和第j条鱼之间的距离；Ni和Nj则分别表示两条鱼的感知范围[17]。当某条鱼的当前状态良好且未达到完全覆盖状态，则其在单位时间内的三维坐标系如图1所示。

图1 移动目标坐标系

结合图1中的目标点坐标系，可以直接确定智能机器人在全局坐标中的位姿，将本体与局部坐标系联合在仪器，就可以获取一个元素坐标向量：

(7)

式中，Gt表示元素坐标向量；xi和yi分别表示该智能机器人到达的预期目标点；ti则表示机器人转换位姿的时间参数[18]。由此可以建立每个目标点的求解代价和：

g(x，y)=k(x，y)Δβdead+d(x，y)Δβdead

(8)

式中，g(x，y)表示起点到当前点的总代价；k(x，y)表示实际代价；d(x，y)表示预估代价。根据运动特性，可以获取机器人向下一个目标点行驶的最小距离：

(9)

式中，Dmn表示智能机器人向下一个目标点行驶的最小距离，当Dmn等于1时，表示该目标点周边有可用栅格，当Dmn大于1时，表示该目标点已进入死区，需要立即脱离，当Dmn=0时，表示该地图上已经没有为覆盖栅格，即路径已经实现了全覆盖[19]。vu表示行驶速度；ap表示机器人在目标区域行驶的最小距离。通过上述公式，可以获取全路径覆盖的判定依据。

3 设计机器人全覆盖路径规划算法

根据采集到的全路径覆盖判定依据信息，划定机器人搜索空间。将搜索空间设定为W维度，人工鱼的寻优变量为a[20]，人工鱼个体之间的距离矢量为Ds=(ds1，ds2， ，dsw， ，dsW)，鱼群移动速度矢量为Fs=(fs1，fs2， ，fsw)。当人工鱼当前状态为Gs=(gs1，gs2， ，gsw， ，gsW)时，鱼种群则开始快速移动，并向食物中心聚集[21]。当前人工鱼最优位置矢量为Gu=(gu1，gu2， ，guw， ，guW)，并且每个人工鱼个体根据公式(10)更新觅食位置：

fsw=φfsw+φ1γ1(gsw-dsw)+φ2γ2(guw-dsw)

(10)

式中，φ表示惯性因素；φ1和φ2表示学习因素；随机的[0，1]用γ1和γ2表示。通过不断更新随机位置和速度，寻找觅食最优解。

(11)

图2 算法流程

在该算法内，首先需要随机一个位置节点，即初始节点，并建立两个不同的子群体，分别为已覆盖群体和未覆盖群体，对数据进行初始化处理。判断此时的位置是否为死区，如果是死区，则需要重新随机位置节点，如果不是死区，则使用鱼群算法进行群体行为的执行过程[24]。判断此时的路径规划是否为局部最优：

(12)

式中，Xi表示当前的路径规划函数；Xp表示算法前期的更新位置[25]；Rand()表示周边未覆盖节点数；Xg表示搜索空间中极值点数量[26]。根据该方法，同步更新网络信息，并判断是否达到全局最优。对鱼群进行操作后，即可得到路径全覆盖规划的最优解，实现智能机器人全覆盖路径规划。

4 实验研究

4.1 实验环境设置

选择Roborock S7 MaxV Ultra型清洁机器人在40 m×60 m的空间内完成全覆盖路径规划实验。清洁机器人导航技术为激光导航，避障类型为结构光避障，续航时间为180 min。在Matlab R2022a的环境下，使用Matlab代码编写算法在主频为1的环境下完成机器人全覆盖路径规划仿真。

实时仿真过程包括七个步骤，具体如下。

步骤1：在simulink环境中，采用C++编程环境多样化，编译机器人轨迹法自动调节补偿器参数，并且同时指定干扰参考跟踪、稳定裕度等多个调节目标。

步骤2：对机器人系统进行高度细化建模，设计高级自主性和低级控制度量，连接ROS系统。

步骤3：根据建立的栅格地图模型，使用MATLAB Coder对经过维护的算法库进行代码自动生成及控制。

步骤4：采用Simulink Coder设定机器人传感器(激光雷达、惯性姿态传感IMU、摄像头)数据，优化机器人的外部物理环境感知效果。

步骤5：将ROS系统直接连接到传感器，完成实验对象的检测跟踪。利用RoboticsSystem Toolbox对传感器提取的信息进行校准、降噪等操作，完成特征提取和算法匹配等。

步骤6：通过Embedded coder对机器人进行最终执行和决策功能设定，生成嵌入式代码实现端到端的机器人控制策略。

步骤7：进行实时仿真证明。

4.2 实验设备

为测试上文中鱼群算法下智能机器人全覆盖路径规划的性能，搭建实验平台。在linux系统下，根据各自的功能，实现话题和服务之间的信息传递。硬件部分使用Core-i5 5200U作为工控机，该工控机可以被网络远程控制，有一个对外接口，体积小，性能高，且支持windows平台。软件平台则包括全覆盖路径规划与点线之间的运动规划两个方面，在接受目标点信息的基础上，实现数据控制。测试过程中的硬件环境，软件环境，软件工具如表1所示。

表1 硬件、软件参数详情表

4.3 实验准备

具体的实验参数设置为：选择机器人定位避障的建图数据作为实验数据，设定机器人的线速度为0.2 m/s，角速度为0.3 rad/s，视场角为280°，角度分辨率为0.5°，最大响应时间为1 s。在此条件下整合测试方案，验证实验可行性，实验测试流程如图3所示。

图3 实验流程图

4.4 实验工况

4.4.1 简单环境下的全覆盖路径规划

在该路径规划实验中，简单环境路径效果如图4所示。

图4 路径示意图

如图4所示，对该路径图进行预处理，图(a)中的方格为遮挡物体，曲线则为不可到达区域的边界，在栅格规划效果图中，将不可到达区域与遮挡部位剔除，就可以得到智能机器人全覆盖路径效果图，其中黑色部位为不可达区域，白色部分为可达区域。在计算机上进行仿真，在障碍物之间，栅格活性函数值为0.6，每一个方格为一步。

如图5所示，在简单环境的全覆盖路径探索中，机器人从一个端口进入，采用单一变量控制的原则，将所有白色区域全部覆盖。

图5 简单环境路径覆盖

4.4.2 复杂环境下的全覆盖路径规划

在该路径规划实验中，复杂环境路径效果如图6所示。

图6 路径示意图

图6为复杂路径下的规划效果与栅格示意图，对比简单路径，该复杂路径内的障碍物为非规范图形。因此智能机器人行走在该路径中，会遇到更多的死角，其重复率和全面覆盖所需要行走的路径长度也会进一步增加。

如图7所示，在复杂环境的路径覆盖规划中，智能机器人从左上角出发，在右下角离开，并多次遇到大幅度的重复行走情况。相比起简单环境，复杂环境虽然同样可以实现全方位覆盖，但其所经历过的重复路径有了明显的增加。

图7 复杂环境路径覆盖

4.5 实验结果与分析

为了验证所提方法(基于鱼群算法的智能机器人全覆盖路径规划)的整体有效性，需要对其展开测试。以文献[4]方法(基于生物启发神经网络的水下坝面表观裂缝检测路径规划算法)、文献[5]方法(基于复杂地块凸划分优化的多无人机覆盖路径规划)、文献[6]方法(基于高效模板法与动态窗口法的服务机器人全覆盖路径规划方法)作为对比方法，进行机器人全覆盖路径规划仿真测试。分别计算简单环境和复杂环境的路径覆盖率、路径重复率、路径长度，获取不同算法下的路径规划对比结果。

4.5.1 路径规划覆盖率对比分析

机器人路径规划覆盖效果越优，说明机器人复杂环境下的运行能力越稳定。若机器人在简单环境和复杂环境下的路径规划覆盖率较高，则对应方法的机器人控制精度越优。路径遍历范围越广，则表明路径规划覆盖率越高，测试结果如图8所示。

图8 路径规划覆盖率结果

根据图8可知，所提方法、文献[4]方法、文献[5]方法、文献[6]方法均不存在机器人路径规划异常值，所有方法都可以完成简单环境和复杂环境下的路径遍历。所提方法在简单环境和复杂环境下的路径覆盖与规划一致，覆盖率为100%，由此证明所提方法可以完成复杂环境下全方位覆盖。而文献[4]方法、文献[5]方法、文献[6]方法在简单环境和复杂环境的路径规划遍历不全，无法实现全方位覆盖。这是因为所提方法构建了智能机器人死区脱困模型，通过计算栅格地图模型中的目标活性值可以优化整体栅格参数，提高描述地图中栅格状态稳定性，进而提高了机器人全覆盖路径规划覆盖率。

4.5.2 路径规划重复率对比分析

在发布数据频率为30 kN、分辨率为0.015%，加速度为0.8的条件下，获取路径规划重复率结果，判别简单环境和复杂环境下的路径规划效果，具体测试结果如图9所示。

图9 路径规划重复率结果

根据图9可知，由于所提方法描述不同目标鱼个体之间的距离，在三重移动目标坐标系下获取元素坐标向量，进而降低了路径规划重复率。因此，在机器人路径规划重复率测试过程中，所提方法在简单环境下的路径重复率为5.23%，复杂环境下的路径重复率为10.24%。而文献[4]方法在简单环境下的路径重复率为6.99%，复杂环境下的路径重复率为15.01%。文献[5]方法在简单环境下的路径重复率为8.01%，复杂环境下的路径重复率为22.05%。文献[6]方法在简单环境下的路径重复率为8.91%，复杂环境下的路径重复率为18.27%。由此表明，所提方法具有更强的实时性，更适合用于复杂环境下的智能机器人全覆盖路径规划。

4.5.3 路径规划长度对比分析

在数据变化趋势提升的环境下，路径规划干扰强度会呈现倍增趋势，在机器人路径规划过程中规划长度可以反映方法的优劣性。在客观环境一致的条件下，路径规划长度越小则方法效果越优。在一阶固有频率下进行测试分析，结果如表2所示。

表2 不同方法路径规划长度结果

根据表2可知，所提方法的路径长度在简单环境与复杂环境下均小于文献[4]方法、文献[5]方法、文献[6]方法。这是因为所提方法利用鱼群算法判断当前位置是否为死区，完成路径规划全局最优解，以此提高了算法的计算算力，缩短路径规划长度。实现智能机器人的全覆盖路径规划。由此表明，所提方法在机器人全覆盖路径规划中性能最优。

5 结束语

本文设计了一种基于鱼群算法的智能机器人全覆盖路径规划方法，该方法可以获取脱离死区的最快方法，并结合全覆盖的判定机制，设计相应算法优化路径最优解，完成路径规划。实验结果显示，该路径规划算法在简单环境与复杂环境下均可以实现全覆盖路径规划，且路径重复率较低，路径长度较短。但是由于研究时间和研究条件的有限，本文仅选择了一种清洁机器人作为测试对象，且在研究过程中未考虑计算的延迟。因此，下一步的研究方向为：在本次研究内容的基础上，引入多类型机器人操作设备完成路径规划任务，并在全覆盖判定过程中加入时延矩阵，进一步优化模型计算算力。以获取的数据结果为依据，从多方面验证路径规划效果。