基于混合蛙跳算法的移动机器人路径规划

潘 翔，唐春晖，张仁杰

(上海理工大学 光电信息与计算机工程学院，上海 200093)

移动机器人的路径规划技术，就是机器人根据自身传感器对环境的感知，自行规划出一条安全的运行路线，同时高效地完成作业任务。移动机器人的路径规划主要解决3 个问题［1］:(1)使机器人能从初始点运动到目标点。(2)用一定的算法使机器人能够绕开障碍物，并经过某些必须经过的点完成相应的作业任务。(3)在完成以上任务的前提下，尽量优化机器人的运行轨迹。目前，国内外学者对移动机器人的路径规划问题进行了广泛而深入的研究，就传统方法而言主要有人工势场法［2］、可视图法［3］、栅格法［4］等。这些方法各有优缺点，例如人工势场法是利用目标点对机器人的引力和障碍物对机器人斥力的综合作用来进行路径规划的，这种方法描述简单，便于实现实时控制，且可生成较为光滑的路径，但其也存在当目标点附近存在障碍物从而使机器人无法到达目标点，或者在两个相近的障碍物前易产生振荡等缺点;可视图法是以起始点、目标点和所有多边形障碍物顶点间的可行直线连线为路径范围来搜索最短路径的，可视图法的优点是直观，且可求得三维空间以下的最短路径，但其缺点是当起始点和目标点发生改变时就需要重新构造可视图，因此缺乏灵活性。近年来，随着智能仿生学算法应用的发展，许多学者开始致力于利用智能算法解决移动机器人的路径规划问题，其主要方法有人工神经网络算法［5］、遗传算法［6］、粒子群算法［7］等。赵娟平等［8］提出了参数模糊自适应窗口蚁群优化算法，即利用模糊控制来优化算法参数，同时为蚂蚁建立动态搜索窗口，并引入城市节点活跃度的概念以指导蚂蚁进行解的构造和信息素的更新;Hsu 等［9］提出的改进蚁群算法，一方面更新最优路径附近栅格的信息素，另一方面增加与目标点反方向栅格的信息素，通过这种信息素更新机制可以有效避免算法在搜索过程中陷入局部最优;Wang 等［10］提出了端点逼近式的蚁群算法，即在迭代过程中，根据路径上残留信息素的强度以及蚂蚁走过的栅格的分布情况，逐渐移动起始栅格和目标栅格，从而缩小二者之间的距离，这样既可简化问题的复杂度，也可加快算法的收敛速度。

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)由Eusuf 和Lansey 为解决组合优化问题于2003年提出［11］。作为一种新型的智能仿生优化算法，其结合了具有较强局部搜索能力的模因演算法(Memetic Algorithm，MA)和具有良好全局搜索性能的粒子群算法(Particle Swarm Algorithm，PSO)的特点，因此其搜索寻优能力强，且具有概念简单、参数调整少、易于实现等优点。

本文利用混合蛙跳算法对移动机器人的路径规划问题进行了研究。首先利用蚁群算法生成一定数量的的路径，然后引入混合蛙跳算法进行全局路径寻优，并对最终生成的路径进行了简化处理，最后通过全局路径仿真实验验证该算法的可行性和有效性。

1 基于混合蛙跳算法的机器人路径规划

1.1 基本思想

在相同的迭代次数内，蚁群算法求值的精度比混合蛙跳算法要高，且可以在迭代初期迅速找到一个较优解，但同时也易陷入局部最优;而混合蛙跳算法的搜索能力要比蚁群算法强，但其搜索结果在迭代过程中分布较为均匀，这使得其求得的解相对较差。因此，基于混合蛙跳算法的移动机器人路径规划的实现思想为:首先利用蚁群算法生成N 条路径，然后调用混合蛙跳算法，并且将这N 条路径作为混合蛙跳算法N 只青蛙的初始值进行全局路径搜索。其中，以路径形式表示的青蛙跳跃称为子群内的Memetic 进化。

1.2 主要的算法策略

1.2.1 适应度的定义及最优青蛙评定方法

为搜索到全局最优路径，定义每只青蛙的适应度为该青蛙所表示的路径长度的值，则划分子群时按照青蛙的适应度值升序排列个体，适应度值最小的称为全局最优青蛙，每个子群中适应度值最小的青蛙称为该群中的最优青蛙，反之称为最差青蛙。

