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

Abstract

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 algoritmosA* 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 paralareplanificació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 resultadossatisfactorios. 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 variantepropuesta, 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. ABSTRACT In this work an efficient solution to the trajectory planning problem is sought through the implementation of the algorithms A* and D* based on heuristics. This article documents the implementation process, as well as the results of the implementation of the algorithms in a virtual environment designed specifically for testing path planning algorithms. For the D* algorithm, a method of stopping rescheduling different from the original D* algorithm is used, due to the complexity that its implementation represents. Some considerations that must be taken into account when implementing algorithms A* and D* to obtain satisfactory results are also explained. After the execution of the algorithms, it is observed that A* is the algorithm that gives faster results (because it does not need to verify changes in the map during execution). No drastic changes in execution times are observed between the D* algorithm and its proposed variant, even with the rescheduling algorithm simpler than the original, although it is still slower in execution time than the A* algorithm for maps that it does not change. Using a simpler rescheduling algorithm can make program implementation easier and give effective results where the increase in execution times is negligible, but execution times can increase for larger environments.