Optimal indoor evacuation path-planning model based on Dijkstra's algorithm

Huiling Jiang, Wei Fang, Tianfeng Xu, Haoxuan Xu, Lan Chen, Liang Zhou, Qing Deng

Journal of Tsinghua University(Science and Technology) ›› 2025, Vol. 65 ›› Issue (4) : 742-749.

PDF(4842 KB)
PDF(4842 KB)
Journal of Tsinghua University(Science and Technology) ›› 2025, Vol. 65 ›› Issue (4) : 742-749. DOI: 10.16511/j.cnki.qhdxxb.2025.27.013
People Evacuation and Risk Assessment

Optimal indoor evacuation path-planning model based on Dijkstra's algorithm

Author information +
History +

Abstract

Objective: This study aimed to enhance the efficiency of indoor evacuation procedures by developing an optimal path-planning model based on the Dijkstra algorithm. The primary goal was to provide a dynamic and intelligent solution for guiding individuals to exit safely and swiftly during emergencies. Considering the complexities of indoor environments and the unpredictability of crowd behavior, the study highlighted the urgent need for a path-planning decision model that can adapt to real-time changes in crowd density and pedestrian flow velocity. Methods: This study employed the single shot detector (SSD) algorithm for person detection and the deep learning-based simple online and real-time tracking (Deep-SORT) algorithm for multi-pedestrian tracking. These approaches, integrated with monocular vision techniques, enabled the extraction of pedestrian counts and flow velocities from architectural surveillance video streams. The Industry Foundation Classes standard was utilized to extract detailed architectural spatial information required for constructing a path network tailored for evacuation purposes. A novel method for predictive edge setting within the existing camera surveillance network was then introduced, allowing for the calculation of residual predictive edge pedestrian flow velocities. This calculation informed the development of an edge weight calculation method for the navigation road network, which is crucial for optimizing evacuation routes. These calculated weights were input into the Dijkstra algorithm to identify the shortest-time evacuation routes from any given node to the nearest exit. Results: The proposed model was validated through experiments conducted using a proprietary pedestrian database under simulated emergency conditions. The SSD algorithm achieved an average precision of 78.2% for pedestrian detection and counting, while the Deep-SORT algorithm achieved multiple object tracking precision and multiple object tracking accuracy scores of 71.2% and 78.5%, respectively. These metrics demonstrate the model's high accuracy in detecting and tracking pedestrians, a crucial aspect of effective evacuation planning. In addition, the model provided optimal path directions at each decision node, allowing for real-time adjustments as conditions change. Moreover, the system could adapt to fluctuating crowd dynamics, a critical feature given the unpredictable nature of human movement during emergencies. Conclusions: This study demonstrated the feasibility of implementing a Dijkstra algorithm-based optimal path-planning model for indoor evacuations, achieving efficient and intelligent route optimization. The research provides a solid theoretical foundation and practical technical support for managing complex indoor evacuation scenarios, thereby contributing to the fields of emergency management and crowd control strategies. Further refinement and application of this model in real-world settings are expected to substantially enhance public safety measures. Additionally, the model's potential integration into existing building management systems presents a promising avenue for improving safety protocols and fostering a more systematic approach to handling indoor evacuations.

Key words

computer vision / Dijkstra algorithm / path planning / emergency evacuation

Cite this article

Download Citations
Huiling Jiang , Wei Fang , Tianfeng Xu , et al . Optimal indoor evacuation path-planning model based on Dijkstra's algorithm[J]. Journal of Tsinghua University(Science and Technology). 2025, 65(4): 742-749 https://doi.org/10.16511/j.cnki.qhdxxb.2025.27.013

References

