Aplicación del método de Fast Marching para planificación de trayectorias en robots móviles

Abstract

En el presente Trabajo Fin de Grado se pretende realizar una comparación objetiva de las fortalezas y debilidades de la planificación de rutas para robots móviles utilizando los algoritmos Fast Marching y Dijkstra en escenarios y casos reales. La planificación usando el algoritmo de Dijkstra no proporciona las características deseadas para estas tareas, surge así la necesidad de encontrar nuevas alternativas que se adapten mejor.
El algoritmo de Fast Marching es un algoritmo numérico que se basa en la expansión de un frente de onda para su propagación, con una velocidad siempre positiva, que crea un campo de velocidades de paso por cada punto de un mapa. Una visión simplificada sería comparar la propagación de Fast
Marching con la onda que se crea al dejar caer una piedra en un estanque que contuviese líquidos de distintas viscosidades. Esto es utilizado por la planificación de rutas para obtener una trayectoria mediante el método del gradiente descendiente.
Después de analizar ambos algoritmos, se estudia la implementación del planificador basado en Fast Marching en el sistema del robot y el diseño de los experimentos utilizados para la comparativa antes de concluir con el
análisis de los resultados.
Para obtener la mejor forma de llevar a cabo la integración del planificador basado en Fast Marching se ha estudiado el sistema del robot. Dicha implementación se ha realizado diseñando un plugin que se integra en el módulo de navegación del robot y que se utiliza para comunicar la información necesaria del módulo de navegación al nodo del planificador basado en Fast Marching.
Una vez desarrollada la integración se procede a diseñar los experimentos necesarios para poder realizar un estudio completo de la comparativa. Para producir los experimentos se han definido los parámetros que resultan relevantes en la planificación de trayectorias, entre los que se encuentran: los planificadores de rutas, los puntos iniciales y finales, y los parámetros que utiliza el módulo de navegación. Para la definición de los puntos, se han elegido unos puntos iniciales y unos puntos finales. Los experimentos se replican de manera exacta en los planificadores basados en los dos algoritmos. Esto da lugar al recorrido del robot de diversas trayectorias.
Previamente al estudio de los datos obtenidos de los experimentos se han analizado los resultados que son relevantes para realizar la comparación.
Dichos resultados son: distancia recorrida, tiempo de ruta y velocidad media de navegación.
En el estudio de los resultados se realizan dos grupos de comparaciones que se diferencian por los valores que se definen para los parámetros del módulo de navegación. Los resultados obtenidos con radio de seguridad y velocidad máxima de navegación con un valor menor son: Dijkstra produce rutas con una distancia recorrida un 4.38% menor que las trazadas con Fast Marching, así como un tiempo de ruta un 7.89% menor y una velocidad media de navegación un 17.53% mayor. Los resultados observados al aumentar ambos parámetros son más acentuados, mientras Dijkstra sigue produciendo rutas con una distancia recorrida un 4.37% menor, el tiempo de ruta pasa a ser un 20.96% menor y la velocidad media de navegación un 44,58% mayor.
El tiempo de ruta y la velocidad media de navegación se ven fuertemente afectados por la modificación de los parámetros del módulo de navegación.
Estos resultados se ven influidos por el diseño de los planificadores de rutas.
El planificador basado en Dijkstra utiliza una planificación dinámica y el planificador basado en Fast Marching lo hace de forma estática. Esto hace que el planificador basado en Dijkstra sea capaz de evitar los conflictos que se generan entre los mapas de costes locales y globales de una manera más rápida y eficaz.
Tras observar estos resultados y teniendo en cuenta un estudio cualitativo de las rutas trazadas por ambos planificadores se puede ver que Dijkstra sigue siendo más eficaz de forma cuantitativa. Aún así, debido a las razones que han afectado a los resultados y a las trayectorias de las rutas obtenidas, queda claro que el planificador basado en Fast Marching realiza rutas de una manera más suave y manteniendo una mayor distancia de seguridad con las paredes, por lo que, desarrollando y mejorando el método de planificación, puede dar lugar a un método de navegación que resulte más eficaz e interesante para las aplicaciones de seguridad y vigilancia.