﻿ 移动机器人全覆盖信度函数路径规划算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2018, Vol. 13 Issue (2): 314-321  DOI: 10.11992/tis.201610006 0

### 引用本文

CAO Xiang, YU Along. Complete-coverage path planning algorithm of mobile robot based on belief function[J]. CAAI Transactions on Intelligent Systems, 2018, 13(2): 314-321. DOI: 10.11992/tis.201610006.

### 文章历史

Complete-coverage path planning algorithm of mobile robot based on belief function
CAO Xiang, YU Along
School of Physics and Electronic Electrical Engineering, Huaiyin Normal University, Huaian 223300, China
Abstract: For the complete-coverage path planning of mobile robot, an algorithm based on grid belief function was proposed. The goal is to control a mobile robot to traverse all reachable locations in work area, while guarantee automatic obstacle avoidance. Firstly, the grid map is assigned with values according to the information of the environment, the obstacles, covered grids and uncovered grids are represented by using different function values; secondly, judging if a mobile robot is caught in dead zone or not, different direction belief functions are introduced to adjust the grid function values; lastly, the robot programs the covered path according to the grid belief function value. The proposed algorithm can guide a robot to realize full coverage of work area, rapidly escape from dead zone and achieve a low repetition rate of the covered path. In the simulation experiments, by compared with bio-inspired neural network algorithm, the algorithm proposed in the paper was verified to own high coverage efficiency.
Key words: mobile robot    complete-coverage path planning    direction belief function    grid belief function    repetition rate

2000年Balch等[8]提出一种移动机器人行为覆盖路径规划方法，机器人根据简单的移动行为，尝试性地覆盖工作区域，如果遇到障碍物，则执行对应的转向命令。这种方法是一种以时间换空间的低成本策略，如不计时间可以达到全覆盖。该算法无需了解整个作业区全貌，也不用依赖过多的传感器，处理器运算量也很小，是一种性价比很高的方案。但是，行为全覆盖算法工作效率低，路径规划策略过于简单，面对复杂地形机器人经常无法逃离死区[9]

1 基于栅格信度函数的全覆盖路径规划算法

