面向屋顶巡检任务的无人机覆盖路径规划算法

doi:10.19678/j.issn.1000-3428.0069718

摘要/Abstract

摘要：

针对现有三维覆盖路径规划(CPP)算法存在求解效率低的问题, 提出一种基于视点采样的三维CPP算法。首先, 构建一种基于栅格降采样的视图规划模型, 将三维建筑屋顶分解至二维空间进行栅格采样提取视点, 并根据平面法向量特征信息计算视线方向, 通过组合视点和视线参数得到建筑屋顶视图数据, 有效消除视图数据的无序现象; 然后, 设计一种基于贪婪搜索的路径规划方案, 利用往复式和螺旋式覆盖路径的特点对视点访问顺序进行贪婪搜索, 并以路径长度、累计转角和高度变化作为评价指标进行优化求解, 生成建筑屋顶的最优覆盖路径, 显著提高路径搜索效率; 最后, 结合八叉树地图模型和覆盖路径信息进行冲突路径的碰撞检测, 并利用视点插值法优化冲突路径。选取平顶型、人字型、四坡型及其复合型建筑屋顶共8组数据进行CPP实验, 结果表明, 所提算法可实现理想的建筑屋顶CPP效果, 在保证覆盖路径综合评价指标最优的同时, 极大地提高了路径规划的求解效率。

关键词: 机载LiDAR, 屋顶巡检, 视图规划, 路径规划, 贪婪搜索

Abstract:

To address the problem of low solving efficiency in existing 3D Coverage Path Planning (CPP) algorithms, a novel 3D CPP algorithm based on viewpoint sampling is proposed. First, a view planning model based on grid downsampling is constructed. This model decomposes a 3D building roof into a 2D space for grid sampling to extract viewpoints. It determines the line of sight direction based on plane normal information. By combining viewpoint and line of sight parameters, building roof view data are obtained, effectively eliminating the disorder in the view data. Subsequently, a path planning scheme based on greedy search is designed. This scheme uses the characteristics of reciprocating and spiral coverage paths to perform a greedy search in the order of viewpoint visits and optimizes the solution using path length, cumulative turning angle, and height variation as evaluation metrics, thus generating the optimal coverage path for the building roof and significantly improving the path search efficiency. Finally, the octree map model and coverage path information are used for collision detection of conflicting paths and the viewpoint interpolation method is used to optimize the conflicting paths. CPP experiments are conducted using eight sets of data for flat, gable, hipped, and composite building roofs. The results show that the proposed algorithm can achieve ideal building roof CPP, significantly improving the solving efficiency of path planning while ensuring optimal comprehensive evaluation metrics for the coverage path.

Key words: airborne LiDAR, roof inspection, view planning, path planning, greedy search

李海旺, 王澳强, 张世龙, 郭彩玲, 李柏林. 面向屋顶巡检任务的无人机覆盖路径规划算法[J]. 计算机工程, 2025, 51(12): 357-367.

LI Haiwang, WANG Aoqiang, ZHANG Shilong, GUO Cailing, LI Bailin. Coverage Path Planning Algorithm for Unmanned Aerial Vehicles in Roof Inspection Tasks[J]. Computer Engineering, 2025, 51(12): 357-367.

https://www.ecice06.com/CN/Y2025/V51/I12/357

图/表 17

图1 建筑屋顶覆盖路径规划技术路线

Fig.1 Technical route for planning roof covering paths in buildings

图2 视图规划流程

Fig.2 Procedure of view planning

图3 路径规划流程

Fig.3 Procedure of path planning

图4 轨迹类型示意图

Fig.4 Schematic diagram of trajectory types

图5 左转、直行、右转轨迹判定方式

Fig.5 Determination methods for left, straight, right trajectories

图6 往复式覆盖路径赋分过程

Fig.6 Scoring process for reciprocating covering paths

图7 视点方位判定方式

Fig.7 Determining methods for viewpoint orientation

图8 螺旋式覆盖路径赋分过程

Fig.8 Scoring process for spiral covering paths

图9 碰撞路径优化示意图

Fig.9 Schematic diagram of collision path optimization

图10 建筑影像数据

Fig.10 Architectural image data

图11 建筑屋顶点云数据

Fig.11 Building roof point cloud data

图12 视图规划结果

Fig.12 View planning results

图13 路径规划结果

Fig.13 Path planning results

参考文献 25

1	俞玉瑾, 韩军, 赵庆喜, 等. 基于IHDR的自主学习巡检技术研究. 计算机工程, 2019, 45 (4): 311-315, 320. doi: 10.19678/j.issn.1000-3428.0050023
	YU Y J , HAN J , ZHAO Q X , et al. Research on autonomous learning inspection technology based on IHDR. Computer Engineering, 2019, 45 (4): 311-315, 320. doi: 10.19678/j.issn.1000-3428.0050023
