Route Planning for Emergency Evacuation Using Graph Traversal Algorithms

Gaitanis, A.; Lentzas, A.; Tsoumakas, G.; Vrakas, D. Route Planning for Emergency Evacuation Using Graph Traversal Algorithms. Smart Cities 2023, 6, 1814-1831. https://doi.org/10.3390/smartcities6040084

Alexandros Gaitanis, Athanasios Lentzas, Grigorios Tsoumakas and Dimitris Vrakas

floor plan; evacuation; image segmentation; panoptic segmentation; neural networks; deep learning

The automatic identification of various design elements in a floor-plan image has gained increasing attention in recent research. Emergency-evacuation applications can benefit greatly from automated floor-plan solutions, as they allow for the development of horizontal solutions instead of vertical solutions targeting a specific audience. In addition to that, current evacuation plans rely on static signs without taking into account the dynamic characteristics of each emergency case. This work aims to extract information from a floor-plan image and transform it into a graph that is used for pathfinding in an emergency evacuation. First, the basic elements of the floor-plan image, i.e., walls, rooms and doors, are identified. This is achieved using Panoptic-DeepLab, which is a state-of-the-art deep neural network for the panoptic segmentation of images, and it is available from DeepLab2, an image segmentation library. The neural network was trained using CubiCasa5K, a large-scale floor-plan image dataset containing 5000 samples, annotated into over 80 floor-plan object categories. Then, using the prediction of each pixel, a graph that shows how rooms and doors are connected is created. An application that presents this information in a user-friendly manner and provides graph editing capabilities was developed. Finally, the exits are set, and the optimal path for evacuation is calculated from each node using Dijkstra’s algorithm.