Hierarchical Coverage Path Planning of Unmanned Aerial Vehicle Under Photogrammetric Constraints

doi:10.3778/j.issn.1002-8331.2409-0186

Abstract

Abstract: To achieve automatic inspection of aircraft surface, an unmanned aerial vehicle-based coverage path planning method is proposed, which guarantees high image quality and path regularity. Firstly, cell decomposition method is employed to satisfy the overlapping ratio constraint, and viewpoints are generated based on the cells to realize complete coverage, avoiding the solution of set cover problem. By meeting the photogrammetric constraints of equidistance, front view, and overlapping ratio, comprehensive and precise evaluation of aircraft surface damage and the condition of its components can be conducted using the captured images. Furthermore, coverage path is planned through hierarchical solution of traveling salesman problem, and the semantic information of aircraft is incorporated, allowing the path exhibits regularity at different levels, which aids operators in monitoring task completion and enhances the readability of collected data flow. In addition, an iterative optimization strategy is employed to make a compromise between the path optimality and the calculation speed. Finally, extensive simulations and comparisons are performed to validate the effectiveness of the proposed algorithm.

Key words: photogrammetric constraints, viewpoint generation, hierarchical path planning, automatic inspection of aircraft surface, unmanned aerial vehicle

摘要： 为了实现飞机表面的自动检测，提出了一种基于无人机的覆盖路径规划方法，该方法保证了图像的高质量和路径的规律性。采用单元格分解方法来满足重叠率约束，并基于单元格生成的视点实现全覆盖，避免集合覆盖问题的求解。通过满足正视、等距和重叠率等摄影测量约束，可以根据采集到的图像对飞机表面损伤及其部件状况进行全面且精确的评价。进一步通过分层求解旅行商问题来规划覆盖路径，并结合飞机的语义信息，使得路径在不同层次上呈现规律性，有助于操作人员监控任务的完成情况，并提高采集数据流的可读性。采用了一种迭代优化策略，在路径最优性和计算速度之间取得了权衡。大量的仿真实验和对比实验验证了所提算法的有效性。

关键词: 摄影测量约束, 视点生成, 分层路径规划, 飞机表面自动检测, 无人机

PIAO Minnan, ZHOU Yuhan, LI Haifeng, LI Haolong, SONG Dezhen. Hierarchical Coverage Path Planning of Unmanned Aerial Vehicle Under Photogrammetric Constraints[J]. Computer Engineering and Applications, 2025, 61(24): 322-330.

朴敏楠, 周雨晗, 李海丰, 李浩龙, 宋德臻. 摄影测量约束下无人机分层覆盖路径规划[J]. 计算机工程与应用, 2025, 61(24): 322-330.

References

