Estudio comparativo de diferentes técnicas bio-inspiradas para encontrar el camino mas corto de un robot móvil dentro de un laberinto

Abstract

La Planificación de Rutas o (path planning) es una tarea difícil en robótica, así como el de construir un robot y controlarlo. La planificación de rutas tiene por objetivo determinar un camino específico que nos lleve a la meta o destino. Esta investigación resuelve el problema de planificación de rutas y la optimización de ésta. Dado un entorno, sobre el cual un robot móvil debe determinar una ruta para llegar a un punto destino, se encuentra el camino más corto que dicho robot pueda seguir. Ésto se realiza utilizando técnicas Bio-inspiradas, tal como Optimización por Colonia de Hormigas (ACO) y los algoritmos Genéticos (AG). ACO está basado en Swarm Intelligence, donde el complejo comportamiento colectivo emerge de agentes. Estos agentes poseen simples capacidades, que al ser comparadas con su comportamiento colectivo son mucho más complejas. Un ejemplo de esto son las colonias de hormigas cuando buscan alimento para su supervivencia. Los AG´s se basan en principios evolutivos y neo-darwinianos al utilizar operadores basados en la selección, cruza y mutación. En esta investigación se propone una modificación al algoritmo de optimización por colonia de hormigas. Este algoritmo se aplica a entornos para obtener el camino más corto. Una vez que se obtiene el grafo de un entorno dado, se aplicará la modificación del algoritmo propuesto de Optimización por Colonia de Hormigas. Debido a que en esta modificación existen varios parámetros que controlan el comportamiento del algoritmo, se optimizarán los parámetros de dicho algoritmo con ayuda de un algoritmo genético. Finalmente para probar la metodología propuesta y medir su eficiencia, se presenta un estudio comparativo entre las técnicas utilizando entornos reales. // Path planning it is a difficult task in robotics, as well as construct and control a robot. The main propose of path planning is find a specific route in order to reach the target destination.This research tries to solve the path planning problem and its optimization. Given an environment, where a mobile robot must determine a route in order to reach a target destination, we found the shortest path that this robot can follow. This goal is reach using bio-inspired techniques, as Ant Colony Optimization (ACO) and the Genetics Algorithms (GA). ACO is based in Swarm Intelligence, where the complex collective behavior emerges from agents. These agents have simple capacities, but when they are compared against its collective behavior, they are much more complex. An example of this is an ant’s colony when they are looking for food for its survival. The GA´s are based on evolutionary principles and neo-darwinian principles using operators based on selection, a crossover and mutation. In this research we propose a modification to ant colony optimization algorithm. This algorithm is applied to different environments for obtain the shortest path. Once the graph of given environment is obtained, the modification of the proposed ACO algorithm is applied. Due to in this modification have several parameters that determine the behavior of proposed algorithm, these parameters were optimized using a genetic algorithm. Finally, in order to test the accuracy of the proposed method, we perform a comparative study between the proposed techniques using real environments.