混合改进人工蜂群算法的机器人路径规划研究

陈信华，孟冠军，张 伟，张 磊

（合肥工业大学机械工程学院，安徽 合肥 230009）

1 引言

路径规划是机器人研究领域中的核心内容之一，针对路径规划的算法研究也是该领域的热点和难点。根据路径规划的不同目的其可以划分为两种形式，分别为点到点的路径规划和完全遍历路径规划[1]。

这里主要研究点到点的路径规划，根据一定准则寻找一条从起点到终点的最优路径。经典的机器人路径规划方法主要包括：多边形拟合（Polygonal Approximation，PA）法[2]、可视图（Visibility Graph，VG）法[3]、人工势场（Artificial Potential Field，APF）法等[4]。虽然这些算法在路径规划方面取得了不错的效果，但都存在着一定的局限性，如易于陷入局部最小值、搜索效率较低等问题。为了改进经典算法在路径规划运用中存在的不足，智能算法得到研究人员的关注。包括蚁群算法（Ant Colony Optimization，ACO）[5]、混合蛙跳算法（Shufled Frog Leaping Algorithm，SFLA）[6]、遗传算法（Genetic Algorithm）[7]在内的各种群体智能算法在路径规划的运用中越来越普遍，也能获得较理想的结果。但同样需要进一步提高算法的收敛速度，避免早熟现象。

人工蜂群（Artificial Bee Colony，ABC）算法是一种基于蜜蜂的觅食行为而启发的算法，在2005年由Karaboga小组为优化代数问题而提出[8]。

该算法具有结构相对简单且易于实现、控制参数较少，无需梯度信息等优点，已经成功应用于任务调度、求解TSP问题、图像处理等众多领域。近年来，人工蜂群算法也被尝试运用于机器人路径规划的研究上，但是标准ABC算法存在易于陷入局部最优，进化后期收敛速度慢等不足，限制了ABC算法在实际中的引用。

为了提高ABC算法在求解路径规划时获取最优解的能力，包括克服早熟、提高收敛速度和寻优精度，使用了新的搜索机制。利用APF算法能在目标点附近产生引力以及在障碍物附近产生斥力的特点，将APF 与ABC 算法相结合以提高算法求解速度。但APF算法和ABC算法存在易于陷入局部最优的缺点，因此针对ABC算法做出改进，将Levy分布与柯西分布分别引入食物源更新公式和随机搜索公式中，增强了ABC算法局部和全局搜索能力。

最后提出一种混合改进人工蜂群算法（Hybrid Improved Artificial Bee Colony，HIABC），通过实验证明了算法能够提高在求解机器人路径规划时解的质量。

2 人工蜂群算法

蜜蜂是一种群居昆虫，自然环境中的蜜蜂能够在任何复杂环境下找到食物源进而采蜜。蜂群所产生的群体智慧的最小搜索模型包括三个要素：食物源、被雇佣的蜜蜂、未被雇佣的蜜蜂[9]。食物源的评价标准由多个因素来确定，包括：离蜂巢的距离、蜜源量的大小以及采蜜难易程度等[10]。

根据蜜蜂的采蜜机制将人工蜂群分为三类：侦察蜂、观察蜂和采蜜蜂。

其中每个采蜜蜂分别对应一个确定的蜜源，并在迭代过程中对蜜源的领域进行搜索同时更新蜜源信息和确定蜜源的花蜜量；

然后观察蜂根据蜜源的丰富程度采用轮盘赌选择策略来选择相应蜜源，并更新蜜源信息和确定蜜源量的大小；当搜索空间被采蜜蜂和观察蜂全部搜索完后，如果在限定的循环次数后蜜源的适应值仍没有改进，则放弃该蜜源，采蜜蜂转为侦查蜂并根据随机搜索策略搜索新蜜源。

ABC算法可简要描述为：蜂群搜索蜜源过程中，首先在搜索空间中随机生成SN个蜜源，每个蜜源代表一个初始解Xi(i=1，2，L，SN)，该解为一个D维向量［11］。

采蜜蜂和观察蜂根据下式进行搜索更新蜜源信息：

式中：vij—新的食物源位置；φij—[ -1 1 ]范围内的随机数，控制着xij领域的生成范围；k、j—k∈{1，2，L，SN}，并且k≠i，j∈{1，2，…，D}，两者下标随机选取。

观察蜂所采用的轮盘赌选择公式为：

式中：SN—解的个数；fiti—第i个解的适应度函数值。适应度函数是影响蜂群算法收敛和稳定的重要因素[12]，fiti值越大则对应的解越优，适应度函数评判标准，如式（3）所示。

