Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (4): 78-87.doi: 10.11896/jsjkx.250700190

• Interdisciplinary Integration of Artificial Intelligence and Theoretical Computer Science • Previous Articles     Next Articles

Mobile Robot Two-dimensional Full Coverage Path Planning Algorithm Based on MaklinkDiagram and Boustrophedon Path

LI Boyao1, ZHAO Binbin2, TAO Mingjie3, CHEN Lu4   

  1. 1 School of Business, China University of Political Science and Law, Beijing 100088, China
    2 School of Mathematical Sciences, Chengdu University of Technology, Chengdu 610051, China
    3 School of Physics, Chengdu University of Technology, Chengdu 610051, China
    4 School of Computer and Cyber Security, Chengdu University of Technology, Chengdu 610051, China
  • Received:2025-07-31 Revised:2025-12-23 Online:2026-04-15 Published:2026-04-08
  • About author:LI Boyao,born in 1988,Ph.D,associate professor,master’s supervisor.His main research interests include social computing,complex systems,financial algorithms and FinTech.
    ZHAO Binbin,born in 2006,undergra-duate.His main research interests include probability statistics and path planning.
  • Supported by:
    Youth Project of the National Natural Science Foundation of China(80303-AZ20240001),Program for Young Innovative Research Team in China University of Political Science and Law(25CXTD04) and Chengdu University of Technology Talent Construction Research Start-up Fund(10912-KYQD2024-10450).

PDF (PC)

75

Abstract: With the increasingly widespread application of complete coverage path planning of mobile robots in production inspection and home cleaning fields,the problems existing in the current algorithms are becoming increasingly obvious,such as high repetitive coverage rate,non-optimal transition paths between sub-regions,and insufficient adaptability to concave polygonal obstacles.Therefore,this paper proposes a two-dimensional complete coverage path planning algorithm for mobile robots,which integrates Maklink graph theory,improved ant colony algorithm and Boustrophedon path.Firstly,the method employs Maklink graph theory to construct an environmental model by generating link lines.These lines are then used to partition the two-dimensional space into multiple convex polygonal subregions and establish an initial feasible path network.Secondly,the method transforms the connection sequence of the sub-regions into a generalized “Traveling Salesman Problem” and uses one-dimensional ant colony algorithm to compute the sequence of the sub-regions that the robot visits.Then,the ant colony algorithm for minimizing results of function and triangular pruning geometric optimization algorithm is applied to obtain the optimal transition paths between sub-regions.Finally,the method performs a zigzag traversal within each sub-region through the visiting sequence by the Boustrophedon path in order to achieve global coverage path planning.Simulation experiments conducted in multiple two-dimensional environments with varying complexities demonstrate that the proposed method can effectively adapt to scenarios containing a variety of polygonal obstacles,achieving a coverage rate of 100% with zero redundancy.Meanwhile,the comparative experiments with only using the traditional ant colony algorithm and the improved ant colony algorithm,this algorithm performs well in three aspects,which are the length of the transformation path,the length of the traversal path,and the repetition rate.The comparison with the traditional full traversal method of constructing environmental models using the raster method shows that the proposed algorithm has high modeling accuracy and excellent storage efficiency.

Key words: Maklink diagram, Boustrophedon path, Ant colony algorithm, Path planning, Full traversal

CLC Number: 

  • TP242
