基于多策略改进鼠群算法的机器人路径规划*

解瑞云，海本斋

(1.河南工学院电缆工程学院，新乡 453000；
2.河南师范大学教育学部，新乡 453000)

近年来，众多的元启发式算法被应用于求解复杂环境中机器人路径规划问题。移动机器人路径规划问题往往可简化为一个带有复杂约束的非线性规划优化问题[1]。引入转弯角度控制因子，采用遗传算法求解了移动机器人路径规划[2]。粒子群优化算法[3]和人工蜂群算法[4]可提高求解移动机器人路径规划问题的寻优精度。从改善算法的寻优角度出发，文献中提出了众多的改进算法用于求解移动机器人路径规划问题。例如：在粒子群算法中嵌入GA的选择、交叉、变异算子和BFO算法提出改进PSO算法[5]，嵌入非线性收敛因子和PSO算法及量子化思想的改进灰狼算法[6]，改进蚁群算法[7-9]，动态分组蚁群规划算法[10]，烟花混合蚁群算法[11]，粒子群-蚁群融合算法[12]，嵌入量子变异算子的量子风驱动优化算法[13]，改进ACO算法[14]，改进生物地理学算法[15]，引入烟花爆炸变异的自适应果蝇算法[16]等。

由文献中结果可看出，相比原有的算法，通过变异算子改进的算法均能够提高了算法在路径规划全局寻优能力，可快速地获取最佳路径，寻优精度、稳定性和鲁棒性均得到改善。

受启发于鼠群的追逐猎物和攻击猎物的行为，DHIMAN等[17]提出了鼠群优化算法(rat swarm optimizer，RSO)。该算法求解高维问题(如移动机器人路径)，存在全局寻优能力较低和早熟现象。为克服RSO算法求解移动机器人路径规划问题的不足，文中首先对RSO算法进行了详细概述，其次，详细介绍了多策略改进鼠群优化(MRSO)算法，并提出了基于MRSO的路径规划算法。最后，在不同地图环境下，评估了MRSO算法的路径寻优能力。

在RSO算法中，老鼠群体利用具备的生活习性，通过发现猎物，然后，鼠群对猎物进行追逐，并对其攻击猎物以此达到获取食物的目的。RSO算法主要包含了鼠群的追逐猎物和攻击猎物的两种行为。算法的主要原理如下：

(1)追逐猎物。当猎物被离其最近的老鼠(最佳位置)发现时，其余老鼠会根据自身当前位置，不断地靠近离猎物最近的老鼠，通过群居竞争行为来追逐猎物，从而利用更新自身的位置来获取最佳的搜索位置。这种追逐猎物行为的数学表达如式(1)～式(3)所示。

P=A×Pi(t)+C×(Pbest(t)-Pi(t))

(1)

(2)

C=2×rand

(3)

式中，Pbest(t)为第t次迭代时老鼠群体的当前最佳位置；
Pi(t)为第i只老鼠在t次迭代时老鼠群体的当前搜索位置；
α为[1,5]内的随机数；
rand为[0,1]内的随机数；
t为当前迭代次数；
tmax为最大迭代次数；
A为线性衰减勘探参数；
C为[0,2]内的随机开发参数。

(2)攻击猎物。老鼠群体靠近猎物后，频繁地更新自身的位置获取最佳的攻击位置，对猎物进行攻击，达到获得猎物的目的。这种老鼠攻击猎物过程的数学模型如式(4)所示。

Pi(t+1)=|Pbest(t)-P|

(4)

式中，Pi(t+1)为第i只老鼠在t+1次时的当前位置。

2.1 旋转小孔成像反向学习(RPOBL)攻击搜索策略

在RSO算法中，随着迭代次数的增加，老鼠群体无限接近全局最佳解时，老鼠群多样性的丧失会使得算法难以跳出局部极值。标准小孔成像反向学习策略可增强算法的局部寻优能力，增加跳出局部最优的概率[18]。

如图1所示，受小孔成像启发的反向学习策略，假设物体位于x轴上[a,b]范围内，高度为h1的物体在C处，投影位置为x，在沿x轴的O处放置一个带有小孔的小孔屏A，物体通过小孔可以在x轴上接收屏B中呈现一个高度为h2的物体倒像位于D处，投影位置为x*(即x的反向点)。由三角相似原理，可得标准小孔成像数学公式如式(5)～式(7)所示。

(5)

令n=h1/h2，则式(5)可等效为式(6)。

(6)

当n=1时，可得：

x*=a+b-x

(7)

图1 标准的小孔成像反向学习策略

式(7)为标准反向学习策略。显然，标准反向学习策略为标准小孔反向学习策略的一种特例。但是，可以明显的看出，当接收屏B固定时，通过标准小孔成像反向学习，x只能产生对应的一个反向点x*(反向解)。这样也会造成算法种群的多样性较弱，不利于增强算法跳出局部最优。

(8)

(9)

图2 旋转小孔成像反向学习策略 图3 旋转产生的反向解

