面向多层复杂结构的立体A*路径规划算法研究

doi:10.12305/j.issn.1001-506X.2026.02.15

Abstract

Abstract:

In order to solve the path planning problem in the case of complex multi-floor structures and local disconnection, a three-dimensional A* path planning algorithm for multi- floor complex structures is proposed. Firstly, the multi-floor complex structures are transformed into undirected weighted graph, and the mathematical model of path planning for multi-floor complex structures are established for minimizing the total weight of the path. Secondly, considering the connection between different levels and local disconnectedness within levels, a multi-floor unidirectional navigation heuristic strategy and a cross-level bidirectional routing heuristic strategy are designed, respectively. Based on the two heuristic strategies, a novel three-dimensional A* path planning algorithm is proposed. Finally, the proposed algorithm is compared with traditional A* algorithm, bidirectional A* algorithm and Dijkstra algorithm. The experimental results show that the proposed algorithm can effectively handle the path planning of complex multi-floor structures and local disconnection problems, and has superior performance in terms of convergence speed and solution quality compared to the comparison algorithms.

Key words: path planning, multi-floor structures, local disconnection, A* algorithm

CLC Number:

TP 18

Weiye TIAN, Yutao CHEN, Yong XIE, Congwei HE. Research on three-dimensional A* path planning algorithm for multi-floor complex structures[J]. Systems Engineering and Electronics, 2026, 48(2): 535-544.

Figures/Tables 13

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Table 2

Fig.6

Fig.7

Table 3

Table 4

Table 5

Table 6

References 40

1	HAMIEH A, DENEUX D, TAHON C. BiMov: BIM-based indoor path planning[C]// Proc. of the International Joint Conference on Mechanics, Design Engineering & Advanced Manufacturing, 2017: 889−899.
2	TANG G, TANG C, CLARAMUNT C, et al. Geometric A-star algorithm: an improved a-star algorithm for AGV path planning in a port environment[J]. IEEE Access, 2021, 9, 59196- 59210. doi: 10.1109/ACCESS.2021.3070054
3	XU S H, GU Y, LI X Y, et al. Indoor emergency path planning based on the Q-learning optimization algorithm[J]. ISPRS International Journal of Geo-Information, 2022, 11 (1): 66. doi: 10.3390/ijgi11010066
4	LIU Z H, ZOU R H. Dynamic evacuation path planning for subway station fire based on IACO[J]. Journal of Building Engineering, 2024, 86, 108828. doi: 10.1016/j.jobe.2024.108828
5	PENG W D, ZHANG Y F, GUO W. Research on indoor UAV 3D path planning based on optimal ant colony-artificial potential field method[C]// Proc. of the International Conference on Mechanical Design, 2023: 795−813.
6	ZHANG M L, HAO P. 2D and 3D path planning for mobile robots based on improved SSA algorithm[J]. International Journal of Intelligent Robotics and Applications, 2024, 9, 176- 188.
7	LIU L X, WANG X, YANG X, et al. Path planning techniques for mobile robots: review and prospect[J]. Expert Systems with Applications, 2023, 227, 120254. doi: 10.1016/j.eswa.2023.120254
8	ALEKSANDROV M, CHENG C, RAJABIFARD A, et al. Modelling and finding optimal evacuation strategy for tall buildings[J]. Safety Science, 2019, 115, 247- 255. doi: 10.1016/j.ssci.2019.02.017
9	GHASEMI P, KHALILI-DAMGHANI K, HAFEZALKOTOB A, et al. Uncertain multi-objective multi-commodity multi-period multi-vehicle location-allocation model for earthquake evacuation planning[J]. Applied Mathematics and Computation, 2019, 350, 105- 132. doi: 10.1016/j.amc.2018.12.061
10	LI Y J, WEI W, GAO Y, et al. PQ-RRT*: an improved path planning algorithm for mobile robots[J]. Expert Systems with Applications, 2020, 152, 113425. doi: 10.1016/j.eswa.2020.113425
11	YANG X X, ZHANG R, LI Y X, et al. Passenger evacuation path planning in subway station under multiple fires based on multiobjective robust optimization[J]. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (11): 21915- 21931. doi: 10.1109/TITS.2022.3190291
12	SRINIKETH K, LE A V, MOHAN R E, et al. Robot-aided human evacuation optimal path planning for fire drill in buildings[J]. Journal of Building Engineering, 2023, 72, 106512. doi: 10.1016/j.jobe.2023.106512
13	LIU L F, ZHANG H J, XIE J P, et al. Dynamic evacuation planning on cruise ships based on an improved ant colony system （IACS）[J]. Journal of Marine Science and Engineering, 2021, 9 (2): 220. doi: 10.3390/jmse9020220
14	PENG Y, LI S W, HU Z Z. A self-learning dynamic path planning method for evacuation in large public buildings based on neural networks[J]. Neurocomputing, 2019, 365, 71- 85. doi: 10.1016/j.neucom.2019.06.099
15	LEE J, PARK H, KIM Y, et al. Multi-level indoor path planning and clearance-based path optimization for search and rescue operations[J]. IEEE Access, 2023, 11, 40930- 40943. doi: 10.1109/ACCESS.2023.3269981
16	PALACÍN J, RUBIES E, BITRIÁ R, et al. Path planning of a mobile delivery robot operating in a multi-story building based on a predefined navigation tree[J]. Sensors, 2023, 23 (21): 8795. doi: 10.3390/s23218795
17	MIRAHADI F, MCCABE B Y. EvacuSafe: a real-time model for building evacuation based on Dijkstra’s algorithm[J]. Journal of Building Engineering, 2021, 34, 101687. doi: 10.1016/j.jobe.2020.101687
18	GUAN W L, HOU S, YU G J, et al. Dynamic evacuation path planning for multi-exit building fire: bi-objective model and algorithm[J]. Fire Technology, 2023, 59 (5): 2853- 2876. doi: 10.1007/s10694-023-01448-x
19	DOU Z, HU Y H, MEBARKI A, et al. Pre-evacuation path planning in chemicals-concentrated areas with risk assessment and individual character analysis[J]. Journal of Loss Prevention in the Process Industries, 2023, 83, 105076. doi: 10.1016/j.jlp.2023.105076
20	REN Y S, ZHANG G M, ZHENG J X, et al. An integrated solution for nuclear power plant on-site optimal evacuation path planning based on atmospheric dispersion and dose model[J]. Sustainability, 2024, 16 (6): 2458. doi: 10.3390/su16062458
21	张新艳, 邹亚圣. 基于改进A*算法的自动导引车无碰撞路径规划[J]. 系统工程理论与实践, 2021, 41 (1): 240- 246. doi: 10.12011/SETP2019-1470
	ZHANG X Y, ZOU Y S. Collision-free path planning for automated guided vehicles based on improved A* algorithm[J]. Systems Engineering-Theory & Practice, 2021, 41 (1): 240- 246. doi: 10.12011/SETP2019-1470