1.2.2 Memetic 进化

每只青蛙均具有自身的文化(Meme)且被定义为问题的一个解，青蛙个体之间通过文化交流实现信息的交换。设计Memetic 进化的关键就是如何实现文化信息的传递。

设有两只青蛙frogA 和frogB，其具有的路径分别为

其中，frogA 的路径长度优于frogB 的路径长度，且下划线表示两只青蛙路径重叠的部分。

要实现frogB 向frogA 的一次跳跃，即用frogA 中的较优路径［11 15］替换frogB 中的路径［16 18 19］，若有多段不重叠的路径，则只替换最后一段不重叠的路径。

1.3 简化算子

对于机器人的行走路径，除了要考虑路线最短外，还要充分考虑到机器人行走的安全性，即避免路径中出现过大的拐角，因过大的拐角既会影响机器人的平衡性，又会增大其在尖峰处能量的消耗，因此路径最优应该包含路径长度和安全性这两个方面。实验中发现，最后生成的路径中会出现两条相交线段的夹角是直角或锐角的情况，这条路径往往不是最优的，故通过引入简化算子可去除一些不必要的节点来改善路径。简化算子的原理就是利用三角形的两边之和大于第三边。如图1 所示，节点3 使得的拐角为直角，这样机器人在行进到节点3 时就需要转弯90°以便继续前进，而通过引入简化算子，如图2 所示，删除节点3 后，一方面行走路径变短，另一方面机器人在节点2 和节点4处只需要转弯45°，拐角减小，更有利于机器人行走的安全性。同样，当遇到U 型陷阱时，为顺利逃脱陷阱会出现如图3 所示的路径，通过删除节点2 也可以达到优化路径的目的，如图4 所示。

图1 原始路线

图2 修改后的路线

图3 原始路线

图4 修改后的路线

1.4 混合蛙跳算法的实现步骤

步骤1 初始化青蛙个体。将动态保留的蚁群算法的前N 个最优路径赋给N 只青蛙，同时计算这N 只青蛙的适应度。

设置初始Memetic 进化次数in=1;初始全局信息交换次数G=1，最大全局信息交换次数为G_max。

步骤2 划分青蛙子群。将N 只青蛙按照适应度升序排列，并将其分成n 个子群，即第1 只青蛙进入第1 个子群，第2 只青蛙进入第2 个子群，第n 只青蛙进入第n 个子群，第n+1 只青蛙进入第1 个子群，以此类推。更新适应度值全局最优青蛙以及每个子群里的最优青蛙，最差青蛙。

步骤3 Memetic 进化。每个子群里的最差青蛙向最优青蛙跳跃一次，若跳跃后最差青蛙的适应度变小，则转至步骤4;否则最差青蛙向全局最优青蛙跳跃一次，然后转至步骤4。

步骤4 in←in+1，若in ＜n，则转至步骤3，否则表明n 个青蛙子群内部均进行了Memetic 进化，则转至步骤5。

步骤5 全局信息交换。G←G+1，若G ＜G_max，则转至步骤2，否则输出全局最优青蛙，转至步骤6。

步骤6 利用简化算子对全局最优青蛙的路径进行优化。输出最优路径，算法结束。

2 仿真实验与结果分析

为验证混合蛙跳算法的全局寻优能力，现使用Matlab 软件对混合蛙跳算法进行仿真，并将其与蚁群算法进行比较与分析。

机器人的环境模型来自文献［12］，各参数分别设置为:青蛙总数N=100，子群个数n=10，全局信息交换次数G_max=100。图5 和图6 分别为蚁群算法和混合蛙跳算法的最优路径图和收敛曲线图。

图5 蚁群算法的最优路径图和收敛曲线图

图6 混合蛙跳算法的最优路径图和收敛曲线图

从所寻最优路径可看出，两种算法从起始点出发，均能成功避开障碍物并且找到一条通往目标点的路径，但混合蛙跳算法所寻路径一方面长度大幅减小，另一方面路径的平滑度也比蚁群算法的路径好，转弯次数以及拐角均比蚁群算法有明显改善，这样更有利于机器人的安全前行;从两种算法的收敛曲线可看出，混合蛙跳算法的收敛速度明显加快，并且其产生解的波动范围比蚁群算法的波动范围要小得多，说明混合蛙跳算法产生的解集中度高，稳定性强。

