Algoritmo de optimización gotas de agua virtuales inteligentes aplicado a la planeación de ruta optima de un robot móvil

Abstract

Este trabajo contiene la descripción, implementación y validación del algoritmo gotas de agua virtuales inteligentes. Con base en los conceptos fundamentales sobre el funcionamiento del algoritmo, se implementó un código en MATLAB® que permite trazar rutas óptimas para robots móviles. Para la validación del algoritmo se utilizó la relación entre el problema del agente viajero (TSP) y la planificación de rutas, además de la solución de laberintos prototipo. La verificación del algoritmo para algunas de las configuraciones de nodos, se realizó simulando condiciones similares a las que presentan los trabajos realizados por Hamed Shah-Hosseini. Los resultados obtenidos muestran que la solución de nodos distribuidos en un círculo mediante este algoritmo, presentan crecimientos abruptos en alrededor de 70 nodos y 100 nodos. También es de notar que el comportamiento del algoritmo es tipo exponencial, y no monotónico, esto se debe a que este algoritmo permite la aleatoriedad para resolver problemas combinatorios, como por ejemplo en la solución de configuraciones del problema TSP, en las que se obtienen resultados aproximados al exacto, para un tiempo de cómputo razonable a pesar de que éste crezca exponencialmente con el incremento en la dimensión del problema. Con esta investigación se comprueba la capacidad del algoritmo para solucionar configuraciones clásicas del problema TSP, aún para situaciones donde un robot móvil requiere visitar más de 100 nodos. Además es evidente la eficiencia del algoritmo frente a la solución de laberintos en tiempo breve, ya que no requiere visitar todos los nodos.