Implementación de un sistema de búsqueda de rutas de evacuación eficientes ante la presencia de sismos en un centro comercial usando el algoritmo D estrella

Abstract

Around the world there are different authors that have shown big interest related to natural disasters such as earthquakes. This have generated different technological solutions around modern evacuation systems. This research explains why it is important to implement an intelligent evacuation system that can recognize the shortest path in a real earthquake. The research also reviews the different modern evacuation systems being used nowadays. In this way, after many phases of analysis, a proof of concept was built to find the shortest path in the first level of a shopping mall using the D star search algorithm. Furthermore, a comparison between the A star algorithm and D star algorithm was made to find out the performance of these. It was found that the A star algorithm finds the shortest path in 3 milliseconds, but it doesn’t support scenarios with dynamic paths. Thus, it was found that D start algorithm can support paths with dynamic obstacles and find the shortest path in 24 milliseconds, making it the most accurate algorithm for real evacuations scenarios. Ultimately, in order to evaluate the performance of the system, the experimental time was measured when the system calculates the shortest path in different environments such as: maps with scales of 5, 10 and 15, different number of existing obstacles and different number of obstacles generated in real time. The results of this research were favorable since the system was able to find an efficient shortest path in 22 milliseconds. Also, the simulator found an alternative path in 3 milliseconds for scenarios in which new obstacles were introduced in the path.

Alrededor del mundo diferentes autores han demostrado gran interés en los desastres naturales como los temblores o terremotos generando soluciones tecnológicas en torno a sistemas de evacuación. En la presente investigación se explica por qué es importante la implementación de un sistema de evacuación inteligente que tenga la capacidad de reconocer el camino más corto en un movimiento sísmico real y se hace una revisión de los diferentes sistemas de evacuación inteligentes empleados en la actualidad. Seguido de esto, al finalizar las etapas de análisis, se logró construir una prueba de concepto para hallar la ruta más eficiente en el primer nivel de un centro comercial empleando el algoritmo de búsqueda D estrella. Además, se consideró la revisión del algoritmo A estrella y D estrella para comparar la eficiencia de estos y se encontró que el A estrella emplea 3 milisegundos en encontrar la ruta más corta pero este no contempla escenarios que requieren de caminos dinámicos. Así, se encontró que el algoritmo D estrella es capaz de reconocer caminos con obstáculos dinámicos y encontrar la ruta más corta en solo 24 milisegundos, convirtiéndolo en el más adecuado para entornos de evacuaciones reales. Por último, para evaluar el desempeño de la prueba de concepto elaborada, se midió el tiempo experimental empleado por el algoritmo D estrella para encontrar la ruta de evacuación más eficiente en ambientes con las siguientes variaciones: diferentes tamaños de planos con escala 5, 10 y 15, diferentes cantidades de obstáculos existentes en el plano y generados en tiempo real. Los resultados obtenidos en el sistema fueron favorecedores al demostrar que la ruta más corta es encontrada en 22 milisegundos y una ruta alternativa es encontrada en 3 milisegundos para escenarios que presentan nuevos obstáculos en el camino.