改进人工鱼群的移动机器人避障寻优算法

郭凡，何柳，侯媛彬，秦学斌，卢志强，王冕

西安科技大学 电气与控制工程学院，陕西 西安 710054

近几年来，随着计算机、信息处理与智能控制的迅猛发展，人们对于机器人的研究也在逐渐加深，机器人的功能也在慢慢完善，而本文所研究的移动机器人也是其中的一种[1]。现在移动机器人的研究已进入较为成熟的阶段，可以先前确定的任务地点为目标，提前对行走的地图做出规划，在移动的过程中根据周围复杂环境障碍物的情况，进行最短距离的判断，完美地避开障碍物。移动机器人按照运行环境，可分为海、陆、空3类[2−3]。本文主要解决如何使移动机器人在行走过程中可获取最短路径的问题，即移动机器人行进的路径规划问题。对此，国内外众多专家学者已进行探究并提出对应的解决办法。文献[4]针对无人机的航路规划问题，提出利用多个处理器来同时执行算法优化过程的思想，并通过仿真来对粒子群和遗传算法进行对应方案的验证，实验结果表明，算法的执行效率明显提升。文献[5]提出将改进的人工蜂群算法应用至机器人的路径规划中，并通过仿真结果将其与差分进化算法相比较，从而验证该改进蜂群算法的实用性。文献[6]提出将传统的ANN与蚁群算法相结合的优化算法运用到路径规划中，并进行相应的仿真实验，验证该优化算法在规划速度和更优路径上的优越性。文献[7]以蚁群算法为基础，引进人工势场的作用，两种算法之间优劣互补，在复杂的行走环境中共同作用以提升寻优能力。国际很多专家对人工鱼群算法进行了改进，应用在不同的领域，文献[8]将支持向量机与人工鱼群算法结合，来解决孪生支持向量机的参数选择问题；文献[9]针对深度神经网络AI研究的可解释性瓶颈，给出了有价值的解释；文献[10−12]利用改进的人工鱼群算法进行图像量化、WSN覆盖优化策略、资源调度算法；文献[13−16]研究改进的人工鱼群算法在时滞系统辨识和非线性优化问题中的应用，也有专家利用混合聚类或海洋流的流动功率对人工鱼群算法进行改进。

国外的专家对移动机器人的控制、组队进行了大量研究，美国专家研究拦截流氓机器人，捕获具有多个追踪器的多个逃逸者的算法[17]；韩国的专家们研究多障碍下移动机器人避障、路径规划及不稳定网络下机器人的跟踪质量问题[18−20]；印度专家对多机器人系统进行建模、实行分散控制[21−23]；德国、法国和加拿大等的专家研究多机器人系统的运动冲突、测量与优化控制问题[24−27]。通过分析国内外的研究现状，可以发现现有的算法研究仍存在一些可优化项，例如：移动机器人的真实环境较为复杂，存在不定时的障碍物，这就要求机器人具备实时避免碰撞的能力。因此，利用更加即时的算法来实现该场景优化具有很强的实际应用意义。

本文针对复杂环境下寻找最短路径问题，提出基于视野自适应的改进人工鱼群(artificial fishswarm algorithm based on adaptive vision,AVAFSA)的机器人路径规划算法，分别引入衰减函数和自适应算子来改善视觉效果，增强步长的自适应能力，从而避免因视野太小而陷入局部最小的情况，由此来缩减机器人在行走过程中的路径长度和时间。

1 系统描述

1.1 结构设计

本文研制的移动机器人设计主要由主控制器Arduino单片机、超声波测距模块、电机驱动模块、摄像头、RS232接口、光电感应以及电源等模块组成。其系统总体框架如图1所示。其中超声波测距和光电感应模块主要完成行走环境的信息获取，包括障碍物的距离和路线检测；Arduino可根据超声波测距和光电感应模块的输送信息来进行判断，从而驱动电机来合理地移动机器人。摄像机主要将机器人周边的环境信息通过RS232接口传送至上位机，由PC机来完成对路径的优化选择。图2给出了自制的移动机器人底部设计示意图。图2中，底部的前面中间的超声波传感器用作小车避障，其他4个红外传感器(红外对管)用作寻迹，左右车轮分别由2个12 V直流电机分别驱动，两轮之间装有型号为ST151的码盘测速器，万向轮配合左右车轮运动。

