移动机器人全局覆盖路径规划算法研究进展与展望

doi:10.11772/j.issn.1001-9081.2014.10.2844

摘要/Abstract

摘要：

首先通过势场栅格法、单元分解法、全局与局部转换法等三大方法介绍了单移动机器人各种不同的全覆盖算法，分析了各种不同算法的性能，指出了它们的优缺点，并对每种方法的改进方法进行了探讨分析;另外，针对多机器人协作全覆盖路径规划的研究，探讨了基于单机器人全覆盖路径规划算法和任务分配算法等结合得到的多机器人协作路径规划算法;最后探讨移动机器人全覆盖路径规划算法的研究方向。分析结果表明，对于移动机器人全覆盖算法的研究，可充分利用现有算法的优势互补，或借助多学科交叉的优势，寻找更有效的算法。

Abstract:

Different complete coverage algorithms for single mobile robot were classified into three kinds. They are potential filed grid based, cellular decomposition based, and transformation between local transform and global transform based approaches. Their performances were analyzed and the advantages and disadvantages were pointed out, then the improved methods were discussed and analyzed. In addition, the complete coverage path planning algorithms for multiple mobile robots based on combination of single robot path planning algorithm and task allocation were investigated. Finally, the further research direction of complete coverage algorithm for mobile robots was discussed. The analytical results show that the full use of complementary advantages of the current algorithms, or taking multi-disciplinary advantages may provide whole algorithm of mobile robot research with more efficient algorithm.

中图分类号:

TP242.6

简毅张月. 移动机器人全局覆盖路径规划算法研究进展与展望[J]. 计算机应用, 2014, 34(10): 2844-2849.

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.

参考文献

