河南科技大学机电工程学院，河南 洛阳

收稿日期：2023年3月31日；录用日期：2023年5月24日；发布日期：2023年5月31日

摘要

针对移动机器人在不同工作环境中，收敛速度慢、易陷入局部最优值、非必要拐点多等问题，本文提出一种改进麻雀搜索算法的路径规划策略。首先，在种群初始阶段采用K-means聚类方法对麻雀个体位置进行聚类和区分，提高种群的工作效率，消除随机性的影响；其次，在危险感知转移策略中，构造一个基于正余弦函数的自适应更新表达式，避免达到局部最优；最后，提出一种拐点系统评估机制，将路径转角处的折线变换为平滑的直线，使机器人更快地到达目标。仿真和实验结果表明，所提改进算法的可靠性和优越性。

关键词

移动机器人，路径规划，麻雀搜索算法，K-Means聚类

Path Planning of Mobile Robot Based on Improved Sparrow Search Algorithm

Kun Su, Pengjun Mao, Wenhui Dan, Qian Fang, Lirui Shen

School of Mechatronics Engineering, Henan University of Science and Technology, Luoyang Henan

Received: Mar. 31^st, 2023; accepted: May 24^th, 2023; published: May 31^st, 2023

ABSTRACT

Aiming at the problems of slow convergence speed, easy to fall into local optimization, and large number of path inflection points in different working environments of mobile robots, an improved sparrow search algorithm is proposed. Firstly, the K-means clustering method is used to cluster and distinguish the individual positions of sparrows in the initial stage of population, which accelerates the work efficiency of the population and eliminates the influence of randomness. Then, in the danger perception transfer strategy, an adaptive position update formula based on the sine and cosine function is constructed to avoid falling into local optimality; Finally, an inflection point system evaluation mechanism is proposed, which transforms the polyline at the corner of the path into a smooth straight line, so as to the robot can reach the target faster. Experimental results show that the optimization efficiency of the proposed improved algorithm is significantly improved, and the path length and inflection point number are significantly reduced compared with the ant colony algorithm, the improved ant colony algorithm and the adaptive sparrow algorithm.

Keywords:Mobile Robot, Path Planning, Sparrow Search Algorithm, K-Means Clustering

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

路径规划是移动机器人导航技术的一个重要方面，也是机器人自主运动的必要功能。移动机器人路径规划的目的是为了找到一条安全且最优或者次优的路径，满足工作需求的最低代价值、最短路径或者较少的计算时间消耗、没有与障碍物的碰撞等 [1] 。国内外学者对路径规划算法进行了大量研究，当前路径规划算法可以分为传统路径规划算法和仿生群智能规划算法两大类 [2] 。传统路径规划算法有A*算法(A-star algorithm) [3] 、快速探索随机树算法 [4] 、模拟退火算法 [5] 等，随着智能仿生优化算法的发展、神经网络算法 [6] 、粒子群算法 [7] 、蚁群算法 [8] 、麻雀搜索算法(sparrow search algorithm) [9] 等在路径规划中应用越来越多。麻雀搜索算法由于其更好的收敛性，控制参数少、易于实现等特点，已成功地应用于各种工程中。

麻雀搜索算法(SSA)是由Xue和Shen提出的一种仿生智能优化算法 [10] ，该算法是受到麻雀捕食猎物的启示，模拟麻雀种群的捕食和躲避天敌行为。虽然麻雀搜索算法具有一定的自身特点，然而在应用中仍存在一些缺点，如算法的稳定性差、寻优速度慢、易陷入局部最小值等问题。Yu等 [11] 选择合适的路径初始化模型，改变发现者的位置更新公式，增强起始-终止线对路径搜索的影响，减少了盲目搜索。Liu等 [12] 引入混沌策略来增强算法种群的多样性，并使用自适应惯性权值来平衡算法的收敛速度和探索能力。Ouyanng等 [13] 提出了一种自适应螺旋飞麻雀搜索算法，提高了麻雀搜索算法的速度和精度。Yang等 [14] 提出采用混沌映射策略对种群进行初始化，设计了一种自适应t分布变异算子，对全局探勘的特性和局部开采的能力有了显著提高，有效减少局部最优地陷入。Yan等 [15] 提出了一种基于迭代局部搜索的麻雀算法，在跟踪者的全局和局部搜索阶段，分别引入可变螺旋因子与迭代局部搜索，提高了搜索精度，防止遗漏最优解。虽然上述改进策略在一定程度上避免了麻雀搜索算法陷入局部最优值，提升了算法的寻优性能，但仍存在算法求解精度不足、寻优时间长、开发能力弱等问题。

