Real-time dynamic multi-source multi-sink path planning method for indoor fire scenarios

doi:10.11772/j.issn.1001-9081.2025091071

Abstract

Abstract:

Real-time dynamic optimal path planning is critical for facilitating rapid evacuation of personnel in indoor fire scenarios. However， due to the rapid development and high dynamics of indoor fires， the existing evacuation path planning algorithms cannot achieve efficient dynamic path planning in multi-source multi-sink environments. To address this issue， an indoor fire emergency evacuation path planning method based on an improved D^*Lite algorithm was proposed， namely Rectangular Constrained Shared Map D^*Lite （RCSM-D^*Lite） algorithm. First， a search rectangle constraint was introduced to reduce the number of traversed nodes. Second， to account for the rapid spread of fire， a dual-layer search mechanism was adopted to ensure that evacuees maintain a safe distance from hazardous fire regions. Finally， a virtual node was introduced to unify exits， and a shared environment map was incorporated to share information such as map layout， fire hazard levels and other fire dynamics， thereby improving algorithm efficiency. Path planning experiments with 20 persons were carried out on a 40×160 map. The results show that the improved D^*Lite algorithm reduces the time computation by 72.1% compared with the original D^*Lite algorithm. Simulation results under dynamic fire scenarios verify that this algorithm allows evacuees to keep a safe distance from hazardous fire regions and reach exits safely， providing support for indoor emergency evacuation simulation and planning.

Key words: indoor fire, path planning, D^*Lite algorithm, emergency evacuation, multi-source and multi-sink problem

摘要：

实时动态的最优路径规划对于室内火灾场景下的人员快速逃生至关重要。然而，由于室内火灾发展迅速且动态性强，现有疏散路径规划算法在多源多汇场景中还无法实现高效的动态路径规划。针对该问题，提出一种基于改进D^*Lite算法的室内火灾应急疏散路径规划方法——矩形约束的共享环境图D^*Lite（RCSM-D^*Lite）。首先，引入搜索矩形约束，减少遍历节点数；其次，针对火灾场景快速扩散的特点，使用双层搜索机制确保逃生主体远离火灾危险区域；最后，引入虚拟节点统一出口并使用共享环境图实现地图、火灾危险度等火灾动态场景的信息共享，提升算法效率。在40×160的地图中进行20人路径规划实验，实验结果表明：改进D^*Lite算法相较于原始D^*Lite算法耗时降低了72.1%；火灾动态场景仿真结果验证了该算法能够确保行人远离火灾危险区域，安全到达出口，为室内应急疏散仿真与规划提供更好的支持。

关键词: 室内火灾, 路径规划, D^*Lite算法, 应急疏散, 多源多汇问题

CLC Number:

TP391.9

Tao HAN, Litao HAN, Ran JI. Real-time dynamic multi-source multi-sink path planning method for indoor fire scenarios[J]. Journal of Computer Applications, 2026, 46(10): 3384-3390.

韩涛, 韩李涛, 纪然. 面向室内火灾的多源多汇实时动态路径规划方法[J]. 《计算机应用》唯一官方网站, 2026, 46(10): 3384-3390.

Figures/Tables 13

References 25

[1]	俞凯，刘萍萍，周鲁洁. 长廊型教学楼火灾疏散模拟及对策研究［J］. 消防科学与技术， 2025， 44（3）： 340-346.
	Yu Kai， Liu Pingping， Zhou Lujie. Fire evacuation simulation and countermeasures research in a long corridor-type academic buildings［J］. Fire Science and Technology， 2025， 44（3）： 340-346.
[2]	Luo M， Hou X， Yang J. Surface optimal path planning using an extended Dijkstra algorithm［J］. IEEE Access， 2020， 8： 147827-147838.
[3]	Wang C， Wang L， Qin J， et al. Path planning of automated guided vehicles based on improved A-star algorithm［C］// ICIA 2015. Piscataway： IEEE， 2015： 2071-2076.
[4]	Sarbini R N， Ahmad I， Bura R O， et al. Development of pathfinding using A-star and D-star lite algorithms in video game［J］. Journal of Theoretical and Applied Information Technology， 2024， 102（3）： 832-841.
[5]	Liu J， Yang J， Liu H， et al. An improved ant colony algorithm for robot path planning［J］. Soft Computing， 2017， 21（19）： 5829-5839.
[6]	Lyu D， Chen Z， Cai Z， et al. Robot path planning by leveraging the graph-encoded Floyd algorithm［J］. Future Generation Computer Systems， 2021， 122： 204-208.
[7]	Koenig S， Likhachev M. Fast replanning for navigation in unknown terrain［J］. IEEE Transactions on Robotics， 2005， 21（3）： 354-363.
[8]	张华军，刘洋，朱震宇，等. 邮轮火灾动态蔓延情况下的最优疏散路径规划［J］. 中国安全科学学报， 2023， 33（1）： 183-190.
	Zhang Huajun， Liu Yang， Zhu Zhenyu， et al. Optimal evacuation path planning under dynamic spreading of cruise ship fire［J］. China Safety Science Journal， 2023， 33（1）： 183-190.