［1］FAN Y, TAN M. The present situation and prospect of robot controller ［J］. Robot, 1999,21(1):75-80.(范永,谭民.机器人控制器的现状及展望［J］.机器人,1999,21(1):75-80.)
［2］YUAN Z, GAO M. A new method for navigation of mobile robot and collision avoidance in a dynamic environment ［J］. Robot, 2000,22(2):81-88.(袁曾任,高明.在动态环境中移动机器人导航和避碰的一种新方法［J］.机器人,2000,22(2):81-88.)［3］LI L, YE T. The present situation and prospect of mobile robot technology ［J］. Robot, 2002,24(5):475-480.(李磊,叶涛.移动机器人技术研究现状与未来［J］.机器人,2002,24(5):475-480.)
［4］WANG Z, GUO G. The present situation and prospect of navigation for mobile robot ［J］. Robot, 2003,25(5):470-474.(王志文,郭戈.移动机器人导航技术现状与展望［J］.机器人,2003,25(5):470-474.)
［5］HAO Z, HONG B, HUANG Q. The planning research of coverage method by robot based on the grid map ［J］. Application Research of Computers, 2007,24(10):56-58.(郝宗波,洪炳镕,黄庆成.基于栅格地图的机器人覆盖路径规划研究［J］.计算机应用研究,2007,24(10):56-58.)
［6］ZELINSKY A. A mobile robot exploration algorithm ［J］. IEEE Transactions on Robotics and Automation, 1992,8(6):707-717.
［7］ZELINSKY A, JARVIS R A, BYRNE J C, et al.Planning paths of complete coverage of an unstructured environment by a mobile robot ［C］// Proceedings of International Conference on Advanced Robotics. Piscataway: IEEE Press, 1993:533-538.
［8］CHOI Y H, LEE T K, BAEK S H, et al.Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform ［C］// Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE Press, 2009:5788-5793.
［9］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.
［10］MICHEL D, McLSAAC K. New path planning scheme for complete coverage of mapped areas by single and multiple robots ［C］// Proceedings of the 2012 International Conference on Mechatronics and Automation. Piscataway: IEEE Press, 2012:1233-1240.
［11］MA Z, YUAN Z. The real-time navigation and obstacle avoidance of mobile robot based on the grid map ［J］. Robot, 1996,18(6):344-348.(马兆青,袁曾任.基于栅格方法的移动机器人实时导航和避障［J］.机器人,1996,18(6):344-348.)
［12］CHOSET H. Coverage for robotics—a survey of recent results ［J］. Annals of Mathematics and Artificial Intelligence, 2001,31(1/2/3/4):113-126.
［13］LATOMBE J C. Robot motion planning ［M］. Dordrecht: Kluwer Academic Publishers, 1996.
［14］CHOSET H. Coverage of known spaces: the boustrophedon cellular decomposition ［J］. Autonomous Robots, 2000,9(3):247-253.
［15］TIAN C, LIU Y, FENG S, et al.Complete coverage algorithm of mobile robot—rectangular decomposition method ［J］. Chinese Journal of Mechanical Engineering, 2005,40(10):56-61.(田春颖,刘瑜,冯申坤,等.基于栅格地图的移动机器人完全遍历算法——矩形分解法［J］.机械工程学报,2005,40(10):56-61.)
［16］GARCIA E, de SANTOS GONZALEZ P. Mobile-robot navigation with complete coverage of unstructured environments ［J］. Robotics and Autonomous Systems, 2004,46(4):195-204.
［17］WANG J, ZHAO H, CHEN W. The study of complete coverage path planning method for mobile robot ［J］. Microcomputer Information, 2006(8):194-197.(王俭,赵鹤鸣,陈卫东.移动机器人全覆盖路径规划研究［J］.微计算机信息,2006(8):194-197.)
［18］WANG J, CHEN W, ZHAO H. A method for complete coverage path planning of mobile robot ［J］. Computer Engineering, 2005,22(31):162-163.(王俭，陈卫东，赵鹤鸣.移动机器人全覆盖路径规划优化方法［J］.计算机工程,2005,22(31):162-163.)
［19］COLORNI A, DORIGO M, MANIEZZO V. An investigation of some properties of an "ant algorithm" ［C］// Proceedings of the Parallel Problem Solving from Nature Conference. Brussels: Elsevier Publishing, 1992:509-520.
［20］ZHANG C, WANG X. Complete coverage path planning based on ant colony algorithm ［J］. China Mechanical Engineering, 2008,19(16):1945-1949.(张赤斌,王兴松.基于蚁群算法的完全遍历路径规划研究［J］.中国机械工程,2008,19(16):1945-1949.)
［21］HOFNER C, SCHMIDT G K. Path planning and guidance techniques for an autonomous mobile cleaning robot ［C］// Proceedings of the IEEE/RSJ/GI International Conference on Intelligent Robots and Systems: Advanced Robotic Systems and the Real World. Piscataway: IEEE Press, 1994:610-617.
［22］JIMENEZ P A, SHIRINZADEH B, NICHOLSON A, et al.Optimal area covering using genetic algorithms ［C］// Proceedings of the 2007 IEEE/ASME International Conference on Advanced Intelligent Mechatronics. Piscataway: IEEE Press, 2007:1-5.
［23］LIU S, LI Z, LI Q. Improved genetic algorithms optimal area covering path planning for family robot ［J］. Computer Engineering and Applications, 2009,45(31):245-248.(刘松,李志蜀,李奇.机器人全覆盖最优路径规划的改进遗传算法［J］.计算机工程与应用,2009,45(31):245-248.)
［24］KANG J W, KIM S J, CHUNG M J, et al.Path planning for complete and efficient coverage operation of mobile robots ［C］// Proceedings of the 2007 International Conference on Mechatronics and Automation. Piscataway: IEEE Press, 2007:2126-2131.
［25］GABRIELY Y, RIMON E. Spanning-tree based coverage of continuous areas by a mobile robot ［J］. Annals of Mathematics and Artificial Intelligence, 2001,31(1/2/3/4):77-98.
［26］GABRIELY Y, RIMON E. Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot ［C］// Proceedings of the 2002 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2002,1:954-960.
［27］GABRIELY Y, RIMON E. Competitive on-line coverage of grid environments by a mobile robot ［J］. Computational Geometry, 2003,24(3):197-224.
［28］BALCH T. The case for randomized search ［C］// Proceedings of the 2000 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2000:213-215.
［29］JIN X, GUPTA S, LUFF J M, et al.Multi-resolution navigation of mobile robots with complete coverage of unknown and complex environments ［C］// Proceedings of the 2012 American Control Conference. Piscataway: IEEE Press, 2012:4867-4872.
［30］ZOU A, HOU Z, FU S, et al.Advances in neural networks-ISNN 2006 ［M］. Berlin: Springer, 2006:1218-1226.
［31］HODGKIN A L, HUXLEY A F. A quantitative description of membrane current and its application to conduction and excitation in nerve ［J］. The Journal of Physiology, 1952,117(4):500-544.
［32］YANG S, LUO C. 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.
［33］LUO C, YANG S. 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.
［34］GUO Y, BALAKRISHNAN M. Complete coverage control for nonholonomic mobile robots in dynamic environments ［C］// Proceedings 2006 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2006:1704-1709.
［35］QIU X, LIU S, SONG J. A complete coverage path planning method for mobile robots in uncertain dynamic environments ［J］. Robot, 2006,28(6):586-592.(邱雪娜,刘士荣,宋加涛.不确定动态环境下移动机器人的完全遍历路径规划［J］.机器人,2006,28(6):586-592.)
［36］ZHANG C, XI Y. Rolling path planning of mobile robot in dynamic unknown environment ［J］. Robot, 2002,24(1):71-75.(张纯刚,席裕庚.动态未知环境中移动机器人的滚动路径规划［J］.机器人,2002,24(1):71-75.)
［37］GUO X. Complete coverage path planning method for mobile robots in unknown environments ［J］. Computer Engineering and Design, 2010,31(1):172-174.(郭小勤.未知环境下移动机器人遍历路径规划［J］.计算机工程与设计,2010,31(1):172-174.)
［38］JANCHIV A, BATSAIKHAN D, KIM G H, et al.Complete coverage path planning for multi-robots based on ［C］// Proceedings of the 2011 11th International Conference on Control, Automation and Systems. Piscataway: IEEE Press, 2011:824-827.
［39］REKLEITIS I, NEW A P, RANKIN E S, et al.Efficient boustrophedon multi-robot coverage: an algorithmic approach ［J］. Annals of Mathematics and Artificial Intelligence, 2008,52(2/3/4):109-142.
［40］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.
［41］LUO C, YANG S. A real-time cooperative sweeping strategy for multiple cleaning robots ［C］// Proceedings of the 2002 IEEE International Symposium on Intelligent Control. Piscataway: IEEE Press, 2002:660-665.
［42］LUO C, YANG S, STACEY D A. Real-time path planning with deadlock avoidance of multiple cleaning robots ［C］// Proceedings of the 2003 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2003:4080-4085.
［43］HAZON N, KAMINKA G A. Redundancy, efficiency and robustness in multi-robot coverage ［C］// Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2005:735-741.
［44］ZHENG X, JAIN S, KOENIG S, et al.Multi-robot forest coverage ［C］// Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE Press, 2005:3852-3857.
［45］HAZON N, MIELI F, KAMINKA G A. Towards robust on-line multi-robot coverage ［C］// Proceedings 2006 IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2006:1710-1715.
［46］HAZON N, KAMINKA G A. On redundancy, efficiency, and robustness in coverage for multiple robots ［J］. Robotics and Autonomous Systems, 2008,56(12):1102-1114.
［47］PARLAKTUNA O, SIPAHIOGLU A, KIRLIK G, et al.Multi-robot sensor-based coverage path planning using capacitated arc routing approach ［C］// Proceedings of the 2009 IEEE Conference on Control Applications. Piscataway: IEEE Press, 2009:1146-1151.
［48］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.
［49］HSU P-M, LIN C-L, YANG M-Y. On the complete coverage path planning for mobile robots ［J］. Journal of Intelligent and Robotic Systems, 2014,74(3/4):945-963.
［50］MAO Y, DOU L, CHEN J, et al.Combined complete coverage path planning for autonomous mobile robot in indoor environment ［C］// Proceedings of the 2009 7th Asian Control Conference. Piscataway: IEEE Press, 2009:1468-1473.
［51］YAN M, ZHU D, YANG S. Complete coverage path planning in an unknown underwater environment based on D-S data fusion real-time map building ［EB/OL］. ［2014-03-05］. http://www.hindawi.com/journals/ijdsn/2012/567959/.