图1 自动搬运机器人系统框图

图2 自制的移动机器人底部设计示意

1.2 移动机器人的环境模型

栅格图是目前在路径规划中应用较为广泛的一种表达方法，因此本文通过栅格法来建立移动机器人的运行模型。栅格法把移动机器人的操作环境投射为栅格二维空间，其中黑色区域为障碍物所在地，白色为机器人可行区域[8]。分析移动机器人的运动环境，特作以下假设。

1)运行环境处于二维空间内，在一个静态平面范围中。

2)在运行空间内，静态障碍物所处的初始位置、当前位置、目标位置与大小均知晓。

3)把移动机器人可看作质点。

4)移动机器人可以随意变化方向[9]，其变化方向如图3所示。

图3 移动机器人移动方向

5)移动机器人可以随意改变行走速度，加速、减速、匀速或者停止等。

2 AVAFSA路径优化算法

2.1 AFSA的基本思想及步骤

人工鱼群算法(artificial fish-swarm algorithm,AFSA)是由李晓磊博士在2002年提出的一种群体智能优化算法。其基本思想是仿照鱼群在一片水域当中寻找最优解的觅食、聚群和追尾等行为，水域中的每一条鱼都对应其中的一个优化解，该水域即为被优化问题的解空间。通过分析人工鱼群的优化理念，可得其人工鱼环境模型如图4所示。假设水域中一条鱼现时状态是X，其可见范围为Visual(公式中用Zvisual表示)，在某一时间点对应的视点位置为Xk，如果该方位较此时状态更优，则可往该地点处向前一步，即抵达Xnext；若该方位无此时状态更优，则一直在可见视线内找寻其他较优地点。

图4 人工鱼环境模型

AFSA在路径规划中的具体步骤如下。

1)初始化设置。对鱼群中的各个参数进行初始设置，包括：该人工鱼群的群体规模、视野、最大迭代次数、每一条鱼的最大移动步长Step(公式中用Lstep)等参数。

2)此时迭代的次数是0，由N条鱼组成初始鱼群，每个鱼表示从初始位置到目标位置的一条路径。

3)对每一条人工鱼都进行行为模拟：觅食、追尾、聚群与随机移动行为，选取其中最优的一种行为来操作。4种行为算法的数学表达如下。

觅食行为

聚群行为

追尾行为

任意移动行为

式中Rand()为随机函数，产生0到1之间的随机数。

4)人工鱼在每次行为之后，选取自身状态和公告牌状态较优的一种进行实时更新。

5)判断是否已到最大迭代次数，若已到达，则输出，否则，转第3)继续运行。

根据以上对于AFSA基本理论和操作步骤的描述中可看出，视野起到了至关重要的作用。在移动过程中，视野值若不变，易引起算法收敛速度变慢，计算量变大。

2.2 AVAFSA机器人路径规划算法

针对上述AFSA在路径规划中所存在的问题，本文提出基于视野自适应的改进人工鱼群算法的机器人路径规划算法。

人工鱼的4种行为中，觅食行为是决定算法是否收敛的关键，因此，仅对觅食行为采用自适应改进，其他的追尾、聚群以及随机移动行为对应的视野保持不变。在觅食行为执行初期，给予其较大的视野，随着过程迭代的进行慢慢减小。

但是，若行为执行到后期时，视野太小，易陷入局部最优。所以，设定在视野的当前值缩减至初始值的一半时，数值保持不变，停止减小。因此，现将觅食行为的数学表达式改写成式(5)数学模型，即目标函数。

式中：k为迭代数；α为衰减因子，a∈(0,1)；β∈(0,1)为视野的下限因子；Vo代表视野初始值，即为优化后觅食行为中的。

