Intelligent analysis of design about roof equipment inspection paths based on graph theory and improved A* algorithm

doi:10.11996/JG.j.2095-302X.2026010216

Abstract

Abstract:

In roof engineering design, the rationality of equipment maintenance circulation routes directly impacts maintenance efficiency and safety. Traditional design methods often rely on empirical judgment, making it difficult to sufficiently evaluate the rationality of these routes during the design phase. To address this, a hybrid algorithm combining graph theory with an improved A* algorithm was developed. Integrated with Building Information Modeling (BIM) technology, an intelligent analysis and design tool for roof equipment maintenance circulation routes was created to address the shortcomings of traditional design via digital model-based route analysis. First, the roof was converted into a weighted equivalent grid map using collision detection and an octree algorithm. Next, an improved A* algorithm was employed to optimize the maintenance paths, comprehensively considering equipment collision volumes and spatial constraints to calculate the optimal maintenance circulation route and evaluate the rationality of detailed route-area design. Finally, the intelligent analysis and design tool based on this algorithm was tested on an actual project. Experimental results demonstrated that the algorithm accurately revealed potential spatial conflicts and irrational layouts, providing data to support design optimization, and enhanced design rationality and operability; it also improved efficiency by more than five times compared with traditional manual design. The intelligent analysis tool based on this algorithm is currently in use in several projects by the Shanghai Construction (No.4) Group Co., Ltd.

Key words: roof maintenance, BIM, route optimization, A* algorithm, graph theory, octree algorithm

CLC Number:

HE Ruiqi, CAO Ying, XU Jinglin, YU Fangqiang. Intelligent analysis of design about roof equipment inspection paths based on graph theory and improved A* algorithm[J]. Journal of Graphics, 2026, 47(1): 216-222.

Figures/Tables 13

Fig. 1 Technology roadmap

Fig. 2 Roof equivalent grid computation workflow

Fig. 3 Mesh computing time graph (with the number of mesh elements on the logarithmic x-axis and computation time on the logarithmic y-axis)

Fig. 4 Roof BIM model

Fig. 5 Cuboid voxel units after grid expansion (the red cube is the representation of the grid in 3D space)

Fig. 6 Roof equivalent grid graph (green represents ordinary grids, red indicates high-weight grids)

Table 1 Algorithm performance comparison table

参数组合	构件阈值	单元尺寸/mm	耗时/min	碰撞检测误差率/%
C1	10	300	128	0.12
C2	10	600	75	0.35
C3	10	1 200	41	1.22
C4	30	300	106	0.09
C5	30	600	63	0.28
C6	30	1 200	35	0.95
C7	50	300	92	0.07
C8	50	600	55	0.21
C9	50	1 200	29	0.78

Fig. 7 Octree algorithm computation workflow

Fig. 8 Octree algorithm schematic diagram (the red mark indicates a branch that meets collision requirement)

Fig. 9 Equipment maintenance inspection route calculation workflow considering navigable volume

Fig. 10 Optimal maintenance route for equipment in project A (green is the normal grid in the optimal path, and red is the obstacle grid in the optimal path)

Fig. 11 Actual maintenance space for equipment in project A

Table 2 Algorithm performance comparison table (Taking remotely located maintenance equipment as an example)

项目	屋面面积/m²	网格划分 (大小/数量)	障碍密度	算法路径长度/m	人工路径长度/m	算法转折/次数	人工转折/次数	算法耗时/min	人工耗时/h
A	2 400	0.2 m×0.2 m/60 000	0.12	218.4	283.6	9	21	28	10.0
B	4 300	0.2 m×0.2 m/107 500	0.28	419.7	491.3	12	25	40	14.0
C	1 850	0.2 m×0.2 m/46 250	0.35	193.2	242.3	14	22	15	6.5

References 15

[1]	郑琪, 丁烈云. 建筑机电系统管道协同设计研究[J]. 建筑科学, 2024, 40(1): 1-12, 33.
	ZHENG Q, DING L Y. Research on pipeline collaborative design of building electromechanical system[J]. Building Science, 2024, 40(1): 1-12, 33 (in Chinese).
[2]	谢婷, 张晓玲, 孙亦军, 等. BIM技术在机电管线综合深化设计中的应用[J]. 建筑技术, 2016, 47(8): 727-729.
	XIE T, ZHANG X L, SUN Y J, et al. Application of BIM technique in general in-depth design of electromechanical pipeline[J]. Architecture Technology, 2016, 47(8): 727-729 (in Chinese).
[3]	邢振华, 胡明媚, 周斌科, 等. BIM技术在大型商业综合体中机电深化设计的应用研究[J]. 施工技术, 2017, 46(S2): 1225-1229.
	XING Z H, HU M M, ZHOU B K, et al. Research and application of BIM technology for the mechanical-electrical detailed design in large commercial complex projects[J]. Construction Technology, 2017, 46(S2): 1225-1229 (in Chinese).
