# A Survey of Algorithms and Systems for Evacuating People in Confined Spaces
## 3 Evacuation Wayfinding Algorithms
### On-Line Evacuation Wayfinding Algorithms
#### Prediction-Based Algorithms  
By inferring the spreading rate and direction of the hazards, prediction-based algorithms predict the future status in the hazardous areas and reduce the fatality rate by avoid that evacuees traverse paths with a high potential risk level. For instance, the research in [100] proposed a Monte Carlo stochastic model to predict the spreading of the fire hazard and the movement of evacuees during an evacuation process; the targeted building was represented by two graph models composed of nodes (compartments) and edges (passageways), one for fire spread modelling and the other for occupant egress modelling; a discrete hazard function based on Bernoulli trials was used to mimic the propagation of the fire; a Bernoulli trial, which is a random experiment with two possible results: \"success\" and \"failure\", and the probability of success or failure is constant whenever the experiment is conducted, was performed at each time step to mimic the transmission of fire from one compartment to another. Each edge of the two graph models was associated with a \"defective\" random variable to represent the time cost for evacuees or the fire hazard to traverse this edge. These defective random variables, which took the value \"infinity\" with non-zero probability, were used to simulate the phenomena such as evacuees cannot reach the next node owing to capacity limitation, fire or an obstruction that impedes reaching the next node. The study in [101] proposed a WSN based distributed navigation algorithm to search for the safest routes for evacuees by maximising the time an evacuee would remain ahead of the hazard while traversing the route. Each sensor would maintain two weighted graphs of the built environment, a \"hazard graph\" and a \"navigation graph\". In the hazard graph, nodes represented the locations of sensor, while edges represented the possible movement directions of the hazard (for example, the hazard may spread through walls or along corridors); the weight of an edge was the shortest time for the hazard to propagate along the edge, and this information could be obtained from off-line hazard simulations [157] or estimated by emergency specialists. The nodes of the graph represented the sensor locations, while edges represented the possible movement directions of evacuees; the weight of an edge was the longest time for an evacuee to traverse the edge. When a fire breaks out, sensors that detected the hazard would broadcast the fire source location over the sensor network, then each sensor calculated the safest path to exit by maximising the overall difference in time between an evacuee arriving at each node on a path and the hazard reaching these nodes. Since it is difficult for fire-fighters to be aware of the actual conditions in a built environment during a fire disaster, the research in [102] presented a novel e-infrastructure to infer the spreading of hazard based on predictive models and living sensory data in a faster-than-real time manner; the system consisted of on-site sensors including smoke detectors and temperature sensors and off-site computational models that were deployed on high-performance computing (HPC) resources. Gathered sensory data were used as inputs to a Monte Carlo-style fire spread model called K-CRISP [158] to predict the movement of fire and smoke; the results were interpreted by using a knowledge-based reasoning scheme within an agent-based command-and-control layer; the outputs were transmitted to fire-fighters for reference.