基于优化人工蜂群算法的多机器人协同规划

张林

（ 深圳供电局有限公司，深圳福田，518001）

   摘要 为了提高人工蜂群算法在多机器人路径规划中的性能，本文提出了优化人工蜂群算法。提出了一种新的环境建模方法，将障碍物边缘平滑化；分析了人工蜂群算法原理，改进了新食物源的生成方法，提出了自适应的搜索因子，兼顾了大范围搜索和算法收敛速度；改进了机器人路径点的表示方法，使用位置夹角表示机器人路径点，减少了位置参数；使用加权方式将路径长度、路径平滑度、路径安全性综合为目标函数。仿真实验结果表明改进在多机器人路径规划中不仅耗时较少，而且路径也短，且随着机器人数量的增加，耗时和路径长度的差距越来越大。

   主题词 多机器人  协同规划  优化人工蜂群算法  自适应搜索因子

Vehicle Anti-collision System Based on Self-adaptive obstacle recognition

Zhang Lin

( Shenzhen Power Supply Bureau Co., Ltd. ShenZhen futian 518001, China)

    Abstract To improve property of Artificial Bee Colony algorithm in multi-robot path planning, optimized Artificial Bee Colony Algorithm is proposed. A new environment model is given, which makes barrier border smooth. Principle of Artificial Bee Colony algorithm is analyzed, adaptive searching factor is raised to improve new food source generation method, which balances searching range and convergence rate. Robot path point is improved by location angle, and by this way location parameter is lessen. Path length, path smoothness and path safety is synthesized to a goal function by weight. Simulation trial shows that path length and time cost of improved algorithm is superior to primary algorithm. And with robot quantity increasing, the gap of the two algorithms is bigger and bigger.

   Key words: Multi-robot, collaborative planning, optimized artificial bee colony algorithm, adaptive searching factor

0 引言

相比于单个机器人，多机器人系统^[1]具有诸多优势：当某一机器人出现故障时，机器人系统依然具有协调完成任务的能力，鲁棒性很强；通过机器人之间的协调，可以完成更加复杂多样的任务，效率很高；相比于制造复杂且功能强大的机器人，功能简单的多机器人成本更低，因此研究多机器人系统具有诸多的现实意义。多机器人的导航问题是多机器人系统重要的研究方向，研究多机器人路径规划问题是实现多机器人自主导航的关键。

根据机器人对工作环境的了解情况，可以将机器人路径规划分为全局路径规划和局部路径规划^[2]。全局路径规划成熟的方法包括栅格法^[3]、自由空间法^[4]、构型空间法^[5]等，栅格法解决路径规划问题简单直观，但栅格大小的选取牵扯到存储量和信息分析率，因此使用受到一定限制；自由空间法适用于障碍物较少的情况，当障碍物增加时算法复杂度增加且不易实现；构型空间法缺点是当机器人紧邻障碍物时，无法保证机器人安全性。局部路径规划成熟的方法包括人工势场法^[6]、神经网络法^[7]等，人工势场法解决机械臂路径规划具有较好效果，但是存在局部极小值和目标不可达问题；神经网络算法有点是鲁棒性强、学习能力强，但是存在数据量的要求；

本文为了研究多机器人路径的协同规划问题，受栅格法启发提出了新的环境建模法；将人工蜂群算法的新食物源生成方法、机器人路径表示方法进行改进，实现了多机器人路径短、平滑、安全且耗时少的目标。

1环境建模方法

对于已知环境的建模问题，当前使用最多的是栅格建模法，就是将工作环境划分为一定大小的栅格，只要栅格中存在障碍物（不论大小）就将其视为障碍物栅格。这种建模方法存在空间开销、计算速度与环境分辨率的矛盾。

本文提出的环境建模方法为：在工作环境中建立直角坐标系，但是不划分栅格，通过给出障碍物的顶点来区别障碍物，如图1中所示，对于圆形障碍物将其简化为一个圆点，同时给出其障碍范围。但是当机器人从顶点之间穿过时，在现实中就是机器人与障碍物相撞，为了解决这一问题，本文将障碍物的顶点进行连线，不允许机器人规划出的路径穿过连线，从而避免机器人与障碍物相撞。