[4]	周勇, 骆发江, 李鹏, 等. 基于BIM技术的屋面深化设计应用[J]. 施工技术, 2016, 45
	( S1: 802-804. ZHOU Y, LUO F J, LI P, et al. Detailed design of the roof based on BIM[J]. Construction Technology, 2016, 45(S1): 802-804 (in Chinese).
[5]	刘子毅, 李铁军, 孙晨昭, 等. 基于BIM的建筑机器人自主导航策略优化研究[J]. 计算机工程与应用, 2022, 58(15): 302-308. DOI
	LIU Z Y, LI T J, SUN C Z, et al. Research on optimization of autonomous navigation strategy of construction robot based on BIM[J]. Computer Engineering and Applications, 2022, 58(15): 302-308 (in Chinese). DOI
[6]	王凡, 李铁军, 刘今越, 等. 基于BIM的建筑机器人自主路径规划及避障研究[J]. 计算机工程与应用, 2020, 56(17): 224-230. DOI
	WANG F, LI T J, LIU J Y, et al. Research on autonomous path planning and obstacle avoidance of building robot based on BIM[J]. Computer Engineering and Applications, 2020, 56(17): 224-230 (in Chinese). DOI
[7]	翟晓卉, 史健勇. BIM和GIS的空间语义数据集成方法及应用研究[J]. 图学学报, 2020, 41(1): 148-157. DOI
	ZHAI X H, SHI J Y. Spatial and semantic data integration method and application of BIM and GIS[J]. Journal of Graphics, 2020, 41(1): 148-157 (in Chinese).
[8]	郭瑞荣, 李朝奎, 李豪, 等. 面向BIM的室内拓扑-栅格分层路径规划方法[J]. 测绘通报, 2024(3): 81-87. DOI
	GUO R R, LI C K, LI H, et al. BIM-oriented indoor topology-grid hierarchical path planning method[J]. Bulletin of Surveying and Mapping, 2024(3): 81-87 (in Chinese). DOI
[9]	陶志远, 徐蔚青, 王石刚, 等. 110kV智能变电站检修机器人带电作业路径规划[J]. 机械设计与研究, 2018, 34(1): 17-20, 25.
	TAO Z Y, XU W Q, WANG S G, et al. Path planning applied on a field robot for hot-line working in 110kV intelligent substation[J]. Machine Design & Research, 2018, 34(1): 17-20, 25 (in Chinese).
[10]	赖李洋, 郑锫骏, 梁海成, 等. 路径规划算法的高层综合设计研究[J]. 电子与信息学报, 2024, 46(11): 4132-4140.
	LAI L Y, ZHENG P J, LIANG H C, et al. Case study of high level synthesis on path planning algorithm[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4132-4140 (in Chinese).
[11]	朱永辉, 张胜文, 支辰羽, 等. 基于改进A^*算法的三维智能布线技术研究[J]. 制造技术与机床, 2023(10): 48-53. DOI
	ZHU Y H, ZHANG S W, ZHI C Y, et al. Research on 3D intelligent wiring technology based on improved A^* algorithm[J]. Manufacturing Technology & Machine Tool, 2023(10): 48-53 (in Chinese).
[12]	苏锦成, 王振中, 贾小攀, 等. 基于A^*算法的核电厂工艺管道自动布局方法[J]. 核科学与工程, 2022, 42(1): 129-135.
	SU J C, WANG Z Z, JIA X P, et al. Automatic layout of pipelines for process systems of nuclear power plant based on A^* algorithm[J]. Nuclear Science and Engineering, 2022, 42(1): 129-135 (in Chinese).
[13]	乔道迹, 张艳兵. 多障碍环境下巡检机器人路径规划优化研究[J]. 现代电子技术, 2025, 48(1): 130-134.
	QIAO D J, ZHANG Y B. Research on path planning optimization of inspection robot in multi-obstacle environment[J]. Modern Electronics Technique, 2025, 48(1): 130-134 (in Chinese).
[14]	贾明超, 冯斌, 吴鹏, 等. 一种融合改进A*算法与改进动态窗口法的文旅服务机器人路径规划[J]. 图学学报, 2024, 45(3): 505-515. DOI
	JIA M C, FENG B, WU P, et al. A path planning for cultural tourism service robot combining improved A* algorithm and improved dynamic window approach[J]. Journal of Graphics, 2024, 45(3): 505-515 (in Chinese). DOI
[15]	梁裕卿, 吉久茂, 杨佳蕾, 等. 基于人工智能的BIM疏散设计自动化方法[J]. 图学学报, 2021, 42(2): 299-306.
	LIANG Y Q, JI J M, YANG J L, et al. BIM evacuation design automation based on artificial intelligence[J]. Journal of Graphics, 2021, 42(2): 299-306 (in Chinese).