Implementación de un algoritmo D* modificado para planificación de trayectorias

Autores/as

  • Carlos Alberto Balderrama-García

Palabras clave:

Algoritmo A*, Algoritmo D*, Búsqueda heurística incremental, Planificación de trayectorias, Teoría de grafos

Resumen

En este trabajo se busca una solución eficiente al problema de planificación de trayectorias a través de la implementación de los
algoritmos A* y D* basados en heurísticas. Este artículo documenta el proceso de implementación, así como los resultados de la
implementación de los algoritmos en un ambiente virtual diseñado específicamente para probar algoritmos de planificación de
trayectorias. Para el algoritmo D* se utiliza un método para la replanificación diferente al del algoritmo D* original, debido a la
complejidad que representa su implementación. Se explican también algunas consideraciones que se deben tener en cuenta al
momento de implementar los algoritmos A* y D* para conseguir resultados satisfactorios. Tras la ejecución de los algoritmos se
observa que A* es el algoritmo que da resultados más rápidamente (debido a que no necesita verificar cambios en el mapa durante
la ejecución). No se observan cambios drásticos en los tiempos de ejecución entre el algoritmo D* y su variante propuesta, incluso
con el algoritmo de replanificación más sencillo que el original, aunque este sigue siendo más lento en tiempo de ejecución que el
algoritmo A* para mapas que no cambian. Utilizar un algoritmo de replanificación más sencillo puede facilitar la implementación
del programa y dar resultados efectivos donde el aumento en los tiempos de ejecución es negligible, pero los tiempos de ejecución
pueden aumentar drásticamente para entornos más grandes

Publicado

2021-05-13

Número

Sección

5th Conference on Computer Science and Computer Engineering