当cosθ=1时，旋转小孔成像反向学习(RPOBL)策略可转换为标准小孔成像反向学习如式(6)所示。当n=1且cosθ=1旋转小孔成像反向学习策略可转换为标准反向学习策略如式(7)所示。将式(9)扩展到D维优化问题中，得到基于旋转小孔成像反向学习策略的公式：

(10)

因此，在RSO算法中，对算法的攻击猎物位置更新方式改进为旋转小孔成像反向学习攻击位置更新方式，通过对鼠群个体的RPOBL反向学习，可丰富算法的个体的多样性，进一步提高算法的收敛效率和精度。采用旋转小孔成像反向学习攻击猎物位置更新策略如式(11)所示。

Pi(t+1)=Pi(t)+RPOBL(Pi(t))

(11)

式中，RPOBL(Pi(t))为旋转小孔成像反向学习的鼠群攻击位置；
Pi(t+1)为鼠群的攻击搜索位置。

2.2 Iterative混沌旋转小孔成像反向学习初始化策略

在RSO算法中，对鼠群初始位置随机产生，易造成鼠群位置的分布不均和种群多样性弱。Iterative混沌映射[19]初始化算法的种群，可增强算法种群的均匀分布性，提高算法的初始寻优效率和收敛精度。因此，融合Iterative混沌映射与RPOBL反向学习策略对算法种群进行初始化，可增强算法寻优精度。Iterative混沌映射如式(12)所示。

xn+1=sin(bπ/xn)

(12)

式中，b取值为(0,1)的值，通常设置为0.5。由Iterative混沌映射产生的种群x={xi,i=1,2,…,N}，xj={xj,j=1,2,…,D}，鼠群个体表示为：

xi+1,j=sin(bπ/xi,j)

(13)

式中，xi+1,j为第i+1个种群在j维上的值。

(14)

式中，[xmin,xmax]为搜索空间的下限与上限，新种群X由种群x和x*组成，对种群X择优选取排名靠前的N个最优的种群个体作为RSO算法的初始种群。

2.3 “双过渡”型非线性自适应因子

RSO算法的全局搜索能力受参数A影响，然而，参数C影响RSO算法局部搜索能力。原有的参数A是线性递减的，本身自适应协调能力较低。同时，参数C在每次迭代中是在[0,2]内的固定的任意随机数，自适应能力弱。因此，原有的参数A和C易造成算法的全局与局部搜索之间的失衡，降低算法的寻优能力。为此，引入“双平滑”过渡机制对参数A采用“双平滑”自适应非线性衰减因子，如图4所示。将RSO算法中的式(2)修改为：

(15)

式中，AS=5；
β为动态收敛调整因子，取值为0.2；
binornd为服从二项分布的随机数。

由图可知，改进后参数A整体呈现非线性衰减。迭代前期，参数A在保持缓慢的变化幅度和速度，且值较大，即鼠群群体以较大的搜索步长进行搜索，这样可以扩大鼠群的搜索空间。在AB段采用平滑过渡机制，参数A变化幅度由缓慢下降逐渐转变为急速下降阶段BC，这样有利于提升算法的收敛速度。同样地，在CD段采用平滑过渡机制，参数A由急速下降阶段BC转变为缓慢下降阶段。参数保持较小的搜索步长，这样有利于加强算法的在迭代后期的局部搜索能力。因此，通过采用“双平滑”过渡机制，增强了参数A的动态调整能力与灵活性，有利于提升算法的寻优性能。

同样地，引入“双碗式”过渡机制对参数C采用“双碗式”自适应非线性波动因子，如图5所示。将RSO算法中的式(3)修改为：

C=C0+C1×((1-t/tmax)×cos(2πt/tmax)+
γ×binornd(p,q)×t/tmax)

(16)

式中，C0和C1为参数C的调整参数且C0=0.7，C1=1.3；
γ为动态收敛调整因子，取值为0.1；
binornd为服从二项分布的随机数。

由图可知，参数C通过“双碗式”过渡机制整体呈现先降低后增加再降低的非线性自适应变化。在迭代初期AB段，参数C快速陡降与参数A缓慢下降形成较大的差异，有利于提升算法早期搜索能力。在迭代中期BC段，利用“碗式”过渡机制，参数C由快速陡降转变为适中上升阶段，这与迭代中期的参数A急速下降也形成较大差异。在迭代中后期,再次利用“碗式”过渡机制，参数C由适中上升转变为缓慢下降，但下降的幅度明显不同于参数A，具有一定的差异性。

图4 “双平滑”自适应非线性衰减因子A 图5 “双碗式”自适应非线性波动因子C

综上可知，“双平滑”和“双碗式”过渡机制可使得参数A和C形成一种动态差异性，这有利于增强算法的全局寻优能力和局部开发能力。

2.4 基于MRSO的移动机器人路径规划算法

由以上改进可知，基于MRSO的移动机器人路径规划算法流程如图6所示及步骤如下：