图1  环境中障碍物表示方法

但是这种障碍物表示方法会增加机器人路径规划时间，也会使机器人产生运算压力，因此考虑将所有障碍物包裹在一个圆形区域内，也就是将每个障碍物都看成适当大小的圆形障碍物，如图2所示。

图2  障碍物表示方法

2 人工蜂群算法

2.1 蜂群采蜜模型

在蜂群采蜜过程中，可以分为三个组成要素和两种基本行为。三个组成要素包括食物源、雇佣蜂和非雇佣蜂，其中非雇佣蜂包括观察蜂和侦察蜂。两种基本行为是招募蜜蜂采蜜、放弃食物源。蜂群觅食的过程是：每只雇佣蜂对应一处蜜源，同时在此蜜源附近搜索新蜜源，若发现新蜜源后则放弃原蜜源；雇佣蜂将蜜源信息以摇摆舞的形式传递给观察蜂，观察蜂根据蜜源远近、花蜜丰富程度等选择蜜源；侦查蜂发现某处蜜源采集次数多而接近枯竭时就放弃此处蜜源。从数学的角度讲，雇佣蜂负责搜索局部极值，观察蜂负责选择全局极值，侦查蜂负责摆脱局部极值。

在蜜蜂采蜜过程中，两种基本行为对应两种反馈机制。当雇佣蜂发现一处花蜜丰富的蜜源时，会以摇摆舞的方式吸引蜜蜂前来采蜜，此处蜂蜜越丰富则前来采蜜的蜜蜂越多，因此招募蜜蜂采蜜行为是一种正反馈机制。但是若某一蜜源经过反复采集面临枯竭而得不到更新时，侦查蜂就会放弃此处蜜源，转而寻找其他食物源，这是一种负反馈机制。

2.2人工蜂群算法模型

首先给出人工蜂群算法^[8,9]的五个策略，而后给出算法步骤。

（1）初始化策略。算法的初始化就是给出初始食物源位置，记为（x1,x2,....,xn），其中N为食物源数量，是一个位置坐标，初始化方法为

    （1）

式中分别为可以取得的最大值和最小值，rand（0,1）为（0,1）之间的随机数。

（2）食物源评价策略。食物源评价策略是对每个食物源给出综合评价并进行比较，从而保留花粉密度大、离蜂巢近的食物源。在人工蜂群算法中食物源适应度函数为

       （2）

式中为相对于食物源的目标函数值，且。

（3）雇佣蜂搜索策略。雇佣蜂会记忆蜜源丰富的食物源传递给观察蜂，同时在此食物源附近搜索新的食物源，发现更加优质的食物源后，雇佣蜂就会抛弃原食物源。其搜索过程为

      （3）

式中为新食物源坐标，为当前食物源坐标，分别为可以取得的最大值和最小值，为随机选取的异于的另一食物源，为搜索系数且。当雇佣蜂发现新的食物源后，就会比较新旧食物源的适应度值，选择并保留适应度大的食物源，放弃适应度小的食物源。

（4）观察蜂选择策略。雇佣蜂通过摇摆舞将食物源信息传递给观察蜂，观察蜂根据这些信息计算每个食物源的适应度，再根据食物源适应度计算选择每个食物源的可能性，计算公式为

           （4）

如果此值大于某一阈值，则观察蜂选择此处食物源，否则放弃。

（5）侦查蜂觅食策略。侦查蜂觅食策略为当经过最大采蜜次数的循环后，某一食物源依旧没有得到改善更新，就会认为此处食物源经过多次采集已经枯竭，侦查蜂就会放弃这些食物源而随机产生食物源，这种觅食策略可以增加食物源多样性，使算法跳出局部极值。侦查蜂的下一食物源选择策略表达式为

   （5）