2	DONG C Z , CATBAS F N . A review of computer vision-based structural health monitoring at local and global levels. Structural Health Monitoring, 2021, 20 (2): 692- 743. doi: 10.1177/1475921720935585
3	CABREIRA T , BRISOLARA L , FERREIRA P R J . Survey on coverage path planning with unmanned aerial vehicles. Drones, 2019, 3 (1): 4. doi: 10.3390/drones3010004
4	孙保燕, 莫春华, 薛伟, 等. 红外成像和倾斜摄影三维融合在建筑检测中的应用. 红外技术, 2022, 44 (9): 991- 998.
	SUN B Y , MO C H , XUE W , et al. Application of 3D fusion of infrared imaging and tilt photography in building detection. Infrared Technology, 2022, 44 (9): 991- 998.
5	刘春, 艾克然木·艾克拜尔, 蔡天池. 面向建筑健康监测的无人机自主巡检与裂缝识别. 同济大学学报(自然科学版), 2022, 50 (7): 921- 932.
	LIU C , AIKERAMMU A , CAI T C . UAV autonomous inspection and crack detection towards building health monitoring. Journal of Tongji University(Natural Science), 2022, 50 (7): 921- 932.
6	祝冰艳, 陈志华, 盛斌. 基于感知增强Swin Transformer的遥感图像检测. 计算机工程, 2024, 50 (1): 216- 223. doi: 10.19678/j.issn.1000-3428.0066941
	ZHU B Y , CHEN Z H , SHENG B . Remote sensing image detection based on perceptually enhanced Swin Transformer. Computer Engineering, 2024, 50 (1): 216- 223. doi: 10.19678/j.issn.1000-3428.0066941
7	GAO Y , ZHANG Y W . Path optimization of welding robot based on ant colony and genetic algorithm. Journal of Applied Mathematics, 2022, 2022, 3608899.
8	ZENG X , ZHU G Y , GAO Z H , et al. Surface polishing by industrial robots: a review. The International Journal of Advanced Manufacturing Technology, 2023, 125 (9): 3981- 4012.
9	SUN Y W , JIA J J , XU J T , et al. Path, feedrate and trajectory planning for free-form surface machining: a state-of-the-art review. Chinese Journal of Aeronautics, 2022, 35 (8): 12- 29. doi: 10.1016/j.cja.2021.06.011
10	SHANG Z X , BRADLEY J , SHEN Z G . A co-optimal coverage path planning method for aerial scanning of complex structures. Expert Systems with Applications, 2020, 158, 113535. doi: 10.1016/j.eswa.2020.113535
11	BIRCHER A , KAMEL M , ALEXIS K , et al. Receding horizon path planning for 3D exploration and surface inspection. Autonomous Robots, 2018, 42 (2): 291- 306. doi: 10.1007/s10514-016-9610-0
12	TAN C S , MOHD-MOKHTAR R , ARSHAD M R . A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 2021, 9, 119310- 119342. doi: 10.1109/ACCESS.2021.3108177
13	GLORIEUX E , FRANCIOSA P , CEGLAREK D . Coverage path planning with targetted viewpoint sampling for robotic free-form surface inspection. Robotics and Computer-Integrated Manufacturing, 2020, 61, 101843. doi: 10.1016/j.rcim.2019.101843
14	CAO C, ZHANG J, TRAVERS M, et al. Hierarchical coverage path planning in complex 3D environments[C]//Proceedings of IEEE International Conference on Robotics and Automation. Washington D. C., USA: IEEE Press, 2020: 3206-3212.
15	戴佳佳, 龚小溪, 汪俊. 面向飞机外表面检测任务的无人机覆盖路径规划方法. 机械工程学报, 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. Journal of Mechanical Engineering, 2023, 59 (16): 243- 253.
16	刘洪鹏, 赵文政, 刘银华, 等. 测量不确定度约束下的结构光检测视点规划方法. 计算机集成制造系统, 2022, 28 (4): 1079- 1086.
	LIU H P , ZHAO W Z , LIU Y H , et al. View planning of structured light for free-form surfaces with control of measurement uncertainty. Computer Integrated Manufacturing Systems, 2022, 28 (4): 1079- 1086.
17	陈丽, 陈洋, 杨艳华. 面向三维结构视觉检测的无人机覆盖路径规划. 电子测量与仪器学报, 2023, 37 (2): 1- 10.
	CHEN L , CHEN Y , YANG Y H . UAV coverage path planning for 3D structure visual inspection. Journal of Electronic Measurement and Instrumentation, 2023, 37 (2): 1- 10.
