1、第 21 卷 第 1 期2023 年 2 月福建工程学院学报Journal of Fujian University of TechnologyVol21 No1Feb 2023doi:103969/jissn16724348202301011改进沙猫群优化算法的机器人路径规划贾鹤鸣1，李永超1，游进华1，李政邦2，饶洪华1，文昌盛1(1 三明学院 信息工程学院，福建 三明 365004;2 福建工程学院 计算机科学与数学学院，福建 福州 350118)摘要:为了寻找更优的机器人移动路径，将沙猫群优化算法与三次样条插值方法进行融合，对沙猫群优化算法进行改进。在改进的沙猫群优化算法中，利用混沌映
2、射的均匀性初始化种群以提高种群多样性;通过融合互利共生和莱维飞行策略减少局部最优解的消极影响，提高算法的收敛速度和精度。通过两种仿真实验对比 6 种优化算法的实验数据，结果表明，改进的沙猫群优化算法的最优解、最差解和平均解都优于对比算法，验证了改进沙猫群优化算法对于解决移动机器人路径规划问题的有效性和工程实用性。关键词:机器人路径规划;沙猫群优化算法;三次样条插值;混沌映射;互利共生;莱维飞行中图分类号:TP18文献标志码:A文章编号:16724348(2023)01007206obot path planning based on improved sand cat swarm optimi
3、zation algorithmJIA Heming1，LI Yongchao1，YOU Jinhua1，LI Zhengbang2，AO Honghua1，WEN Changsheng1(1 Department of Information Engineering，Sanming University，Sanming 365004，China;2 School of Computer Science and Mathematics，Fujian University of Technology，Fuzhou 350118，China)Abstract:In order to find a
4、better robot moving path，the sand cat swarm optimization algorithm was combinedwith the cubic spline interpolation method to improve the sand cat swarm optimization algorithm In the im-proved sand cat swarm optimization algorithm，the uniformity of chaotic mapping was used to initialize the pop-ulati
5、on to improve the population diversity Secondly，by integrating mutualism and introducing Levy flightstrategy，the negative impact of local optimal solution was reduced and the convergence speed and accuracy ofthe algorithm were improved In two simulation experiments，the experimental data of the six o
6、ptimization algo-rithms were compared esults show that the optimal solution，the worst solution and the average solution of theimproved sand cat swarm optimization algorithm were all better than those of the comparison algorithm，whichverifies the effectiveness and engineering practicability of the im
7、proved sand cat swarm optimization algorithmfor solving the path planning problem of mobile robotsKeywords:robot path planning;sand cat swarm optimization algorithm;cubic spline interpolation;chaoticmapping;mutual symbiosis;Levy flight收稿日期:20221206基金项目:福建省自然科学基金面上项目(2021J011128)第一作者简介:贾鹤鸣(1983)，男，黑龙
8、江哈尔滨人，教授，博士，研究方向:群体智能优化算法及工程应用。路径规划是移动机器人研究的一大技术难题，优秀的路径规划技术能够减少移动机器人的成本、提高效率以及安全性能1。国内外就移动机器人的路径规划问题开展了诸多研究，提出了自由空间法2、强化学习方法3、深度学习方法4 和人工势场法5 等方法。但是，当空间里的障碍物数量过多时，自由空间法的复杂度也会过高;在计算复杂障碍空间时，强化学习方法无法在数据量较小的情况下进行高效的路径规划;人工势场法会出现目标不可达的问题;障碍空间不完第 1 期贾鹤鸣，等:改进沙猫群优化算法的机器人路径规划全可见或者不稳定时，深度学习方法也不能很好地解决。群体智能算法在
9、求解复杂空间时具有独特的优势，如教与学优化算法6、蚁群优化算法7、人工蜂群优化算法8 等。但是，未经优化改进的算法容易产生经过障碍物的无效路径，且容易陷入局部最优等缺点。因此，寻找收敛速度更快、路线更好的改进群体智能算法是学者们共同的研究方向。2022 年 Amir Seyyedabbasi 提出一种模拟沙猫捕食的群体智能算法 沙猫群优化算法11(sand cat swarm optimization，SCSO)。SCSO 作为最近提出的群体智能优化算法，有着优于传统算法的优化性能，但是容易被局部最优点干扰，导致算法易陷入局部最优，无法找到全局最优解。当遇到的障碍物较为复杂时，使用圆弧9 或直
10、线10 进行分段式产生的移动路线折点较多，在平滑性和连续性上效果一般。而使用三次样条插值拟合出的动态路径更加平滑，可以保证机器人具有更好的应急机动性能。本研究将沙猫群优化算法进行改进，并与三次样条插值方法进行融合，提高算法的收敛速度和精度，更加有效解决机器人路径规划问题。1沙猫群智能优化算法沙猫群智能优化算法的灵感来源于沙猫对于低频噪声的检测能力，沙猫无论在地面上还是在地面下，都能凭借它独特的能力来找到猎物。11搜索猎物控制探索与开发阶段过渡的最终参数和主要参数是，当 1 时，沙猫对进行猎物搜索。沙猫对猎物的搜索依赖于低频噪声的释放，假设沙猫的灵敏度范围rG?从 0 到 2 kHz。sM值的灵
11、感来自沙猫的听觉特征，假设其值为 2。iterc为当前迭代，itermax为最大迭代，r?显示了每只猫的敏感范围。r?用于勘探或开发阶段的操作，rand(0，1)表示 0 到 1 的随机数。r?G=sMsMitercitermax，(1)?=2r?Grand(0，1)r?G(2)r?=r?Grand(0，1)(3)每只沙猫根据最佳候选位置(Pos?bc)和当前位置(Pos?c)及其灵敏度范围(r?)更新自己的位置。因此，沙猫能够找到其他可能的最佳猎物位置。Pos?(t+1)=r?(Pos?bc(t)rand(0，1)Pos?c(t)(4)12攻击猎物当 1 时，沙猫进行攻击猎物。首先，利用最佳
12、位置Pos?bc与当前位置Pos?c来生成一个随机位置Pos?rnd。假设沙猫的灵敏度范围是一个圆，利用轮盘赌法给每只沙猫随机选择一个角度，最后通过公式(6)实现攻击猎物。其中，随机位置能够保证沙猫向猎物靠近，随机角度有助于算法跳出局部最优。Pos?rnd=rand(0，1)Pos?b(t)Pos?c(t)(5)Pos?(t+1)=Pos?b(t)r?Pos?rndcos()(6)2改良的沙猫群智能优化算法沙猫群优化算法在计算过程中也存在着探索和开发之间的矛盾。种群在初始化时候的分布情况决定了算法的收敛精度与速度。为了使沙猫种群在搜索空间均匀分布，本研究引入了混沌映射来提高种群初始化的分布多样
13、性，引入互利共生策略和莱维飞行策略，加强个体与最优个体之间的信息交流，扩大开采的周密性，提高算法的寻优精度和速度。21混沌映射初始化混沌映射12 具有良好的随机性、规律性和遍历性，不但能使得种群具有良好的多样性，也能使得算法在全局搜索能力、收敛速度、收敛精度上都有所提高。改进公式如下:Ck+1=Ck/a，0Cka(1Ck)/(1a)，aCk1(7)Pos?id=lb+(ublb)Cid(8)式中，a 一般取 04;Pos?id表示第 i 只沙猫的第 d 维的位置;ub 和 lb 表示种群的搜索范围;Cid表示由式(7)产生的混沌序列。22引入互利共生策略沙猫群优化算法在攻击猎物时，会通过轮盘赌
14、法随机选择角度来靠近猎物进行攻击。但这样的攻击方式随机性较大，也易于陷入局部最优，互利共生策略12 通过加强个体与最优个体的信息交流，可以消除沙猫攻击猎物时的消极影响，提高37福建工程学院学报第 21 卷沙猫的寻优精度和收敛速度。改进公式如下:Pos?new=Pos?bc+(Pos?bcbfMV)(9)MV=(Pos?bc+Pos?rnd)/2(10)式中，Pos?new为更新后的位置;Pos?bc为最优个体的位置;Pos?rnd为随机个体的位置;bf 表示利益因子，随机选择 1 或 2，表示可能部分受益或全部受益;MV表示最优个体与随机个体的信息交流。23引入莱维飞行策略沙猫群优化算法在搜索
15、猎物和攻击猎物时，都是通过随机角度进行的，导致算法会遗漏部分较优的解，降低收敛精度。为了增强搜索的周密性，消除局部最优解的消极影响，本算法引入莱维飞行策略13，既加强了算法的局部搜索能力，又能保证算法在全局搜索时具有良好的周密性。改进公式如下:Pos?new=Pos?bc+Pos?bcPos?Levylcos(2l)(11)Pos?Levy=1(Pos?rndPos?bc)(12)=(1+)sin2()(1+)2212(13)式中，Pos?new为更新后的个体位置;Pos?bc表示最优个体的位置;Pos?Levy表示莱维飞行位置;l 是(0，1)的随机数;Pos?rnd表示随机个体的位置;是服
16、从N(0，2)的随机数，其中 为伽马函数，为(0，2)的随机数。3基于三次样条插值的路径规划采用三次样条插值的方法可以保证机器人在面临紧急情况时具有更好的动力学特性，优越于用直线与圆弧拟合机器人路径。31三次样条插值在区间 a，b上取 n+1 个结点，并假设 a=x1x2xn=b，假如 s(x)满足:s(x)C2 a，b;s(xi)=fi(i=1，2，n);xi，xi+1代表一个三次多项式。三次样条插值函数是一个分段式的三次多项式，在所有的区间 xi，xi+1 上都可以写成:s(x)=aix3+bix2+cix+di(i=1，2，n1)，其中 ai，bi，ci，di为待定系数，因此 s(x)共有 4n 个需要确定的系数。为了求得 s(x)，需要有对应的 4n 个条件。由 s(xi)=fi(i=1，2，n)可得 n+1 个插值条件。由 s(x)C2 a，b可知，s(x)在区间 a，b上是二阶连续可导，那么 s(xi)=s+(xi)，i=1，2，n1，这里可以得到 n1 个条件。进一步的，s(x)在区间 a，b上也是一阶连续可导且连续的，那么:s(xi)=s+(xi)，i=1，2，n1s(