混沌狼群围捕算法的车间机器人导航路径规划

周 璟

（无锡工艺职业技术学院电子信息系，江苏 宜兴 214200）

1 引言

随着社会的进步和生产力发展，人类对机器人的活动范围和工作效率提出了更高要求。机器人精确导航是机器人从事一切生产活动的基础，路径规划是导航的首要工作[1]。研究机器人导航规划问题，对提高机器人工作效率具有明显意义。

机器人导航包括机器人定位、工作地图创建、路径规划等三个方面，主要研究机器人导航路径规划方法。机器人导航规划的研究热点集中在群智能算法方面，包括粒子群算法、蚁群算法、鱼群算法、蜂群算法、狼群围捕算法等，文献[2]将差分进化算法用于提高粒子群算法多样性，降低了导航路径长度；文献[3]对蚁群算法信息素提出了多种改进方法，规划出的路径更短、更平滑；文献[4]在鱼群算法中引入方向算子和免疫记忆操作，使路径规划时间更短、稳定性更好；文献[5]提出了自适应搜索因子改进人工蜂群算法，兼顾算法搜索与收敛，应用于多机器人协同规划用时较少。相比于其他群智能算法，狼的个体智力更高，狼群捕食行为更能够体现强强联合，群智能算法更加高效。但是基本狼群围捕算法也存在初始化不合理、易陷入局部极值等问题。

研究了车间移动机器人导航规划问题，建立了机器人导航规划模型，使用狼群围捕算法进行求解。针对狼群围捕算法易陷入局部极值和初始化不合理问题，改进了算法初始化方法、狼群围捕步长、种群进化方法等方面，算法性能得到了改进，路径规划结果得到了提高。

2 狼群围捕算法

狼群围捕算法是模拟狼群猎食行为提出的算法，猎食行为被区分为“游走”“召唤”“围攻”等行为，按照“强者多得食”的分配方式进行优胜劣汰[6-7]。

2.1 狼群围捕算法原理

记搜索空间为d维空间，第i只狼的位置信息为Pi=（pi1，pi2，L，pid），狼群规模为SN，对于求解最小值问题，记目标函数为f（P），则猎物浓度（适应度函数）为Y=1/f（P）。第i只狼的猎物浓度记为Yi，头领狼猎物浓度为Ylead。则狼群围捕算法由以下行为完成：

（1）狼群初始化与竞做头领狼。使用式（1）进行狼群位置初始化。

式中：pij—第 i只狼第 j维初始化位置；rand—（0，1）间的随机数；puj、plj—分别为第j维位置的上下限。计算所有狼的适应度函数，适应度最大的狼为头领狼，指挥狼群的围捕行为。

（2）搜寻行为。为了提高食物搜寻效率，狼向四面八方h个方向前进一步，并计算各方向的适应度值Yik（k=1，2，L，h），当存在Yik大于当前位置适应度时，选择最大的Yik作为前进方向，则：

（3）奔走行为。在头领狼号召下，围攻狼向头领狼奔走，奔走过程中，若某一位置适应度值大于头领狼，则立马替代头领狼指挥狼群。奔走方式为：

（4）围攻行为。在围攻狼向头领狼奔走过程中，当其与头领狼的距离小于某一阈值Slimit时，奔走行为转换为围攻行为。距离阈值计算方法为：

式中：Slimit—距离阈值；maxj、minj—第 j维最大值与最小值；ω—距

离控制因子。围攻行为的移动方式为：

式中：Stepc—围攻步长，λ∈［-1，1］—一个随机数。在围攻过程中，若某一位置适应度值高于头领狼，则代替头领狼指挥狼群围捕猎物。

（5）狼群更新。狼群更新模拟自然选择过程中，使用“强者生存”法则，选择适应度最差的m只狼淘汰，而后使用随机生成方式产生m只狼补充。

2.2 狼群围捕算法流程

根据上节介绍，给出基本狼群围捕算法流程，如图1所示。

图1 基本狼群围捕算法流程Fig.1 Flow of Basic Wolf Pack Besieging Algorithm

3 混沌狼群围捕算法的提出

在基本狼群围捕算法基础上，从三个方面对狼群围捕算法进行改进，分别为种群初始化方法、围捕步长和种群进化方法。

3.1 基于混沌映射的种群初始化

在基本狼群围捕算法中，狼群初始化使用随机函数实现，这可能导致种群初始分布不均匀，影响算法的寻优能力。混沌映射具有遍历性和类随机性[8]，因此提出改进混沌映射方法初始化狼群位置。Tent映射结构简单，分布较均匀，遍历性好。表达式为：

