移动机器人路径规划仿真研究

梁凯 陈志军 闫学勤

摘 要： 在移动机器人有效路径规划问题的研究中，针对传统移动机器人有效路径规划算法收敛速度慢、搜索时间长、寻优能力差等问题，提出一种人工鱼群算法与遗传算法相结合的有效路径规划算法。通过栅格法对机器人运动环境进行建模，在静态环境下使用人工鱼群算法进行初始路径规划，将规划所得的初始路径作为遗传算法的初始种群，并使用改进的遗传算法进行迭代优化，寻求一条从起点到目标点的全局最优有效路径。大量仿真结果表明，该混合算法相比其他算法，具有较快的收敛速度和较强的寻优能力。

关键词： 移动机器人； 路径规划； 遗传算法； 人工鱼群算法； 最优有效路径； 人工鱼群遗传算法

中图分类号： TN911.1?34； TP242 文献标识码： A 文章编号： 1004?373X（2018）17?0167?06

Abstract： An efficient path planning algorithm combining artificial fish swarm algorithm and genetic algorithm （AFSA?GA） is proposed to overcome the problems of slow convergence speed， long search time and poor search ability existing in the traditional effective path planning algorithms for mobile robot. The grid method is used to model the robot motion environment. The artificial fish swarm algorithm is used in the static environment to plan the initial path. The planned initial path is used as the initial population of the genetic algorithm， and the improved genetic algorithm is used for iterative optimization to seek a global optimal efficient path from the starting point to the target point. A large number of simulation results show that the hybrid algorithm has faster convergence speed and stronger optimization ability than other algorithms.

Keywords： mobile robot； path planning； genetic algorithm； artificial fish swarm algorithm； optimal effective path； AFSA?GA

0 引 言

移动机器人的路径规划在机器人学领域是最基本同时也是很重要的一个研究课题。它被学者们描述为：如果给机器人确定一个所要运动的环境，还有起点和期望的终点，那么机器人就可以根据任务要求（如路径是否最短、能量是否消耗最少或时间使用是否最短）来寻求一条运动轨迹，该轨迹要满足能连接起点和终点，还能躲开环境中的障碍物，则这样的运动轨迹称为最优或次优的有效路径。

国内外众多学者对移动机器人的路径规划问题进行了广泛的研究，并取得了一定的成果。传统的路径规划方法有自由空间法[1]、可视图法、人工势场法等[2]，但均存在不足。如自由空间法在获取最优路径上得不到保证；可视图法当起点和目标点位置发生变化时，需要重新构造可视图，降低路径规划的效率[3]；人工势场法会忽略一些有价值的障碍物分布信息，从而陷入局部最小值等[4]。近年来，一些学者提出将神经网络算法、蚁群算法、模拟退火算法、粒子群算法等智能算法应用于机器人的路径规划中，虽然都取得了一定的研究成果，但这些智能算法的缺点也非常突出。例如文献[5]中提出的基于蚁群算法的移动机器人路径规划方法，虽然一定程度上提高了机器人路径规划的效率，但传统的蚁群算法后期易陷入局部最优解使得收敛速度较慢，不适合求解连续优化问题，因此也不适用于复杂环境下的移动机器人路径规划。文献[6]对遗传算法在机器人的路径规划上进行了研究，但传统的遗传算法容易出现早熟现象、局部寻优能力也较差，无法保证可靠性的要求。文献[7]研究了基于粒子群算法的移动机器人路径规划，但粒子群算法后期搜索能力不强，易陷入局部最优解求解质量不高。

针对上述问题，本文提出了一种人工鱼群算法與遗传算法相结合的改进算法。该混合算法中，在静态栅格环境下使用人工鱼群算法来规划初始路径，将得到的初始路径作为遗传算法的初始种群，再通过改进的遗传算法对初始种群进行迭代优化，最后求出全局最优解。通过仿真实验对比发现，混合算法具有较快的收敛速度和较强的寻优能力。

1 移动机器人路径规划原理

移动机器人有效路径规划是指在一个所要运动的环境中，机器人根据任务要求来寻求一条最优有效运动轨迹，该轨迹可以连接起点和目标点，同时还能躲开环境中的障碍物。机器人路径规划主要包括以下两个步骤：

1） 环境模型的建立，根据机器人的真实运动环境建立相关的抽象环境模型。

2） 路径搜索方法，即寻找能实现任务要求的路径搜索算法。

