基于分治思想的扫地机器人全覆盖路径规划算法研究

doi:10.16088/j.issn.1001-6600.2020100402

广西师范大学学报（自然科学版） ›› 2021, Vol. 39 ›› Issue (6): 54-62.doi: 10.16088/j.issn.1001-6600.2020100402

基于分治思想的扫地机器人全覆盖路径规划算法研究

许伦辉^*, 林世城

华南理工大学土木与交通学院, 广东广州 510641

收稿日期:2020-10-04 修回日期:2020-11-10 出版日期:2021-11-25 发布日期:2021-12-08
通讯作者: 许伦辉(1965—), 男, 江西南康人, 华南理工大学教授, 博导。E-mail: lhxu@scut.edu.cn
基金资助:
国家自然科学基金(61572233); 广东省科技计划项目(2016A040403045, 2017B030307001)

Research on Full Coverage Path Planning Algorithm of Sweeping Robot Based on Divide and Conquer

XU Lunhui^*, LIN Shicheng

School of Civil and Transportation, South China University of Technology, Guangzhou Guangdong 510641, China

Received:2020-10-04 Revised:2020-11-10 Online:2021-11-25 Published:2021-12-08

摘要/Abstract

摘要： 针对大多数扫地机器人在进行全覆盖路径规划时,普遍存在重复率偏高和覆盖率偏低问题,并且在遇到密集零散的障碍区域时,会产生线路规划凌乱甚至不能覆盖的问题,设计一种基于分治思想的全覆盖路径规划算法,通过在地图上构建若干线段序列,按照线段序列端点间曼哈顿距离最小原则对局部路径线段进行相连,形成若干弓形线路块;然后采用分治算法实现全局各弓形线路块间最近端点对的匹配,并进行衔接,最终生成路径均匀的全覆盖线路。通过与牛耕式单元分解结合生物激励神经网络覆盖算法进行场景实验对比,分析表明在密集零散的障碍区域中,本文算法仍能规划出整齐平滑的可通行路径,覆盖率仍能高达91.3%,重复率下降约39.3%,时间花销约降低28.1%。

关键词: 全覆盖路径规划, 曼哈顿距离, 分治思想, 线段序列, 扫地机器人

Abstract: Most of the sweeping robots have the problems of high repetition rate and low coverage rate. When planning the full coverage path and encountering dense and scattered obstacle areas, the route planning is messy and even can’t be covered. Therefore, this paper designs a full coverage path planning algorithm based on divide and conquer idea. By constructing a number of line segments on the map, the local path segments are connected according to the principle of minimum Manhattan distance between the endpoints of line segments to form a number of arcuate circuit blocks. Then, divide and conquer algorithm is used to realize the global matching of the nearest end points of each bow block and connect them. A full coverage route with uniform path is generated. Compared with the cow tillage unit decomposition combined with bio inspired neural network coverage algorithm, the analysis shows that in the dense and scattered obstacle areas, the algorithm can plan a neat and smooth passable path, the coverage rate can reach 91.3%, the repetition rate is reduced by 39.3%, and the time cost is reduced by 28.1%.

Key words: full coverage path planning, manhattan distance, divide and conquer algorithm, line sequence, sweeping robot

中图分类号:

TP242

许伦辉, 林世城. 基于分治思想的扫地机器人全覆盖路径规划算法研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(6): 54-62.