式中：a∈（0，1），当 x1∈（0，1）时系统处于混沌状态。

设置参数a=0.5、x1=0.32，将Tent映射迭代200次得数据序列，如图2所示。

图2 Tent映射数据Fig.2 Tent Mapping Data

由图2可以看出，数据在（0，1）间的遍历性很好，但是数据主要集中在（0.2～0.8）之间，两端部分数据取值较少，鉴于这一问题，引入随机方程对Tent映射进行扰动，为：

设置参数a=0.5、x1=0.32，将改进Tent映射迭代200次得数据序列，如图3所示。

图3 改进Tent映射数据Fig.3 Improved Tent Mapping Data

对比图2和图3可知，改进Tent映射既保持了良好的遍历性，同时相比于Tent映射的分布更加均匀，因此使用随机方程扰动的Tent映射初始化狼群位置，使狼群在搜索空间中分布均匀，有利于算法初期对整个区域的完全搜索。

3.2 Levy飞行改进围攻步长

Levy飞行特点是长时间短距离的来回搜索和偶尔的长距离搜索相互穿插[9]，对于大范围的搜索空间和有限的搜索个体，levy飞行这一特点既能满足小范围的细致搜索，防止遗失目标，也能够使用偶尔的长距离跳出局部极值。

Levy飞行步长，如图4所示。从图中可以看出，levy飞行穿插进行了长时间小步长搜索和偶尔大步长搜索。

图4 Levy飞行步长Fig.4 Levy Fighting Step-length

将levy飞行应用于狼群围攻行为，得：

式中：s—levy飞行步长。Levy飞行长时间小距离来回搜索有利于算法长期进行细致搜索，防止遗失目标；偶尔的长距离搜索可以使算法跳出局部极值。

3.3 基于遗传思想的种群进化方法

在基本狼群围捕算法中，使用“强者生存，弱者淘汰”的生存法则，对于被淘汰个体，使用随机生成的方式进行补充。这种个体补充方式使种群进化效率较低，借鉴遗传思想提出了种群进化方法[10]，可以引导算法朝着收敛的方向进化。

（1）父代的选择。记每次淘汰的狼数为m，每一次迭代后对狼群依据适应度排序，选择适应度最高的m头狼作为一组父代Xi，另外一组父代Yi在其余狼中随机选取，这样既能遗传高适应度个体的优势，又能通过随机选择增加种群多样性。

（2）染色体的构造。使用十进制方法构造染色体，记其维数为 L，则 X=（x1，x2，…，xL）。

（3）染色体重组。有性生殖通过父代基因重组产生下一代，传统的重组方法有离散重组、中间重组、混杂重组等，在中间重组基础上改进，提出了权值可调节重组法。记父代染色体分别为Xi与Xj，权值可调整重组法为：

式中：α、β—两个父代的权重，权重可以根据问题特点和父代的适应度进行设置，使子代进化具有针对性和方向性；权值也可以随机设置，增强进化的随机性，增加物种多样性。

将由式（10）产生的m个个体补充到狼群中，保持种群规模不变。由以上分析可以看出，通过遗传方式维持种群规模并促进种群进化，既可以遗传优秀个体的优势，同时可以控制种群进化方向，在算法收敛和搜索方面都优于基本算法。

本节对算法的三点改进，没有改变算法的流程，因此改进算法流程图与基本算法一致，在此不再给出。

4 机器人导航问题建模

4.1 环境建模

依据机器人尺寸、障碍物尺寸及分布等情况，通过投影的方式将机器人工作的三维空间简化为二维空间，使用矢量建模方法建立工作环境的二维模型。某一工作区域的环境模型，如图5所示。

图5 环境模型Fig.5 Environment Model

图中多边形与圆形表示障碍物区域，S表示出发点，T表示目标点，pi点为中间点。

4.2 路径表示与适应度函数

正常情况下机器人路径由一系列二维点组成，为了与这里的寻优算法吻合且降低路径规划复杂度，将二维搜索问题降为一维，如图5所示。在起始点与目标点之间作n-1条Y轴的平行线，将ST分成n段，只要规划出每条平行线的纵坐标，就实现了路径规划。

将路径长度作为路径规划目标，路径长度d（p）各段路径的累加和，即：

式中：yi—机器人每一步的纵坐标；驻=dST/n—平行线间的距离。

4.3 边界约束与碰撞检测

狼群在寻优过程中，可能超出边界，因此狼群每更新完一次就要进行一次检测，当狼的位置超越边界值时则将狼的位置定义为边界值，否则不进行干涉。