综上所述可知，机器人路径规划的关键技术是路径搜索算法。当前的传统遗传算法实现路径规划时存在收敛速度慢，路径规划时间长，寻优能力差等问题。本文将用人工鱼群算法和遗传算法相结合的混合算法解决传统方法存在的问题。

2 人工鱼群遗传算法的机器人有效路径规划

2.1 环境建模

本文采用栅格法对机器人工作空间进行建模。假设机器人工作在含有障碍物的10×10的二维静态空间，即起点、目标点和障碍物位置信息已知且不发生变化。用大小相同的栅格对机器人二维工作空间进行划分，如果栅格内有障碍，这样的栅格叫不可行栅格，相反叫可行栅格。划分后的工作空间如图1所示，图中黑色区域为不可行栅格，其余的为可行栅格。

2.2 人工鱼群算法基本原理

人工鱼群算法（AFSA）是一种模仿鱼类行为的群体智能优化算法。该算法通过模拟鱼类的觅食、聚群和追尾来实现最优路径的搜索。人工鱼群算法多用于解决连续空间的优化问题，然而基于栅格的机器人路径规划是一个离散的优化问题。因此，当用人工鱼群算法解决基于栅格的机器人路径规划问题时，需要对人工鱼群算法进行新的定义和说明。

2.2.1 相关基本定义

2.2.2 人工鱼的行为策略

人工鱼的觅食行为是自由搜索的行为，另外两个行为是追逐最优点的行为。为了提高人工鱼的搜索能力，本文对人工鱼行为策略做以下描述：

觅食行为：设人工鱼所在栅格为[gi]，其食物浓度为[hgi]，在[neighborgi]中选择[gj]作为下一步要走的位置，其食物浓度为[hgj]。设[t]为从可行邻域栅格中选择栅格的次数，设[trynumber]为从可行邻域栅格中选择栅格的最大次数，则觅食过程步骤为：

1） 设置参数[t]和[trynumber]的大小。

2） 设人工鱼所在栅格为[gi]，在其可行邻域栅格中选择[gj]作为下一步要走的位置，则有[gj=random（neighborgi）]。