式中trial为优化次数或更新次数，limit为允许的最大选择次数。

通过以上对人工蜂群算法^[10]的分析，给出算法步骤如下。

Step1：初始化参数。给出食物源数目N、最大循环次数MaxLoop、优化限制次数limit；

Step2：产生初始食物源；

Step3：雇佣蜂觅食。在每个食物源附近搜索并计算食物源适应度值，选择优质食物源放弃劣质食物源；

Step4：观察蜂选择。观察蜂对雇佣蜂传递回的食物源信息进行比较，计算选择每个食物源的可能性，对于最大可能性最大（最优值）的食物源，分配蜜蜂前去采蜜；

Step5：侦查蜂觅食策略。若经过limit次选择最优食物源扔得不到更新，则随机产生一食物源，从而达到了摆脱局部极值的目的；

Step6：若循环次数达到上限而没到达目标点，则路径规划失败，算法结束；若多机器人均到达目标点则规划成功，算法结束。

3 优化人工蜂群算法

本节主要对新食物源的生成方法和机器人路径点的表示方法进行改进，而后以路径最短、平滑和安全等三个方面作为优化目标给出了目标函数。

3.1 新食物源生成方法改进

在人工蜂群算法中，侦查蜂对附近区域食物源的搜索方式如式（3）所示，也就是根据记忆中的两个食物源，在(-1,1)范围内随机产生一个因子进行搜索，在算法运行的前期，如此大的搜索范围可以使得侦查蜂在更大范围内搜索全局最优值，但是在算法后期，如此大的搜索范围使算法无法快速收敛到哦全局最优。

因此可以随着算法的推进，自适应的改变搜索系数的值，使其在算法前期保持较大搜索范围，在算法后期逐渐减小其搜索范围，使其能够快速收敛至全局最优。自适应搜索系数表达式为

           （6）

式中Loop为算法的当前迭代次数，MaxLoop为算法的最大迭代次数。由上式可以看出，随着算法的进行，搜索范围最终缩小为原来的1/e。

3.2 机器人路径点的表示方法

机器人路径由机器人路径点连接而成，在栅格法中，使用机器人所在栅格坐标表示机器人路径点，本文以路径平滑度作为优化的一个目标，使用坐标的方法难以对路径平滑度进行表示，因此本文提出了使用下一位置相对于当前位置的夹角表示机器人路径点，如下图所示。

图3  机器人路径点表示方法

图中绿色方块表示机器人位置，规定机器人步长恒定为StepLen，夹角1和夹角2就可以用来表示机器人当前位置点。将此方法转化为机器人坐标表示的方法为

                （7）

式中为机器人当前路径点坐标，为下一路径点坐标。为下一位置相对于当前位置夹角。

此方法将坐标表示的横纵坐标两个变量转化为夹角一个变量，简化了表示方法，减少了算法的计算过程，提高了路径规划的实时性。

3.3 目标函数及食物源评价策略

本文将路径总长度、路径平滑性、路径安全性作为优化的三个目标，使用综合加权的方法将三个目标转化为一个目标。路径平滑性使用夹角的差值表示，路劲安全性使用机器人到障碍物距离倒数表示。最终优化目标Obj为

 （8）

式中分别表示距离、安全性、平滑性权重，表示当前位置与目标点距离，表示当前位置与障碍物距离，Z为障碍物数量，Step为机器人步数。

在机器人路径规划中，机器人之间互为动态障碍物，若进行食物源评价时，若两机器人路径出现重合点，要分析是否到达此重合点，若是则将适应度值置0重新进行路径规划，否则按照式（2）计算适应度值。

4 仿真实验验证

仿真软件为Matlab，计算机配置为Intel Core i5处理器、主频2.6GHz、8G内存。设置的验证试验包括两个方面：一是验证改进人工蜂群算法相对于标准算法的用时短，二是验证改进算法的平滑性和路径长度优于标准算法。机器人起点和目标点随机产生。