AVAFSA机器人路径规划算法实现步骤为

1)初始化设置。结合栅格图大小，设置每格的边长、障碍物的个数、机器人起点S坐标和终点T坐标位置；为对鱼群中的各个参数进行初始设置，包括：该人工鱼群的群体规模、视野、最大迭代次数和拥挤度因子等参数，设每一条鱼的最大移动步长Lstep=1、视野的下限因子β=0.5。

2)迭代的次数从0开始，由N条鱼组成初始鱼群，每个鱼表示从初始位置到目标位置的一条路径。

3)对每一个人工鱼都进行行为模拟。包括觅食、追尾、聚群与随机移动行为(此处觅食行为的视野是改进后的，采用目标函数公式(5)迭代)；在栅格图上机器人的当前位置，选取当中最优的一种行为来操作。

4)人工鱼在每次行为之后，选取自身状态和公告牌状态较优的一种进行实时更新。

5)判断运行次数是否等于初始设置的最大迭代次数，若是，则继续；否则，转到步骤3)继续。

6)判断机器人是否到达栅格图的终点T坐标位置，若是，则结束；否则，转到步骤3)继续。

3 实验与分析

为了验证本文所提改进的人工鱼群算法与传统人工鱼群在移动机器人路径规划上的优越性，在此选择相同的运行环境作对比仿真实验。结合栅格法[28]，利用MATLAB进行仿真验证，栅格图大小设为120 cm×120 cm，其每格的边长为4 cm，序号初始化值是0，在X、Y方向对各个栅格按照顺序进行编号，把障碍物所在的栅格位置标记成黑色，其他区域为白色，货物存放地47个，起点S坐标为 (2,2)，终点T坐标为 (118,118)，最大迭代次数均设定为100。2种算法在该相同环境下各自优化的最优路线与收敛曲线分别如图5和图6所示。相关数据总结见表1。图7为自制的移动小车在实际运行的状态，图7(a)为避障选道，图7(b)为右转弯运行。

图7 自制的移动小车在实际运行的状态

表1中，Lf为最优路径长度，Kmin为训练次数。由仿真图、实验及表中数据可得，2种算法在移动机器人路径规划的应用中，本文所改进的人工鱼群算法最优路径长度与迭代次数上均优于传统的人工鱼群算法。由图4可得，AVAFSA优化下的最优路径长度明显较AFSA短，为186 cm；从图5可看出，在路径寻优的整个过程中，AVAFSA最终找到最优路径所需迭代的次数为35次，比AFSA少了15次；此外，当2种算法的最大迭代次数均设置为100时，AVAFSA会最先达到次数上限，迭代用时较短，仅为10.15 s，比AVAFSA缩短了2.18 s。总之，本文所提出的基于视野自适应的改进人工鱼群优化算法较传统的人工鱼群算法在移动机器人的路径规划应用上存在明显的优势。

图52 种算法的最优路径搜索

图62 种算法的收敛曲线

表1 2种算法最优路径相关参数对比

4 结论

本文通过建立移动机器人的环境模型，分析传统人工鱼群在路径优化方面存在的问题，提出基于视野自适应的改进人工鱼群优化算法，结合栅格图法的优点，形成了AVAFSA机器人避障和优化算法。该算法利用鱼群视野自适应的形式来对可见视线值的下限进行设定，引入衰减函数来改善视觉效果，引入自适应算子来增强步长的自适应能力，从而避免因视野太小而导致易陷入局部最小。计算机仿真和通过自制的小车实验结果表明，如果在环境中有未知障碍物，本文的AVAFSA机器人路径规划算法也能实时避障，重新优化运行的路径。在同样环境条件下，AVAFSA机器人避障和优化算法相比于传统的人工鱼群算法获取最优路径的迭代次数减少了，路径长度缩短了8.82%，收敛速度提高了17.68%。由此可见，视野自适应的人工鱼群优化算法在移动机器人的避障和路径规划上效果明显。