3） 判断[hgj

4） 判断[t>trynumber]是否成立，如果不成立，转步骤2）；如果成立，转步骤5）。

5） 移动到栅格[gj]。

2.3 遗传算法基本原理

遗传算法的基本思想是对于要研究的问题，在其可行解中初始化一个种群，该种群是由多个个体组成，每个个体都是由基因编码构成。初始生成的种群通过优胜劣汰的原理进行逐代演化，最终会生成越来越好的个体，而且每一代种群中个体的优劣程度都可以通过适应度函数来体现。种群中的个体可以通过选择、交叉和变异等操作来生成新一代种群个体，且新一代种群中的个体会变得越来越好。当满足最后的迭代终止条件时，把末代群体中最优的个体经过解码等操作还原为原问题的解，那么这个解就是所要求得的近似最优解。

通过上面的分析，可以发现遗传算法主要包括：

1） 初始种群，其规模一般为50～200；

2） 适应度函数，用于评价个体优劣程度；

3） 选择操作，为了使好的个体以更大的概率遗传到下一代；

4） 交叉操作，是遗传算法中起核心作用的操作，交叉概率一般为0.5～1；

5） 变异操作，变异能拓展新的搜索空间，使种群保持多样性，变异概率一般为0.05～0.1。

遗传算法操作步骤：

1） 设置问题参数并编码；

2） 初始化种群；

3） 计算每个个体的适应度函数；

4） 执行遗传操作；

5） 产生下一代种群；

6） 判断是否满足所设定的最大迭代次数，如果满足，则执行步骤7），否则执行步骤3）；

7） 输出最优个体。

2.4 人工鱼群遗传算法

遗传算法由于其较好的全局寻优能力和较强的并行计算能力而被广泛应用到路径规划领域。但是遗传算法容易受到初始种群的影响，因为初始种群质量的好坏直接影响遗传算法的计算效率和获取全局极值的速度。所以本文通过将人工鱼群算法和遗传算法相混合，即把人工鱼搜索到的路径解当作遗传算法的初始解，再通过遗传操作进行迭代优化最终来求解全局最优解。

2.4.1 初始种群的产生

1） 设定拥挤度因子[δ]，视野域半径[R]，最大选择栅格次数trynumber，人工鱼总数[N]，种群大小pop_size，設种群个体数目计数器[n=0]，为每个种群个体创建路径表[Gpathn]，同时为每条人工鱼创建路径表[pathk]。

2） 把[N]条人工鱼放在起点[gstart]，并且把[gstart]加入路径表[pathk]（[k=]1，2，…，[N]）。令[k=1]，[k]用来累计鱼群。

3） 设人工鱼[fk]所在栅格位置为[gk]，其可行相邻栅格域为[neighborgk]。设人工鱼[fk]下一步移动到栅格[gnext]，则栅格[gnext=random（neighborgk）]。

4） 人工鱼[fk]在栅格位置[gk]通过执行追尾行为和聚群行为，选择使得[hgnext]取值最小的行为作为最终要执行的行为，缺省行为记为觅食行为。

5） 把[gnext]加入到路径表[pathk]，判断人工鱼[fk]是否到达[ggoal]，如果到达，则保存路径[pathk]到[Gpathn]，转步骤7）；否则，若[k

6） 当所有人工鱼都走过一步之后，若没有人工鱼到达终点栅格[ggoal]，令[k=1]，转步骤3）。

7） [n=n+1]，如果[n≥pop_size]，算法结束，产生大小为[pop_size]的初始种群。如果[n

2.4.2 适应度函数的建立

适应度函数是评价个体好坏的一种有效手段。首先根据任务要求建立适应度函数，然后通过适应度函数计算各个个体的适应度值大小，通过求得的适应度值的大小来判断个体的优劣程度。本文以路径最短作为任务要求，通过规定适应度函数越大代表路径越好，适应度函数越小代表路径越差来建立适应度函数，则适应度函数公式可写为：

2.4.3 遗传操作

1） 选择操作。选择操作就是把适应度值较大的个体以比较大的概率被选择遗传到下一代。本文采用比例选择操作，具体步骤是：通过求出每一个个体的适应度值来算出总的适应度值；再求出每一個个体的适应度值与总的适应度值的比值，它表示了个体被选择遗传到下一代的概率；通过模仿赌盘操作来确定每个个体被选择的次数。

以个体[k]为例，个体[k]被选择的概率为[pk=Lki=1pop_sizeLi]，其中种群大小为[pop_size]，再计算个体[k]的累积概率[qk=i=1kpi]。在0～1范围内生成一个随机数[λ]，若满足[qk-1<λ≤qk]，则选中个体[k]，这种选择方法可以让适应度函数值较大的个体以较大的概率被选择遗传到下一代，这也确保了优秀个体能很好地繁衍到下一代。

2） 交叉操作。交叉操作就是在种群中通过选择两个父代个体让其进行基因片段的互换以此产生子代个体。目前交叉操作的方式有很多，单点交叉和多点交叉应用的最多且效果显著，然而两者本质差别不大，所以本文采用单点交叉方式。具体方法是：为了保证交叉后产生的个体不是间断路径，在配对的两个个体中选择在相同栅格位置进行交叉，如果相同栅格有很多，则在它们中只要选择一个进行交叉就可以了，如果被选的两个父代个体没有共同的栅格，则不执行交叉操作。

3） 变异操作。变异能拓展新的搜索空间，使种群保持多样性，当种群趋于局部收敛时，可以通过变异防止出现早熟现象。一般情况下变异操作会使得路径变成间断路径，同时会给算法增加难度和运算时间。本文变异操作步骤为：先在路径中任意选择一个节点但该节点不能是起点和终点，然后通过选择随机数来确定该被选节点的位置，对被选择的位置通过变异概率判断是否要删除，删除之后的路径会被分成上下两段；把上半段的终点看成路径起点，把下半段的起点看成路径终点，再采用本文人工鱼群算法的觅食行为将断开的两段路径给连接起来使之成为一条连续路径。

2.4.4 终止条件

本文终止条件设为：算法进化代数达到了设定的最大值。

2.4.5 算法流程

人工鱼群遗传算法流程如图2所示。

3 仿真结果与分析

为了验证本文人工鱼群遗传算法的可行性和优越性，在10×10的栅格环境下对该混合算法进行模拟仿真，并与传统遗传算法进行比较，仿真过程中混合算法的参数设置为：[δ=0.6]，[N=10]，[R=4]，[trynumber]=3，pop_size=100，迭代次数为50，交叉概率[pc]=0.6，变异概率[pm]=0.1。传统遗传算法的参数设置为：初始种群大小为100，迭代次数为50，[pc]=0.6，[pm]=0.1。

通过Matlab仿真软件对混合算法和传统遗传算法平均运行30次，每次50代，对两种算法在获得最优解方面进行了研究，两种算法获得的最优有效路径如图3所示，两种算法在获得最优有效路径所需迭代次数的对比如图4所示。

图3为两种算法在栅格环境下找到的最优有效路径，其起点为栅格序号1，终点为栅格序号100，通过栅格序号表示该最短路径为{1 2 13 23 33 44 55 56 66 76 87 97 98 99 100}，其长度为15.656 9。

图4是两种算法各运行30次，对两种算法在获得最优解所需迭代次数进行了比较。从图中可以看到，人工鱼群遗传算法收敛速度较快可以在平均16代以内收敛找到全局最优解，且前期的搜索速度较快，而遗传算法平均将近42代才能找到全局最优解，且前期搜索速度较慢。

为了更好说明本文算法的优越性，下面将在10×10的栅格环境中对本文算法和其他算法运行30次进行比较，在各算法相同参数下比较结果总结于表1。

从表1分析可得知，在获取路径长度方面，本文算法在获取最优路径上要明显好于其他两种算法，传统遗传算法在获取最优有效路径上的稳定性最差，其次是文献[8]算法。在规划成功率上，文献[8]算法和本文算法都可以保证获得有效路径，但遗传算法不能确保获得有效路径。在路径规划耗时上，文献[8]算法平均用时最短，其次是本文算法，虽然文献[8]算法规划用时短，但不能保证路径的质量。在平均迭代次数上，本文算法所需迭代次数最少。综上性能分析可以发现，本文算法在迭代次数和寻优能力上要明显好于其他算法。验证了本文算法的可行性和优越性。

4 结 语

针对由于初始种群的影响而使得传统遗传算法收敛速度慢、寻优能力差的问题，本文提出一种人工鱼群算法与遗传算法相结合的混合算法解决该问题。通过对本文算法与其他算法进行仿真比较可以看出，本文算法在寻优能力和迭代次数上明显好于其他算法，验证了本文算法在有效路径规划上的可行性和优越性。

注：本文通讯作者为陈志军。

参考文献

[1] 张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005（2）：439?443.

ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and prospect of mobile robot path planning technology [J]. Journal of system simulation， 2005（2）： 439?443.

[2] 张颖，吴成东，原宝龙.机器人路径规划方法综述[J].控制工程，2003（z1）：152?155.

ZHANG Ying， WU Chengdong， YUAN Baolong. A survey of path planning methods for robot [J]. Control engineering， 2003（S1）： 152?155.

[3] 张琦，马家辰，马立勇.基于简化可视图的环境建模方法[J].东北大学学报（自然科学版），2013，34（10）：1383?1386.

ZHANG Qi， MA Jiachen， MA Liyong. An environment modeling method based on simplified view [J]. Journal of Northeastern University （natural science edition）， 2013， 34（10）： 1383?1386.

[4] 赵荣齐.基于人工势场法的机器人路径规划研究[D].济南：山东大学，2008.

ZHAO Rongqi. Research on robot path planning based on artificial potential field method [D]. Jinan： Shandong University， 2008.

[5] 张银玲，牛小梅.蚁群算法在移动机器人路径规划中的仿真研究[J].计算机仿真，2011，28（6）：231?234.

ZHANG Yinling， NIU Xiaomei. Simulation research of ant colony algorithm in mobile robot path planning [J]. Computer simulation， 2011， 28（6）： 231?234.

[6] 杨献峰，付俊辉.移动机器人路径规划的仿真研究[J].计算机仿真，2012，29（7）：223?226.

YANG Xianfeng， FU Junhui. Simulation research on path planning of mobile robot [J]. Computer simulation， 2012， 29（7）： 223?226.

[7] 鲁丹.粒子群算法在移动机器人路径规划中的应用研究[D].武汉：武汉科技大学，2009.

LU Dan. Application of particle swarm optimization in mobile robot path planning [D]. Wuhan： Wuhan University of Science and Technology， 2009.

[8] 徐晓晴，朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报，2012，40（8）：1694?1700.

XU Xiaoqing， ZHU Qingbao. Multi artificial fish swarm algorithm and a rule library based dynamic collision avoidance algorithm for robot path planning in a dynamic environment [J]. Acta electronica Sinica， 2012， 40（8）： 1694?1700.

[9] ZHANG Yi， GUAN Guolun， PU Xingchen. The robot path planning based on improved artificial fish swarm algorithm [J]. Mathematical problems in engineering， 2016（11）： 1?11.

[10] BAKDI A， HENTOUT A， BOUTAMI H， et al. Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy?logic control [J]. Robotics & autonomous systems， 2016， 89（1）： 95?109.