文章快速检索 高级检索

A biogeography-based mobile robot path planning algorithm
MO Hongwei , MA Jingwen
College of Automation, Harbin Engineering University, Harbin 150001, China
Abstract: At present, there are many intelligent computing methods used in mobile robot path planning; however, in complex environments, most of them have low efficiency and poor results. In order to solve such problems, this paper proposes a new method for mobile robot path planning, which combines the grid coding method based on the effective vertex with the improved biogeography-based optimization (BBO). On the basis of the environmental infor-mation that has been learned, the BBO is improved in three aspects:elite strategies, dimension reduction mecha-nisms and migration based on inertial operator. The improved BBO is applied in path planning. The method is com-pared with artificial bee colony (ABC), particle swarm optimization (PSO) and artificial fish algorithm (AFA). Experiment results show that the improved method can solve the problem of mobile robot path planning in a complex environment more efficiently.
Key words: mobile robot     path planning     biogeography-based optimization (BBO)     effective vertex     grid coding method

1 有效顶点栅格环境

1) 栅格在被选入路径后需要加入禁忌表，即该栅格不能再次被选入路径中，这样当遇到一些U型槽等复杂环境会迅速生成有效的路径；

2) 自由栅格大部分都不是有效栅格，路径规划结果的信息仅包含障碍物顶点附近的部分栅格；

3) 分辨率大小难以确定。分辨率过高，增加搜索算法的运算量；分辨率过小会导致路径规划结果粗糙，在极端情况下会造成本来分开的障碍物连通，最终得不到有效的路径。

m×n的栅格环境中，定义g(i,j)为{g(i,j)|i∈[1,m－1],j∈[1,n－1],iN,jN}。若栅格g(i,j)，g(i,i+1)，g (i+1,j)，g(i+1,j+1) 4个栅格中有且只有一个障碍物栅格gob(xob,yob)，那么这个4个栅格中必存在一个有效顶点gv(xv,yv)，gobgv同时满足以下2个条件：

 图 1 基于有效顶点的栅格示意图Fig. 1 Schematic diagram of grids based on effective vertex

2 BBO

2.1 适应度指数变量SIV与机器人路径的关系

SIVi需要包含的变量个数需要达到N-1(N为有效顶点列表S的个数)才能够保证机器人路径生成的绝对安全。

2.2 BBO的迁移操作

2.3 BBO的变异操作

1)初始化最大循环次数N； 初始化BBO的各个参数：岛屿数 M，最大变异率mmax；最大物种数Smax=M－1，最大迁出率E=1，最大嵌入率I=1；初始化每个岛屿i的SIV，SIVij= rand(0,1)；

2)计算每个岛屿的路径D，并根据Di确定Si，以及PSi；保存最小路径信息和最小路径值到Dmin

3)初始化迭代次数nc=0；

4)执行迁移操作；

5)是否执行变异操作，若不执行则跳过；

6)计算每个岛屿的路径D，并根据Di确定Si，以及PSi；计算当前代数最小路径Dminnc，若Dminnc<Dmin，则Dminnc=Dmin，保存最小路径信息；

7)nc<N是否成立，若成立，则nc=nc+1，跳到4)；若不成立，则跳到7)；

8)输出最短路径值和最短路径信息。

2.5 算法的改进 2.5.1 精英策略

2.5.2降维

t时刻所有岛屿的SIV的维数：

1)BBO算法岛屿总数M设为30，最大变异率mmax设为0.4。算法1为有精英岛屿的BBO算法，算法2为无精英岛屿的BBO算法。2个算法各运行30次，仿真迭代趋势图，规划结果统计图，规划时间消耗统计图分别如图2~4所示。

 图 2 精英岛屿对算法迭代的影响趋势Fig. 2 Influence of the elite island on algorithm iteration
 图 3 精英岛屿对算法结果的影响统计Fig. 3 Statistics of the influence of the elite island on results of algorithm
 图 4 精英岛屿对算法时效的影响统计Fig. 4 Statistics of influence of the elite island on algorithm effectiveness