[1] LIU Y P, DONG J X, LI Y D, et al. A UAV-based aircraft surface defect inspection system via external constraints and deep learning[J]. IEEE Transactions on Instrumentation and Measurement, 2022, 71: 5019315.
[2] YASUDA Y D V, CAPPABIANCO F A M, MARTINS L E G, et al. Aircraft visual inspection: a systematic literature review[J]. Computers in Industry, 2022, 141: 103695.
[3] SAHA A, KUMAR L, SORTEE S, et al. An autonomous aircraft inspection system using collaborative unmanned aerial vehicles[C]//Proceedings of the 2023 IEEE Aerospace Conference. Piscataway: IEEE, 2023: 1-10.
[4] 戴佳佳, 龚小溪, 汪俊. 面向飞机外表面检测任务的无人机覆盖路径规划方法[J]. 机械工程学报, 2023, 59(16): 243-253.
DAI J J, GONG X X, WANG J. Coverage path planning method of unmanned aerial vehicle for aircraft surface detection task[J]. Journal of Mechanical Engineering, 2023, 59(16): 243-253.
[5] WANG H P, ZHANG S Y, ZHANG X Y, et al. Near-optimal 3-D visual coverage for quadrotor unmanned aerial vehicles under photogrammetric constraints[J]. IEEE Transactions on Industrial Electronics, 2022, 69(2): 1694-1704.
[6] 张世勇, 张雪波, 苑晶, 等. 旋翼无人机环境覆盖与探索规划方法综述[J]. 控制与决策, 2022, 37(3): 513-529.
ZHANG S Y, ZHANG X B, YUAN J, et al. A survey on coverage and exploration path planning with multi-rotor micro aerial vehicles[J]. Control and Decision, 2022, 37(3): 513-529.
[7] ALMADHOUN R, TAHA T, GAN D M, et al. Coverage path planning with adaptive viewpoint sampling to construct 3D models of complex structures for the purpose of inspection[C]//Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2019: 7047-7054.
[8] 陈威, 王从庆, 曾强, 等. 面向飞机表面视觉检查的无人机覆盖路径规划[J]. 系统工程与电子技术, 2025, 47(4): 1206-1213.
CHEN W, WANG C Q, ZENG Q, et al. UAV coverage path planning for aircraft surface visual inspection[J]. Systems Engineering and Electronics, 2025, 47(4): 1206-1213.
[9] SILBERBERG P, LEISHMAN R C. Aircraft inspection by multirotor UAV using coverage path planning[C]//Proceedings of the 2021 International Conference on Unmanned Aircraft Systems. Piscataway: IEEE, 2021: 575-581.
[10] ALMADHOUN R, TAHA T, SENEVIRATNE L, et al. GPU accelerated coverage path planning optimized for accuracy in robotic inspection applications[C]//Proceedings of the 2016 IEEE 59th International Midwest Symposium on Circuits and Systems. Piscataway: IEEE, 2017: 1-4.
[11] ALMADHOUN R, TAHA T, SENEVIRATNE L, et al. Multi-robot hybrid coverage path planning for 3D reconstruction of large structures[J]. IEEE Access, 2022, 10: 2037-2050.
[12] SUN Y F, MA O. Automating aircraft scanning for inspection or 3D model creation with a UAV and optimal path planning[J]. Drones, 2022, 6(4): 87.
[13] 张二虎, 郑永帅, 杨朝栋, 等. 面向大飞机上表面视觉覆盖任务的无人机路径规划[J]. 计算机工程与应用, 2025, 61(12): 385-390.
ZHANG E H, ZHENG Y S, YANG C D, et al. UAV path planning for large aircraft upper surface visual coverage tasks[J]. Computer Engineering and Applications, 2025, 61(12): 385-390.
[14] MANSOURI S S, KANELLAKIS C, FRESK E, et al. Cooperative coverage path planning for visual inspection[J]. Control Engineering Practice, 2018, 74: 118-131.
[15] CAO C, ZHANG J, TRAVERS M, et al. Hierarchical coverage path planning in complex 3D environments[C]//Proceedings of the 2020 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2020: 3206-3212.
[16] CABREIRA T M, BRISOLARA L B, FERREIRA JR P R. Survey on coverage path planning with unmanned aerial vehicles[J]. Drones, 2019, 3(1): 4.
[17] CAO Y, CHENG X H, MU J Z. Concentrated coverage path planning algorithm of UAV formation for aerial photography[J]. IEEE Sensors Journal, 2022, 22(11): 11098-11111.
[18] JUNG S, SONG S, YOUN P, et al. Multi-layer coverage path planner for autonomous structural inspection of high-rise structures[C]//Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2019: 1-9.
[19] 陈艺, 于纪言. 复杂环境下无人机全覆盖三维路径规划算法[J]. 计算机集成制造系统, 2023, 29(8): 2563-2573.
CHEN Y, YU J Y. Full coverage 3D path planning algorithm for UAV in complex environment[J]. Computer Integrated Manufacturing Systems, 2023, 29(8): 2563-2573.
[20] GALCERAN E, CAMPOS R, PALOMERAS N, et al. Coverage path planning with real-time replanning and surface reconstruction for inspection of three-dimensional underwater structures using autonomous underwater vehicles[J]. Journal of Field Robotics, 2015, 32(7): 952-983.
[21] ENGLOT B, HOVER F S. Sampling-based sweep planning to exploit local planarity in the inspection of complex 3D structures[C]//Proceedings of the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2012: 4456-4463.
[22] PIAO M N, LI H F, ZHANG F, et al. Viewpoint generation for coverage inspection of airplane fuselage surface based on unmanned ground vehicles[C]//Proceedings of the 2023 42nd Chinese Control Conference. Piscataway: IEEE, 2023: 4413-4418.
[23] M?LLER T, TRUMBORE B. Fast, minimum storage ray-triangle intersection[J]. Journal of Graphics Tools, 1997, 2(1): 21-28.
[24] HELSGAUN K. An effective implementation of the Lin Kernighan traveling salesman heuristic[J]. European Journal of Operational Research, 2000, 126(1): 106-130.
[25] LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning[R]. The Annual Research Report. 1998.
[26] ENGLOT B, HOVER F. Planning complex inspection tasks using redundant roadmaps[C]//Proceedings of the 15th International Symposium on Robotics Research. Cham: Springer International Publishing, 2017: 327-343.
[27] MODARES J, GHANEI F, MASTRONARDE N, et al. UB-ANC planner: energy efficient coverage path planning with multiple drones[C]//Proceedings of the 2017 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2017: 6182-6189.