Optimización de trayectorias en entornos discretos mediante autómatas celulares y el algoritmo A*
Resumen
En el presente trabajo se implementa el algoritmo de búsqueda heurística A-Star (A*) para la determinación de la ruta óptima en entornos de navegación tipo laberinto con condiciones de contorno (inicio y fin) predefinidas. El objetivo principal consiste en establecer la trayectoria de longitud mínima que conecte ambos puntos, garantizando la evasión estricta de los obstáculos presentes en el dominio. Se presentan tres casos de estudio con niveles de complejidad incremental, donde se demuestra que el núcleo algorítmico del método A* mantiene su consistencia y eficacia frente a diversas restricciones espaciales. Asimismo, se propone una metodología de implementación basada en la integración de marcos de datos (data frames) cuyos índices estén asociados a las filas y columnas de matrices construidas para este propósito, una estructura que optimiza la gestión de la información y mejora la eficiencia computacional del proceso de búsqueda.
Citas
E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1) (1959) 100–107. doi:https://ir.cwi.nl/pub/9256/9256D.pdf.
P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions Of Systems Science And Cybernetics 4 (2) (1968) 269–271. doi:https://doi.org/10.1109/TSSC.1968.300136.
R. Kay, A. Mattacchione, C. K. . B. Hatton, Stepwise slime mould growth as a template for urban design, Nature Scientific Reports 12 (1322) (2022) 1–15. doi:https://doi.org/10.1038/s41598-022-05439-w.
F. S. Gharehchopogh, A. Ucan, T. I. . B. Arasteh, G. Isik, Slime mould algorithm: A comprehensive survey of its variants and applications, Archives of Computational Methods in Engineering 30 (1322) (2023) 1–15.doi:https://doi.org/10.1007/s11831-023-09883-3.
J. Jones, Characteristics of pattern formation and evolution in approximations of physarum transport networks, Artificial Life 16 (2) (2010) 127–153. doi:https://doi.org/10.1162/artl.2010.16.2.16202.
E. F. Krause, Taxicab Geometry: An Adventure in Non-Euclidean Geometry, 1st Edition, Dover Books on Mathematics, 1987.
P. E. Black, Manhattan distance, https://www.nist.gov/dads/HTML/manhattanDistance.html, accessed: 22 10 2025 (2019).
M. Barile, Taxicab metric, https://mathworld.wolfram.com/TaxicabMetric.html, accessed: 22 10 2025 (2025).
R. Fareh, M. Baziyad, M. H. Rahman, T. Rabie, M. Bettayeb, Investigating reduced path planning strategy for differential wheeled mobile robot, Robotica 38 (2) (2020) 1–21. doi:https://doi.org/10.1017/S0263574719000572.
J. Chen, N. R. Baziyad, M. H. Sturtevant, Conditions for avoiding node re-expansions in bounded suboptimal search, Vol. 18, 2019, pp. 1220–1226. doi:https://dl.acm.org/doi/10.5555/3367032.3367206.
A. V. Goldberg, H. Kaplan, R. F. Werneck, Reach for a*:efficient point-to-point shortest path algorithms, Tech. rep., accessed: 22 10 2025 (2005).
C. J. Cramer, Essentials of Computational Chemistry, 2nd Edition, John Wiley & Sons, Ltd, 2004.
P. Compeau, Biological Modeling A Short Tour, 1st Edition, Philomath Press, LLC, 2022.
D. Harabor, A. Grastien, Online graph pruning for pathfinding on grid maps, Vol. 25, 2011, pp. 1114–1119. doi:https://doi.org/10.1609/aaai.v25i1.7994.
R. N. Sarbini, I. Ahmad, R. O. Bura, L. Simbolon, Development of pathfinding using a-star and d-star lite algorithms in video game, Journal of Theoretical and Applied Information Technology 102 (3) (2024) 832–841. doi:https://www.jatit.org/volumes/Vol102No3/5Vol102No3.pdf.
Esta obra está bajo licencia internacional Creative Commons Reconocimiento-NoComercial 4.0.
Avisos de derechos de autor propuestos por Creative Commons
1. Política propuesta para revistas que ofrecen acceso abierto
Aquellos autores/as que tengan publicaciones con esta revista, aceptan los términos siguientes:
- Los autores/as conservarán sus derechos de autor y garantizarán a la revista el derecho de primera publicación de su obra, el cuál estará simultáneamente sujeto a la Licencia de reconocimiento de Creative Commons que permite a terceros compartir la obra siempre que se indique su autor y su primera publicación esta revista.
- Los autores/as podrán adoptar otros acuerdos de licencia no exclusiva de distribución de la versión de la obra publicada (p. ej.: depositarla en un archivo telemático institucional o publicarla en un volumen monográfico) siempre que se indique la publicación inicial en esta revista.
- Se permite y recomienda a los autores/as difundir su obra a través de Internet (p. ej.: en archivos telemáticos institucionales o en su página web) antes y durante el proceso de envío, lo cual puede producir intercambios interesantes y aumentar las citas de la obra publicada. (Véase El efecto del acceso abierto).