为进一步验证混合蛙跳算法的优越性，现将实验结果与文献［12］的实验结果进行比较。

表1 文献算法与本文算法仿真比较

需要说明的是文献［12］中的算法计算路径长度时相邻斜对角栅格的路径长度取的是1.414，而本文算法取的是，因此文献［12］寻得的最优路径长度28.038 与文本算法最优路径长度28.0416 其实是一致的。从表1 中可看出，本文算法和文献算法都能找到最优路径，但在效率方面，本文算法运行10 次有7次找到了最优路径，而文献算法只有1 次，因此混合蛙跳算法具有更强的路径搜索能力，效率更高。

同时，还选取一个更为复杂的40×40 栅格地图，该地图模型来自文献［13］，图7 为利用本文混合蛙跳算法得到的最优路径图。

图7 混合蛙跳算法的最优路径图

利用本文算法运行10 次，得到的最优路径分别为:60.669 0，61.840 6，61.254 8，60.669 0，61.254 8，61.840 6，60.426 4，61.254 8，61.840 6，60.834 0，而文献［13］中得到的最优路径为69.213。这说明本文提出的混合蛙跳算法在大规模栅格地图中也能够表现出良好的路径搜索能力，且搜索过程不易陷入局部最优，因此，可解决复杂地图模型中的路径规划问题。

3 结束语

本文以栅格地图作为环境模型，将混合蛙跳算法应用于解决移动机器人的路径规划问题。首先利用蚁群算法在栅格地图中生成一定数量的路径，然后引入混合蛙跳算法，子群内进行Memetic 进化，最坏青蛙根据与子群最优青蛙或全局最优青蛙的路径交点栅格进行路径更新，最后，考虑到机器人路径行走的平滑要求，利用简化算子对算法寻得的路径进行优化，以消除不必要的路径尖峰，减小机器人在路径拐角处的能量消耗，确保其行走的安全性。

仿真实验表明，本文提出的混合蛙跳算法在栅格地图中能有效避开障碍物的同时快速地规划出一条通往目标点的优化路径，且较之蚁群算法，在解的优化性、收敛性、波动性方面均有很大提高，并由于混合蛙跳算法具有较强的全局搜索能力，使其也适用于大规模、障碍物覆盖率高的环境，从而验证了算法的有效性和可行性。

［1］ 朱大奇，颜明重.移动机器人路径规划技术综述［J］.控制与决策，2010，25(7):961－967.

［2］ Khatib O.Real－time obstacle avoidance for manipulators and mobile robots［J］.The International Journal of Robotics Research，1986，5(1):90－98.

［3］ Lozano－Pérez T，Wesley M A.An algorithm for planning collision－free paths among polyhedral obstacles［J］.Communications of the ACM，1979，22(10):560－570.

［4］ Mansor M A，Morris A S.Path planning in unknown environment with obstacles using virtual window［J］.Journal of Intelligent and Robotic Systems，1999，24(3):235－251.

［5］ Simon D.The application of neural networks to optimal robot trajectory planning［J］.Robotics and Autonomous Systems，1993，11(1):23－34.

［6］ Holland J H.Genetic algorithms and the optimal allocation of trials［J］.SIAM Journal on Computing，1973，2(2):88－105.

［7］ Kennedy J.Particle swarm optimization encyclopedia of machine learning［M］.US:Springer，2010.

［8］ 赵娟平，高宪文，刘金刚，等.移动机器人路径规划的参数模糊自适应窗口蚁群优化算法［J］.控制与决策，2011，26(7):1096－1100.

［9］ Hsu C C，Hou R Y，Wang W Y.Path planning for mobile robots based on improved ant colony optimization［C］.IEEE International Conference on Systems，Man and Cybernetics(SMC)，IEEE，2013.

［10］Wang P，Tang G，Li Y，et al.Ant colony algorithm using endpoint approximation for robot path planning［C］.China:IEEE Control Conference(CCC)，2012.

［11］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129(3):210－225.

［12］万晓凤，胡伟，方武义，等.基于改进蚁群算法的机器人路径规划研究［J］.计算机工程与应用，2014，50(18):63－66.

［13］Zhou Z，Nie Y，Min G.Enhanced ant colony optimization algorithm for global path planning of mobile robots［C］.International Conference on Computational and Information Sciences(ICCIS)，IEEE，2013.