针对上述问题，本文提出一种基于改进麻雀搜索算法(KSSA)的移动机器人路径规划方法。首先采用K-means聚类方法对麻雀种群进行初始化，减少随机干扰；其次提出一种危险感知转移策略更新侦察者的位置，在更新位置的过程中，麻雀个体在不同阶段以不同的收敛速度进行位置搜索，保证算法的收敛精度，避免陷入局部最优值；最后，引入拐点系统评估机制作为算法的后处理方法，从而使最终的路径更加平滑。

2. 环境建模

为对机器人所处的环境进行更好的路径规划，需要对环境进行地图建模，建模方法通常有自由空间法、拓扑法、栅格法等。由于栅格法可以简单而精确地表示各种不规则障碍物的信息，并在实验中取得了良好的效果，因此将其用于二维环境建模。在二维环境地图上，将移动机器人视为质点，在执行任务时，将工作区域划分为栅格，如图1所示，以20 × 20栅格地图为例。

图1. 机器人工作环境栅格地图

机器人可以在栅格上移动，栅格坐标由中心点表示，白色栅格表示为机器人可以自由移动的空间，机器人允许通行；黑色栅格为约束区域，表示道路上有障碍物。当机器人移动到图中的网格时，去掉最后一个移动方向，机器人可以向当前位置附近的任何方向移动，如下图2(a)所示。机器人从A点移动到B点的过程中，存在障碍物，且机器人在移动的过程中绕过障碍物或者穿越障碍物，则认为该路径为有效路径，如图2(b)和图2(d)所示。若机器人在移动过程中与障碍物有接触，则认为该路径为无效路径，如图2(c)所示。

图2. 机器人行走路径示意图

3. 基本麻雀搜索算法及改进

3.1. 基本麻雀搜索算法

在SSA算法中，麻雀都有一个重要的位置属性，他表现在整个麻雀种群觅食过程中，觅食过程可以抽象为一个发现者–加入者–侦察者的模式。发现者通常拥有比较高的适应度值与能量储存，它引导加入者进行觅食和探索。加入者跟随具有最佳适应度值的发现者寻找食物，增加自己的能量储备和适应度值。同时一些加入者也会监视侦察者争夺食物。侦察者在意识到处于危险位置时，向种群发出预警，迅速移动到更安全、更有利的位置，如果预警值大于安全值，侦察者将加入者带离危险区域。同时，种群中的麻雀也会随机靠近其他麻雀，达到反繁殖行为的目的。

3.1.1. 发现者位置更新

由于发现者负责整个搜索食物并负责整个种群的移动，因此与其它麻雀相比，发现者可以在更大距离内进行探索。在进行迭代时，位置更新表达式如下：

$X_i^t=\{\begin{array}{ll}{X}_i^t\cdot \exp \left(\frac{-i}{\alpha \cdot ite{r}_{\max }}\right)\hfill & R<ST\hfill \\ X_i^t+Q\cdot L\hfill & R\ge ST\hfill \end{array}$ (1)

式中，t表示迭代次数、 $ite{r}_{\max }$ 为最大迭代次数、 $\alpha \in \left(0,1\right)$ ， $R\in \left[0,1\right]$ 、 $ST\in \left[0.5,1\right]$ 分别表示预警值和安全值。Q为服从正态分布的随机数， $L$ 为 $1\times d$ 的矩阵，其内部元素都为1。

3.1.2. 加入者位置更新

加入者跟随发现者搜索食物，其位置更新公式与发现者相联系，表达式如下：

$X_{\text{i}}^{t+1}=\{\begin{array}{ll}Q\cdot \exp \left(\frac{X_r^t-X_i^t}{i^2}\right)\hfill & i>\frac{n}{2}\hfill \\ X_b^{t+1}+\left|X_i^t-X_b^{t+1}\right|A^{+}L\hfill & i\le \frac{n}{2}\hfill \end{array}$ (2)

式中， $X_b^{t\text{+1}}$ 表示t + 1代中发现者的最优位置、 $X_r^t$ 表示目前t代全局最差麻雀个体位置， $A$ 是一个 $1\times d$ 的多维矩阵(其内部元素均为1或−1)，且当 $i>n/2$ 时，第i个麻雀处于最差的位置，适应度值最低的麻雀可能会饿死，否则第i个麻雀会跟随发现者移动到最佳位置附近进行觅食。

3.1.3. 侦察者位置更新

在麻雀种群中，选取10%~20%左右的麻雀个体充当侦察者，其位置更新表达式如下：

$X_i^{t+1}=\{\begin{array}{ll}{X}_b^t+\beta \left|X_i^t-X_b^t\right|\hfill & f_i>f_b\hfill \\ X_i^t+k\frac{\left|X_i^t-X_r^t\right|}{\left(f_i-f_r\right)+\epsilon }\hfill & f_i=f_b\hfill \end{array}$ (3)

式中， $\beta$ 是一个步长控制参数，是服从均值为0，方差为1的标准正态分布的随机数。 $K\in \left[-1,1\right]$ 的一个随机数， $f_i$ 表示当前麻雀个体的适应度值， $f_r$ 和 $f_b$ 则表示目前全局最差和最佳的适应度值， $\epsilon$ 是避免除数为零而选择的较小数， $f_i>f_b$ 时代表群体边缘的麻雀，没有处于最佳觅食区域，危险来临时，它会移动到最佳区域， $f_i=f_b$ 时表示麻雀处于比较危险的位置，需要移动到安全位置。

3.2. 改进麻雀搜索算法

3.2.1. 采用K-Means聚类方法对麻雀种群初始化

麻雀搜索算法的种群角色少，初始优化工作量大，而且取决于随机初始化的种群位置。因此，利用K-means对麻雀个体的初始位置进行分配和更新，使其工作有序，提高了种群的容错率。

K-means的思想是对于给定的类别数目k，首先给出初始划分，通过迭代改变样本和簇的隶属关系，使得每一次改进之后的划分都比前一次好 [16] 。基本实施过程如下：

1) 选择初始的k个类别中心 ${\mu }_1,{\mu }_2,\cdot \cdot \cdot ,{\mu }_k$ 。

2) 对于每个样本 $X_i$ ，将其标记为距离类别中心最近的类别 ${\mu }_i$ ，距离为d。

3) 将每个隶属该类别的样本均值更新为类别中心。

