Path planning simulation in controlled environments using the Ant Colony Optimization algorithm

Abstract

La Planificacion de Rutas es un tema ampliamente estudiado debido a sus diversas aplicaciones en robótica, planificación de socorro, planificación de rutas comerciales e incluso en la industria de los videojuegos. En consecuencia, los métodos computacionales de planificación de rutas son diversos, buscan resolver problemas en entornos desconocidos hasta encontrar un camino con la navegación más fluida. Desafortunadamente, esta diversidad provoca que algunos métodos pasen por alto ciertos aspectos al atender un problema de propósito específico. En este proyecto, analizar características como el tiempo de ejecución, la adaptabilidad y las representaciones del entorno. La literatura muestra que las implementaciones actuales tienen limitaciones en algunos de estos aspectos. En muchos casos, algunas técnicas tienen un rendimiento satisfactorio en una o dos de estas características, pero una deficiencia en las demás. Por esta razón, el presente proyecto tiene como objetivo diseñar un algoritmo de planificación de ruta basado en textit Ant Colony Optimization (ACO), que considera mejoras para estas limitaciones. El diseño y la parte experimental de este trabajo se basaron en un estilo incremental. En este sentido, propusimos un algoritmo básico, y luego agregamos algunas interacciones globales y locales para tratar algunos de los problemas. Luego, seleccionamos las configuraciones con el mejor rendimiento para definir nuestra propuesta final y compararla con otros métodos ya conocidos. Finalmente, mostramos algunos resultados en una simulación gráfica para mostrar su comportamiento adaptativo. El algoritmo ha demostrado resolver las limitaciones antes mencionadas. Mientras trabajábamos con una metaheurística, no siempre obtuvimos resultados óptimos, sino soluciones factibles lo suficientemente buenas para las aplicaciones de la técnica. Sin embargo, el algoritmo genera resultados promete- dores con una precisión de 95% aproximadamente.