基于改进人工鱼群算法的移动机器人路径规划

江 岩 黄宜庆

（1.安徽工程大学电气工程学院 安徽省电气传动与控制重点实验室；2.高端装备先进感知与智能控制教育部重点实验室 安徽芜湖 241000）

路径规划是移动机器人导航的关键技术，具有十分重要的研究意义。机器人路径规划是指在预先设定的条件下，从起点到终点的路径当中躲避障碍物寻找到一条最短的路径[1]。根据环境信息是否已知，可将移动机器人路径规划问题分为两类：全局路径规划和局部路径规划[2]，前者为环境信息完全已知，后者为环境信息未知或者部分已知。因此，在局部路径规划过程中需要通过传感器对环境信息进行感知。

传统的路径规划方法主要有人工势场法[3]、可视图法[4]、自由空间法等，但均存在不足之处。其中，人工势场法结构比较简单，但在全局路径规划时容易陷入局部最优解的问题；可视图法的路径规划虽然能够获得最短路径但效率比较低；自由空间法比较灵活，起点和终点的位置改变不会重构可视图，但是在障碍物较多时有时无法获得最短路径。随着研究的进一步深入，群智能算法成为目前机器人路径规划的热门方法。主要包括人工鱼群算法[5]、蚁群算法[6]、粒子群算法等。文献[1]采用连接图法进行环境建模，得到起点和终点的网络有权图，再利用Dijkstra算法得到初始的路径，最后利用遗传算法优化得到的路径。文献[2]将扰动机制加入粒子群算法当中，采用个体修正的方法代替进入进化停滞状态的个体，从而引导算法搜索可行路径，使算法避免陷入局部极值。文献[3]分析了传统人工势场法路径规划时，由于局部最优而导致路径规划失败的原因。对于势函数进行改进的基础上又结合了构造虚拟障碍物的方法，使得算法逃脱局部极小值点。文献[4]针对静态已知环境下的全局路径规划，在可视图法建模的基础上，利用遗传算法进行优化，并加入了目标导向启发函数，使得算法的收敛时间得到改善。文献[5]针对移动机器人的全局路径规划问题，提出了一系列的改进人工鱼群算法策略，引入多策略混合机制，实现了对于传统人工鱼群算法的改进。文献[6]对于传统的蚁群算法进行改进，提出了更新优质蚂蚁信息素的原则，对挥发系数进行动态调整，并对路径进行二次规划，降低机器人运行时间和能量消耗。

一、基本人工鱼群算法行为

基本的人工鱼群算法[7]可以描述为：人工鱼个体的状态可以表示为向量X=(x1,x2,…,xn)，其中xi(i=1,2,…,n)为欲寻优的每条人工鱼，种群大小为N；Y=f(x)为当前人工鱼所在位置的食物浓度（Y为目标函数值）；每条人工鱼都试图通过觅食行为、群聚行为、追尾行为、和随机行为来找到最合适的位置来满足它们的食物要求。四种基本行为概述如下[8]：

（一）觅食行为。这是鱼群趋向食物的一种活动，设当前人工鱼状态为为其视野范围内的随机状态，的下一个时刻位置。如果食物浓度为则人工鱼按照式（1）向的方向移动一步。否则再次随机选择状态并判断是否满足上述条件。如果重复trynum次后，仍不满足前进条件，则按照（2）式随机移动一步。综上所述，觅食行为可以表示为：

（三）追尾行为。当某一条鱼或者几条鱼发现食物时，它的附近的鱼会尾随而来，进而导致更远处的鱼也会尾随过来。设当前的人工鱼状态为Xi，有NF条人工鱼位于其视野范围内，其中Xj为最优的个体对应的状态，若满足Yj/NF>δYi,则按照（4）式向Xj方向移动一步，否则继续执行觅食行为。

（四）随机行为。当人工鱼未能找到较优位置时，在其视野范围内随机选择一个状态或位置，然后游向所选择的位置。如（2）式所示，随机行为是觅食行为的缺省行为，它增加样本的多样性，可在一定程度上避免陷入局部极值。

二、栅格环境下的人工鱼群算法

采用栅格法建模，将机器人工作环境由三维环境转换成二维环境，然后按照一定大小的栅格对二维环境进行划分。我们以xoy 平面建立坐标系，规定黑色栅格表示障碍物环境，白色栅格表示机器人可以移动的区域。划分后的工作空间如下图所示，栅格左上角为机器人移动的起点，右下角为终点。

图1 机器人工作环境栅格模型

栅格法相关基本定义。

定义1 机器人只可以在相邻的栅格移动，并且不可以越过障碍物，也不能碰撞障碍物，因此机器人的移动步长为

定义4:人工鱼pi的视野其中R为视野区域半径，设为常数，S表示整个区域。

定义5:定义δ为拥挤度因子，其取值范围为（0,1）。

