机器人导航的自主选择搜索策略蜂群规划算法

王明超

（无锡工艺职业技术学院，江苏 宜兴 214200）

1 引言

当前机器人不仅应用领域越来越广，而且相关的智能技术研究也越来越深，使机器人在人类生产和生活种日益重要。机器人导航技术是移动机器人一切工作的基础，决定了机器人的安全和效率[1]。因此研究机器人智能导航问题具有明显的安全意义和经济意义。

导航技术分为目标定位、路径规划、环境建模等3 个子技术，研究导航路径智能规划问题。按照导航路径规划方法出现时间划分，可以将路径规划分为传统路径规划方法和智能算法规划方法。传统路径规划方法包括栅格法[2]、拓扑法[3]、可视图法[4]、人工势场法[5]等，其共同特点是使用简单的几何数学模型完成路径规划。智能算法规划方法包括基于遗传算法规划方法、基于蚁群算法规划方法、基于神经网络规划方法、基于粒子群算法规划等，此类方法共同特点是将路径规划问题转化为优化问题，使用智能仿生算法进行优化。文献[6]改进了蚁群算法的转移概率和信息素更新策略，提出了机器人路径的自适应蚁群算法规划策略，降低了工作路径长度；文献[7]使用莱维飞行优化粒子群算法，优化了焊接机器人工作路径；文献[8]建立了多个优化目标，分别为焊接质量函数、机器人运动平稳性函数、双机器人碰撞函数，使用多目标遗传算法进行求解，获得了双机器人协调焊接路径。总之，机器人导航智能化程度越来越高，正朝着多传感器融合、多算法融合、多机器人分工协作等方向发展。

为了提高机器人导航路径的质量和规划速度，提出了自主选择搜索策略蜂群算法的规划方法。通过坐标旋转法将二维规划问题转化为一维，使用自主选择搜索策略蜂群算法搜索最优路径点，达到了减少路径长度和提高规划速度的目的。

2 自主选择搜索策略蜂群算法

2.1 人工蜂群算法

人工蜂群算法将蜜蜂分为三类，分别为引领蜂、观察蜂和侦查蜂，不同蜜蜂使用不同的蜜源搜索方式，通过分工协作发挥群体智能实现最优蜜源搜索。

（1）蜜蜂位置初始化。蜂群规模记为N，生存维度记为D，蜂群以随机的方式进行位置初始化，为：

（2）引领蜂蜜源搜索策略。引领蜂使用交叉方式搜索蜜源，对于蜜蜂i，随机选择另一个体k≠i，则引领蜂蜜源搜索公式为：

（3）观察蜂蜜源搜索策略。引领蜂通过摇摆舞将蜜源浓度信息传递给观察蜂，观察蜂依据蜜源浓度选择观察蜂，即：

式中：pi—引领蜂的被选概率；NB—引领蜂数量；fiti—第i 只引领蜂所在位置蜜源浓度。分析式（3）可知，引领蜂所在位置蜜源浓度越高则被选概率越大，保证了较优蜜源附近区域的细致搜索。观察蜂选择引领蜂后，与引领蜂一起进行小范围细致搜索，蜜源搜索方式与引领蜂完全一致。

（4）侦查蜂蜜源搜索策略。当引领蜂或观察蜂在某一蜜源附近搜索次数达到设定次数且蜜源浓度没有明显提高时，则蜜蜂放弃此处蜜源同时转化为侦查蜂，在搜索区域内进行大范围随机搜索，即：

2.2 多方式搜索策略

进化论表明蜂群中蜜蜂的搜索行为受环境因素的影响，不同环境对应的搜索行为也不一致。蜜蜂对环境的认知信息有多种来源，包括个体自身认知信息、群体最佳个体的认知信息、种群平均认知信息和其他个体认知信息等，多种认知信息来源对应多种方式的蜜源搜索策略。在此需要强调的是，此多种方式的蜜源搜索策略适用于引领蜂或观察蜂，侦查蜂的蜜源搜索方式保持不变。

（1）基于自身认知、最佳个体认知、其他个体认知的蜜源搜索方式。此方法参考粒子群算法中的信息获取方式，种群中蜜蜂参考自身对环境的认知、种群中最优认知和其他个体的认知，综合形成自身的蜜源搜索方式，为：

（2）基于群体平均认知的蜜源搜索方式。如同人类社会中的“从众”心理，种群中的个体也具有一定的趋同性，也即蜜蜂的搜索行为受种群共同认知的影响。使用所有蜜蜂的位置质心表示种群平均认知，则基于种群平均认知的搜索方式为：

式中：pj—第j 维的质心。

