基于改进LPSO混合算法的多机器人编队

仇国庆+牛婷+寇倩倩

摘 要：针对领航跟随法和基于行为法在机器人编队控制上的缺点，采用了混合编队方法即动态偏转角度φ值的虚拟领航跟随法结合基于行为法，能弥补传统领航跟随法的缺陷，可以保持队形的稳定，形成队形反馈，在两种编队方法结合的基础上，加入混合算法进行在线优化，该混合算法是在PSO算法的基础上改进惯性权重公式，加速收敛速率和解决易掉进局部最优的缺陷；同时引入能进行长短离搜索的莱维飞行，该混合算法能进一步加快粒子跳出局部最优，避免陷入早熟的情况，从而有效的优化机器人编队的路径，可以使机器人的编队时间缩短。实验仿真成果证实，所采用的方法的可行性和有用性。

关键词：编队控制；粒子群算法；惯性权重；莱维飞行

引言

近年来，多机器人编队控制[1]是已经成为多机器人协作的重要研究方向之一。编队控制[2]是指机器人以一定的队形避开环境的约束向目标点运动的控制技术，很多学者根据任务需求，提出许多经典方法，包含有领航跟随（leader-follower）[3-4]基于行为法（behavior-based）[5]、人工势场法[6]、虚拟结构法（virtual-structure）等。文献[7]在虚拟领航者的基础上加入分散控制算法，但是仍然无法保证队形的稳定性，文献[8]提出特定领航者的编队方法，但是该算法要在一定的充分条件和收敛区间才能发挥作用，文献[9]提出了改进的人工势场法的編队控制，通过沿墙导航法来控制机器人的队形变换，机器人无法到达最优路径，上述研究虽然都可以完成机器人的编队控制，但是很少会在线对机器人的路径做优化。

针对上述问题，提出了一种用莱维飞行算法结合惯性权重对数递减的粒子群算法来进行多机器人编队控制，该方法的思想是当领航者的角度发生变化时，跟随者能适应其角度的变化，不会发生掉队的现象，队形保持稳定，同时对粒子群算法的公式做改进，以对数递减函数做粒子群算法的惯性权重，可以使收敛速度有一定的提高，莱维飞行的引入，可以增加种群的搜索能力，避免早熟，得到最佳的机器人路径。

1 混合编队控制

1.1 基于动态φ值的虚拟领航跟随法

由于领航跟随法比较简单、容易理解，所以就受到研究编队控制人员的青睐，它的主要原理[10]是选取当中某个机器人作为leader，另外剩余的机器人作为follower，设定领航者（leader）和跟随者（follower） 运动位置关系，然后follower以固定的距离和方向跟随leader，形成一定的队形。但是这种方法太依赖于领航者，一旦领航者出现故障，那么机器人编队的队形就无法保持，且该方法无法形成反馈和只能求解局部最优而不是全局最优。动态偏转角度φ值的虚拟领航跟随法能弥补其缺点，所示当领航者遇到阻碍，偏转角度太大，跟随者可以自适应的改变自己的角度，迅速到达队形点。

1.2 基于行为法

基于行为法[11]是有几个子行为组成，它有明确的队形反馈。但是也存在着一些不足，没有固定的数学模型，导致行为难以融合，即机器人躲避障碍物的时候和向目标点移动有可能很难同时进行，所以队形的稳定性就无法控制。

1.3 混合编队方法

针对前面所述的两种方法的优缺点，本文提出了动态偏转角度 φ值的虚拟领航跟随法，同时结合基于行为法的机器人编队控制，两者之间相互互补，完成编队任务。

当领航机器人遇到障碍物时，会改变其原有的方向，如果偏转角度过大，会使跟随者产生掉队或者回退的现象，采用动态偏转角度φ值的虚拟领航跟随法，可以使跟随者始终和领航者保持相同的偏转角度φ，产生相同的弧形，稳定队形，同时在动态偏转角度φ值的虚拟领航跟随法上加入基于行为法，可以防止机器人进入死锁状态，通过基于行为法的随机扰动行为和通向目标点的行为，使机器人脱离死锁，形成完整的队形。

2 改进的LPSO（Levy Particle Swarm Optimization）算法

2.1 改进的PSO（Particle Swarm Optimization）算法

式中β为对数调整因子，取1.2。K为当前代次数，对数递减的ωi的变化是先减少缓慢后加速减小，因此它可以使全局和局部的搜索能力有所改善，并加速收敛速度和提高收敛精度。

二是对改进适应度函数，它在算法中占有很高的地位，其性能可以反映粒子本身的好坏程度，本文所采用的就是在机器人原本路径的基础上加入稳定度因子、光滑度因子，最后对所有的参数进行加权平均，其公式：F=α×f1+β×f2+γ×f3，α、β、γ分别为的加权因子，可以通过调节α、β、γ来决定各自函数占的比重，且它们都是大于或者等于零，且小于1的实数。f1为机器人的路径长度，f2为稳定函数，与粒子直线到目标点遇到障碍物的个数有关，f2=M，M是一个较大的为起点到终点的直线路径上的障碍物之和，f3路径光滑度函数，f3=πr+πr，n1为机器人在原始方向上改变为45度的次数之和，n2为在原始方向上改变为90度的次数之和，r为机器人的半径。f1在公式中占有的很高的地位，因此α的取值就比较高，f2其次，β就比α低一个数量级，f3几乎可以不考虑，γ为接近或者等于0，仿真试验中α为0.9，β为0.09，γ为0.001。

2.2 莱维飞行

Levy飞行是服从Levy分布的随机搜索路径[13]，既能进行短距离也能进行长距离的搜索，现很多优化的领域都已在使用，主要原因是因为它不仅能扩大搜索的范围，也可以增加种群的多样性，因此采用莱维飞行能跳出局部最优点[14]。

