基于改进粒子群蜣螂算法的机器人路径规划研究

摘 要：在机器人路径规划中，粒子群算法（Particle Swarm Optimization，PSO）是一种常用的算法。然而在迭代后期粒子群算法会出现粒子多样性下降和易陷入局部最优解的情况。为解决以上问题，本文提出了一种改进的粒子群蜣螂算法。建立栅格地图模型对机器人进行路径规划，在粒子群算法中加入动态非线性调整惯性权重系数，引入惩罚系数来建立适应度函数，并与引入了莱维飞行进行改进的蜣螂算法相结合，以增强算法的搜索能力。试验仿真结果表明，与已有的粒子群算法相比，本文提出的改进粒子群蜣螂算法适用性更强，能够找到更短的最优路径。

关键词：路径规划；蜣螂算法；粒子群算法；莱维飞行

中图分类号：TP 242" " " " " 文献标志码：A

移动机器人在各个领域中得到广泛应用，其导航的核心环节是路径规划，具有重要的研究价值。针对路径规划问题，目前已有的方法包括Dijkstra算法、改进A*算法和快速扩展随机树（Rapidly-exploring Random Tree， RRT*）算法等。群体智能算法优化也应用于路径规划领域，例如魏冠伟[1]提出的改进型人工神经网络，王梓强[2]提出的改进遗传算法，赵甜甜[3]提出的改进粒子群（Particle Swarm Optimization，PSO）算法等。

这些方法虽然提高了路径规划质量，但是仍然存在不足，尤其是粒子群算法容易陷入局部最优。因此，本文提出一种改进的粒子群蜣螂算法，利用迭代次数动态调整粒子群的惯性权重，引入莱维飞行对蜣螂偷窃行为进行改进，提高算法的搜索能力。结合粒子群的全局搜索和蜣螂算法的局部优化来规划最优路径。

1 环境建立

本文采用栅格地图构建移动机器人的工作环境，20 m×

20 m格栅地图如图1所示，白色栅格为自由栅格，黑色栅格为障碍物栅格，每个白色栅格均可选中成为路径点，将机器人简化为1个很小的质点。路径规划的任务是在有障碍物的环境中为机器人找到1条从起点至终点的最优路径。

2 粒子群算法

2.1 基本粒子群算法

粒子群算法起源于模拟鱼类或鸟类的觅食行为，假设在D维空间中有m个粒子，在第k次迭代中第i个粒子的位置向量为xik=（xk i1，xk i2，...，xk id），其中i=1，2，…，m。粒子的速度用向量表示为vik=（vk i1，vk i2，...，vk id），其中i=1，2，…，m。粒子根据自身的位置向量、速度向量、每个粒子的历史信息以及种群信息在算法迭代的过程中不断更新自己的位置。

算法更新过程如公式（1）、公式（2）所示。

=ω+c1r1（Pbest-）+c2r2（Gbest-） （1）

式中：vk+1 id 为当第k+1次迭代时第i个粒子的速度，k为迭代次数；ω为惯性权重；vk id为当第k次迭代时第i个粒子的速度；c1为粒子群算法中的学习因子；r1为分布在[0～1]的随机数；Pbest为个体已知最优解；xk id为第k次迭代时第i个粒子的位置；c2为粒子群算法中的学习因子； r2为分布在[0～1]的随机数；Gbest为群体已知最优解。

=+ " " " " " " " " " " " " " "（2）

式中：xk+1 id为第k+1次迭代第i个粒子的位置。

2.2 动态非线性递减惯性权重

惯性权重是影响算法全局搜索与局部搜索能力、收敛速度与精度的重要参数。当种群处于进化早期时，需要比较快的速度以便于全局搜索；当种群处于进化后期时，需要比较慢的速度以便于局部搜索。文献[4]提出了一种非线性递减的惯性权重系数，使粒子能更细致地搜索优化目标，如公式（3）所示。

（3）

式中：ωmax、ωmin为惯性权重的最大值和最小值；K为最大迭代次数。

本文算法在公式（3）的基础上添加了自适应因子，如公式（4）所示。

（4）

式中：ωk+1第k+1次迭代的惯性权重；ωk为第k次迭代的惯性权重；n为调节参数；ϕ为指数函数对权重系数的影响程度；β为指数函数的递减速度；幂函数保证惯性权重在迭代初期较大，有助于全局搜索，在迭代后期较小，促进局部搜索，加快收敛速度；指数函数ϕ‧exp（-βk）提供了一种平滑的递减方式，增强了搜索的适应性。

2.3 适应度函数

路径规划的目标是找到1条最短且比较平滑的路径，该路径能够避开所有障碍物，并连接起点和终点。路径长度的计算过程如公式（5）所示。