[9]	Han B， Qu T， Tong X， et al. Grid-optimized UAV indoor path planning algorithms in a complex environment［J］. International Journal of Applied Earth Observation and Geoinformation， 2022， 111： No.102857.
[10]	蒙盾，胡卓，张华军. 基于改进A^*算法的多层邮轮疏散系统仿真［J］. 系统仿真学报， 2022， 34（6）： 1375-1382.
	Meng Dun， Hu Zhuo， Zhang Huajun. Simulation of multi-layer ship evacuation system based on improved A^* algorithm［J］. Journal of System Simulation， 2022， 34（6）： 1375-1382.
[11]	Liu Z， Liu H， Lu Z， et al. A dynamic fusion pathfinding algorithm using Delaunay triangulation and improved A-star for mobile robots［J］. IEEE Access， 2021， 9： 20602-20621.
[12]	Liu L， Wang B， Xu H. Research on path-planning algorithm integrating optimization A-star algorithm and artificial potential field method［J］. Electronics， 2022， 11（22）： No.3660.
[13]	Ferguson D， Stentz A. The delayed D^* algorithm for efficient path replanning［C］// ICRA 2005. Piscataway： IEEE， 2005： 2045-2050.
[14]	李墨潇，张建辉，王晟旻，等. 基于改进D^*Lite算法的疏散路径规划方法研究［J］. 中国安全生产科学技术， 2025， 21（3）： 42-49.
	Li Moxiao， Zhang Jianhui， Wang Shengmin， et al. Research on evacuation path planning method based on improved D^*Lite algorithm［J］. Journal of Safety Science and Technology， 2025， 21（3）： 42-49.
[15]	刘毅，沈斐敏. 考虑灾害实时扩散的室内火灾疏散路径选择模型［J］. 控制与决策， 2018， 33（9）： 1598-1604.
	Liu Yi， Shen Feimin. Route selection model in indoor evacuation under real effect of fire spread［J］. Control and Decision， 2018， 33（9）： 1598-1604.
[16]	刘军，冯硕，任建华. 移动机器人路径动态规划有向D^*算法［J］. 浙江大学学报（工学版）， 2020， 54（2）： 291-300.
	Liu Jun， Feng Shuo， Ren Jianhua. Directed D^* algorithm for dynamic path planning of mobile robots［J］. Journal of Zhejiang University （Engineering Science）， 2020， 54（2）： 291-300.
[17]	鞠慕涵，刘万科，胡捷，等. 改进D^*算法的未知场景机器人运动规划［J］. 导航定位学报， 2024， 12（3）： 145-153.
	Ju Muhan， Liu Wanke， Hu Jie， et al. Motion planning for robots in unknown scenes based on improved D^* algorithm［J］. Journal of Navigation and Positioning， 2024， 12（3）： 145-153.
[18]	LaValle S M. Rapidly-exploring random trees： a new tool for path planning［R/OL］. ［2025-07-17］..
[19]	陈小龙，李明智，汪雅琴，等. 基于人工势场法改进RRT^*算法的无人船路径规划［J］. 舰船科学技术， 2026， 48（5）： 151-157.
	Chen Xiaolong， Li Mingzhi， Wang Yaqin， et al. Unmanned ship path planning based on the improved RRT^* algorithm of artificial potential field method［J］. Ship Science and Technology， 2026， 48（5）： 151-157.
[20]	Xu T， Ma J， Qin P， et al. An improved RRT^* algorithm based on adaptive informed sample strategy for coastal ship path planning［J］. Ocean Engineering， 2025， 333： No.121511.
[21]	韩李涛，郭欢，张海思. 一种多出口室内应急疏散路径规划算法［J］. 测绘科学， 2018， 43（12）： 105-110.
	Han Litao， Guo Huan， Zhang Haisi. An algorithm for route planning applied in multi-exit indoor emergency evacuation［J］. Science of Surveying and Mapping， 2018， 43（12）： 105-110.
[22]	钟委，霍然，史聪灵. 热释放速率设定方式的几点讨论［J］. 自然灾害学报， 2004， 13（2）： 64-69.
	Zhong Wei， Huo Ran， Shi Congling. Some discussion on methodology to design heat release rate［J］. Journal of Natural Disasters， 2004， 13（2）： 64-69.
