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

• 研究论文 • 上一篇    下一篇

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

许伦辉*, 林世城   

  1. 华南理工大学 土木与交通学院, 广东广州 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   

  1. 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

PDF (PC)

851

摘要： 针对大多数扫地机器人在进行全覆盖路径规划时,普遍存在重复率偏高和覆盖率偏低问题,并且在遇到密集零散的障碍区域时,会产生线路规划凌乱甚至不能覆盖的问题,设计一种基于分治思想的全覆盖路径规划算法,通过在地图上构建若干线段序列,按照线段序列端点间曼哈顿距离最小原则对局部路径线段进行相连,形成若干弓形线路块;然后采用分治算法实现全局各弓形线路块间最近端点对的匹配,并进行衔接,最终生成路径均匀的全覆盖线路。通过与牛耕式单元分解结合生物激励神经网络覆盖算法进行场景实验对比,分析表明在密集零散的障碍区域中,本文算法仍能规划出整齐平滑的可通行路径,覆盖率仍能高达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
[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.
[1] 陈林奇,李廷会. 基于双空间PSO算法的四旋翼无人机自抗扰控制器优化设计[J]. 广西师范大学学报（自然科学版）, 2019, 37(3): 42-49.
[2] 谢小辉, 孙立宁, 张峰峰. 基于事件的机器人主-被动混合力-位控制方法[J]. 广西师范大学学报（自然科学版）, 2020, 38(2): 121-127.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 胡锦铭, 韦笃取. 不同阶次分数阶永磁同步电机的混合投影同步[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 1 -8 .
[2] 武康康, 周鹏, 陆叶, 蒋丹, 闫江鸿, 钱正成, 龚闯. 基于小批量梯度下降法的FIR滤波器[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 9 -20 .
[3] 刘东, 周莉, 郑晓亮. 基于SA-DBN的超短期电力负荷预测[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 21 -33 .
[4] 张伟彬, 吴军, 易见兵. 基于RFB网络的特征融合管制物品检测算法研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 34 -46 .
[5] 王金艳, 胡春, 高健. 一种面向知识编译的OBDD构造方法[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 47 -54 .
[6] 逯苗, 何登旭, 曲良东. 非线性参数的精英学习灰狼优化算法[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 55 -67 .
[7] 李莉丽, 张兴发, 李元, 邓春亮. 基于高频数据的日频GARCH模型估计[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 68 -78 .
[8] 李松涛, 李群宏, 张文. 三自由度碰撞振动系统的余维二擦边分岔与混沌控制[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 79 -92 .
[9] 赵红涛, 刘志伟. λ重完全二部3-一致超图λK(3)n,n分解为超图双三角锥[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 93 -98 .
[10] 李梦, 曹庆先 , 胡宝清. 1960—2018年广西大陆海岸线时空变迁分析[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 99 -108 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发