[1]	卢金燕戚肖克. 基于点线特征的解耦视觉伺服控制方法[J]. 计算机应用, 0, (): 0-0.
[2]	郑思诚, 孔令华, 游通飞, 易定容. 动态环境下基于深度学习的语义SLAM算法[J]. 计算机应用, 2021, 41(10): 2945-2951.
[3]	黄巨挺, 高宏力, 戴志坤. 基于编码解码结构的移动端电力线语义分割方法[J]. 计算机应用, 2021, 41(10): 2952-2958.
[4]	郑李萍, 王建强, 张玉召, 董祚帆. 多时空配送任务驱动的无人车队车辆数优化方法[J]. 计算机应用, 2021, 41(5): 1406-1411.
[5]	栾佳宁, 张伟, 孙伟, 张奥, 韩冬. 基于二维码视觉与激光雷达融合的高精度定位算法[J]. 计算机应用, 2021, 41(5): 1484-1491.
[6]	梁臻, 房体育, 李金屏. 基于虚拟导航线的农业机器人精确视觉导航方法[J]. 计算机应用, 2021, 41(1): 191-198.
[7]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[8]	赵宏, 刘向东, 杨永娟. 基于RGB-D图像的室内机器人同时定位与地图构建[J]. 计算机应用, 2020, 40(12): 3637-3643.
[9]	席志红, 王洪旭, 韩双全. 基于ORB-SLAM2系统的快速误匹配剔除算法与地图构建[J]. 计算机应用, 2020, 40(11): 3289-3294.
[10]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[11]	罗飞, 刘鹏飞, 罗元, 朱思蒙. 多特征融合的运动想象脑电特征提取方法[J]. 计算机应用, 2020, 40(2): 616-620.
[12]	席志红, 韩双全, 王洪旭. 基于语义分割的室内动态场景同步定位与语义建图[J]. 计算机应用, 2019, 39(10): 2847-2851.
[13]	付久鹏, 曾国辉, 黄勃, 方志军. 基于双向快速探索随机树的狭窄通道路径规划[J]. 计算机应用, 2019, 39(10): 2865-2869.
[14]	黄超, 梁圣涛, 张毅, 张杰. 基于多目标蝗虫优化算法的移动机器人路径规划[J]. 计算机应用, 2019, 39(10): 2859-2864.
[15]	赵旭浩, 王轶群, 刘健, 徐春晖. 基于能量约束的自主水下航行器任务规划算法[J]. 计算机应用, 2019, 39(9): 2529-2534.