22	张浩杰, 张玉东, 梁荣敏, 等. 改进A*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45 (2): 513- 520. doi: 10.12305/j.issn.1001-506X.2023.02.23
	ZHANG H J, ZHANG Y D, LIANG R M, et al. Energy-efficient path planning method for robots based on improved A* algorithm[J]. Systems Engineering and Electronics, 2023, 45 (2): 513- 520. doi: 10.12305/j.issn.1001-506X.2023.02.23
23	李文刚, 汪流江, 方德翔, 等. 联合A*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
	LI W G, WANG L J, FANG D X, et al. Path planning algorithm combining A* with DWA[J]. Systems Engineering and Electronics, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
24	FU B, CHEN L, ZHOU Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems, 2018, 106, 26- 37. doi: 10.1016/j.robot.2018.04.007
25	BAO J S, ZHANG M Y, GE S R, et al. Underground driverless path planning of trackless rubber tyred vehicle based on improved A* and artificial potential field algorithm[J]. Journal of China Coal Society, 2022, 47 (3): 1347- 1360.
26	WANG P Y, LIU Y L, YAO W M, et al. Improved A-star algorithm based on multivariate fusion heuristic function for autonomous driving path planning[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2023, 237 (7): 1527- 1542. doi: 10.1177/09544070221100677
27	TIAN H, YANG Z H, SUN G M, et al. An improved A* path-planning algorithm for nuclear spill evacuation and radioactive source retrieval in complex terrain[J]. Nuclear Engineering and Design, 2023, 408, 112314. doi: 10.1016/j.nucengdes.2023.112314
28	HAN C Y, LI B Y. Mobile robot path planning based on improved A* algorithm[C]// Proc. of the IEEE 11th Joint International Information Technology and Artificial Intelligence Conference, 2023, 11: 672−676.
29	李仲明. 室内多层环境三维导航方法研究[D]. 天津: 中国民航大学, 2020.
	LI Z M. Research on three-dimensional navigation method for indoor multi-layer environment[D]. Tianjin: Civil Aviation University of China, 2020.
30	刘武平, 熊维茜. 一种基于多层导航网格的室内路径规划算法[J]. 测绘地理信息, 2020, 45 (6): 18- 21. doi: 10.14188/j.2095-6045.2018349
	LIU W P, XIONG W Q. An indoor path planning algorithm based on multi-layer navigation grid[J]. Journal of Geomatics, 2020, 45 (6): 18- 21. doi: 10.14188/j.2095-6045.2018349
31	ZHENG W, HUANG K P, WANG C Y, et al. Research on 3D path planning of quadrotor based on improved A* algorithm[J]. Processes, 2023, 11 (2): 334. doi: 10.3390/pr11020334
32	MEYSAMI A, KELOUWANI S, CUILLIERE J C, et al. An efficient indoor large map global path planning for robot navigation[J]. Expert Systems with Applications, 2024, 248, 123388. doi: 10.1016/j.eswa.2024.123388
33	WANG H W, LOU S J, JING J, et al. The EBS-A* algorithm: an improved A* algorithm for path planning[J]. PloS One, 2022, 17 (2): e0263841. doi: 10.1371/journal.pone.0263841
34	WANG P, MUTAHIRA H, KIM J, et al. ABA–adaptive bidirectional A algorithm for aerial robot path planning[J]. IEEE Access, 2023, 11, 103521- 103529. doi: 10.1109/ACCESS.2023.3317918
35	CHEN H B, TAO J Y, ZHOU B Z, et al. Research on an autonomous uav search and rescue system based on the improved EGO-planner algorithm[C]// Proc. of the 5th International Conference on Computer Engineering and Application, 2024: 1170−1175.
36	ZHANG H C, LI G. Precise indoor path planning based on hybrid model of GeoSOT and BIM[J]. ISPRS International Journal of Geo-Information, 2022, 11 (4): 243. doi: 10.3390/ijgi11040243
37	SONG P H, LI Y, JIA J Y. Fast path planning algorithm for 3D indoor scene roaming based on path table[C]// Proc. of the International Conference on Intelligent Computing, 2024: 118−129.
38	杨栋. 大型公共建筑火灾应急疏散路径优化及仿真研究[D]. 沈阳: 沈阳建筑大学, 2022.
	YANG D. Research on optimization and simulation of fire emergency evacuation path in large public buildings[D]. Shenyang: Shenyang Jianzhu University, 2022.
39	VERMA D, MESSON D, RASTOGI M, et al. Comparative study of various approaches of Dijkstra algorithm[C]// Proc. of the International Conference on Computing, Communication, and Intelligent Systems, 2021: 328−336.
40	LI Y, ZHANG H Y, ZHU H Z, et al. IBAS: index based A-star[J]. IEEE Access, 2018, 6, 11707- 11715.

模型	节点数	楼层数	楼梯数	算例	起点楼层	终点楼层
小规模	97	2	14	A	1（连通层）	1（连通层）
				B	1（连通层）	2（不连通层）
				C	2（不连通层）	2（不连通层）
中规模	191	3	37	D	1（连通层）	1（连通层）
				E	1（连通层）	3（不连通层）
				F	3（不连通层）	3（不连通层）
大规模	547	9	87	G	1（连通层）	1（连通层）
				H	1（连通层）	9（不连通层）
				I	9（不连通层）	9（不连通层）

节点规模	算例	求解路径长度/m				平均计算时间/ms				改进率/%
节点规模	算例	$ {L}_{{\mathrm{TDA}}^{*}} $	$ {L}_{\mathrm{TA}^{*}} $	$ {L}_{\mathrm{BA}^{*}} $	$ {L}_{\mathrm{D}} $	$ {T}_{\mathrm{TDA}^{*}} $	$ {T}_{\mathrm{TA}^{*}} $	$ {T}_{\mathrm{BA}^{*}} $	$ {T}_{\mathrm{D}} $	$ \text{Imp}_{\mathrm{IH}-\mathrm{T}}^{T} $	$ \text{Imp}_{\mathrm{IH}-\mathrm{B}}^{T} $	$ \text{Imp}_{\mathrm{IH}-\mathrm{D}}^{T} $
小	A	174	174	174	174	11.4	14	13.6	41	18.6	16.2	72.2
	B	197.03	197.03	197.03	197.03	14.6	24.9	15.4	51.6	41.4	5.2	71.7
	C	173.23	173.23	173.23	173.23	16.4	30.1	21.7	50.8	45.5	24.4	67.7
中	D	196	196	196	196	13.1	28.2	44.3	172.4	53.5	70.4	92.4
	E	211.16	211.16	211.16	211.16	20.7	63.1	31.1	174.2	67.2	33.4	88.1
	F	256.91	237.17	237.17	237.17	25.4	64.6	30.6	183.5	60.7	17.0	86.2
大	G	68	68	68	68	10.3	18.1	13.8	1394.5	43.1	25.4	99.3
	H	105.49	105.49	105.49	105.49	65	86.5	72	1412.9	24.9	9.7	95.4
	I	108.21	108.21	108.21	108.21	38.8	82.7	63.4	1472.9	53.1	38.8	97.4

算法	平均路径长度/m	成功率/%
算法	$ L $	$ {S}^{20\;\text{ms}} $	$ {S}^{30\;\text{ms}} $
TDA*	80.46	53.3	93.3
TA*	80.20	33.3	73.3
BA*	80.20	40	66.7

算法	平均路径长度/m	成功率/%
算法	$ L $	$ {S}^{35\;\text{ms}} $	$ {S}^{50\;\text{ms}} $
TDA*	89.21	60	93.3
TA*	82.03	40	53.3
BA*	82.03	53.3	60

节点规模	算例	平均求解时间/ms		改进率/%
节点规模	算例	$ {T}_{\mathrm{IA}^{*}} $	$ {T}_{\mathrm{TA}^{*}} $	$ \text{Imp}_{I-T}^{T} $
小	A	9.1	12.6	27.8
中	D	12.9	26.1	50.6
大	G	12.2	22.3	45.3

Research on three-dimensional A* path planning algorithm for multi-floor complex structures

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 40

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Pengcheng YANG, Qingqing YANG, Yingying GAO, Zhiwei YANG, Kewei YANG, Bo AI. Path planning for maritime moving targets search based on reinforcement learning [J]. Systems Engineering and Electronics, 2026, 48(2): 515-523.
[2]	Zeyu LU, Yao WANG, Weinan WU, Yiming SUN, Chunlin GONG. Two-layered path planning for unmanned aerial vehicle swarm in three-dimensional dynamic environment [J]. Systems Engineering and Electronics, 2026, 48(1): 132-143.
[3]	Wen WEN, Chenguang SHI, Jianjiang ZHOU. Stealthy paths planning algorithm for UAV swarm in multiple-threat environment [J]. Systems Engineering and Electronics, 2025, 47(9): 2971-2984.
[4]	Zhao YANG, Jinbiao HU, Yan WANG, Hongbiao QI. UAV coverage path planning for mountain patrol considering different takeoff and landing nests [J]. Systems Engineering and Electronics, 2025, 47(8): 2622-2631.
[5]	Xiaozhen YAN, Xinyue ZHOU, Qinghua LUO. Improved A-star algorithm for dynamic path planning of unmanned ships [J]. Systems Engineering and Electronics, 2025, 47(7): 2314-2328.
[6]	Junchao TANG, Chunhe HU. Complete coverage path planning for UAVs in 3D terrain and wind field environment [J]. Systems Engineering and Electronics, 2025, 47(7): 2349-2356.
[7]	Yijie LIU, Bin JIANG, Yajie MA, Wenbo LI, Chengrui LIU. Collision avoidance path planning and re-planning for USV formation [J]. Systems Engineering and Electronics, 2025, 47(6): 1964-1974.
[8]	Wei CHEN, Congqing WANG, Qiang ZENG, Zhan LI. UAV coverage path planning for aircraft surface visual inspection [J]. Systems Engineering and Electronics, 2025, 47(4): 1206-1213.
[9]	Ze GENG, Yanyan HUANG, Han ZHANG. UAV swarm anti-artillery search path planning based on artillery transfer path prediction [J]. Systems Engineering and Electronics, 2025, 47(4): 1222-1234.
[10]	Wenzhao YU, Jingchao QIAO, Zhe DU, Zhukai XING, Xinyuan WAN. Multi-USV cooperative task planning based on clustering optimization algorithm [J]. Systems Engineering and Electronics, 2025, 47(11): 3708-3720.
[11]	Yuqi XIA, Yanyan HUANG, Qia CHEN. Path planning for unmanned vehicle reconnaissance based on deep Q-network [J]. Systems Engineering and Electronics, 2024, 46(9): 3070-3081.
[12]	Bowen FEI, Weidong BAO, Daqian LIU, Xiaomin ZHU. Air-ground cooperative autonomous task allocation method for dynamic target search and strike [J]. Systems Engineering and Electronics, 2024, 46(7): 2346-2358.
[13]	Jie LI, Yuejin TAN. Operation loop recommendation method based on integrated improved ant colony algorithm [J]. Systems Engineering and Electronics, 2024, 46(6): 2002-2012.
[14]	Jiawei SUN, Minghui YU, Dapeng YANG, Haoquan TANG, Dapeng BIAN. Path planning of carrier aircraft traction system based on CL-RRT and MPC [J]. Systems Engineering and Electronics, 2024, 46(5): 1745-1755.
[15]	Dong SUI, Zhenyu YANG, Songbin DING, Tingting ZHOU. Three-dimensional path planning of UAV based on EMSDBO algorithm [J]. Systems Engineering and Electronics, 2024, 46(5): 1756-1766.