（3）基于其他个体认知的蜜源搜索方式。这种随机选取个体获取认知信息的方式类似于遗传算法中的个体变异，此种信息获取方式与混沌理论相比更具有方向性，对应的蜜源搜索方式为：

式中：r1≠r2≠r3—随机选择的三个不同个体。

2.3 搜索策略自主选择方法

2.2 节给出了3 种环境认知方式和相应的蜜源搜索方式，加上式（2）给出的原算法搜索方式，共有4 种蜜源搜索方式供引领蜂和观察蜂选择。在此提出不同蜜源搜索方法的即时价值和后效价值，通过即时价值和后效价值计算不同蜜源选择策略的选择概率，实现蜜蜂对搜索策略的自主选择。

（1）不同蜜源搜索策略的即时价值。后文中将此算法应用于机器人导航路径规划，因此将目标函数f（x，t）定义为路径长度，则蜜蜂i 对应的目标函数f（xi，t）越小说明蜜蜂i 越优。蜜源搜索策略的即时价值定义为迭代一次后目标函数的减小程度，即：

式中：Valik（t）—粒子i 选择蜜源搜索策略k 迭代后的即时价值；f（xi，t-1）—粒子i 迭代t-1 次时的目标函数值；fk（xi，t）—粒子i 选择搜索策略k 迭代t 次时的目标函数值。当Valik（t）＞0 时说明选择搜索策略k 迭代一次后蜜源浓度有所提高，当Valik（t）=0 时说明选择搜索策略k 迭代一次后蜜源浓度没有提高。

（2）不同蜜源搜索策略的后效价值。信心上界算法[9]在计算机棋盘程序中用于计算不同落子点的未来价值，在围棋程序中取得了很好的效果。参考这一思想，使用信息上界算法计算蜜源选择策略的后效价值，为：

（3）搜索策略自主选择方法。首先使用不同搜索策略的即时价值、后效价值和历史经验计算搜索策略的得分，而后根据得分构造不同搜索策略的选择概率。使用即时价值、后效价值和历史经验构造搜索策略的得分，为：

蜜蜂i 根据式（11）计算不同搜索策略的选择概率，并最终选择概率最大的搜索策略为下一次迭代的搜索策略，从而在迭代时获得最佳的即时价值和后效价值。通过以上方式，蜜蜂完成了对搜索策略的自主选择。

2.4 自主选择搜索策略蜂群算法流程

根据人工蜂群算法原理和多方式蜜源搜索自主选择策略，制定自主选择搜索策略蜂群算法流程为：

（1）初始化人工蜂群算法参数和蜜蜂初始位置；

（2）根据蜜蜂位置对应的目标函数值，将蜜蜂区分为引领蜂和观察蜂；

（3）引领蜂和观察蜂计算使用不同蜜源搜索策略的即时价值、后效价值和选择概率；

（4）引领蜂和观察蜂自主选择概率最大的蜜源搜索策略更新位置，若新位置蜜源优于原位置则选择新蜜源，否则选择旧蜜源；

（5）引领蜂和观察蜂是否满足转化为侦查蜂的条件？若满足则转化为侦查蜂，按照式（4）进行搜索；若不满足则继续按照多搜索策略进行搜索；

（6）算法是否达到最大迭代次数？若是则结束；若否则转至（3）。

2.5 算法性能测试

为了验证自主选择搜索策略蜂群算法的搜索性能，选择具有代表性的3 个测试函数，如表1 所示。3 个测试函数的空间维度均设置为n=30。分别使用自主选择搜索策略蜂群算法（Choose Searching Strategy Independently Bee Colony Algorithm，CSSIBC）、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）、改进人工蜂群算法[10]（Modified Artificial Bee Colony Algorithm，MABC）对测试函数进行寻优。

表1 测试函数Tab.1 Testing Function

性能测试的实验环境为：Windows 7 操作系统，Intel 酷睿i5处理器，2.5Hz 主频，4G 内存，仿真软件为Matlab R2014a。算法参数设置为：种群规模N=30、迭代次数itermax=1000、个体未来价值和全局未来价值的平衡系数α=0.5；改进人工蜂群算法参数设置参照文献[10]。每种算法对3 个测试函数独立运行10 次，统计寻优结果的最优值、最差值、平均值、方差、迭代次数和运行时间，结果如表2 所示。

表2 对测试函数的寻优结果Tab.2 Optimizing Result for Testing Function

从表2 中对测试函数的寻优结果可以看出，在对3 个测试函数的寻优中，自主选择搜索策略蜂群算法每次都能够搜索到最优值，说明了其强大的寻优能力。从寻优精度和稳定性等方面看，CSSIBC 算法最优，其次为MABC 算法，ABC 算法最差。从迭代次数和运行时间看，CSSIBC 算法搜索到最优值时的迭代次数最小、耗时也最少，但是就耗时与迭代次数的比值来看，CSSIBC 算法最大，说明CSSIBC 算法单次迭代时的耗时最多，这是因为每次迭代时对搜索策略的选择过程耗时较大。总的来讲，自主选择搜索策略蜂群算法的寻优精度最高、寻优稳定性最好，同时耗时也最少。