1.1 栅格位置性质函数

 ${x_j} = \left\{ {\begin{array}{*{20}{l}}{1,\quad \text{该单元未覆盖}}\\{0.5,\quad \text{该单元被覆盖}}\\{ - \infty ,\quad \text{该单元是障碍物}}\end{array}} \right.$ (1)

 Download: 图 1 栅格地图 Fig. 1 The grid map
1.2 方向信度函数

 ${y_j} = \left\{ {\begin{array}{*{20}{l}}{1 - \displaystyle\frac{{\Delta {\theta _j}}}{\text{π} },\quad \text{机器人未陷入死区}}\\{\cos \Delta {\varphi _j},\quad \text{机器人陷入死区}}\end{array}} \right.$ (2)

 $\begin{array}{c}\!\!\!\!\!\!\!\!\! \Delta {\theta _j} = \left| {{\theta _j} - {\theta _c}} \right| = \\\!\!\!\!\!\!\!\!\! |a\tan 2({y_{{p_j}}} - {y_{{p_c}}},{x_{{p_j}}} - {x_{{p_c}}}) - a\tan 2({y_{{p_c}}} - {y_{{p_p}}},{x_{{p_c}}} - {x_{{p_p}}})|\end{array}$ (3)

 Download: 图 2 未陷入死区方向信度函数 Fig. 2 The direction belief function in the free zone
 Download: 图 3 陷入死区方向信度函数 Fig. 3 The direction belief function in the dead zone

 $\begin{array}{c}\Delta {\varphi _j} = \left| {{\varphi _T} - {\theta _j}} \right| = |a\tan 2({y_{{T_j}}} - {y_{{p_c}}},{x_{{T_j}}} - {x_{{p_c}}}){\kern 1pt} - \\{\kern 1pt} \;\;\;\;\;\;\;\;\;a\tan 2({y_{{p_j}}} - {y_{{p_c}}},{x_{{p_j}}} - {x_{{p_c}}})|\end{array}$ (4)

1.3 路径选择策略

 ${p_j} \Leftarrow {F_{{P_j}}} = \max \{ {F_j} = {x_j} + c{y_j},{\kern 1pt} \;\;\;j = 1,2,\cdots \!,k\}$ (5)

 Download: 图 4 各个栅格综合信度函数值 Fig. 4 The comprehensive belief function of each grid

 Download: 图 5 机器人路径选择过程 Fig. 5 The process of robot’s path selection

2 仿真实验分析

2.1 动态障碍物环境中全覆盖路径规划

 Download: 图 6 动态障碍物环境中的机器人全覆盖路径规划 Fig. 6 Complete-coverage path planning of robot in the dynamic obstacle environment
2.2 不同算法的比较

 Download: 图 7 不同算法全覆盖路径规划结果 Fig. 7 The results of complete-coverage path planning with different algorithms

3 结束语

 [1] 简毅, 张月. 移动机器人全局覆盖路径规划算法研究进展与展望[J]. 计算机应用, 2014, 34(10): 2844-2849, 2864. JIAN Yi, ZHANG Yue. Complete coverage path planning algorithm for mobile robot: progress and prospect[J]. Journal of computer applications, 2014, 34(10): 2844-2849, 2864. DOI:10.11772/j.issn.1001-9081.2014.10.2844 (0) [2] YAN Mingzhong, ZHU Daqi. An algorithm of complete coverage path planning for autonomous underwater vehicles[J]. Key engineering materials, 2011, 467-469: 1377-1385. DOI:10.4028/www.scientific.net/KEM.467-469 (0) [3] 莫宏伟, 马靖雯. 一种生物地理学移动机器人路径规划算法[J]. 智能系统学报, 2015, 10(5): 705-711. MO Hongwei, MA Jingwen. A biogeography-based mobile robot path planning algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(5): 705-711. (0) [4] LI Yan, CHEN Hai, JOO ER MENG, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876-885. DOI:10.1016/j.mechatronics.2010.10.009 (0) [5] 蒲兴成, 赵红全, 张毅. 细菌趋化行为的移动机器人路径规划[J]. 智能系统学报, 2014, 9(1): 69-75. PU Xingcheng, ZHAO Hongquan, ZHANG Yi. Mobile robot path planning research based on bacterial chemotaxis[J]. CAAI transactions on intelligent systems, 2014, 9(1): 69-75. (0) [6] KAPANOGLU M, ALIKALFA M, OZKAN M, et al. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time[J]. Journal of intelligent manufacturing, 2012, 23(4): 1035-1045. DOI:10.1007/s10845-010-0404-5 (0) [7] 杜鹏桢, 唐振民, 陆建峰, 等. 不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J]. 电子学报, 2014, 42(3): 616-624. DU Pengzhen, TANG Zhenmin, LU Jianfeng, et al. Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J]. Acta electronica sinica, 2014, 42(3): 616-624. (0) [8] BALCH T. The case for randomized search[C]//Proceedings of Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation. San Francisco, CA: IEEE Press, 2000: 213–215. (0) [9] HABIB M A, ALAM M S, SIDDQUE N H. Optimizing coverage performance of multiple random path-planning robots[J]. Paladyn, 2012, 3(1): 11-22. (0) [10] JIN Xin, GUPTA S, LUFF J M, et al. Multi-resolution navigation of mobile robots with complete coverage of unknown and complex environments[C]//Proceedings of 2012 American Control Conference. Montreal: IEEE Press, 2012: 4867–4872. (0) [11] YAZICI A, KIRLIK G, PARLAKTUNA O, et al. A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J]. IEEE transactions on cybernetics, 2014, 44(3): 305-314. DOI:10.1109/TCYB.2013.2253605 (0) [12] HSU P M, LIN Chunliang, YANG Mengyao. On the complete coverage path planning for mobile robots[J]. Journal of intelligent and robotic systems, 2014, 74(3/4): 945-963. (0) [13] 邱雪娜, 刘士荣, 宋加涛, 等. 不确定动态环境下移动机器人的完全遍历路径规划[J]. 机器人, 2006, 28(6): 586-592. QIU Xuena, LIU Shirong, SONG Jiatao, et al. A complete coverage path planning method for mobile robots in uncertain dynamic environments[J]. Robot, 2006, 28(6): 586-592. (0) [14] GUO Yi, BALAKRISHNAN M. Complete coverage control for nonholonomic mobile robots in dynamic environments[C]//Proceedings of 2006 IEEE International Conference on Robotics and Automation. Orlando, FL, USA: IEEE Press, 2006: 1704–1709. (0) [15] YANG S X, LUO Chaomin. A neural network approach to complete coverage path planning[J]. IEEE transactions on systems, man, and cybernetics, part B: cybernetics, 2004, 34(1): 718-724. DOI:10.1109/TSMCB.2003.811769 (0) [16] LUO Chaomin, YANG S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE transactions on neural networks, 2008, 19(7): 1279-1298. DOI:10.1109/TNN.2008.2000394 (0) [17] YAN Mingzhong, ZHU Daqi, YANG S X. Complete coverage path planning in an unknown underwater environment based on D-S data fusion real-time map building[J]. International journal of distributed sensor networks, 2012, 2012: 567959. DOI:10.1155/2012/567959 (0) [18] 朱大奇, 颜明重. 移动机器人路径规划技术综述[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. (0) [19] LEE T K, BAEK S H, CHOI Y H, et al. Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation[J]. Robotics and autonomous systems, 2011, 59(10): 801-812. DOI:10.1016/j.robot.2011.06.002 (0) [20] 欧阳鑫玉, 杨曙光. 基于势场栅格法的移动机器人避障路径规划[J]. 控制工程, 2014, 21(1): 134-137. OUYANG Xinyu, YANG Shuguang. Obstacle avoidance path planning of mobile robots based on potential grid method[J]. Control engineering of china, 2014, 21(1): 134-137. (0) [21] 郝宗波, 洪炳镕, 黄庆成. 基于栅格地图的机器人覆盖路径规划研究[J]. 计算机应用研究, 2007, 24(10): 56-58. HAO Zongbo, HONG Bingrong, HUANG Qingcheng. Study of coverage path planning based on grid-map[J]. Application research of computers, 2007, 24(10): 56-58. DOI:10.3969/j.issn.1001-3695.2007.10.016 (0) [22] SIPAHIOGLU A, KIRLIK G, PARLAKTUNA O, et al. Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach[J]. Robotics and autonomous systems, 2010, 58(5): 529-538. DOI:10.1016/j.robot.2010.01.005 (0)