定义6:每条人工鱼的下一时刻的随机行，只可以发生在当前人工鱼pi的可行域(allow_area) 内, 且pi,pf∈Allow,pi,pf∉Barrier，其中Allow表示机器人的可移动区域，Barrier表示区域中的障碍物，pf表示可行域当中的位置。

三、改进人工鱼群算法

（一）加权自适应视野范围和步长。在传统的AFSA中，人工鱼的视野范围被设为固定的常量，所以在局部极值附近的人工鱼无法看到全局极值，从而使得算法后期的收敛速度变慢，并且不容易摆脱局部极值。因此提出了基于加权自适应视野范围和步长的方法，在算法的不同阶段自适应调整视野范围和移动步长，保证算法的收敛速度并防止陷入局部最优。具体如下：以有N条人工鱼为例，人工鱼记为记Ki(i=1,2,…,N)第Ki条人工鱼与j条人工鱼之间的距离为Ri,j,定义距离权值为ωi,j，人工鱼Ki的视野范围Vi可以由加权平均[9]方法得到，具体为：

在算法进行的初期，人工鱼之间的距离较大，视野范围也较大。随着算法的进行，人工鱼都向着食物浓度高的地方移动，使得鱼群越来越聚集，个体之间的距离逐渐变小。由（7）式可以看出人工鱼的视野范围也在随着算法的进行逐渐变小，从而有利于提高算法的搜索效率。

步长也是影响算法寻优精度的一个非常重要的参数，步长step越大，算法寻优精度越低；步长step越小，寻优精度越高[10]。因此和加权自适应的视野范围的思想类似，可在算法收敛的前期采用相对较大的移动步长，有利于加快算法前期的收敛速度，随着算法的进行，在算法后期采用较小的移动步长，可以提高算法寻优精度。因此对步长Step引入了一个权值如（8）式所示：

式中t为当前时刻的迭代次数，TotalIter为总的迭代次数。从（8）式可以看出，算法在不同的阶段，权值会相应的调整，进而调整移动步长。

（二）路径优化算子。针对路径规划的轨迹中存在的路径冗长的问题，给出了一种路径优化算子来优化得到的轨迹。设p(kx,ky)为第k 时刻求解的最优鱼群位置坐标，n为栅格地图矩阵的维数，kt 为已经优化的解的个数。goal(x,y) 是目标点的位置坐标。优化算子R(t)可以描述为[11]：

（三）改进人工鱼群算法的实现步骤。

Step1.初始化人工鱼群参数，包括鱼群规模N、人工鱼移动步长step、视野visual拥挤度因子δ以及最大迭代次数等。

Step2.公告板初始化，计算出每条人工鱼的适应度值，通过比较将最优的个体的值及其位置信息在公告板当中记录下来。

Step3.参数调整，根据式（7）、（8）计算视野和步长。

Step4.人工鱼执行觅食行为、群聚行为、追尾行为和随机行为并更新位置。

Step5.路径优化，根据(9)、（10）、（11）式对算法获得的路径进行优化。

Step6.检查终止条件。若满足终止条件，则终止迭代过程并输出最优解，否则返回到step3。

四、仿真验证

使用栅格法分别建立（10*10）和（20*20）的环境，障碍物覆盖率分别为20%和35%。设定参数如下：鱼群规模N=50，视野和拥挤度因子的初始值分别为visual=10,δ=0.618，蚁群算法中蚂蚁的个数Nant=50。由图2、图3和图4的对比可以看出（10*10）栅格环境下，改进后算法规划的路径明显优于传统鱼群算法和蚁群算法，并且解决了传统鱼群算法和蚁群算法存在的局部路径冗长现象。从表1 的数据可以看出，改进后算法的最优路径比传统算法优化了9.23%，比蚁群算法规划的路径优化了12.58%。

图2 10＊10传统AFSA规划结果

图3 10＊10改进AFSA规划结果

图4 10＊10蚁群算法规划结果

图5 20＊20蚁群算法规划结果

图6 20＊20传统AFSA规划结果

在（20*20）栅格环境下，如图6所示，传统人工鱼群算法虽然可以规划出路径但是仍然存在路径冗长现象。同样，蚁群算法规划出的路径也存在这种现象，并且用时较长。改进后的人工鱼群算法在最优路径长度上相比传统人工鱼群算法优化了9.11%，比蚁群算法优化了8.1%。这些数据充分表明改进人工鱼群算法在移动机器人路径规划中的优越性。

图7 20＊20改进AFSA规划结果

表1 栅格环境算法比较

五、结论

针对传统人工鱼群算法收敛速度慢、寻优精度低、易陷入局部最优等不足进行改进，设计了加权自适应的视野范围和步长，使得算法在前期进行快速的大范围搜索，后期则着重最优值的收敛，提高了算法的全局搜索能力和精度。针对算法规划的局部路径存在冗长的现象，采用了路径优化算子策略，对于规划后的曲线进行进一步优化，以消除局部路径冗长的现象。仿真结果表明，改进算法在收敛速度以及寻优精度上相比传统算法和蚁群算法均有明显的改善。