基于多层代价地图的启发式覆盖路径规划算法

doi:10.3778/j.issn.1002-8331.2312-0440

摘要/Abstract

摘要： 为更好地解决室外起伏地形下移动机器人的覆盖路径规划问题，提出了一种基于多层代价地图的启发式覆盖方法。分析了地形可穿越性评估的重要性，并结合机器人的运动学模型，生成了包含高度、坡度和粗糙度信息的多层二维栅格地图。以可穿越层为基本层，同时调用高度层地图信息，提出了一种基于能耗最优的多目标启发式算法，综合了距离、旋转角度和地形高度变化因素，为机器人提供了在复杂室外环境中高效且节能的路径规划。提出的方法能有效排除不可穿越区域，并通过启发式算法降低能耗。仿真与真实场景实验表明，与Z字形和螺旋形算法相比，该研究方法在路径长度、旋转角度和能耗上均具有显著优势。

关键词: 移动机器人, 覆盖路径规划, 启发式算法, 可穿越性评估

Abstract: For the problem of coverage path planning for mobile robots in undulating terrains, a heuristic coverage method based on multi-layer cost maps is proposed. The significance of terrain traversability assessment is analyzed, and a multi-layer two-dimensional grid map containing information on elevation, slope, and roughness is generated, considering the robot’s kinematics model. A new multi-objective heuristic algorithm leverages layers of traversability and height map information, synthesizing factors such as distance, rotational angle, and terrain elevation changes to provide efficient and energy-saving path planning for robots in complex outdoor settings. Through the methodology proposed in this study, the?non-traversable region can be effectively excluded, and energy consumption can be reduced through the heuristic algorithm. Simulations and real-world scenario experiments demonstrate that, compared to the Zig-zag and Spiral algorithms, the new method has significant advantages in terms of path length, rotation angles, and energy consumption.

Key words: mobile robots, coverage path planning, heuristic algorithm, traversability assessment

申思康, 孙波, 薛瑞雷, 马铜伟. 基于多层代价地图的启发式覆盖路径规划算法[J]. 计算机工程与应用, 2025, 61(9): 363-369.

SHEN Sikang, SUN Bo, XUE Ruilei, MA Tongwei. Multi-Layer Cost Map-Based Heuristic Coverage Path Planning Algorithm[J]. Computer Engineering and Applications, 2025, 61(9): 363-369.

参考文献

