Propuesta para Encontrar una ruta más Corta en un Entorno de Búsqueda 2D
Resumen
Para construir espacios de búsqueda (Laberintos) existen diversos algoritmos, estos se clasifican en laberintos simplemente conectados (LSC) y laberintos de conexión múltiple (LCM), los LSC tienen una única solución para dos celdas indicadas como entrada y salida. También hay diversos algoritmos para buscar la solución de un laberinto [1], [2], [8], Dijkstra es uno de los más utilizados en la representación con grafos, otros algoritmos, utilizan una representación matricial, con el uso de métricas de distancia utilizan información a priori para alcanzar el objetivo o meta, ejemplo de ello es A* o D* [2, 3]. En este trabajo se propone una estrategia para encontrar la trayectoria en un entorno de búsqueda o laberinto con una representación matricial tipo LSC, en la que se aprovecha información a priori que se obtiene durante la construcción del espacio de búsqueda, los movimientos se representan en forma de etiquetas numéricas que facilitan la navegación por una ruta en el entorno; en la ruta encontrada se identifican patrones binarios para realizar movimientos en diagonal de esa manera obtener una trayectoria más corta entre dos celdas.
Descargas
Citas
Alamri, S., Alshehri, S., Alshehri, W., Alamri, H., Alaklabi, A., & Alhmiedat, T. (2021). Autonomous maze solving robotics: Algorithms and systems. International Journal of Mechanical Engineering and Robotics Research, 50-62.
Balderrama-Garcia, C. A., & Orozco-Rojas, U. P. (2021). Implementación de un algoritmo D* modificado para planificación de trayectorias. Investigación Básica y Aplicada, 8(16), 2026-232. Obtenido de https://repositorio.cetys.mx/handle/60000/1299
Bu, Z., & Korf, R. E. (2022). A*+BFHS: A Hybrid Heuristic Search Algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10138-10145. doi: https://doi.org/10.1609/aaai.v36i9.21253
Castro, M., & Arturo, C. (23 de 09 de 2021). Implementación de planificadores de trayectorias Dijkstra y Astra para un robot móvil diferencial. Colombia, Colombia, Colombia. Obtenido de http://hdl.handle.net/11634/35769
Cruz-Ruiz, I. O., Lara-Velázquez, P., De-Los-Cobos-Silva, S. G., Rincón-García, E. A., Mora-Gutiérrez, R. A., & Gutiérrez-Andrade, M. A. (2019). Un algoritmo estocástico para resolver laberintos. Revista de Matemática: Teoría y Aplicaciones, 319-338.
Fernandez, R., & Monserrat, A. (20 de 05 de 2019). Evaluación del algoritmo Theta* para planeación de trayectorias. Obtenido de Centro Nacional de Investigación y Desarrollo Tecnológico, Repositorio tesis: https://rinacional.tecnm.mx/jspui/handle/TecNM/5452
Hernández Hernández, G.; Tomás Mariano, V. T. (2012). Búsqueda de Rutas Implementando A* en un Entorno Virtual 2D. Escuela Superior de Huejutla. UAEH. México
Jamal, A., Tauhidur-Rahaman, M., Al-Almadi, H. M., Ullah, I., & Zahid, M. (2020). Intelligent Intersection Control for Delay Optimization: Using Meta-Heuristic Search Algorithms. 12(5), 1896. doi:1896; https://doi.org/10.3390/su12051896
Kaur, N. K. (2019). A Review of Various Maze Solving Algorithms Based on Graph Theory. International Journal for Scientific Research & Development, 6(12), 431-434.Obtenido de https://www.researchgate.net/publication/331481380_A_Review_of_Various_Maze_Solving_Algorithms_Based_on_Graph_Theory
Llambías, V., & Osimani, P. (2022). Planificación de trayectorias óptimas, tesis de grado. Uruguay. Obtenido de https://hdl.handle.net/20.500.12008/32631
Ma, Z., Wan, W., Song, L., Liu, C., Liu, H., & Wu, Y. (2022). An Approach of Path Optimization Algorithm for 3D Concrete Printing Based on Graph Theory. Applied Sciences, 12(22), 11315. doi:https://doi.org/10.3390/app122211315
Niemczyk, R., & Zawiślak, S. (2018). Review of Maze Solving Algorithms for 2D Maze and Their Visualisation. Springer, 239-252.
Tomás-Mariano, V. T., Núñez-Cárdenas, F. d., & Andrade-Hernández, E. (2014). Propuesta de construcción dinámica de espacios de búsqueda. Res. Comput. Sci., 155-166.
Trujillo-Romero, F. (2022). Planificación de trayectorias usando metaheurísticas. Visión electrónica, 16(1).
Vargas, J. M., Pinzón, C. T., & Patiño, C. R. (2008). Técnicas de inteligencia artificial para la solución de laberintos de estructura desconocida. Scientia et technica, 2(39).
Derechos de autor 2023 Victor Tomás Tomás Mariano , Jorge Hernández Camacho, Felipe de Jesús Núñez Cárdenas
Esta obra está bajo licencia internacional Creative Commons Reconocimiento 4.0.