一种改进的全覆盖路径规划算法

计算机与现代化 ›› 2021, Vol. 0 ›› Issue (02): 100-103.

一种改进的全覆盖路径规划算法

（1.河南工业职业技术学院电子信息工程学院，河南南阳473000;2.武汉大学计算机学院，湖北武汉430072）

出版日期:2021-03-01 发布日期:2021-03-01
作者简介:李淑霞(1982—),女,河南南阳人,讲师,硕士,研究方向:人工智能,嵌入式系统,E-mail: lisx0717@163.com；杨俊成(1982—),男,河南南阳人,副教授,博士研究生,研究方向:人工智能,大数据。
基金资助:
河南省高等学校青年骨干教师培养计划基金资助项目(2018GGJS230)

An Improved Complete Path Planning Algorithm

(1. School of Electronic Information Engineering, Henan Polytechnic Institute, Nanyang 473000, China;
2. School of Computer, Wuhan University, Wuhan 430072, China）

Online:2021-03-01 Published:2021-03-01

摘要/Abstract

摘要： 全覆盖路径规划在现实生活中具有很广泛的应用，本文针对已存在的全覆盖路径规划算法中的内螺旋算法进行改进，提出带有优先级的内螺旋算法PISC算法。在算法中加入行走优先级，并采用回溯法解决清扫机器人进入的死角问题，优化机器人的清扫路径，最后在Visual C+〖KG-*3〗+6.0编程环境下进行算法仿真。实验结果表明，清扫机器人能有效地避开障碍物，在自由区域顺利行走，提高了清扫机器人的清扫效率，减少了机器人清扫的重复路径。

关键词: 全覆盖路径规划, 内螺旋, 行走优先级, 回溯法

Abstract: Complete coverage path planning is widely used in real life. This paper improves the Internal Spiral Coverage algorithm that is one of the existing full coverage path planning algorithms. And the PISC algorithm with priority is proposed. It adds the walking priority to Internal Spiral Coverage algorithm, uses backtracking to solve the dead problem of cleaning robot, so as to optimize robots cleaning path. Finally, simulation experiments under Visual C+〖KG-*3〗+ 6.0 programming environment show this algorithm enables the cleaning robot to avoid obstacles effectively and smoothly walk in free area, so as to improve the cleaning efficiency of cleaning robot and reduce the repeat paths of cleaning robot.

Key words: complete coverage path planning, internal spiral coverage, walking priority, backtracking

李淑霞, 杨俊成, . 一种改进的全覆盖路径规划算法[J]. 计算机与现代化, 2021, 0(02): 100-103.

LI Shu-xia, YANG Jun-cheng, . An Improved Complete Path Planning Algorithm[J]. Computer and Modernization, 2021, 0(02): 100-103.

参考文献［23］

［1］	陈浩,王光林,郝询. 移动机器人的路径规划综述与发展趋势［J］. 物流技术与应用, 2020,25(10):158-160.
［2］	OH J S, CHOI Y H, PARK J B, et al. Complete coverage navigation of cleaning robots using triangular-cell-based map［J］. IEEE Transactions on Industrial Electronics, 2004,51(3):718-726.
［3］	LE A V, NHAN N H K, MOHANR E. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots［J］. Sensors, 2020,20(2):445.
［4］	ZHANG Y G, SCHERVISH M J, ACAR E U, et al. Probabilistic methods for robotic landmine search［C］// Proceedings of 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2001,3:1525-1532.
［5］	季长明. 面向室外清扫作业的机器人移动平台研制［D］. 北京:北京邮电大学, 2019.
［6］	PALACIN J, LASA X, MARCO S. Straight-line path following in cleaning robots using lateral ultrasonic sensors［C］// Proceedings of the 20th IEEE Instrumentation and Measurement Technology Conference. 2003,2:1484-1487
［7］	刘欢. 智能搜救机器人路径规划算法研究［D］. 长春:长春理工大学, 2020.
［8］	SAMPEDRO C, RODRIGUEZ-RAMOS A, BAVLE H, et al. A fully-autonomous aerial robot for search and rescue applications in indoor environments using learning-based techniques［J］. Journal of Intelligent & Robotic Systems, 2019,95(2):601-627.
［9］	陈鹏. 移动机器人全遍历覆盖路径规划研究［D］. 淄博:山东理工大学, 2014
［10］	杨俊成,李淑霞,蔡增玉. 路径规划算法的研究与发展［J］. 控制工程, 2017,24(7):1473-1480.
［11］	GAGE D W. Randomized search strategies with imperfect sensors［C］// Proceedings of SPIE Mobile Robots VIII. 1993,2058:270-279.
［12］	BALCH T. The case for randomized search［C］// Proceedings of Workshop on Sensors and Motion. IEEE International Conference on Robotics and Automation. 2000:213-215.
［13］	赵慧南,刘淑华,吴富章,等. 基于二分搜索的牛耕式全覆盖规划算法研究［J］. 计算机工程与应用, 2011,23:51-53.
［14］	QIU X N, LIU S R, SONG J T. A rolling method for complete coverage path planing in uncertain environments ［C］// 2004 IEEE International Conference on Robotics and Biomimentics. 2014:146-151.
［15］	郝宗波,洪炳镕,黄庆成. 基于栅格地图的机器人覆盖路径规划研究［J］. 计算机应用研究, 2007,24(10):56-58.
［16］	DE CARVALHO R N, VIDAL H A, VIEIRA P, et al. Complete coverage path planning and guidance for cleaning robots［C］// Proceedings of the IEEE International Symposium on Industrial Electronics. 1997,2:677-682.
［17］	CHOSET H. Coverage of known spaces: The boustrophedon cellular decomposition［J］. Autonomous Robots, 2000,9(3):247-253.
［18］	刘海，郭小勤，余得贵. 清洁机器人全覆盖路径规划算法综述［J］. 机电产品开发与创新， 2008, 21(6):36-38.
［19］	王俭,赵鹤鸣,陈卫东. 移动机器人全覆盖路径规划研究［J］. 微计算机信息, 2006(8):194-197.
［20］	刘淑华,夏菁,孙学敏,等. 已知环境下一种高效全覆盖路径规划算法［J］. 东北师大学报(自然科学版), 2011,43(4):39-43.
［21］	李磊,叶涛,谭民,等. 移动机器人技术研究现状与未来［J］. 机器人, 2002,24(5):475-480.
［22］	李淑霞,杨俊成. 一种室内清扫机器人路径规划算法［J］. 计算机系统应用, 2014(9):170-172.
［23］	林丹. 一种室内清洁机器人返回路径规划算法［J］. 重庆科技学院学报(自然科学版), 2010,12(1):110-113.

[1]	孙国伟;买阿丽. 基于对称性计算N皇后问题的非递归算法[J]. 计算机与现代化, 2013, 1(1): 19-21.
[2]	应莉. 0-1背包问题及其算法分析[J]. 计算机与现代化, 2009, 1(6): 24-26.