4) 计算误差平方和 $\sigma$ 。

迭代终止条件： $\sigma$ 不再改变或者类别中心 ${\mu }_i$ 不再变化。

麻雀个体到类别中心欧式距离d，类别中心u以及聚类中心的及其各元素的误差 $\sigma$ 平方和的计算公式如下：

$d\left(x_i,{\mu }_j\right)=\sqrt{{\displaystyle {\sum }_{j=1}^n{\left(x_i-{\mu }_j\right)}^2}}$ (4)

${\mu }_j=\frac{1}{n}{\displaystyle {\sum }_{x\in A_j}x}$ (5)

$\sigma ={{\displaystyle {\sum }_{j=1}^k{\displaystyle {\sum }_{x_i\in A_j}\left|x_i-{\mu }_j\right|}}}^2$ (6)

在麻雀搜索算法中引入K-means聚类算法，通过循环使用不同的聚类中心来实现对麻雀种群的初始化，保证了算法的寻优精度，削弱了种群初始化的影响。

3.2.2. 基于正余弦函数的自适应位置更新

在麻雀种群中，发现者、加入者以及侦察者的角色不是固定不变的，加入者可以转变为发现者，发现者可以转变为加入者。发现者和加入者都可以转变为侦察者，去感知风险，帮助种群转移到更好，更安全的位置。因此针对侦察者的位置更新公式，提出一种基于正余弦函数的自适应位置更新公式。

从上述公式(4)中可以看出当麻雀具有最佳适应度值时，它会移动到自己位置附近的位置。移动距离取决于最佳位置和最差位置之间的距离差与最佳适应度和最差适应度之间的距离差的比率。在这种情况下，由于移动搜索的距离有限，往往容易陷入局部最优情况。因此，文中提出基于正余弦函数的自适应调节算法，构造的调节因子公式如下：

$\text{s}=\mu +\cos \left(t^3/\max \_ite{r}^3\right)-t^2/\max \_ite{r}^2$ (7)

式中， $\mu \in \left[0,1\right]$ ，本文选择1，由图3可知，s值在早期迭代中相对较大，而整体下降速度较慢，便于算法在早期进行探索。只要迭代过程不断发展，整体递减速度逐渐加快，就会实现快速收敛。

图3. s函数曲线图

将调节因子和正余弦函数相结合，引入侦察者的位置更新中，如式(8)所示：