XU Lunhui, LIN Shicheng. Research on Full Coverage Path Planning Algorithm of Sweeping Robot Based on Divide and Conquer[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(6): 54-62.

参考文献

[1] 高亚男. 清洁机器人全覆盖导航技术研究[D]. 济南:山东大学,2016.
[2] 马云飞. 移动机器人全覆盖路径规划与自主导航算法研究[D]. 北京:北京邮电大学,2019.
[3] 任云天. 扫地机器人避障全覆盖路径规划算法的研究与设计[D]. 武汉:华中科技大学,2019.
[4] 王鼎新. 基于改进Q-learning算法的AGV路径规划[J]. 电子设计工程,2021, 29(4):7-10, 15.
[5] 周林娜,汪芸,张鑫,等. 矿区废弃地移动机器人全覆盖路径规划[J].工程科学学报,2020,42(9):1220-1228. DOI:10.13374/j.issn2095-9389.2019.09.09.004.
[6] 李楷,陈永府,金志勇,等.基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学,2019,41(7):1227-1235. DOI:10.3969/j.issn.1007-130X.2019.07.012.
[7] 刘晶,姚维,章玮. 移动机器人全覆盖路径规划算法研究[J]. 工业控制计算机,2019,32(12):52-54.
[8] 赵慧南,刘淑华,吴富章,等. 基于二分搜索的牛耕式全覆盖规划算法研究[J]. 计算机工程与应用,2011,47(23):51-53,60. DOI:10.3778/j.issn.1002-8331.2011.23.015.
[9] ŠELEK A,SEDER M,PETROVIĆ I. Mobile robot navigation for complete coverage of an environment[J]. IFAC-PapersOnLine,2018,51(22):512-517. DOI:10.1016/j.ifacol.2018.11.582.
[10] LIU H,MA J Y,HUANG W B. Sensor-based complete coverage path planning in dynamic environment for cleaning robot[J]. CAAI Transactions on Intelligence Technology,2018,3(1):65-72. DOI:10.1049/trit.2018.0009.
[11] LE A V,NHAN N H K,MOHAN R E. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots[J]. Sensors,2020,20(2):445. DOI:10.3390/s20020445.
[12] KHAN A,NOREEN I,TYU H,et al. Online complete coverage path planning using two-way proximity search[J]. Intelligent Service Robotics,2017,10(3):229-240. DOI:10.1007/s11370-017-0223-z.
[13] SANDAMURTHY K,RAMANUJAM K. A hybrid weed optimized coverage path planning technique for autonomous harvesting in cashew orchards[J]. Information Processing in Agriculture,2020,7(1):152-164. DOI:10.1016/j.inpa.2019.04.002.
[14] 张丹红,陈文文,张华军,等. A^*算法与蚁群算法相结合的无人艇巡逻路径规划[J]. 华中科技大学学报(自然科学版),2020,48(6):13-18. DOI:10.13245/j.hust.200603.
[15] 宁洪斌,祝俊伟,邓小飞,等. 移动机器人滑模路径的跟踪控制[J]. 吉首大学学报(自然科学版),2020,41(1):30-34. DOI:10.13438/j.cnki.jdzk.2020.01.006.
[16] 周玉林,熊鹏荣,朱洪. 求平面点集最近点对的一个改进算法[J]. 计算机研究与发展,1998,35(10):956-960.
[17] 杜聪,张喆,李温静,等. 基于狄利克雷分布的可信路由转发机制[J]. 北京邮电大学学报,2020,43(1):74-79. DOI:10.13190/j.jbupt.2019-089.
[18] 姜春茂,张国印. 使用动态矩形窗求最近点对的几何算法[J]. 哈尔滨工程大学学报,2013,34(3):350-357.DOI:10.3969/j.Issn.1006-7043.201204044.
[19] 蔡火荣. 基于分治策略的物流在途时间预测模型研究[D].杭州:浙江理工大学,2017.
[20] 王洪斌,尹鹏衡,郑维,等. 基于改进的A^*算法与动态窗口法的移动机器人路径规划[J]. 机器人,2020,42(3):346-353. DOI:10.13973/j.cnki.robot.190305.
[21] 许伦辉,刘景柠,朱群强,等. 自动引导车路径偏差的控制研究[J].广西师范大学学报(自然科学版),2015,33(1):1-6. DOI:10.16088/j.issn.1001-6600.2015.01.001.
[22] HESS W ,KOHLER D ,RAPP H ,et al. Real-time loop closure in 2D LIDAR SLAM[C]//2016 IEEE International Conference on Robotics and Automation (ICRA). Piscataway,NJ:IEEE,2016:1271-1278. DOI:10.1109/ICRA.2016.7487258.
[23] 马小陆,梅宏.基于JPS策略的ACS移动机器人全局路径规划[J]. 机器人,2020,42(4):494-502.DOI:10.13973/j.cnki.robot.190463.
[24] 王耀南,潘琪,陈彦杰. 改进型生物激励神经网络的路径规划方法[J]. 控制工程,2018,25(4):541-548. DOI:10.14107/j.cnki.kzgc.151019.
[25] LAKSHMANAN A K,MOHAN R E,RAMALINGAM B,et al. Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot[J]. Automation in Construction,2020,112:103078. DOI:10.1016/j.autcon.2020.103078.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于分治思想的扫地机器人全覆盖路径规划算法研究

Research on Full Coverage Path Planning Algorithm of Sweeping Robot Based on Divide and Conquer

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

Metrics

本文评价

推荐阅读 10

[1]	陈林奇,李廷会. 基于双空间PSO算法的四旋翼无人机自抗扰控制器优化设计[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 42-49.
[2]	谢小辉, 孙立宁, 张峰峰. 基于事件的机器人主-被动混合力-位控制方法[J]. 广西师范大学学报（自然科学版）, 2020, 38(2): 121-127.