2)设BBO算法岛屿总数M设为30，最大变异率mmax设为0.4。算法1为有降维机制的BBO算法，算法2为无降维机制的BBO算法。2个算法各运行30次，仿真迭代趋势图，规划结果统计图，规划时间消耗统计图分别如图5~7所示。

 图 5 降维机制对算法迭代影响的趋势图Fig. 5 Influence of the dimensionality reduction mechanism on algorithm iteration
 图 6 降维机制对算法结果影响的统计Fig. 6 Statistics of the influence of dimensionality reduction mechanism on results of algorithm
 图 7 降维机制对算法时效影响的统计Fig. 7 Statistics of the influence of dimensionality reduction mechanism on algorithm effectiveness

BBO：岛屿数M=30，最大变异率mmax=0.3，采用上面提到的降维机制和精英策略，以及双向搜索机制；

PSO：粒子个数M=30，惯性常数ωmax=0.8,ωmmin=0.4，c1=0.5,c2=0.5，采用线性动态ω调整策略、降维机制和双向搜索机制；

AFSA：人工鱼个数M=30，拥挤度因子设为2，感知距离为0.1，最大移动步长0.08，最大试探次数10，同样采用双向搜索机制和降维机制；

ABC：人工蜂个数M=30，最大尝试次数Limit=15，同样采用双向搜索机制和降维机制。

 图 8 仿真环境模型Fig. 8 Simulation environment models

 栅格地图 有效顶点数 理论最小值 20×20 141 28.812 2 30×30 321 43.903 0 40×40 575 58.993 8 50×50 903 73.952 6 60×60 1 305 88.820 5 70×70 1 781 103.688 4

 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率/% 20×20 (141) BBO 29.348 7 29.376 2 29.349 8 29.348 7 0.005 1 1.87 PSO 29.348 7 35.621 8 30.791 4 30.398 8 1.530 0 6.87 AFSA 29.348 7 29.348 7 29.348 7 29.348 7 0 1.86 ABC 29.348 7 29.404 5 29.350 6 29.348 7 0.010 2 1.87 30×30 (321) BBO 44.216 6 45.559 6 44.558 5 44.555 2 0.293 9 2.58 PSO 47.058 9 58.530 9 51.798 3 51.495 1 3.418 8 17.98 AFSA 44.388 2 48.034 4 46.136 0 45.876 3 1.056 4 5.09 ABC 44.582 8 52.077 6 49.115 8 49.384 1 2.058 7 11.87 40×40 (575) BBO 59.423 2 65.792 1 63.229 2 63.600 3 1.275 3 7.18 PSO 70.058 2 92.295 3 77.519 8 77.268 4 4.736 3 31.40 AFSA 62.941 4 73.515 4 68.606 0 68.770 4 2.433 6 16.29 ABC 64.973 6 81.521 4 74.413 9 74.051 8 3.785 0 26.14 50×50 (903) BBO 81.799 4 92.407 6 88.612 9 88.733 3 3.271 3 19.84 PSO 90.701 7 126.772 0 109.324 3 108.261 0 11.269 8 47.85 AFSA 87.008 4 100.621 0 95.752 1 96.859 1 3.931 5 29.50 ABC 92.565 6 116.311 0 105.551 4 106.293 5 7.353 5 42.75 60×60 (1305) BBO 103.741 0 120.983 0 114.791 5 116.312 5 5.918 0 29.24 PSO 121.012 0 156.372 0 136.067 2 136.008 0 10.605 7 53.19 AFSA 117.059 0 136.808 0 128.630 1 131.973 0 6.455 5 44.82 ABC 125.807 0 154.789 0 142.289 9 143.070 5 10.756 9 60.20 70×70 (1781) BBO 147.224 0 174.286 0 158.493 0 157.741 0 8.401 9 52.86 PSO 141.577 0 219.568 0 181.430 5 177.859 5 25.627 5 74.98 AFSA 132.976 0 170.408 0 149.900 2 148.404 5 12.995 1 54.21 ABC 164.998 0 234.324 0 194.063 4 191.770 0 24.829 0 87.16