$X_i^{t+1}=\{\begin{array}{ll}{X}_B^t+s\cdot \sin \left(r\right)\cdot \left|X_i^t-X_B^t\right|\hfill & f_i>f_b\hfill \\ X_i^t+s\cdot \cos \left(r\right)\cdot \frac{\left|X_i^t-X_B^t\right|}{\left(f_i-f_r\right)}\hfill & f_i=f_b\hfill \end{array}$ (8)

式中，r是介于0和2π之间的随机数。如式(8)所示，当前麻雀个体具有最佳位置时，经过余弦函数和调节因子的扰动，避免陷入局部最优值。当前侦察者没有处于最优位置时，正弦波动和调节因子帮助麻雀个体以不同的收敛速度进行搜索，直到下一次迭代中接近最优值。

3.2.3. 拐点系统评估机制

如果一个移动机器人路径规划任务创造了了几个不必要的拐角，那么将增加整个规划路径的长度，且对移动机器人带来不可预测的风险。为了进一步平滑路径，减少不必要的拐点，本文提出了一种新的拐点系统评估机制作为算法的后处理方法。

整个拐点系统评估机制分为两个阶段：检测障碍物和选择路径。具体流程如下：

1) 选择一个点，依次扩展三个点；

2) 连接第一点和第三点，判断第一点和第三点的连线是否与障碍物相交；

3) 如果连线与障碍物不相交，则删除第二点；如果与障碍物相交，跳出循环并继续评估路径。

该机制的执行过程如图4所示。

图4. 拐点系统评估机制过程图

3.2.4. 改进麻雀算法的流程描述

本文所改进的麻雀搜索算法步骤如下：

1) 初始化麻雀种群数、设置发现者比例、警戒者比例、定义迭代次数。

2) 计算每个麻雀个体的适应度值并找出最大值和最小值(添加拐点系统评估机制)。

3) 通过K-means对种群进行聚类和区分。

4) 通过式(1)、(2)、(9)对麻雀个体位置进行更新。

5) 计算适应度值，并更新个体最优和最差适应度值及其位置。

6) 判断是否达到最大迭代次数，如果是则执行步骤(7)，否则执行步骤(4)。

7) 最终输出麻雀个体的最佳位置和最优适应度值。

文中改进麻雀搜索算法的流程如下图5所示。

图5. KSSA算法流程图

4. 仿真实验结果分析

4.1. 仿真实验

为测试算法的寻优性能 [17] ，设定麻雀种群规模数为50，最大迭代次数为300，发现者比例r = 0.3，侦察者比例s = 0.2，安全值ST = 0.8，起始点、终止点等初始参数值后，对障碍物位置不同的工作环境进行实验验证，其结果如图6所示。

图6. 移动机器人路径规划实验

为了验证了文中提出的KSSA算法的可行性和优越性，采用4种路径规划算法——IACO、GA-ACO、ISSA和本文算法，在Matlab仿真平台上进行30次实验(算法参数如表1所示)，将实验结果与IACO、GA-ACO、ISSA算法进行对比，验证本文算法的优越性，实验结果如图7和图8所示。

表1. 参数初始值

图7. 相同环境下四种算法的路径规划实验

图8. 栅格环境下四种算法收敛曲线变化趋势图

由上图7和图8知，GA-ACO、IACO、KSSA规划的路径存在冗余，算法运行时间较长，其中IACO规划路径过长，GA-ACO算法运行时间长、效率低，ISSA包含的非必要拐点个数多，而KSSA则能在路径最短、用时最少的前提下，减少非必要的拐点，提高路径的平滑度。

表2所示为相同条件下30次路径规划的比较和统计结果，综合分析可知，在多次路径规划实验中，IACO收敛速度较快，但早熟概率最高，极易导致路径质量严重下滑；GA-ACO收敛速度最慢，且路径平滑度较差；ISSA的收敛速度和平滑度有所改善，但非必要拐点个数；KSSA则能在搜索到最短路径的同时，大幅缩短寻路时间，减少必要的拐点，提高路径平滑度，有效降低算法出现早熟的概率。

表2. 算法测试结果

4.2. 结论

本文针对SSA算法寻优速度慢、易陷入局部最优值、路径平滑度差等问题，通过K-means对种群进行初始化，降低了盲目搜索性，提高种群的工作效率；基于此，设计符合根据环境变化的自适应位置更新表达式，麻雀个体在不同阶段以不同的收敛速度进行位置搜索，保证算法的收敛精度；最后引入拐点系统评估机制对路径进行平滑处理，减少非必要的拐点，保证机器人工作的安全性。实验结果表明，与传统算法相比，在获得路径质量更优的前提下，基于改进的麻雀搜索算法规划的路径更短、更平滑、寻优效率更高，证实了本文算法在不同环境中作为移动机器人路径规划算法的有效性与优越性。

文章引用

苏 坤,毛鹏军,淡文慧,方 骞,申礼瑞. 基于改进麻雀搜索算法的移动机器人路径规划
Path Planning of Mobile Robot Based on Improved Sparrow Search Algorithm[J]. 建模与仿真, 2023, 12(03): 2930-2939. https://doi.org/10.12677/MOS.2023.123270

参考文献