步骤1：初始化设置：设置栅格地图环境，初始化移动机器人的始末坐标位置，设置MSRO算法参数如：种群数量，最大迭代次数等；

步骤2：Iterative混沌映射与RPOBL反向学习策略对算法种群进行初始化如式(13)和式(14)所示，并评估初始最佳路径长度和初始最优路径信息；

步骤3：更新“双平滑”自适应非线性衰减因子A和“双碗式”自适应非线性波动因子C；

步骤4：根据式(1)，式(15)和式(16)进行鼠群追逐行为更新鼠群位置；

步骤5：
采用旋转小孔成像反向学习策略更新攻击猎物位置如式(10)和式(11)所示；

步骤6：重新评估路径适应度值更新最佳路径长度及路径信息；

步骤7：判断是否满足迭代终止条件，若是，则输出全局最佳路径长度及最优路径规划信息，反之，返回步骤3继续寻优；

步骤8：算法寻优结束，输出最优路径规划结果。

图6 基于MRSO的移动机器人路径规划算法流程

3.1 地图环境及算法参数设置

通常采用栅格法[6]来创建移动机器人路径规划地图环境。实验共选择3种不同大小规格的地图分别为：16 m×16 m(如图7a所示)，26 m×26 m(如图7b所示)和36 m×36 m(如图7c所示)。对3种地图设置相同的移动机器人路径起始点和终止点，黑色区域部分代表不可通行区域即障碍物，白色区域代表可通行区域。移动机器人路径规划的目标函数是移动机器人从起始点移动至终止点处，绕开障碍物所需要的最短移动距离。

(a) 16 m×16 m地图环境 (b) 26 m×26 m地图环境

实验选取3种著名算法即RSO[17]、TSO[20]、GWO[21]，与MRSO算法求解机器人路径规划问题进行对比分析。同时设置算法寻优种群数量为100，最大迭代次数为600，计算次数设置为20次。实验结果评价指标为路径长度的最优解、平均解、标准差、折弯次数及寻优成功率。

3.2 实验结果分析

表1～表3给出了不同大小地图的移动机器人路径规划仿真实验结果。

表1 16 m×16 m路径规划结果

表2 26 m×26 m路径规划结果

表3 36 m×36 m路径规划结果

由结果可知，对16 m×16 m，26 m×26 m和36 m×36 m的地图，MRSO算法获得的路径最优解分别为24.43 m，39.07 m，54.12 m。同时，MRSO算法获得的路径平均解分别为24.65 m，39.09 m，54.39 m。MSRO算法的路径最优解和平均解均小于RSO、TSO和GWO。TSO算法可获得排名第二好的路径最优解和平均解。对不同大小的地图环境，MRSO算法的路径标准差精度至少可达1E-02，明显优于RSO、TSO和GWO。对于16 m×16 m，26 m×26 m和36 m×36 m的地图，GWO算法的寻优成功率分别为0.8，0.65和0.75，但是RSO、TSO和MRSO的成功率均为1；
同时MRSO算法的路径规划转折次数均小于RSO、TSO和GWO算法，这说明MRSO算法的路径规划线路的平滑度更优和效率较高。因此，相比RSO、TSO和GWO算法，MRSO算法路径寻优性能最优，可提供较好的移动机器人路径规划结果。

(a) 最短路径规划 (b) 路径寻优收敛曲线

(a) 最短路径规划 (b) 路径寻优收敛曲线

(a) 最短路径规划 (b) 路径寻优收敛曲线

由图8a～图10a可知，对于所有的地图环境，MRSO算法可通过较少的转弯就能够获取更加合理的路径规划线路，路径平滑度明显优于其他算法。由图8b～图10b可知，MRSO算法可以较少的迭代次数快速的获取最短路径长度值，其收敛曲线位于RSO、TSO和GWO算法的下方，这说明MRSO算法收敛效率较高。然而，对于复杂的地图环境(26 m×26 m和36 m×36 m)，RSO收敛曲线会存在一定局部停滞现象，收敛缓慢且精度较低。与RSO算法相比，MRSO算法明显改善了RSO算法的这种局部停滞现象，提升了算法的收敛效率和收敛精度。这是因为MRSO算法采用了Iterative混沌映射与RPOBL反向学习种群初始化策略，提升了迭代初期收敛效率与精度，同时，采用了“双平滑”和“双碗式”非线性自适应因子之间实现了动态平衡调整，增强了算法的全局与局部搜索能力，提高了算法的寻优精度。

由实验结果分析可知，MRSO算法可以稳定、高效地求解复杂环境中移动机器人路径规划问题，能够提高较好的求解结果。

(1)为更好解决移动机器人路径问题，提出了基于MRSO算法的路径规划方法。

(2)提出了一种新颖的旋转小孔成像反向搜索策略，提高了算法求解移动机器人路径问题时跳出局部极的概率。

(3)路径规划仿真实验结果表明：MRSO算法能快速稳定获得最小路径长度，其路径寻优性能优于RSO、GWO和TSO算法，可以快速和高效地解决复杂环境中移动机器人路径规划问题。