Evacuation in Buildings: Path-Finding for Real-Time Evacuation Systems

Finding the shortest path between any two nodes in a network is a classical problem in a number of research areas. Although some general shortest path algorithms have already been developed, such as Dijkstra’s shortest path algorithm, in some situations, their computation complexity is too high to be of any practical use.

In some real-time computation systems, computing the shortest path in a short time is a basis on which the computation systems could be applied to solve real world problems. The real world problem specifies the requirements on the computation speed, software and hardware limitations and the accuracy level for an algorithm. As this research is to find the shortest path in a large indoor area and the algorithm developed would be implemented on a real-time emergency evacuation system, it is required that the computing speed be fast enough even the network is large in terms of the numbers of nodes and arcs.

To solve the above problem, some common inside-building topologies have to be analyzed, followed by the development of fast shortest path finding algorithms for the topologies, which frequently appear in indoor areas like campus and commercial buildings. This series of algorithms combined classical shortest path algorithms in graph theory with interval routing techniques in computer networks in order to get a high computation speed especially for large scale networks.

The developed fast algorithms could serve as the main shortest path finding tool in emergency evacuation systems for large indoor areas, and extend traditional evacuation systems from virtual simulation to real-time problem solving.