18	HAMZAH R A , KADMIN A F , GHANI S F A , et al. Disparity refinement process based on RANSAC plane fitting for machine vision applications. Journal of Fundamental and Applied Sciences, 2018, 9 (4S): 226. doi: 10.4314/jfas.v9i4S.13
19	LYU Y C, HUANG X M, ZHANG Z M. Learning to segment 3D point clouds in 2D image space[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington D. C., USA: IEEE Press, 2020: 12255-12264.
20	LI E C , QI K K . Ant colony algorithm for path planning based on grid feature point extraction. Journal of Shanghai Jiaotong University (Science), 2023, 28 (1): 86- 99. doi: 10.1007/s12204-023-2572-4
21	XIE J F , GARCIA CARRILLO L R , JIN L . Path planning for UAV to cover multiple separated convex polygonal regions. IEEE Access, 2020, 8, 51770- 51785. doi: 10.1109/ACCESS.2020.2980203
22	CABREIRA T M , DI FRANCO C , FERREIRA P R , et al. Energy-aware spiral coverage path planning for UAV photogrammetric applications. IEEE Robotics and Automation Letters, 2021, 3 (4): 3662- 3668.
23	DUBERG D , JENSFELT P . UFOMap: an efficient probabilistic 3D mapping framework that embraces the unknown. IEEE Robotics and Automation Letters, 2020, 5 (4): 6411- 6418. doi: 10.1109/LRA.2020.3013861
24	李海旺, 周恒可, 赵兴, 等. 机载LiDAR点云数据的建筑屋顶面提取算法. 计算机工程与应用, 2024, 60 (11): 233- 241.
	LI H W , ZHOU H K , ZHAO X , et al. Algorithm for extracting building roof surfaces from airborne LiDAR point cloud data. Computer Engineering and Applications, 2024, 60 (11): 233- 241.
25	姬翔. 多特征融合的旋翼无人机能耗优化路径规划方法研究[D]. 西安: 西北大学, 2021.
	JI X. Research on energy consumption optimization path planning method of rotary-wing UAV based on multi-feature fusion[D]. Xi'an: Northwest University, 2021. (in Chinese)

[1]	周青, 潘凡安, 陈文冲, 江波. 面向工业互联网平台的物流服务选择性众包与路径规划研究[J]. 计算机工程, 2025, 51(4): 360-372.
[2]	张博强, 陈新明, 冯天培, 吴兰, 刘宁宁, 孙朋. 基于混合A^*和修正RS曲线融合的路径规划[J]. 计算机工程, 2025, 51(4): 373-382.
[3]	李淑怡, 阳波, 陈灵, 沈玲, 唐文胜. 自适应奖励函数的PPO曲面覆盖方法[J]. 计算机工程, 2025, 51(3): 86-94.
[4]	祁永强, 胡杞澍. 基于MA-PPA的露天煤矿智能巡视机器人路径规划研究[J]. 计算机工程, 2025, 51(11): 366-376.
[5]	张国胜, 李彩虹, 张耀玉, 周瑞红, 梁振英. 基于改进人工势场法的机器人局部路径规划[J]. 计算机工程, 2025, 51(1): 88-97.
[6]	陈浩, 陈珺, 刘飞. 基于自主探索的移动机器人路径规划研究[J]. 计算机工程, 2025, 51(1): 60-70.
[7]	王志特, 罗丽平, 廖义奎. 改进A^*算法融合改进动态窗口法的移动机器人路径规划[J]. 计算机工程, 2024, 50(8): 86-101.
[8]	刘国名, 李彩虹, 李永迪, 张国胜, 张耀玉, 高腾腾. 基于改进PPO算法的机器人局部路径规划[J]. 计算机工程, 2023, 49(2): 119-126,135.
[9]	岳荣康, 丁行, 江海, 龙吟. 基于互斥锁传播的多智能体路径规划算法[J]. 计算机工程, 2023, 49(12): 103-110.
[10]	李奇儒, 耿霞. 基于改进DQN算法的机器人路径规划[J]. 计算机工程, 2023, 49(12): 111-120.
[11]	詹京吴, 黄宜庆. 融合安全A^*算法与动态窗口法的机器人路径规划[J]. 计算机工程, 2022, 48(9): 105-112,120.
[12]	马华伟, 马凯, 郭君. 考虑多投递的带无人机车辆路径规划问题研究[J]. 计算机工程, 2022, 48(8): 299-305.
[13]	黄金瑶, 刘同来, 吴嘉鑫, 武继刚. 多周期家庭护理的路径规划与调度算法[J]. 计算机工程, 2022, 48(7): 292-299.
[14]	李冠达, 金兢, 王凡, 夏营威, 杨学志. 室内场景下应用拓扑结构的高效路径规划算法[J]. 计算机工程, 2022, 48(6): 95-106.
[15]	杨思明, 单征, 曹江, 郭佳郁, 高原, 郭洋, 王平, 王景, 王晓楠. 基于模型的强化学习在无人机路径规划中的应用[J]. 计算机工程, 2022, 48(12): 255-260,269.

选择文件类型/文献管理软件名称

选择包含的内容