前文将障碍物建模为多边形和圆形两种情况，因此碰撞检测也分这两种情况分析。

（1）多边形障碍物的碰撞检测。狼群围捕算法规划出某段路径后，首先判断多边形各顶点与路径端点横坐标关系，若处于路径端点之外则障碍物对此段路径无影响；若多边形各顶点在路径端点内，则判断各顶点在路径同侧还是两侧，若处于路径同侧则不发生碰撞，若处于路径两侧则发生碰撞。

（2）圆形障碍物的碰撞检测。计算路径上任意一点到圆心的距离，若距离大于圆半径则路径安全，否则路径发生碰撞。

5 仿真验证及分析

机器人导航路径规划验证在在MATLAB仿真环境下进行，设想机器人在车间内工作或者为家庭服务机器人，按照此类机器人行驶能力和工作环境大小将机器人工作区域设置为（200×120）m，区域内设置10个障碍物，障碍物位置及形状随机生成，起点S坐标为（0，0），目标点 T坐标为（180，120）。狼群围捕算法参数设置为：种群规模SN=30，算法最大迭代次数MaxCycle=250，搜寻步长Stepa=0.1，奔走步长Stepb=0.2，搜寻方向h=4。

分别使用基本狼群围捕算法和混沌狼群围捕算法搜索最优路径，分别运行100次。在迭代过程中，两种算法的最优路径长度随迭代次数的变化情况，如图6所示。

图6 路径长度随迭代次数变化图Fig.6 Variation Condition of Path Length with Iteration Time

由图6可以看出，基本狼群围捕算法迭代80次后路径长度不再下降，算法陷入局部极值而无法跳出。混沌狼群围捕算法在迭代至55次时路径长度不再下降，算法搜索到最优路径。这是因为混沌狼群围捕算法中levy飞行具有偶尔长距离搜索的特点，使算法具有跳出局部极值的能力；且遗传思想可以引导狼群进化方向，朝算法收敛方向进化，使混沌狼群围捕算法收敛更快。

混沌狼群围捕算法与基本狼群围捕算法搜索的最优路径，如图7所示。

图7 基本狼群围捕算法与混沌狼群围捕算法规划路径Fig.7 Path Planned by Basic Wolf Pack Besieging Algorithm and Chaotic Wolf Pack Besieging Algorithm

由图7可以看出，混沌狼群围捕算法规划出的路径明显短于基本狼群围捕算法，这意味着混沌狼群围捕算法的寻优能力优于基本狼群围捕算法，这是因为混沌隐射的狼群初始化方法使狼群分布均匀，利于整个区域完全搜索；且levy飞行长时间短距离搜索特点，使算法能够长时间细致搜索，防止丢失目标，使算法寻优精度更高。

统计基本狼群围捕算法与混沌狼群围捕算法100次搜索路径的最短长度、最长长度、平均长度与搜索到最短路径耗时，结果如表1所示。

表1 两种算法的性能统计Tab.1 Property Statistics of the Two Algorithms

由表1可知，混沌狼群围捕算法最短路径比基本狼群围捕算法最短路径长度减少了16.7%，寻优耗时减少了37.5%。结合表1、图6与图7的结果，充分验证了混沌狼群算法在寻优精度和寻优耗时上的双重优势，这是因为使用Tent映射初始化狼群，使狼群分布更加均匀，增加了对整个区域的搜索能力；其次levy飞行长时间短距离来回搜索与偶尔大步长搜索相互穿插，即实现了细致搜索，又可以以大步长跳出局部极值，以上两种改进都增加了算法寻优能力和精度；再者，使用遗传思想引导狼群进化方向，使狼群算法朝着收敛方向进化，增加了算法收敛速度。基于以上原因，与传统狼群围捕算法相比，混沌狼群算法在寻优精度和收敛速度上均具有明显优势。

5 结论

研究了移动机器人导航规划问题，建立了机器人导航问题模型，使用混沌狼群围捕算法进行求解，经仿真验证得到了以下结论：（1）基于混沌映射的种群初始化方法可以使狼群分布均匀，利于算法对整个区域的完全搜索；（2）levy飞行长时间短距离来回搜索与偶尔大步长搜索相互穿插，既有利于算法进行长时间细致搜索，又保持了跳出局部极值的能力；（3）混沌狼群围捕算法规划的路径长度比传统狼群算法减少了16.7%，耗时减少了37.5%，证明了混沌狼群算法在收敛速度和寻优精度上的优势。