2.3 混合算法的机器人编队控制

在机器人编队控制中，引入莱维飞行的改进的PSO混合算法，可以使机器人避免陷入局部极小点，并迅速找到最优解，机器人能找到一条最优路径到达目标点，混合算法优化机器人编队的步骤：

Step1：初始化种群，包括各参数N、x、v、Tmax；

Step2：计算适应度函数F，找到每个粒子的局部最优和整体最优；

Step3：根據具有对数递减的惯性权重粒子群公式更新粒子的位置和速度；

Step4：粒子更新迭代的次数是否大于10，如果大于10，则执行Step5，否则执行Step6；

Step5：进行莱维飞行算法，重复Step2 和Step3；

Step6：判断迭代的次数，如若大于Tmax，则程序结束，否则转向Step2。

3 仿真成果和分析

为了检验本文所采用算法的具体效果，在VC6.0的基础上对其进行仿真测试，在7×7的仿真测试环境下，并与传统的MPLA编队算法进行比较分析。

MPLA算法[15]是在传统的LFB编队的基础上，加入多智能体粒子群算法（MAPSO），MAPSO是将多个Agent智能体与PSO算法结合，引入邻居的概念，加强粒子与其他粒子的相互通信，改变粒子本身的行为，使其多样性增加，同时利用邻居间的信息完成搜索到最优值。以下是两种算法的比较仿真图，这两种算法在多个复杂障碍物中的仿真结果如图1和图2。图中矩形和圆形分别代表障碍物，黑色的点代表领航机器人。

在两种算法中，设定机器人以三角形的队形开始运行，仿真过程中，机器人可以迅速到达三角形的队形点，躲避障碍物完成编队，但是两种算法相比较，从仿真图可以看出机器人在简单障碍物和复杂障碍物的情况下，机器人所走的路径不同，在改进的LPSO算法下，机器人的路径得到优化，因此本文所采用算法的编队路径效果优于MPLA算法。

为了更好的表现所采用算法优越性，表1记录了简单障碍物和复杂障碍物下的两种算法的性能指标，即路径长度、仿真时间和转角次数。

由表1可以看出，本文所采用算法的转角次数少，机器人路径的稳定性和光滑性得到提高，同时队形保持的效果更为明显，在运动过程中，不会出现多次的拐角震荡，保持稳定的队形向前移动；仿真时间少于MPLA算法，可见其收敛速度快于MPLA，机器人能迅速到达目标点，完成编队的效率也有所提高；机器人所走的路径步数也不同，且本文算法的路径步数小于MPLA算法的步数，证实改进的LPSO算法能使机器人选择最佳路径，使其到达目标点所走的步数少，获得的最优路径也比MPLA短。

4 结束语

把动态偏转角度φ值的虚拟领航跟随法，与基于行为法相结合，形成队形反馈，可以减少掉队和保持队形，在编队控制中，本文采用对惯性权重和适应度函数做改进的PSO算法对路径规划，并在此基础上引入莱维飞行，加快收敛速度，跳出局部极值，得到最优路径。实验仿真研究表明，本文算法能使机器人很快找到最优路径到达最终点，达成编队要求。

参考文献

[1]韩光胜，韩佳彤.多机器人编队的研究与实现[D].北京：北京工业大学，2010.

[2]董胜龙，陈卫东，席裕庚.多机器人编队的分布式控制系统[J].机器人，2000，22（6）：433-438.

[3]Yu W W， Chen G R， CAO M. Distributed leader- follower flocking control for multi-agent dynamic a systems with time varying velocities[J].Systems and Control Letter，2010，59（9）：543-552.

[4]Ren D H， Lu G Z. Consideration on formation control[J].Control and Decision Making， 2005 2005，20（6）：601-606.

[5]FRESLUND J，MATARIC M J. A general algorithm for robot formations using local sensing and minimal communication robotics and automation[J].IEEE Transactions on Robotics and Automation，2002，18（5）：837-846.

[6]杨丽，曹志强，谭民.不确定环境下多机器人的动态编队控制[J].机器人，2010，32（2）：283-288.

[7]高芹，郑新娟，钟毅，等.基于PSO算法虚拟Leader的多机器人的编队控制[J].武汉理工大学学报，2014，36（2）：136-140.

[8]杜柏阳，张良国，孙一杰，等.基于特定领航者的多机器人编队控制方法[J].电光与控制，2015，22（9）：72-76.

[9]周自维，周冰，赵雪.基于改进人工势场的多机器人编队控制[J].科技创新与应用，2015，33.

[10]付帅. 动态环境下的多机器人编队控制方法的研究[J].计算机仿真，2014，31（12）：384-387.

[11]瞿勇，宋业新，张建军.一类模糊多目标双矩阵对策的粒子群优化算法[J].海军工程大学学报，2009（3）：6-11.

[12]杨娇，叶春明.应用新型萤火虫算法求解Job-shop调度问题[J].计算机工程与应用，2013，49（11）：213-215.

[13]Yang X S. Nature-inspired metaheuristic algorithm[M].2nded.Frome：Luniver Press，2010：16-29.

[14]王庆喜，郭晓波.基于莱维飞行的粒子群优化算法[J].计算机应用研究，2015，33.

[15]唐贤伦，刘念慈，邓露，等.基于MAPSO的混合式多机器人编队控制[J].华中科技大学学报（自然科版），2015，43（7）：104-107.

作者简介：仇国庆（1963-），男，重庆人，副教授，硕士，主要从事现场总线控制、智能仪器仪表及控制装置、运动控制系统。

寇倩倩（1991-），女，晋运城人，硕士研究生，主要研究方向：交通流的数据挖掘。