计算机科学 ›› 2026, Vol. 53 ›› Issue (4): 78-87.doi: 10.11896/jsjkx.250700190
李伯尧1, 赵斌斌2, 陶明杰3, 陈露4
LI Boyao1, ZHAO Binbin2, TAO Mingjie3, CHEN Lu4
摘要： 随着复杂障碍物环境下移动机器人的全覆盖路径规划在生产巡检、家庭卫生等领域的应用越来越广泛,现有方法存在的重复覆盖率高、子区域间转换路径复杂以及对凹多边形障碍物适应性不足等问题愈发凸显。因此,提出一种融合Maklink图论、改进蚁群算法和Boustrophedon路径的移动机器人全覆盖路径规划方法。该方法首先利用Maklink图论构建环境模型,生成链接线,利用链接线将二维空间划分为多个凸多边形子区域并构建初步可行路径网络;其次,将子区域访问顺序建模为广义的TSP问题,利用一维蚁群算法获取子区域间的访问序列;然后,结合求最小函数值的蚁群算法与三角剪枝几何优化,得到子区域间最优转换路径;最后,按照访问顺序在各子区域内采用Boustrophedon路径进行“弓”字形路径遍历,形成全局覆盖路径。在多个不同二维复杂度环境中的仿真实验表明,所提方法可有效适应存在多种多边形障碍物的环境,覆盖率均可达100%,重复率为0。与传统蚁群算法和改进蚁群算法两种单一算法的对比实验表明,该算法在转换路径长度、遍历路径长度及重复率三方面均具有较好的表现;与传统利用栅格法构建环境模型的全遍历方法的对比结果表明,该算法建模精度高,存储效率优。
中图分类号:
| [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] | 宫婧, 杨玉发, 郑一帆, 孙知信. 基于无冲突路径算法的多目标智能仓储路径规划 Multi-objective Intelligent Warehousing Path Planning Based on Conflict Free Path Algorithm 计算机科学, 2026, 53(4): 88-100. https://doi.org/10.11896/jsjkx.250200035 |
| [2] | 张永良, 李子文, 许家豪, 江雨宸, 崔滢. 基于拥塞感知和缓存通信的多智能体路径规划 Congestion-aware and Cached Communication for Multi-agent Pathfinding 计算机科学, 2025, 52(8): 317-325. https://doi.org/10.11896/jsjkx.240900012 |
| [3] | 付文浩, 葛礼勇, 汪文, 张淳. 基于改进Dueling-DQN的多无人机路径规划算法 Multi-UAV Path Planning Algorithm Based on Improved Dueling-DQN 计算机科学, 2025, 52(8): 326-334. https://doi.org/10.11896/jsjkx.240600104 |
| [4] | 刘清云, 游雄, 张欣, 左吉伟, 李佳. 移动机器人路径规划算法综述 Review of Path Planning Algorithms for Mobile Robots 计算机科学, 2025, 52(6A): 240900074-10. https://doi.org/10.11896/jsjkx.240900074 |
| [5] | 叶明君, 王姝鉴. 基于改进蜣螂优化算法的无人机路径规划 UAV Path Planning Based on Improved Dung Beetle Optimization Algorithm 计算机科学, 2025, 52(6A): 240900136-6. https://doi.org/10.11896/jsjkx.240900136 |
| [6] | 赵学健, 叶昊, 李豪, 孙知信. 基于改进DDPG的多AGV路径规划算法 Multi-AGV Path Planning Algorithm Based on Improved DDPG 计算机科学, 2025, 52(6): 306-315. https://doi.org/10.11896/jsjkx.240500099 |
| [7] | 余浩楠, 席万强, 齐飞. 基于蚁群混合势场法的无人机路径规划 UAV Path Planning Method Based on Ant Colony Mixed Potential Field Method 计算机科学, 2025, 52(11A): 241100179-6. https://doi.org/10.11896/jsjkx.241100179 |
| [8] | 彭可, 刘宏胜, 张志成, 朱亮, 贺劢勍, 张旭辉, 曾启瑾, 张嗣愿. 融合改进A*算法和TEB算法的AGV路径规划 Path Planning for AGV Integrating Improved A* Algorithm and TEB Algorithm 计算机科学, 2025, 52(11A): 240900148-7. https://doi.org/10.11896/jsjkx.240900148 |
| [9] | 刘意, 齐洁. 考虑无人艇运动学约束的IRRT*-APF路径规划算法 IRRT*-APF Path Planning Algorithm Considering Kinematic Constraints of Unmanned Surface Vehicle 计算机科学, 2024, 51(9): 290-298. https://doi.org/10.11896/jsjkx.230900017 |
| [10] | 赵宏伟, 董昌林, 丁兵如, 柴海龙, 潘志伟. 路径规划问题的多策略改进樽海鞘群算法研究 Study on Multi-strategy Improved Salp Swarm Algorithm for Path Planning Problem 计算机科学, 2024, 51(6A): 230600083-9. https://doi.org/10.11896/jsjkx.230600083 |
| [11] | 魏书鑫, 王群京, 李国丽, 许家紫, 文彦. 基于改进自适应蚁群算法的移动机器人路径规划 Path Planning for Mobile Robots Based on Modified Adaptive Ant Colony Optimization Algorithm 计算机科学, 2024, 51(6A): 230500145-9. https://doi.org/10.11896/jsjkx.230500145 |
| [12] | 孙迪迪, 李超超. 航母航空保障作业中异质群体的动态路径规划算法 Dynamic Path Planning Algorithm for Heterogeneous Groups in Aircraft Carrier Aviation SupportOperations 计算机科学, 2024, 51(3): 226-234. https://doi.org/10.11896/jsjkx.221200119 |
| [13] | 王紫阳, 王佳, 熊明亮, 王文涛. 基于改进近端策略优化算法的智能渗透路径研究 Intelligent Penetration Path Based on Improved PPO Algorithm 计算机科学, 2024, 51(11A): 231200165-6. https://doi.org/10.11896/jsjkx.231200165 |
| [14] | 安阳, 王秀青, 赵明华. 基于策略融合及Spiking DRL的移动机器人路径规划方法 Mobile Robots' Path Planning Method Based on Policy Fusion and Spiking Deep ReinforcementLearning 计算机科学, 2024, 51(11A): 240100211-11. https://doi.org/10.11896/jsjkx.240100211 |
| [15] | 蒋一波, 周泽宝, 李强, 周轲. 基于遗传算法的低碳导向的物流中心配送优化 Optimization of Low-carbon Oriented Logistics Center Distribution Based on Genetic Algorithm 计算机科学, 2024, 51(11A): 231200035-6. https://doi.org/10.11896/jsjkx.231200035 |
|
||
首页