Path planning based on fast marching method

Abstract

Con el avance de la tecnología de la información, la planificación de rutas se ha convertido en un área de investigación muy activa. La planificación de rutas es muy importante en diferentes áreas; por ejemplo, modelado de tumores, navegación robótica, análisis sismológico, procesamiento de imágenes, videojuegos, etc. El uso de estas técnicas de búsqueda ha demostrado que existen problemas de optimización y eficiencia, tanto en su implementación como en su diseño. Es por esto que actualmente se han desarrollado muchas soluciones y modificaciones de algoritmos que han intentado solucionar estos problemas en base a diferentes tipos de almacenamiento, estas alternativas se han propuesto con dos objetivos principales: reducir su tiempo computacional y mejorar su precisión. Aunque varios algoritmos resuelven el problema de planificación de rutas, el método Fast Marching no ha sido el más popular entre ellos. FMM es un algoritmo utilizado principalmente para calcular mapas de tiempos de llegada. FMM es un caso especial de métodos de ajuste de nivel, éste es capaz de proporcionar un camino suave de un punto a otro. El método Fast Marching se ha modificado de diferentes formas, tanto en su forma de almacenar datos como en su flujo de trabajo para resolver sus problemas de complejidad computacional. Por tanto, el primer paso es describir todas estas alternativas que presenta este método dentro de un marco común y comparar los diferentes métodos, con base en métricas previamente definidas para dar respuesta a la pregunta de investigación: ¿Cómo lograr un desempeño óptimo de FMM aplicado a la planificación de rutas? En el presente trabajo realizamos un algoritmo basado en el FMM enfocado en planificación de rutas, y reducimos el tiempo de ejecución del algoritmo FMM. El presente trabajo consta de seis capítulos. El Capítulo 2 presenta la revisión de la literatura de la investigación relacionada con la planificación de rutas y el método Fast Marching. Aquí se cubren los conceptos principales de la ecuación de Eikonal en la planificación de rutas y los componentes principales del método Fast Marching. El siguiente capítulo presenta información relacionada con la modificación del método Fast Marching y el uso de pilas en la implementación del algoritmo. El Capítulo 4 presenta el planteamiento del problema y la metodología utilizada en este proyecto de investigación. Además, nuestra propuesta para modificar el método Fast Marching se explica en detalle en este capítulo. En los últimos capítulos, presentamos los resultados de este proyecto, los escenarios de simulación y cómo se evaluaron todos algoritmos. Los resultados de este trabajo de investigación fueron muy gratificantes. En todos los escenarios evaluados la modificación de FMM presentada en este trabajo obtuvo el menor tiempo de ejecución. Nuestra modificación de FMM tuvo una mejora en el tiempo de ejecución de alrededor del $35\%$ con relación al FMM clásico.