（5）

式中：f1为1个粒子与其所有相邻点之间距离的和；d为当前粒子位置；xi、yi为粒子现在的坐标，i为粒子起始位置；xi+1、yi+1为粒子下一个位置的坐标。

为减少机器人与障碍物的碰撞次数，本文引入惩罚函数。当机器人与障碍物碰撞时惩罚因子变大时，生成碰撞路径的概率变小，惩罚函数f2如公式（6）所示。

（6）

式中：N为生成的路线和障碍物的碰撞次数；M为1个较大的常数。

路径的平滑程度是在路径规划中的1个重要指标，因此引入路径平滑程度，避免机器人路径波动过大。路径平滑程度计算过程如公式（7）所示。

（7）

式中：f3为生成路线上夹角值之和，其和越小，平滑度越高；Pi+1、Pi和Pi-1分别为第i+1、i和i-1个粒子的坐标。

综合所得适应度函数f如公式（8）所示。

f=η‧f1+ε‧f2+γ‧f3 " " " "（8）

式中：η、ε和γ分别为各自函数的加权因子，范围均为0～1，η+ε+γ=1。

3 蜣螂算法

蜣螂算法（Dung Beetle Optimizer，DBO）[5]灵感来自蜣螂的不同行为。算法将种群划分为滚球、觅食、繁衍和偷窃4个组群分别进行优化。4种蜣螂种群的分布如图2所示。

3.1 滚球蜣螂

滚球蜣螂可分为无障碍模式和障碍模式2种工作模式。当采用无障碍模式时蜣螂的位置更新公式如公式（9）所示。

xit+1=xit+α‧ξ‧xit-1+b‧|xit-xtworst| " " " " （9）

式中：xit+1为当第t+1次迭代时蜣螂的位置；xit为当第t次迭代时第i只蜣螂的位置；t为当前迭代次数；α为自然系数，取-1或1，当α为-1时与原方向偏离，当α为1时与原方向无偏差；ξ为偏转系数，ξ∈（0，0.2）；xit-1为当第t-1次迭代时蜣螂的位置；b为常数，b∈（0，1），本文中为0.3；xtworst为适应度最差的蜣螂位置；|xit-xtworst|为模拟光强的变化。

当有障碍物时蜣螂的位置更新过程如公式（10）所示。

xit+1=xit+tanθ|xit-xit-1| " " " （10）

式中： θ为随机数，θ∈[0，π]；tanθ为遇到障碍后蜣螂重新调整的方向，当或π时，不更新当前位置。

3.2 繁殖蜣螂

DBO利用雌蜣螂的产卵行为来模拟算法中种群的繁殖过程，其繁殖是根据边界选择策略进行模拟的，如公式（11）所示。

（11）

式中：Lb*、Ub*分别为产卵区的上边界与下边界；xtgbest为当前局部最优位置；T为最大迭代次数；Lb、Ub分别为搜索空间的上边界和下边界。

根据公式（11）可知，蜣螂的繁殖区域会随着迭代进行调整，繁殖蜣螂的位置也进行调整，如公式（12）所示。

Bit+1=xtgbest+b1‧（Bit-Lb*）+b2‧（Bit-Ub*） （12）

式中：Bit+1为当第t+1次迭代时第i个子代的位置；b1、b2为2个大小为1×D的独立随机向量，D为维数；Bit为第i个子代当第t次迭代时的位置。

3.3 觅食蜣螂

小蜣螂成熟后会寻找食物，觅食区域的更新过程如公式（13）所示。

（13）

式中： Lbl、Ubl分别为最优觅食区域的下边界和上边界；xtlbest为当前种群局部最优位置。

小蜣螂的位置更新过程如公式（14）所示。

xit+1=xit+C1‧（xit-Lbl）+C2‧（xit-Lbl） " " （14）

式中：C1为服从正态分布的随机数，即C1～N（0，1）；C2为1×D∈（0，1）的随机向量。

3.4 偷窃蜣螂

有一些蜣螂会偷窃种群中其他蜣螂的食物，偷窃蜣螂位置更新定义如公式（15）所示。

xit+1=xtlbest+S‧g‧（|xit-xtgbest|+|xit-xtbest|） " "（15）

式中：S为常数值；g为1×D的随机向量。

3.5 莱维飞行

莱维飞行是一种随机行走，其步数是由步长决定的。莱维飞行是一种非高斯的随机过程，其具有遍历性和随机性，其平稳增量服从莱维分布。其主要原理是模拟自然界中昆虫的飞行行为，即无规则地向任意方向前进任意距离。该行为能够扩大搜索范围，提升效率。

