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

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

摘要/Abstract

摘要：

针对复杂多层结构及局部不连通问题，提出面向多层复杂结构的立体A*路径规划算法。首先，将多层复杂结构转换为无向赋权图，并且以最小化路径的总权值为目标，建立了多层复杂结构路径规划的数学模型；随后，考虑不同层级之间的连接及层内局部不连通性，分别设计多层单向导航启发式策略和跨层双向绕行启发式策略，并基于两种启发式策略，提出一种新型的立体A*路径规划算法。最后，与传统A*算法、双向A*算法和Dijkstra算法进行了对比实验。实验结果表明，本文提出的算法能有效处理复杂多层结构路径规划及局部不连通问题，在收敛速度和解的质量方面更具优越性。

关键词: 路径规划, 多层结构, 局部不连通, A*算法

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

中图分类号:

TP 18

田维野, 陈于涛, 谢勇, 贺聪炜. 面向多层复杂结构的立体A*路径规划算法研究[J]. 系统工程与电子技术, 2026, 48(2): 535-544.

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.

图/表 13

图1

图2

图3

图4

图5

表1

表2

图6

图7

表3

表4

表5

表6

参考文献 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