PDF(4842 KB)
基于Dijkstra算法的室内疏散最优路径规划模型
蒋慧灵, 方伟, 徐天锋, 徐浩轩, 陈兰, 周亮, 邓青
清华大学学报(自然科学版) ›› 2025, Vol. 65 ›› Issue (4) : 742-749.
PDF(4842 KB)
PDF(4842 KB)
基于Dijkstra算法的室内疏散最优路径规划模型
Optimal indoor evacuation path-planning model based on Dijkstra's algorithm
为提高人员室内疏散效率,实现疏散最优路径规划的高效化和智能化,该文开展了基于Dijkstra算法的室内疏散最优路径规划模型的研究。首先,基于计算机视觉技术和单目视觉方法,获取了建筑监控视频中的人群数量和人流速度信息。接着,基于IFC(industry foundation classes)标准提取建筑空间信息,构建了符合疏散需求的路径网络,并提出了设置预测边的摄像监控网络布局方法。然后,提出了计算剩余预测边的人流速度的方法,规定了导航路网中边权的计算方法。最后,利用Dijkstra算法得到各个节点到终点的用时最短的路径。利用自建行人数据库开展测试实验,实验结果表明,该模型可在每一个决策节点处动态显示当前最优路径方向。通过上述研究,验证了基于Dijkstra算法的室内疏散最优路径规划模型在提高疏散效率与安全性方面的可行性,为应对复杂室内疏散场景提供了理论基础和技术支持。
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.
计算机视觉 / Dijkstra算法 / 路径规划 / 应急疏散
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)
|
/
| 〈 |
|
〉 |