根据偷窃蜣螂的位置更新公式可知，其搜索步长为固定值，可能会陷入局部最优。因此引入莱维飞行可以有效提高算法的全局搜索能力，防止种群陷入局部最优。根据Mantegna方法，莱维分布的步长如公式（16）所示。

（16）

式中：λ为莱维分布的参数，取值为1≤λ≤3，λ一般取值为1.5；u、v为服从正态分布的随机变量，如公式（17）所示。

（17）

式中：u∶N（0，σu2）为均值为0、方差为σu2的正态分布随机变量；v∶N（0，σu2）为均值为0、方差为σv2的正态分布随机变量；Γ为伽马函数；Γ的计算方法如公式（18）所示。

Γ（1+λ）=∫0∞wλe-1dw " " " " " "（18）

式中：w为积分变量。

引入莱维飞行后蜣螂偷窃位置更新如公式（19）所示。

xit+1=Levy（λ）‧xtlbest+S‧g‧（|xit-xtgbest|+|xit-xtbest|） （19）

4 试验仿真和结果分析

为了验证文中提出的改进粒子群蜣螂算法在路径规划问题中的有效性，与传统粒子群算法进行对比。采用栅格法构建1张环境大小为 20 m×20 m的地图，其中黑色区域为障碍物，白色区域为自由区域。相邻栅格距离为1 m。坐标（0，0）为原点，从左上角至右下角依次编号，坐标（1，1）为起点，坐标（20，20）为终点。

本文在粒子群算法的基础上融合了蜣螂优化算法中的蜣螂滚球、繁殖、觅食和偷窃行为，结合了粒子群算法和蜣螂算法的优点。具体操作步骤如下。1）确定地图各个节点的坐标位置。2）初始化参数，将种群划分为4个子群，设定粒子速度和位置。3）计算粒子的适应度并根据适应度值更新粒子最优解以及全局最优解。4）更新惯性权重。5）根据融合了莱维飞行的蜣螂算法对各个子群进行位置更新。6）判断是否满足终止条件，如果是，那么算法结束并输出结果，否则返回第三步。

在同一张栅格地图中对2种算法进行试验，其路径规划比较如图3所示，黑色直线表示2种算法生成的路径轨迹。由图3可知，2种算法都到达目标点，但是粒子群算法规划的路径长度更长，路径波动更明显。在路径规划中，采用本文算法，路径平滑程度更高，路径长度更短。

粒子群与改进粒子群蜣螂算法对比如图4所示，由图4可知，与传统粒子群算法相比，改进粒子群蜣螂算法在收敛速度和最优值方面都具有明显优势。在迭代初期，改进粒子群蜣螂算法收敛速度更快，最终找到了更优的解，说明改进算法在全局搜索和局部优化方面均优于传统算法。

将2种算法各自运行50次，结果见表1。

表1 2种算法结果对比

算法 最优路径 均值 方差

粒子群算法 31.752 6 37.142 5 130.520 7

改进粒子群蜣螂算法 27.102 5 32.576 5 110.254 1

由上文可知，与本文算法的最优路径相比，原粒子群算法的最优路径更短，方差更小，稳定性更高，其生成的路径更适于机器人的路径规划。

5 结论

在机器人路径规划问题中，传统的粒子群算法存在迭代后期粒子多样性下降、容易陷入局部最优解等问题，本文提出一种改进粒子群蜣螂算法。采用动态非线性惯性权重，引入惩罚系数建立适应度函数；在粒子群算法中融合蜣螂优化算法中的滚球、繁殖、觅食和偷窃行为，结合莱维飞行来优化全局搜索能力，采用划分子群的方法提高算法性能。仿真和分析结果表明，与传统粒子群算法相比，本文算法在移动机器人路径规划中生成的路径平滑度更高，距离更短，适用性更强。

参考文献

[1]魏冠伟，付梦印.基于神经网络的机器人路径规划算法[J].计算机仿真，2010，27（7）：112-116.

[2]王梓强，胡晓光，李晓筱，等.移动机器人全局路径规划算法综述[J].计算机科学，2021，48（10）：19-29.

[3]赵甜甜，王思明.基于改进PSO算法的移动机器人路径规划[J].传感器与微系统，2018，37（2）：57-60.

[4]张万绪，张向兰，李莹.基于改进粒子群算法的智能机器人路径规划[J].计算机应用，2014，34（2）：510-513.

[5]XUE J K，SHEN B.Dung" bele" optimizer：a" new" metaheuristic

algorithm for global optimization[J]. The Journal of Supercomputing，

2023，79（7）：7305−7336.