Abstract
In this work is proposed an approach for addressing the problem to find the shortest-safe routes in buildings with many evacuation doors and where the accessibility of internal areas could be changed by different kind of sensors. We present two advantages over the common use of Dijkstra’s algorithm, related to the problem of obtaining evacuation routes: (1) Fast search of the shortest-safe evacuation route to multiple exits with a backward approach and (2) Support to dynamic environments (graph with variable vertex availability). Four Dijkstra-based algorithms were considered in order to evaluate the performance of the proposed approach, achieving short times in evacuation to multiple exits.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cho, J., Lee, G., Won, J., Ryu, E.: Application of dijkstra’s algorithm in the smart exit sign. In: The 31st International Symposium on Automation and Robotics in Construction and Mining (ISARC 2014) (2014)
Santos Navarrete, M.E., et al.: Estudio y simulación de algoritmos para la evacuación de personas en situaciones de emergencia sobre una estructura similar al rectorado de la espol. RTE (2015)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)
Bellman, R.: On a routing problem. Technical report, DTIC Document (1956)
Randell, B.: Edsger dijkstra. In: The Ninth IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, WORDS 2003 Fall, p. 3, October 2003
Kim, D.O., Mun, H.W., Lee, K.Y., Kim, D.W., Gil, H.J., Kim, H.K., Chung, Y.S.: The development of the escape light control system. J. Korean Inst. Illum. Electr. Install. Eng. 23(6), 52–58 (2009)
Gualandi, I.: Dijkstra, Dantzig, and shortest paths. (2012). http://stegua.github.io/blog/2012/09/19/dijkstra/. Accessed 18 Jun 2015
Acknowledgement
This work has been supported by the ESPOL under Project G4-DI-2014.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Oyola, A., Romero, D.G., Vintimilla, B.X. (2017). A Dijkstra-Based Algorithm for Selecting the Shortest-Safe Evacuation Routes in Dynamic Environments (SSER). In: Benferhat, S., Tabia, K., Ali, M. (eds) Advances in Artificial Intelligence: From Theory to Practice. IEA/AIE 2017. Lecture Notes in Computer Science(), vol 10350. Springer, Cham. https://doi.org/10.1007/978-3-319-60042-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-60042-0_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-60041-3
Online ISBN: 978-3-319-60042-0
eBook Packages: Computer ScienceComputer Science (R0)