式中：n—机器人运动路径等分点数。侦查蜂所采用的随机搜索公式为：

3 混合改进人工蜂群算法

3.1 食物源更新公式的改进

在标准ABC算法中，采蜜蜂与观察蜂根据式（1）在蜜源附近来搜索并更新蜜源。但这种更新只是基于当前蜜源i在附近随机选取其它蜜源，会导致个体间的信息未能被充分利用，使得算法在局部搜索能力较弱且种群淘汰效果不佳。因此考虑在食物源更新公式中引入当前最优蜜源位置xbestj，使历史最优位置对当前位置产生影响，提高算法在局部的搜索能力。

同时标准ABC算法更新种群时采用随机步长，步长太大或太小会导致新解远离当前最优解和新解变化小，搜索效率低。针对以上存在的问题，考虑引入变异算子来调整步长。

由线性组合分布理论知Levy 分布[13]满足重尾的稳定分布，其兼具正态分布与柯西分布的特性，可产生合适步长，在进化陷入局部最优时，服从Levy分布的随机数可引导个体快速跳出，使算法具有较好的全局搜索能力。引入Levy分布后的食物源更新公式可表示为：

式中：xbestj—当前最优蜜源位置；Levy(β)—对应于xij服从指数为β的Levy分布，即为：

其中，通常设置λ=1。由于Levy分布生成的步长相对复杂，可由Mantegna 算法来实现对称Levy 稳定分布。采用式（7）来计算步长：

式中：β取值范围同上，通常β=1.5；u、ν—服从正态分布。

σμ和συ表达式如下：

式中：Γ—标准的Gamma函数[14]。食物源更新公式为：

3.2 随机搜索策略的改进

侦查蜂根据随机搜索策略的公式随机产生一个新解来代替xi。由于公式产生的解随机性太强导致算法在寻优过程中容易陷入局部极值。为克服该缺陷，引入柯西分布［15］，将随机变换rand( 0，1)换成柯西变异算子C(0，1)。

柯西变异算子使得公式能充分利用当前搜索到的信息，增加了算法的抗扰动能力，改进后的随机搜索公式为：

3.3 HIABC算法中的势场力法

根据人工势场法的特点，人工势场包括引力势场和斥力势场，路径规划环境中在目标点附近形成一个引力势场，而在障碍物附近一定范围形成斥力势场。

设在环境中某处为Q，则该处引力势场可表示为：

式中：ξ—引力尺度因子，非负数；d(q，q goal)—机器人当前位置与目标的距离。

故机器人所受目标引力即为引力场对距离的导数：

当机器人越接近目标时所受到的引力就会越小，直到为零。Q处的斥力势场为：

式中：η—是斥力尺度因子；ρ(q,qobs)—机器人当前位置与障碍物的距离；ρ0—障碍物斥力范围。

同理机器人所受障碍物斥力即为斥力场对距离的导数：

综上所述，机器人在运动环境中所受的总的势力场即为引力场和斥力场的叠加，所受力即为来自目标点的引力和来自障碍物的斥力的合力，该合力决定了机器人的运动方向。

3.4 路径规划的HIABC算法执行步骤

综合上述描述，HIABC算法执行可以分为以下步骤：

（1）种群参数初始化。主要包括种群的规模，如初始解xi的个数SN及其维数D，计算评价各个解的适应度函数值；算法的最大限制次数Limit值和最大迭代次数。

（2）每只采蜜蜂根据表达式（10）在搜索空间中对蜜源进行邻域搜索，找出新的蜜源并计算其适应值。如果该适应值优于当前蜜源，则取代该蜜源，反之则不变。

（3）基于上步得到的各适应值，观察蜂通过式（2）采用轮盘赌选择策略来选择蜜源，并在蜜源领域进行再搜索，采用式（10），更新蜜源位置。记录最优解。

（4）若到达算法的限制次数Limit后，蜜源仍旧没有更新，则该蜜源被放弃。采蜜蜂变为侦查蜂，且根据式（11）产生随机解，用于替换被放弃的蜜源位置。否则转到（5）。

（5）完成一次迭代，记下该次迭代中的最优蜜源位置。

（6）判断循环迭代次数是否达到终止条件，若达到，则停止循环转到（7）；若未达到，则跳到（2）。

（7）连接每次迭代中的最优蜜源节点，进而得到一条从起始点到目标点的最优路径，即为机器人的规划路径。

4 路径规划仿真试验及分析

4.1 机器人运动环境模型

