An Improved Complete Path Planning Algorithm

Abstract

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

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

References ［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]	HUANG Yi-hu, YU Ya-nan. Anti-collision Shortest Path Planning Based on Improved Dijkstra Algorithm [J]. Computer and Modernization, 2022, 0(08): 20-24.
[2]	ZHANG Lian-na, ZHANG Hui-ping, LI Rong-peng, SONG Xue-li. Sparse Signal Reconstruction of Backtracking Generalized Orthogonal Matching Pursuit Algorithm Based on Secondary Screening [J]. Computer and Modernization, 2022, 0(03): 111-115.
[3]	SUN Guowei;MAI Ali. A Nonrecursive Algorithm of Solving NQueens Problem Using Symmetry  [J]. Computer and Modernization, 2013, 1(1): 19-21.
[4]	WU Hong-ping. Implementation and Analysis of N Queens Problem with Java Language [J]. Computer and Modernization, 2011, 1(3): 15-16,2.