3 路径规划与仿真分析

3.1 路径规划方案与性能指标

机器人工作空间设定为二维空间且为静态环境，本节使用坐标旋转法将路径的二维规划问题转化为一维规划问题，如图1所示。图中OXY 坐标系为原始坐标系，称其为惯性坐标系，S 为路径起点，T 为路径目标点。为了实现问题降维，以S 点为原点，以ST 方向为X′轴，以ST 垂直方向为Y′轴，从而建立局部坐标系SX′Y′。使用L1～LD共条平行线将ST 等分为D+1 段，那么路径规划可描述为在等分线L1～LD上确定各自的Y′坐标值，将规划点顺次连接后进行平滑处理就得到了规划路径，从而实现了路径规划由二维降为一维。

图1 坐标转换方法Fig.1 Coordinate Transform Method

记X′轴与X 轴夹角为θ，则以S 点为顶点顺时针旋转角度θ，并将坐标原点平移，就可以实现坐标间的转换。

惯性坐标系任意一点（x，y）与局部坐标系相应点（x′，y′）间的转换关系为：

式中：（xs，ys）—起始点S 坐标。

使用路径长度作为机器人路径规划的唯一指标，根据上文的路径规划方案，得到平行线间距为△l=‖ST‖/（D+1），则机器人路径长度为：

3.2 路径规划仿真分析

本节进行机器人路径规划的仿真环境和参数设置与2.5 节保持一致。设置了两种环境下的仿真验证，分别使用自主选择搜索策略蜂群算法、人工蜂群算法进行路径规划，每种算法独立运行10 次，两种环境下搜索到的最优路径，如图2 所示。图中实线为自主选择搜索策略蜂群算法规划的路径，虚线为人工蜂群算法规划的路径。路径起点设置为（20，20），路径目标点设置为（190，190）。从图中可以看出，自主选择搜索策略蜂群算法规划的路径长度明显短于人工蜂群算法，人工蜂群算法为躲避障碍物而规划的路径存在较多的冗余曲折路径。为了进一步分析两种算法在机器人路径规划中的性能，给出迭代过程中路径长度随迭代次数的变化曲线，如图3 所示。图中虚线为人工蜂群算法的迭代曲线，实线为自主选择搜索策略蜂群算法的迭代曲线。

图2 两种环境下的规划路径Fig.2 Path Planned Under Two Environment

图3 两种环境下的迭代曲线Fig.3 Iterating Curve Under Two Environment

从图3 可以看出，在环境一和环境二两种情况下，自主选择搜索策略蜂群算法搜索到最优值的迭代次数明显少于人工蜂群算法，且收敛值也远小于人工蜂群算法。经统计，在环境一中，自主选择搜索策略蜂群算法规划的最优路径长度为389.12，人工蜂群算法规划的最优路径长度为441.36，比这里的算法增加了13.43%；自主选择搜索策略蜂群算法搜索到最优值的迭代次数为176 次，人工蜂群算法搜索到最优值的迭代次数为289 次，比这里的算法增加了64.20%。在环境二中，自主选择搜索策略蜂群算法规划的最优路径长度为263.72，人工蜂群算法规划的最优路径长度为321.56，比这里的算法增加了21.93%；自主选择搜索策略蜂群算法搜索到最优值的迭代次数为195 次，人工蜂群算法搜索到最优值的迭代次数为302 次，比这里的算法增加了54.87%。综合以上数据可以看出，在不同环境的路径规划中，自主选择搜索策略蜂群算法规划的路径长度远远优于人工蜂群算法，搜索到最优值时的迭代次数也远远优于人工蜂群算法，这是因为自主选择搜索策略蜂群算法设计了多种蜜源搜索方式，并根据不同蜜源搜索方式的即时价值和后效价值给出了自主选择方法，使算法每次迭代均使用最有价值的搜索方式，因此规划的路径质量和迭代次数都远远优于人工蜂群算法。

4 结论

研究了全局静态环境下的机器人导航路径规划问题，使用坐标旋转法将二维问题转化为一维，提出了自主选择搜索策略蜂群算法用于路径规划，经验证得出了以下结论：（1）自主选择搜索策略蜂群算法的寻优速度和寻优精度远远优于人工蜂群算法；（2）多种蜜源搜索方式相结合，并根据即时价值和后效价值对搜索方式自主选择，能够提高算法的搜索性能。