[1]LIU Y J,ZENG G H,HUANG B.Research on path planning ofmobile robots based on improved ant colony optimization algorithm[J].Transducer and Microsystem Technologies,2020,39(4):56-58,62.
[2]PAN Y,LI L,QIN J,et al.Unmanned aerial vehicle-human collaboration route planning for intelligent infrastructure inspection[J].Computer-Aided Civil and Infrastructure Engineering,2024,39(14):2074-2104.
[3]MIAO S Y,ZHOU Y S.Design of motion control of tractor-trailer wheeled mobile robots with on-axle hitching based on curvature tracking method[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2024,41(2):26-33.
[4]WU Y F,LI J,BI S,et al.Research on improved ant colony algo-rithm for mountain hiking emergency rescue path planning[J].Journal of Geo-information Science,2023,25(1):90-101.
[5]TANG Y L,MU R R,ZHANG X F,et al.Research on path planning of rescue robots based on improved A* algorithm[J].Journal of Chongqing Technology and Business University(Na-tural Science Edition),2025 42(6):33-40.
[6]MAO J X,HE Z Y,WANG Y N,et al.Review of Path Planning Technology and Applications for Electric Power Inspection Robots[J].Control and Decision,2023,38(11):3009-3024.
[7]WU K,WU Z,LU S,et al.Full coverage path planning strategyfor cleaning robots in semi-structured outdoor environments[J].Robotics and Autonomous Systems,2025,192:105050.
[8]CHEN J Y,GUO Z J,YIN Y K.Full-traversal path planningand system design of intelligent lawn mower based on hybrid algorithm[J].Computer Science,2021,48(S1):633-637.
[9]LI J,SHENG H,ZHANG J,et al.Coverage path planning me-thod for agricultural spraying UAV in arbitrary polygon area[J].Aerospace,2023,10(9):755.
[10]CHEN Y,LU Z M,CUI J L,et al.A Complete Coverage Path Planning Algorithm for Lawn Mowing Robots Based on Deep Reinforcement Learning[J].Sensors,2025,25(2):416.
[11]HU Z H,YANG Z H,LIU X C,et al.Research on unmanned boat path planning algorithm based on navigation radar[J].Science Sinica Technologica,2021,51(11):1401-1409.
[12]YUE G F,ZHANG M,SHEN C,et al.Bidirectional smooth A-star algorithm for mobile robot navigation planning[J].Science Sinica Technologica,2021,51(4):459-468.
[13]SUN Y,FANG M,SU Y.AGV path planning based on improved Dijkstra algorithm[C]//Journal of Physics:Conference Series.Bristol:IOP Publishing,2021:012052.
[14]WANG J,CHI W,LI C,et al.Neural RRT*:Learning-based optimal path planning[J].IEEE Transactions on Automation Science and Engineering,2020,17(4):1748-1758.
[15]LI Q,XU Y,BU S,et al.Smart vehicle path planning based on modified PRM algorithm[J].Sensors,2022,22(17):6581.
[16]ZHANG W,WANG N,WU W.A hybrid path planning algo-rithm considering AUV dynamic constraints based on improved A* algorithm and APF algorithm[J].Ocean Engineering,2023,285:115333.
[17]LI Y,ZHAO J,CHEN Z,et al.A robot path planning method based on improved genetic algorithm and improved dynamic window approach[J].Sustainability,2023,15(5):4656.
[18]ZHAO L,BAI Y,WANG F,et al.Path planning for autonomous surface vessels based on improved artificial fish swarm algorithm:a further study[J].Ships and Offshore Structures,2023,18(9):1325-1337.
[19]PHUNG M D,HA Q P.Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J].Applied Soft Computing,2021,107:107376.
[20]DE CASTRO G G R,PINTO M F,BIUNDINI I Z,et al.Dynamic path planning based on neural networks for aerial inspection[J].Journal of Control,Automation and Electrical Systems,2023,34(1):85-105.
[21]LUO Q,WANG H,ZHENG Y,et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications,2020,32(6):1555-1566.
[22]LI Z L,LUO S P,JIA Y T.A review of path planning algorithms for mobile robots.Modern Information Technology[J].Modern Information Technology,2024,8(19):184-188.
[23]CAI Z,LIU J,XU L,et al.Cooperative path planning study of distributed multi-mobile robots based on optimised ACO algorithm[J].Robotics and Autonomous Systems,2024,179:104748.
[24]HAO Z M,AN P J,LI H Y,et al.Mobile Robot Path Planning Based on Enhanced Target-Inspired Ant Colony Algorithm[J].Science Technology and Engineering,2023,23(22):9585-9591.
[25]LIU Y Q,XIANG J,CAO S Q.Path planning for underwaterautonomous navigation robots based on improved ant colony algorithm[J].Computer Engineering and Science,2022,44(3):536.
[26]PENG X D.Improved visual path planning algorithms.Modern Information Technology[J].Modern Information Technology,2021,5(3):152-154,158.
[27]QIAN L X,LI H L,WANG H R,et al.Research on underwater target search and delivery strategy based on improved hidden Markov model[J].Scientia Sinica(Technologica),2025,55(3):520-539.
[28]ZHANG B F,XIE X L,HE A.Construction water path planning based on maklink diagram and cuckoo search algorithm[J].Journal of Shanghai Maritime University,2020,41(3):6-11,30.
[29]HOU T,LI J,PEI X,et al.A spiral coverage path planning algo-rithm for nonomnidirectional robots[J].Journal of Field Robo-tics,2025,42(5):2260-2279.
[30]TAN C S,MOHD-MOKHTAR R,ARSHAD M R.A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms[J].IEEE Access,2021,9:119310-119342.
[31]NASIRIAN B,MEHRANDEZH M,JANABI-SHARIFI F.Efficient coverage path planning for mobile disinfecting robots using graph-based representation of environment[J].Frontiers in Robotics and AI,2021,8:624333.
[32]MENG X G.Path planning strategy for unmanned boats orien-ted to observation tasks[J].Intelligent Computer and Applications,2020,10(8):76-83.
[33]WANG X Y,SHENG G J,ZHANG K,et al.Path Planning for Mowing Robots Based on Improved A* Algorithm and DFS Algorithm[J].Journal of China Agricultural Machinery,2023,44(2):142-147.
[1] GONG Jing, YANG Yufa, ZHENG Yifan, SUN Zhixin. Multi-objective Intelligent Warehousing Path Planning Based on Conflict Free Path Algorithm [J]. Computer Science, 2026, 53(4): 88-100.
[2] ZHANG Yongliang, LI Ziwen, XU Jiahao, JIANG Yuchen, CUI Ying. Congestion-aware and Cached Communication for Multi-agent Pathfinding [J]. Computer Science, 2025, 52(8): 317-325.
[3] FU Wenhao, GE Liyong, WANG Wen, ZHANG Chun. Multi-UAV Path Planning Algorithm Based on Improved Dueling-DQN [J]. Computer Science, 2025, 52(8): 326-334.
[4] LIU Qingyun, YOU Xiong, ZHANG Xin, ZUO Jiwei, LI Jia. Review of Path Planning Algorithms for Mobile Robots [J]. Computer Science, 2025, 52(6A): 240900074-10.
[5] YE Mingjun, WANG Shujian. UAV Path Planning Based on Improved Dung Beetle Optimization Algorithm [J]. Computer Science, 2025, 52(6A): 240900136-6.
[6] ZHAO Xuejian, YE Hao, LI Hao, SUN Zhixin. Multi-AGV Path Planning Algorithm Based on Improved DDPG [J]. Computer Science, 2025, 52(6): 306-315.
[7] YU Haonan, XI Wanqiang, QI Fei. UAV Path Planning Method Based on Ant Colony Mixed Potential Field Method [J]. Computer Science, 2025, 52(11A): 241100179-6.
[8] PENG Ke, LIU Hongsheng, ZHANG Zhicheng, ZHU Liang, HE Maiqing, ZHANG Xuhui, ZENG Qijin, ZHANG Siyuan. Path Planning for AGV Integrating Improved A* Algorithm and TEB Algorithm [J]. Computer Science, 2025, 52(11A): 240900148-7.
[9] LIU Yi, QI Jie. IRRT*-APF Path Planning Algorithm Considering Kinematic Constraints of Unmanned Surface Vehicle [J]. Computer Science, 2024, 51(9): 290-298.
[10] WEI Shuxin, WANG Qunjing, LI Guoli, XU Jiazi, WEN Yan. Path Planning for Mobile Robots Based on Modified Adaptive Ant Colony Optimization Algorithm [J]. Computer Science, 2024, 51(6A): 230500145-9.
[11] MA Yinghong, LI Xu’nan, DONG Xu, JIAO Yi, CAI Wei, GUO Youguang. Fast Path Recovery Algorithm for Obstacle Avoidance Scenarios [J]. Computer Science, 2024, 51(6): 331-337.
[12] SUN Didi, LI Chaochao. Dynamic Path Planning Algorithm for Heterogeneous Groups in Aircraft Carrier Aviation SupportOperations [J]. Computer Science, 2024, 51(3): 226-234.
[13] GU Wei, DUAN Jing, ZHANG Dong, HAO Xiaowei, XUE Honglin, AN Yi , DUAN Jie. Prediction of Spatial and Temporal Distribution of Electric Vehicle Charging Loads Based on Joint Data and Modeling Drive [J]. Computer Science, 2024, 51(11A): 231100110-6.
[14] AN Yang, WANG Xiuqing, ZHAO Minghua. Mobile Robots' Path Planning Method Based on Policy Fusion and Spiking Deep ReinforcementLearning [J]. Computer Science, 2024, 51(11A): 240100211-11.
[15] GU Chan, FU Yan, YE Shengli. Tourism Route Planning Based on Colored Traveling Salesman Problem [J]. Computer Science, 2024, 51(11A): 231200072-8.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.