参数设置。仿真的循环次数为1000，种群大小为20。在第一次验证试验中，对3个机器人进行路径规划，工作区域中含有4个不同大小的障碍物，使用建模方法将其转换为适当大小的圆形障碍物，分别使用改进人工蜂群算法和标准算法对其进行路径规划如下图所示。

（a）改进算法             （b）标准算法

图4  两种算法的规划结果

从图中可以看出，改进算法的路径平滑度明显优于标准算法，这是由于本文提出的建模方法中障碍物边缘处圆滑，使机器人没有急转弯。此次试验主要对比算法消耗的时间，将路径规划任务重复10遍，统计10次路径规划所用时间，如表1所示。

表1  算法消耗时间统计

通过以上数据可以看出，改进算法与标准算法耗时查究较大，主要有三点原因：一是机器人路径点的改进，将横纵坐标两变量转化为夹角一个变量，减少了算法运算时间；二是对搜索因子的改进在算法后期使算法快速收敛，极大减少了算法收敛时间；三是改进算法路径相对平滑且路径较短，也就是说改进算法进行路径规划循环次数比标准算法要少。这种耗时上的差距会随着机器人数量的增加而逐渐拉大。

第二次试验试验验证路径平滑度和路径长度，参数设置与试验一不变。规划三个机器人在四个障碍物环境中的路径，起始点分别为（2,2）（2,9）（7,1），相应的目标点分别为（8,9）（9,4）（2,6）。分别使用改进算法和标准算法进行路径规划，得到的结果如下所示。

（a）改进算法             （b）标准算法

图5  两种算法的规划结果

从图中明显的可以看出改进算法的路径平滑度优于标准算法。统计去10此规划出的路径长度，如下表所示。

表2  路径长度统计

从表中可以看书，改进算法的路径长度短于标注算法，主要原因包括两方面：一是环境建模方法使路径平滑，少走了弯路；二是搜索因子前期大范围的搜索保证了全局最优的发现。

5 结论

通过以上分析可以得出以下结论：（1）本文提出的环境建模方法使障碍物边缘处平滑，保证了路径的平滑性；（2）搜索因子的改进既保证了前期的大范围搜索，又减少了算法收敛时间；（3）机器人路径点表示方法减少了参数，节约了算法时间，也更适用于本文提出的环境建模方法。

参  考  文  献

[1] 吴军, 徐昕, 王健,等. 面向多机器人系统的增强学习研究进展综述[J]. 控制与决策, 2011, 26(11):1601-1610.

[2] 余勇. 基于改进蚁群算法的移动机器人路径规划研究[J]. 机械传动, 2016(7):58-61.

[3] 柴寅, 唐秋华, 邓明星,等. 机器人路径规划的栅格模型构建与蚁群算法求解[J]. 机械设计与制造, 2016(4):178-181.

[4] 王丹. 自由漂浮空间机器人路径规划研究[D]. 长春：吉林大学, 2015.

[5] 蔡佐军, 孙德宝, 秦元庆,等. 基于构型空间法的机器人路径规划研究[J]. 计算机与数字工程, 2006, 34(4):88-90.

[6]张殿富, 刘福. 基于人工势场法的路径规划方法研究及展望[J]. 计算机工程与科学, 2013, 35(6):88-95.

[7] 魏明明. 进化脉冲神经网络的路径规划研究[D]. 兰州：西北师范大学, 2013.

[8] 宁爱平, 张雪英. 人工蜂群算法的收敛性分析[J]. 控制与决策, 2013(10):1554-1558.

[9] 邱剑锋. 人工蜂群算法的改进方法与收敛性理论的研究[D]. 合肥：安徽大学, 2014.

[10] 王艳娇. 人工蜂群算法的研究与应用[D]. 哈尔滨：哈尔滨工程大学, 2013.

基金项目：教育部重大创新工程培育资金资助项目（708045）

作者简介：张林（1987-），男，江苏徐州人，硕士，高级工程师，研究方向为机器人控制技术研究、输变电领域技术研究与管理。