2. 安徽省检测技术与节能装置省级重点实验室, 安徽 芜湖 241000
2. Anhui Key Laboratory of Detection Technology and Energy Saving Devices, Wuhu 241000, China
1 引言
路径规划是移动机器人导航技术的一个重要组成部分，具有重要的研究价值.移动机器人的路径规划是根据预先设置的条件从起始点开始，避开障碍物从而移动到目标点的最短路径[1].根据移动机器人对所行走的环境信息的探知程度，可将移动机器人的路径规划分为全局路径规划和局部路径规划[2].全局路径规划是移动机器人在环境信息完全可知时的路径规划；而局部路径规划则需要通过传感器对移动机器人行走环境信息进行探测.
目前，移动机器人路径规划方法大致可以分成两类：一类是诸如基于人工势场法[3]、Voronoi图法[4]和可视图法[5]的路径规划方法.其中，人工势场方法拥有简单的结构，但存在容易陷入局部最优解的问题；可视图法能够获得最短路径但其搜索效率较低；而Voronoi图法虽然安全性较高，但起始节点到目标节点的路径较长.随着技术的发展，环境模型复杂性和任务难度的增加，基于群智能算法的路径规划方法也随之出现.群智能优化算法[6-8]是模拟种群个体之间的觅食和进化行为并将其转变为优化算法中的搜索和优化过程，将自然界中的个体转变为优化空间中的点，将种群对环境的适应能力转变为优化算法中的目标函数.如蚁群算法[9-10]、遗传算法[11-12]、蜂群算法[13]、蛙跳算法[14]、粒子群算法[15-17]等.其中，蚁群算法是群智能优化算法中被研究者研究的最为透彻的一种优化算法，也是在移动机器人路径规划中应用最为广泛的一种优化算法，但是其搜索时间长、易于出现停滞现象；遗传算法是典型的智能化优化算法，它是将遗传算子应用到移动机器人的路径规划中，但其占据较大的存储空间且局部寻优能力较差；蜂群算法搜索速度快、易于实现，但搜索效率较低；蛙跳算法的缺点在于易收敛于局部最优解、求解精度较低；粒子群算法的优势在于简单且容易实现，但其本身存在易过早收敛而陷入局部最优的缺点.
人工鱼群算法(artificial fish swarm algorithm，AFSA)是一种模拟鱼群的觅食、聚群、追尾等行为的新型群智能优化算法[18-19]，具有并行性、简单性、寻优速度快且全局寻优能力强等特点.近年来，在人工鱼群算法的研究中取得了许多有意义的研究成果[20-22].然而，分析现有的研究成果不难发现，在人工鱼群算法的应用过程中，存在一些缺陷：首先，假设人工鱼的视野范围和步长均是固定的，视野范围固定必然导致算法后期的收敛速度变慢，而步长的不变性会影响最优解的精确度；其次，传统人工鱼群算法中的个体本身不具有变异机制，从而降低了种群的多样性.基于上述的考虑，本文通过引入3种策略混合机制，即视野范围的加权平均距离策略、步长的对数函数移动因子策略和个体的高斯变异策略，从而大大改善了鱼群算法的优化性能.通过经典函数优化和TSP求解问题测试了算法的性能；最后建立移动机器人的环境模型，将此种新型多策略混合鱼群算法应用于移动机器人的路径规划问题.通过仿真比较说明了本文算法的优越性和有效性.
2 多策略混合人工鱼群算法鱼类不具备人类所拥有的逻辑和判断能力，但它们可以通过个体的简单行为和群体间的相互影响，进而能实现群体的生存和进化.该算法的基本思想是在一片水域中，鱼的生存数目与该区域富含营养物质的浓度成正比，依据这个特点，可以模仿鱼群的觅食、聚群、追尾等行为，进而实现全局寻优.本文通过引入3种策略混合机制，进一步提高算法的性能，每一种改进策略表述如下：
2.1 加权平均距离策略在传统的人工鱼群算法中人工鱼的视野范围是固定的，所以在局部极值附近的人工鱼无法看到全局极值，而且使得算法的收敛速度变慢.为此，在算法收敛的过程中需要选择合适的视野，以保证其收敛速度及防止陷入局部最优.本文引入加权平均距离策略优化人工鱼的视野.以有n条人工鱼为例，人工鱼表示为Ki(i=1，2，…，n)，其中Ki到其它j条人工鱼的距离为Ri，j，距离权值定义为ωi，j.此时人工鱼Ki的视野距离di可以通过加权平均计算得到，具体计算方法为
|
(1) |
采用加权平均距离策略，在算法优化初期，人工鱼随机分布在整个区域内，相互之间的距离较大，每条人工鱼的视野范围也比较大，因此人工鱼在前期的移动步长较大，便于像食物浓度(人工鱼位置状态的目标函数值)大的方向前进，也就是说人工鱼群算法在前期收敛速度很快.随着大多数的人工鱼都不断地向着食物浓度大的方向聚集，使得人工鱼之间的距离逐渐变小，它们的视野范围也随着距离的缩小变得越来越小，有利于提高算法的搜索效率和寻找到全局最优值.
2.2 对数函数移动因子策略传统人工鱼群算法中人工鱼除了视野固定不变外，步长也是固定不变的.步长的不变性可能造成若步长取值过小，则算法在前期由于步长过小收敛速度缓慢；若取值过大，则使得算法在后期的精确收敛过程中由于步长过大而造成的振荡现象.因此在算法优化的过程中需要选择合适的步长，以保证全局收敛速度和提高最优解的精确性.
为了加快算法的全局收敛速度，本文选择对数递增函数作为移动因子，采用对数函数设计步长更新公式：
|
(2) |
其中，p代表种群内部的当前迭代次数，Nc代表种群的最大迭代次数.改进后的种群更新公式中的移动步长s为
|
(3) |
进一步地，更新后的解的位置表示如下：
|
(4) |
其中，Xi+1(t)为人工鱼的下一个状态，Xε(t)为人工鱼的将要搜索的状态，Xi(t)为当前状态，N为人工鱼的群体规模.
由式(4) 可看出，迭代次数的增加，移动步长也逐步适应迭代次数的变化，改进后的移动因子能够进行全面的局部搜索，使得算法能够很好地定位前进方向，移动到目标区域，后期保持优化解的全局搜索能力，加快了收敛速度.
2.3 高斯变异策略人工鱼群算法与其它的仿生群智能优化算法一样，更新的过程中的寻优能力主要依靠个体间的聚群、觅食、追尾等行为的相互作用，但个体本身不具有变异机制，一旦受到局部最优值的约束，自身很难摆脱束缚，并在进化过程中，个体不断向着当前全局最优解前进，使得种群的多样性降低.变异策略的引入可以避免算法的种群多样性的降低，又可以提高算法的全局搜索能力.
高斯变异是指在原有个体状态上加上一个服从高斯分布的随机扰动项，定义如式(5) 所示：
|
(5) |
其中，N(0，1) 为标准正态分布又称高斯分布，Xi+1(t)为人工鱼下一个状态，Xi(t)为当前状态.
采用的高斯变异策略更新后的位置表示为
|
(6) |
为了验证所提出的多策略混合鱼群算法的有效性，选取了Rosenbrock、Rastrigin、Ackley和Needle四种经典函数测试算法的性能.表 1给出了传统人工鱼群算法(artificial fish swarm algorithm，AFSA)、基于加权平均距离策略的鱼群算法(weighted average distance artificial fish swarm algorithm，WAD-AFSA)、基于对数函数移动因子策略的自适应鱼群算法(adaptive logarithmic function artificial fish swarm algorithm，ALF-AFSA)及本文多步策略混合人工鱼群算法(multi-strategy hybrid artificial fish swarm algorithm，MH-AFSA)在相同解的精度条件下运行50次，4种算法所用的最长时间和最优时间，从表 1中可以看出在相同的寻优精度和相同的参数条件下，本文给出的MH-AFSA算法优化的时间最短.
表 2给出的是在迭代次数相同的条件下，解的精度对比结果.通过对选取的4个经典函数进行测试，本文MH-AFSA的寻优精度相较于AFSA、WAD-AFSA和ALF-AFSA三种算法有明显的提高.
TSP是数学领域中一个著名的组合优化问题，其可以简单描述为：设有n个城市，用数字1，…，n表示，每两个城市i和j之间的距离dij已知，TSP可以描述为：要遍访每个城市恰好一次的一条完整回路，并且其回路路径总长度为最短.其数学模型可描述为
|
(7) |
|
(8) |
|
(9) |
|
(10) |
式中，n为城市数，式(7) 为目标函数，式(8) 和式(9) 表示经过每个城市一次且仅一次，式(10) 保证了没有子回路解的产生.
本文选取TSPLIB中的EIL51、EIL76、RAT99、LIN105四个实例，分别采用AFSA、WAD-AFSA、ALF-AFSA和MH-AFSA求解TSP问题.得到的最优值和相关算法的迭代次数如表 3所示，可以看出，本文提出的MH-AFSA的全收敛速度比其它3种算法更高，搜寻到的最优值更加靠近实例的最优解.
将移动机器人行走的3维环境空间转换为2维环境模型.假设移动机器人行走的2维环境为G，行走的距离为Z，将Z作为对X轴、Y轴进行划分的单位长度，并将X轴、Y轴划分成n等分，在每个等分点处作X轴、Y轴的垂线得到n×n的等分栅格，通常栅格的边长都设置为1，移动机器人就是以这个等分的栅格环境作为行走的环境模型.栅格的位置可以由坐标或序列号表示，坐标与序列号之间的关系如图 1所示.
|
| 图 1 坐标与序列号 Figure 1 Coordinate and serial number |
进一步地，移动机器人行走空间环境中的障碍物转化成2维栅格模型，用黑色的栅格表示障碍物所在区域且对于障碍物所在区域的栅格，不满一个栅格也要按照一个栅格计算，而用白色的栅格表示没有障碍物区域.机器人在寻找路径过程中只能由一个栅格向相邻的栅格中移动且只能在白色的栅格中移动.基于上述的描述，本文建立的移动机器人环境模型如图 2所示.
|
| 图 2 移动机器人运行环境模型 Figure 2 Running environment model of the mobile robots |
将多策略混合鱼群算法应用于移动机器人路径规划问题，其优化步骤表述为：
Step 1 将机器人行走的环境根据栅格法进行环境建模，并随机生成N条可行性路径.
Step 2 设定高斯变异人工鱼群算法的详细参数.人工鱼的群体规模N=50，视野范围visual=0.15，移动步长step=0.45，拥挤度因子δ=0.8，尝试次数N_max=50.
Step 3 采用加权平均距离人工鱼群算法的视野作为人工鱼的视野，将对数函数作为人工鱼移动步长的移动因子并按照高斯变异的公式(6) 更新人工鱼的步长和位置.
Step 4 计算每条人工鱼在初始状态时各自的食物浓度将其作为目标函数并把最小值放入公告板(用来记录最优人工鱼的个体状态).
Step 5 执行人工鱼的追尾行为、聚群行为并采用行为选择策略选择优的前进方向，缺省行为是觅食行为.
Step 6 在计算执行各种行为之后，将每条人工鱼的食物浓度作为目标函数并将得到的最小值与公告板中初始值进行比较，更新公告板使得公告板中的值最小.
Step 7 判断是否满足终止条件(算法迭代达到设置的最大次数时或最小误差要求).如果满足条件，跳转至步骤Step 8；否则，跳转至步骤Step 5.
Step 8 程序结束，公告板中的值就是最优值，对应的路径则是最优路径.
图 3给出了AFSA、WAD-AFSA、ALF-AFSA及MH-AFSA的路径规划结果.从仿真结果可以看出：本文提出的MH-AFSA在移动机器人路径规划上的寻优路径更好，所搜寻的路径比其它3类算法更优.
|
| 图 3 移动机器人路径规划 Figure 3 Path planning for the mobile robots |
表 4给出了AFSA、WAD-AFSA、ALF-AFSA及MH-AFSA在机器人路径规划中的数据比较，可以看出基于传统AFSA的移动机器人路径规划平均路径长度为33.213 2，而基于WAD-AFSA、ALF-AFSA和MH-AFSA的移动机器人路径规划的平均路径长度分别为29.520 0、29.132 6、28.273 8.从算法迭代所需时间来分析，相较于其它3种算法，本文的MH-AFSA收敛速度更快，使用时间最少，全程路径最短，解决了容易陷入局部最优和收敛速度慢的问题.
通过对传统人工鱼群算法的分析，本文引入多步策略混合机制，即人工鱼视野范围的加权平均距离策略、步长的对数移动因子策略和个体的高斯变异策略.上述策略提高了算法的收敛速度、优化精度和种群的多样性；采用经典函数优化问题和TSP问题对算法进行测试，验证了算法的优良性能；最后，将多策略混合人工鱼群算法应用于移动机器人的路径规划，仿真结果说明了本文方法的有效性.需要指出的是，复杂场景下的移动机器人路径规划问题是未来研究的发展趋势.本文后续的研究工作将重点考虑多策略混合鱼群算法在此问题中的应用.
| [1] |
毕慧敏, 董海鹰.
改进遗传算法在机器人路径规划中的应用[J].测控技术, 2006, 25(4): 53–55.
Bi H M, Dong H Y. Application of improved genetic algorithm in path design of robot[J]. Measurement and Control Technique, 2006, 25(4): 53–55. |
| [2] |
马千知, 雷秀娟.
改进粒子群算法在机器人路径规划中的应用[J].计算机工程与应用, 2011, 47(25): 241–244.
Ma Q Z, Lei X J. Application of improved particle swarm optimization algorithm in robotic path planning[J]. Computer Engineering and Applications, 2011, 47(25): 241–244. DOI:10.3778/j.issn.1002-8331.2011.25.064 |
| [3] |
姚正华, 任子辉, 陈艳娜.
基于人工鱼群算法的煤矿救援机器人路径规划[J].煤矿机械, 2014, 35(4): 59–61.
Yao Z H, Ren Z H, Chen Y N. Path planning for mine rescue robot based on AFSA[J]. Coal Mine Machinery, 2014, 35(4): 59–61. |
| [4] |
许松清, 吴海彬, 林宜, 等.
基于Voronoi图法的移动机器人路径规划[J].中国工程机械学报, 2005, 3(3): 336–340.
Xu S Q, Wu H B, Lin Y, et al. Path planning of mobile robot based on Voronoi diagram method[J]. Chinese Journal of Construction Machinery, 2005, 3(3): 336–340. |
| [5] |
郗安民, 王琦, 孙学彬.
一种有效的地图创建方法和机器人路径规划[J].机械设计, 2010, 27(1): 35–37.
Xi A M, Wang Q, Sun X B. A kind of effective map creation method and path planning of robot[J]. Journal of Machine Design, 2010, 27(1): 35–37. |
| [6] | Deng W, Chen R, He B, et al. A novel two-stage hybrid swarm intelligence optimization algorithm and application[J]. Soft Computing, 2012, 16(10): 1707–1722. DOI:10.1007/s00500-012-0855-z |
| [7] | Tang Q, Shen Y, Hu C Y, et al. Swarm intelligence: Based cooperation optimization of multi-modal functions[J]. Cognitive Computation, 2013, 5(1): 48–55. DOI:10.1007/s12559-012-9144-5 |
| [8] | Yang B, Zhang Q L, Zhou Z H. Solving truss topological optimization via swarm intelligence[J]. KSCE Journal of Civil Engineering, 2015, 19(7): 1962–1972. DOI:10.1007/s12205-015-0218-2 |
| [9] |
史恩秀, 陈敏敏, 李俊, 等.
基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报, 2014, 45(6): 53–57.
Shi E X, Chen M M, Li J, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6): 53–57. DOI:10.6041/j.issn.1000-1298.2014.06.009 |
| [10] | Zhou Z P, Nie Y F, Gao M. Enhanced ant colony optimization algorithm for global path planning of mobile robots[C]//International Conference on Computational and Information Sciences. Piscataway, NJ, USA: IEEE, 2013: 698-701. |
| [11] |
冯金玲, 柳延领, 周洲, 等.
自适应遗传算法在移动机器人路径规划中的应用[J].北京科技大学学报, 2008, 30(3): 316–323.
Feng J L, Liu Y L, Zhou Z, et al. Application of adaptive genetic algorithm to optimum path planning of mobile robots[J]. Journal of University of Science and Technology Beijing, 2008, 30(3): 316–323. |
| [12] | Fang N Z, Jian Z, Zhang R. A hybrid of real coded genetic algorithm and artificial fish swarm algorithm for short-term optimal hydrothermal scheduling[J]. International Journal of Electrical Power & Energy Systems, 2014, 25(6): 617–629. |
| [13] |
殷霞红, 倪建军, 吴榴迎.
一种基于改进人工蜂群算法的机器人实时路径规划方法[J].计算机与现代化, 2015(3): 1–4.
Yin X H, Ni J J, Wu L Y. An improved artificial colony algorithm for real-time path planning of mobile robot[J]. Computer and Modernization, 2015(3): 1–4. |
| [14] |
潘桂彬, 潘丰, 刘国栋.
基于改进混合蛙跳算法的移动机器人路径规划[J].计算机应用, 2014, 34(10): 2850–2853.
Pan G B, Pan F, Liu G D. Path planning for mobile robots based on improved shuffled frog leaping algorithm[J]. Journal of Computer Applications, 2014, 34(10): 2850–2853. DOI:10.11772/j.issn.1001-9081.2014.10.2850 |
| [15] |
翁理国, 纪壮壮, 夏旻, 等.
基于改进多目标粒子群算法的机器人路径规划[J].系统仿真学报, 2014, 26(12): 2892–2898.
Weng L G, Ji Z Z, Xia M, et al. Robot path planning based on improved multi-objective particle swarm[J]. Journal of System Simulation, 2014, 26(12): 2892–2898. |
| [16] | Zhang J H, Gong D W, Zhang Y. A niching PSO-based multi-robot cooperation method for localizing odor sources[J]. Neurocompting, 2014, 123: 308–317. DOI:10.1016/j.neucom.2013.07.025 |
| [17] | Zhang J H, Yang S Z. A novel PSO algorithm based on an incremental-PID-controlled search strategy[J]. Soft Computing, 2016, 20(3): 991–1005. DOI:10.1007/s00500-014-1560-x |
| [18] | He Q, Hu X T, Ren H, et al. A novel artificial fish swarm algorithm for solving large-scale reliability-redundancy application problem[J]. ISA transactions, 2015, 59: 105–13. DOI:10.1016/j.isatra.2015.09.015 |
| [19] | Gao Y B, Guan L W, Wang T J. Optimal artificial fish swarm algorithm for the field calibration on marine navigation[J]. Measurement, 2014, 50: 297–304. DOI:10.1016/j.measurement.2014.01.003 |
| [20] |
杨淑云, 徐云霞, 李盼池.
基于Bloch球面搜索的量子鱼群算法[J].信息与控制, 2014, 43(6): 647–653.
Yang S Y, Xu Y X, Li P C. Quantum-inspired artificial fish swarm algorithm based on the bloch sphere search algorithm[J]. Information and Control, 2014, 43(6): 647–653. |
| [21] | Yang W H. An improved artificial fish swarm algorithm and its application in multiple sequence alignment[J]. Journal of Computational and Theoretical Nanoscience, 2014, 11(3): 888–892. DOI:10.1166/jctn.2014.3442 |
| [22] | Wang J S, Han S, Guo Q P. Echo state networks based predictive model of vinyl chloride monomer convention velocity optimized by artificial fish swarm algorithm[J]. Soft Computing, 2014, 18(3): 457–468. DOI:10.1007/s00500-013-1068-9 |