5 结束语

 [1] 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7):961-967. ZHU Daqi, YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7):961-967. [2] VASUDEVAN C, GANESAN K. Case-based path planning for autonomous underwater vehicles[C]//Proceedings of the 1994 IEEE International Symposium on Intelligent Control. Columbus, USA, 1994:160-165. [3] LIU Yu, ZHU Shiqiang, JIN Bo, et al. Sensory navigation of autonomous cleaning robots[C]//The 5th World Conference on Intelligent Control Automation. Hangzhou, China, 2004:4793-4796. [4] RAM A, SANTAMARÍA J C. Continuous case-based reasoning[J]. Artificial Intelligence, 1997, 90(1/2):25-77. [5] ARLEO A, SMERALDI F, GERSTNER W. Cognitive navigation based on nonuniform Gabor space sampling, unsupervised growing Networks, and reinforcement learning[J]. IEEE Transactions on Neural Network, 2004, 15(3):639-652. [6] FUJIMURA K, SAMET H. A hierarchical strategy for path planning among moving obstacles[mobile robot][J]. IEEE Transactions on Robotic Automation, 1989, 5(1):61-69. [7] KO N Y, LEE B H. Avoidability measure in moving obstacle avoidance problem and its use for robot motion planning[C]//IEEE International Conference on Intelligent Robots and System. Osaka, 1996:1296-1303. [8] GE S S, CUI Y J. New potential functions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation, 2000, 16(5):615-620. [9] 陈清阳, 张小波, 孙振平, 等. 非结构化环境下自主车辆轨迹规划方法[J]. 中南大学学报:然科学版. 2011, 42(11):3377-3383. CHEN Qingyang, ZHANG Xiaobo, SUN Zhenping, et al. Trajectory planning for autonomous driving in unstructured environments[J]. Journal of Central South University:atural and Technology, 2011, 42(11):3377-3383. [10] 王鸿鹏, 杨云, 刘景泰. 高速移动机器人的研究现状与发展趋势[J]. 自动化与仪表, 2011, 26(12):1-4. WANG Hongpeng, YANG Yun, LIU Jingtai. Research and development trend of high-speed mobile robot[J]. Automation and Instrumentation, 2011, 26(12):1-4. [11] 谭民, 王硕. 机器人技术研究进展[J]. 自动化学报, 2013, 39(7):963-972. TAN Min, WANG Shuo. Research progress on robotics[J]. Acta Automatica Sinica, 2013, 39(7):963-972. [12] JARADAT M A K, GARIBEH M H, FEILAT E A. Dynamic motion planning for autonomous mobile robot using fuzzy potential field[C]//Proceeding of the 6th International Symposium on Mechatronics and its Applications. Sharjah, UAE, 2009:24-26. [13] LINGELBACH F. Path planning using probabilistic cell decomposition[C]//IEEE International Conference on Robotics and Automation. New Orleans, USA, 2004:467-472. [14] MO Hongwei, MENG Longlong. Robot path planning based on differential evolution in static environment[J]. International Journal of Digital Content Technology and its Applications, 2012, 6(20):122-129. [15] MO Hongwei, XU Lifang. Biogeography migration algorithm for traveling salesman problem[J]. International Journal of Intelligent Computing and Cybernetics, 2011, 4(3):311-330.
DOI: 10.11992/tis.201407003

0

#### 文章信息

MO Hongwei, MA Jingwen

A biogeography-based mobile robot path planning algorithm

CAAI Transactions on Intelligent Systems, 2015, 10(05): 705-711.
DOI: 10.11992/tis.201407003