[1] ZHANG H M, HONG W, CHEN M J. A path planning strategy for intelligent sweeping robots[C]//Proceedings of the 2019 IEEE International Conference on Mechatronics and Automation. Piscataway: IEEE, 2019: 11-15.
[2] CHOI S, LEE S, VIET H H, et al. B-theta*: an efficient online coverage algorithm for autonomous cleaning robots[J]. Journal of Intelligent & Robotic Systems, 2017, 87(2): 265-290.
[3] ENGELSONS D, TIGER M, HEINTZ F. Coverage path planning in large-scale multi-floor urban environments with applications to autonomous road sweeping[C]//Proceedings of the 2022 International Conference on Robotics and Automation. Piscataway: IEEE, 2022: 3328-3334.
[4] HAMEED I A. Intelligent coverage path planning for agricultural robots and autonomous machines on three-dimensional terrain[J]. Journal of Intelligent & Robotic Systems, 2014, 74(3): 965-983.
[5] JEON C W, KIM H J, YUN C, et al. Design and validation testing of a complete paddy field-coverage path planner for a fully autonomous tillage tractor[J]. Biosystems Engineering, 2021, 208: 79-97.
[6] OKSANEN T, VISALA A. Coverage path planning algorithms for agricultural field machines[J]. Journal of Field Robotics, 2009, 26(8): 651-668.
[7] TANG J T, SUN C, ZHANG X Y. MSTC: multi-robot coverage path planning under physical constrain[C]//Proceedings of the 2021 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2021: 2518-2524.
[8] BORMANN R, JORDAN F, HAMPP J, et al. Indoor coverage path planning: survey, implementation, analysis[C]//Proceedings of the 2018 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2018: 1718-1725.
[9] BORMANN R, HAMPP J, H?GELE M. New brooms sweep clean-an autonomous robotic cleaning assistant for professional office cleaning[C]//Proceedings of the 2015 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2015: 4470-4477.
[10] SHANG G G, LIU G, ZHU P, et al. Complete coverage path planning for horticultural electric tractors based on an improved genetic algorithm[J]. Journal of Applied Science and Engineering, 2021, 24(3): 447-456.
[11] SHEN M W, WANG S Z, WANG S, et al. Simulation study on coverage path planning of autonomous tasks in hilly farmland based on energy consumption model[J]. Mathematical Problems in Engineering, 2020, 2020(1): 4535734.
[12] WEI M H, ISLER V. Coverage path planning under the energy constraint[C]//Proceedings of the 2018 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2018: 368-373.
[13] 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.
[14] NASR S, MEKKI H, BOUALLEGUE K. A multi-scroll chaotic system for a higher coverage path planning of a mobile robot using flatness controller[J]. Chaos, Solitons & Fractals, 2019, 118: 366-375.
[15] CAI Z Y, LI S X, GAN Y, et al. Research on complete coverage path planning algorithms based on A*Algorithms[J]. Proceedings of the Open Cybernetics & Systemics Journal, 2014, 8(1):418-426.
[16] TANG G, TANG C Q, ZHOU H, et al. R-DFS: a coverage path planning approach based on region optimal decomposition[J]. Remote Sensing, 2021, 13(8): 1525.
[17] BORMANN R, JORDAN F, HAMPP J, et al. Indoor coverage path planning: survey, implementation, analysis[C]//Proceedings of the 2018 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2018: 1718-1725.
[18] 赵慧南, 刘淑华, 吴富章, 等. 基于二分搜索的牛耕式全覆盖规划算法研究[J]. 计算机工程与应用, 2011, 47(23): 51-53.
ZHAO H N, LIU S H, WU F Z, et al. Research on boustrophedon complete coverage path planning based on binary search[J]. Computer Engineering and Applications, 2011, 47(23): 51-53.
[19] 谢必成, 张小俊. 立面维护作业的多机器人全覆盖路径规划[J]. 计算机工程与应用, 2023, 59(24): 319-327.
XIE B C, ZHANG X J. Complete coverage path planning for multiple robots for facade maintenance operations[J]. Computer Engineering and Applications, 2023, 59(24): 319-327.
[20] 刘松, 李志蜀, 李奇. 机器人全覆盖最优路径规划的改进遗传算法[J]. 计算机工程与应用, 2009, 45(31): 245-248.
LIU S, LI Z S, LI Q. Improved genetic algorithms optimal area covering path planning for family robot[J]. Computer Engineering and Applications, 2009, 45(31): 245-248.
[21] HAMEED I A, LA COUR-HARBO A, OSEN O L. Side-to-side 3D coverage path planning approach for agricultural robots to minimize skip/overlap areas between swaths[J]. Robotics and Autonomous Systems, 2016, 76: 36-45.
[22] LIN Y Y, NI C C, LEI N, et al. Robot coverage path planning for general surfaces using quadratic differentials[C]//Proceedings of the 2017 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2017: 5005-5011.
[23] JIN J, TANG L. Coverage path planning on three-dimensional terrain for arable farming[J]. Journal of Field Robotics, 2011, 28(3): 424-440.
[24] WU C M, DAI C K, GONG X X, et al. Energy-efficient coverage path planning for general terrain surfaces[J]. IEEE Robotics and Automation Letters, 2019, 4(3): 2584-2591.
[25] DOGRU S, MARQUES L. Energy efficient coverage path planning for autonomous mobile robots on 3D terrain[C]//Proceedings of the 2015 IEEE International Conference on Autonomous Robot Systems and Competitions. Piscataway: IEEE, 2015: 118-123.