1
KRIZHEVSKY A , SUTSKEVER I , HINTON G E , et al. ImageNet classification with deep convolutional neural networks[J]. Communications of the ACM, 2017, 60 (6): 84- 90.
2
GIRSHICK R, DONAHUE J, DARRELL T, et al. Rich feature hierarchies for accurate object detection and semantic segmentation[C]// Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, USA: IEEE, 2014: 580-587.
3
REDMON J, DIVVALA S, GIRSHICK R, et al. You only look once: Unified, real-time object detection[C]// Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, USA: IEEE, 2016: 779-788.
4
REDMON J, FARHADI A. YOLO9000: Better, faster, stronger[C]// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Honolulu, USA: IEEE, 2017: 6517-6525.
5
LIU W, ANGUELOV D, ERHAN D, et al. SSD: Single shot multibox detector[C]// 14th European Conference on Computer Vision. Amsterdam, The Netherlands: Springer, 2016: 21-37.
6
WOJKE N, BEWLEY A, PAULUS D. Simple online and realtime tracking with a deep association metric[C]// 2017 IEEE International Conference on Image Processing. Beijing, China: IEEE, 2017: 3645-3649.
7
BEWLEY A, GE Z Y, OTT L, et al. Simple online and realtime tracking[C]// 2016 IEEE International Conference on Image Processing (ICIP). Phoenix, USA: IEEE, 2016: 3464-3468.
8
秦全德, 程适, 李丽, 等. 人工蜂群算法研究综述[J]. 智能系统学报, 2014, 9 (2): 127- 135.
QIN Q D , CHENG S , LI L , et al. Artificial bee colony algorithm: A survey[J]. CAAI Transactions on Intelligent Systems, 2014, 9 (2): 127- 135.
9
杨维, 李歧强. 粒子群优化算法综述[J]. 中国工程科学, 2004, 6 (5): 87- 94.
YANG W , LI Q Q . Survey on particle swarm optimization algorithm[J]. Strategic Study of CAE, 2004, 6 (5): 87- 94.
10
姜雪, 杨欢, 张培红. 基于蚁群算法的商业步行街应急疏散决策优化[J]. 中国安全科学学报, 2021, 31 (10): 144- 151.
JIANG X , YANG H , ZHANG P H . Emergency evacuation decision optimization for commercial pedestrian streets based on ant colony algorithm[J]. China Safety Science Journal, 2021, 31 (10): 144- 151.
11
乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24 (3): 209- 212.
LE Y , GONG J Y . An efficient implementation of shortest path algorithm based on Dijkstra algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24 (3): 209- 212.
12
王树西, 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学, 2012, 39 (5): 223- 228.
WANG S X , WU Z X . Improved Dijkstra shortest path algorithm and its application[J]. Computer Science, 2012, 39 (5): 223- 228.
13
任少强, 汪一鸣. 基于改进Dijkstra算法的人群反馈调节疏散[J]. 计算机系统应用, 2022, 31 (1): 279- 285.
REN S Q , WANG Y M . Dynamic crowd evacuation with improved Dijkstra algorithm[J]. Computer Systems & Applications, 2022, 31 (1): 279- 285.
14
刘建美, 马寿峰, 马帅奇. 基于改进的Dijkstra算法的动态最短路计算方法[J]. 系统工程理论与实践, 2011, 31 (6): 1153- 1157.
LIU J M , MA S F , MA S Q . Computation method of the dynamic shortest path based on improved-Dijkstra algorithm[J]. Systems Engineering-Theory & Practice, 2011, 31 (6): 1153- 1157.
15
陈远, 逯瑶. 基于IFC标准的BIM模型空间结构组成与程序解析[J]. 计算机应用与软件, 2018, 35 (04): 162-167+194.4.
CHEN Y , LU Y . Spatial Structural Composition and Parsing for BIM Based on IFC Standard[J]. Computer Applications and Software, 2018, 35 (04): 162-167+194.4.
16
林雕. 基于上下文感知的室内路径规划研究与实践[D]. 郑州: 解放军信息工程大学, 2015.
LIN D. Research and practice of the context-aware indoor routing[D]. Zhengzhou: PLA Information Engineering University, 2015. (in Chinese)

RIGHTS & PERMISSIONS

All rights reserved. Unauthorized reproduction is prohibited.
PDF(4842 KB)

Accesses

Citation

Detail

Sections
Recommended

/