Optimal Path Planning With Spatial-Temporal Mobility Modeling for Individual-Based Emergency Guiding

This paper proposes an individual-based framework for emergency guiding. The spatial-temporal mobility of all people is modeled to determine a dedicated path that provides the shortest evacuation time for each person. According to our review of relevant research, this is the first optimal solution without using time-expanded graphs, and corridor capacities and lengths, exit capacities, concurrent motion, and distribution of people are considered to minimize evacuation time. We prove that the proposed path planning algorithm is optimal and analyze its time and space complexity. The proposed framework can be used to estimate the evacuation time for each person accurately and evenly distribute evacuation load among exits to achieve the most efficient load balance. In the proposed framework, the congestion in all corridors and exits can be alleviated to maximally reduce the total evacuation time. Simulation results show that our approach outperforms existing schemes, and can be used to determine an optimal escape path for each person and, thus, achieve the shortest total evacuation time.