设机器人的工作任务空间为二维空间，空间中存在着若干静止且大小不变的障碍物，机器人需在空间中绕过障碍物从起点到达指定目标点。

采用栅格法来建立路径规划的运动环境模型，通过栅格将环境空间分割成多个大小相同的单元格，处于障碍物范围的单元格作为障碍栅格，反之即为自由栅格。

设机器人工作任务空间由（20×20）的栅格组成，环境中共有20个不同大小障碍物，对栅格依次进行编号，黑色栅格表示障碍物，白色栅格表示自由可行栅格，如图1所示。

图1 机器人运动环境模型图Fig.1 Robot Motion Environment Model Diagram

为了简化分析，假设机器人每次只行进一个格子包括斜对角线，那么机器人在运动过程中就存在以下两种情况：

（1）当机器人运动至环境中间处（非边界处），则机器人周围存在8个可以选择的路径，如图2所示。

图2 机器人运动位置图Fig.2 Robot Motion Location Map

假设当前机器人坐标为(x0,y0)，那么机器人8种路线的坐标变化分别为：

（2）当机器人运动至边界则存在8个特殊位置（A-H），这8种地方的位置坐标条件以及可走的路线分别为：

其中A处可走路线2、3、5；B处可走路线1、2、3、4、5；C处可走路线1、2、4；D处可走路线1、2、4、6、7；E处可走路线4、6、7；F处可走路线4、5、6、7、8；G处可走路线5、7、8；H处可走路线2、3、5、7、8。

4.2 仿真环境及参数设置

仿真环境：利用MATLAB R13a，在Intel（R）Core（TM）i5-3210M CPU@2.50GHZ、4.00GB内存、Window 7操作系统下进行仿真验算。

首先在MATLAB中建立图1所示的环境模型图，根据具体环境模型将HIABC 算法的参数设置为：种群规模SN=20；蜜源个体维度D=10；最大限制次数Limit=20；最大循环次数Gmax=100；路径长度权值1；起始点坐标（0.5，19.5）；终点坐标（19.5，0.5）。

4.3 仿真结果及分析

在同一变量参数下，采用标准ABC算法和HIABC算法对图1环境模型进行求解，求解结果，如图3、图4所示。

图3 两种算法的最优路径规划Fig.3 Optimal Path Planning for Two Algorithms

从图中可以看出，两种算法下选择的最优路线不同，可以看到基于HIABC算法下的机器人路径规划结果明显更优。两种算法下所得到的迭代曲线图，如图4所示。

图4 两种算法的迭代曲线图Fig.4 Iterative Graph of Two Algorithms

两种算法的路径搜索模型在整体上都呈收敛趋势。在搜索之初虽然出现了一定的波动，但随着波动的持续变化，搜索的路径越来越短。

在搜索中后期，随机搜索的数量越来越少，最优路径趋于平缓。HIABC 算法下的路径规划在迭代约20 次后收敛到最短路径，路径长度约为30.000。

而标准ABC算法的路径规划是在迭代约40次后收敛到最短路径，路径长度约为32.300。

为了更好的比较ABC和HIABC算法的性能，将两种算法在同样的实验条件下运行10次，如表1所示。

由表1数据可知，ABC算法在求解路径规划时得到的路径长度存在一定的波动，且很难获取最优值。

表1 路径规划长度和运行时间Tab.1 Total Length and Run Time of Path Planning

而HIABC算法获得的路径长度值则相对稳定一些，由于人工势场法的结合，使得获取解的效率也得到大大提高。实验结果表明基于HIABC算法在路径规划的研究中能够更高效的找到机器人运动的最短路径。

5 结束语

提出了一种基于混合改进人工蜂群算法的机器人路径规划研究方法。

在标准ABC算法的基础上，对算法中的食物源更新公式和随机搜索策略进行改进，弥补了标准ABC算法收敛速度慢且易陷入局部最优导致算法停滞的不足。

同时利用人工势场法简单高效的优点将其与ABC算法相结合提高了算法的收敛速度。基于此方法在MATLAB 软件中进行了仿真实验，实验结果证明了HIABC算法的可行性和有效性，为研究机器人路径规划提供了重要的参考价值。

不足之处是在算法的参数设置上仍有待进一步优化，简化了环境中的约束条件导致与实际情况有一定的差距。

进一步研究工作展望：

（1）在算法中引入更加有效的约束条件，进一步提高算法的收敛速度和寻优精度。

（2）设计机器人动态环境模型，将算法运用到实时避障路径规划系统以及更多的实际应用当中。