[23]	李明海，兰亚乐，马骁，等. 建筑火灾全局动态疏散路径规划研究［J］. 安全与环境学报， 2025， 25（1）： 205-215.
	Li Minghai， Lan Yale， Ma Xiao， et al. Research on global dynamic path planning for evacuation during building fires［J］. Journal of Safety and Environment， 2025， 25（1）： 205-215.
[24]	倪凌佳，黄晓霞，李红旮，等. 基于协作式深度强化学习的火灾应急疏散仿真研究［J］. 系统仿真学报， 2022， 34（6）： 1353-1366.
	Ni Lingjia， Huang Xiaoxia， Li Hongga， et al. Research on fire emergency evacuation simulation based on cooperative deep reinforcement learning［J］. Journal of System Simulation， 2022， 34（6）： 1353-1366.
[25]	谢玮，张玉春. 能见度对个体疏散速度及路径选择的影响研究［J］. 中国安全生产科学技术， 2017， 13（7）： 62-67.
	Xie Wei， Zhang Yuchun. Experimental study on impact of visibility on individual evacuation speed and path selection［J］. Journal of Safety Science and Technology， 2017， 13（7）： 62-67.

算法	路径点数	路径长度	遍历点数	算法耗时/s
Dijkstra算法	29	35.042	1 623	0.035
A^*算法	29	35.042	322	0.018
D^*Lite算法	29	35.042	353	0.029
矩形约束的Dijkstra算法	29	35.042	362	0.018
矩形约束的A^*算法	29	35.042	182	0.015
矩形约束的D^*Lite算法	29	35.042	187	0.026

算法	路径点数	路径长度	遍历点数	算法耗时/s
Dijkstra算法	29	35.042	1 623	0.035
A^*算法	29	35.042	322	0.018
D^*Lite算法	29	35.042	353	0.029
矩形约束的Dijkstra算法	29	35.042	362	0.018
矩形约束的A^*算法	29	35.042	182	0.015
矩形约束的D^*Lite算法	29	35.042	187	0.026

［起点，终点］	D^*Lite算法		矩形约束的D^*Lite算法		双层搜索算法^［14］
［起点，终点］	算法耗时/s	遍历点数	算法耗时/s	遍历点数	算法耗时/s	遍历点数
合计	0.104	2 262	0.075	1 622	10.909	12 374
［（34，63），（13，58）］	0.023	205	0.024	107	0.593	1 032
［（7，27），（13，63）］	0.008	104	0.006	91	0.279	646
［（13，57），（28，71）］	0.006	152	0.007	150	0.211	603
［（8，70），（24，47）］	0.004	129	0.004	129	0.552	888
［（22，57），（19，57）］	0.002	20	0.001	8	0.042	158
［（31，132），（38，74）］	0.008	222	0.008	212	0.674	1 289
［（26，84），（34，33）］	0.015	433	0.006	248	3.990	2 811
［（33，117），（11，60）］	0.021	450	0.013	430	2.021	1 923
［（36，77），（30，32）］	0.012	356	0.003	134	1.932	1 955
［（8，48），（7，88）］	0.005	191	0.003	113	0.615	1 069

［起点，终点］	D^*Lite算法		矩形约束的D^*Lite算法		双层搜索算法^［14］
［起点，终点］	算法耗时/s	遍历点数	算法耗时/s	遍历点数	算法耗时/s	遍历点数
合计	0.104	2 262	0.075	1 622	10.909	12 374
［（34，63），（13，58）］	0.023	205	0.024	107	0.593	1 032
［（7，27），（13，63）］	0.008	104	0.006	91	0.279	646
［（13，57），（28，71）］	0.006	152	0.007	150	0.211	603
［（8，70），（24，47）］	0.004	129	0.004	129	0.552	888
［（22，57），（19，57）］	0.002	20	0.001	8	0.042	158
［（31，132），（38，74）］	0.008	222	0.008	212	0.674	1 289
［（26，84），（34，33）］	0.015	433	0.006	248	3.990	2 811
［（33，117），（11，60）］	0.021	450	0.013	430	2.021	1 923
［（36，77），（30，32）］	0.012	356	0.003	134	1.932	1 955
［（8，48），（7，88）］	0.005	191	0.003	113	0.615	1 069

算法	图5地图算法平均耗时/s	对比地图算法平均耗时/s	图5地图标准差	对比地图标准差
D^*Lite算法	0.481	0.642	0.016	0.015
矩形约束的D^*Lite算法	0.296	0.478	0.011	0.018
共享环境图D^*Lite算法	0.151	0.174	0.014	0.013
RCSM-D^*Lite算法	0.134	0.166	0.013	0.016