PDF(4842 KB)
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)
Optimal indoor evacuation path-planning model based on Dijkstra's algorithm
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.
computer vision / Dijkstra algorithm / path planning / emergency evacuation
| 1 |
|
| 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.
|
| 9 |
杨维, 李歧强. 粒子群优化算法综述[J]. 中国工程科学, 2004, 6 (5): 87- 94.
|
| 10 |
姜雪, 杨欢, 张培红. 基于蚁群算法的商业步行街应急疏散决策优化[J]. 中国安全科学学报, 2021, 31 (10): 144- 151.
|
| 11 |
乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24 (3): 209- 212.
|
| 12 |
王树西, 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学, 2012, 39 (5): 223- 228.
|
| 13 |
任少强, 汪一鸣. 基于改进Dijkstra算法的人群反馈调节疏散[J]. 计算机系统应用, 2022, 31 (1): 279- 285.
|
| 14 |
刘建美, 马寿峰, 马帅奇. 基于改进的Dijkstra算法的动态最短路计算方法[J]. 系统工程理论与实践, 2011, 31 (6): 1153- 1157.
|
| 15 |
陈远, 逯瑶. 基于IFC标准的BIM模型空间结构组成与程序解析[J]. 计算机应用与软件, 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)
|
/
| 〈 |
|
〉 |