Algoritmo Bat para la optimización de trayectorias en robótica

Abstract

La inteligencia de enjambres ha emergido recientemente como una de las tendencias más interesantes e innovadoras en inteligencia artificial. En un sentido amplio, la inteligencia de enjambres (o swarm intelligence, SI) puede definirse como la propiedad de un sistema mediante la cual los comportamientos colectivos de agentes no sofisticados que interactúan localmente entre sí y con su entorno, provocan que surjan patrones globales funcionales coherentes. Esos agentes no son demasiado inteligentes: obedecen reglas simples y tienen una percepción limitada. Como resultado, no pueden llevar a cabo individualmente las tareas que pretenden realizar. Es la cooperación de agentes la que aporta inteligencia al sistema, pero de una manera más bien descentralizada. La principal característica de un SI es la falta de un comportamiento central que determina la evolución del enjambre. En vez de eso, son las interacciones locales entre los agentes las que rigen el comportamiento global del enjambre. En este proyecto se pretende analizar y simular, desde un punto de vista práctico, la evolución de un enjambre a través de la cooperación de varios microcontroladores individuales utilizando un algoritmo de inteligencia de enjambre (el algoritmo bat). El sistema está diseñado para cumplir un objetivo común de manera colectiva, inteligente y eficiente. Se desarrollarán varios ejemplos prácticos para ilustrar los fundamentos de este comportamiento colectivo y cómo mejora el desempeño de los agentes individuales en la realización de una tarea específica. El algoritmo Bat es un poderoso método de inteligencia de enjambre inspirado en la naturaleza propuesto por el Profesor Xin-She Yang en 2010, con notables aplicaciones en dominios industriales y científicos. Sin embargo, parece ser que este algoritmo nunca se había aplicado hasta ahora en el contexto de enjambres robóticos. Con el objetivo de llenar este vacío, este documento presenta la primera implementación práctica del algoritmo murciélago en los enjambres robóticos. Nuestra implementación se realiza en dos niveles: un nivel físico, donde diseñamos y construimos un prototipo robótico real; y un nivel computacional, donde desarrollamos un marco de simulación robótica. Una característica muy importante de nuestra implementación es su alta especialización: todos los componentes (físicos y lógicos) están totalmente optimizados para replicar las características más relevantes de los murciélagos reales y el algoritmo bat lo más fielmente posible. Nuestra implementación ha sido probada en la problemática de encontrar una ubicación de destino dentro de entornos 3D de interiores y exteriores estáticos desconocidos. Nuestros resultados experimentales muestran que los patrones de comportamiento observados tanto en los enjambres robóticos reales como en simulados son muy similares.

Swarm intelligence has recently emerged as one of the most exciting trends in artificial intelligence. In a broad sense, swarm intelligence (SI) can be defined as the property of a system whereby the collective behaviors of unsophisticated agents interacting locally with one another and with their environment cause coherent functional global patterns to arise. Those agents are not very intelligent: they obey simple rules and have a limited perception. As a result, they cannot individually carry out the tasks they intend to. It is the cooperation of agents which actually brings intelligence to the system, but in a rather decentralized way. A trademark of SI is the lack of a central behavior determining the evolution of the swarm. Instead, are those local interactions among agents which govern the global behavior of the swarm. In this project, we aim at analyzing and simulating, from a practical standpoint, the evolution of a swarm through the cooperation of several individual single-board microcontrollers by using a swarm intelligence algorithm (the bat algorithm). The system is designed to fulfill a common objective in a collective, intelligent, and efficient way. A practical example will be developed to illustrate the fundamentals of this collective behavior and how it improves the performance of individual agents in carrying out a specific task. Bat algorithm is a powerful nature-inspired swarm intelligence method proposed by Prof. Xin-She Yang in 2010, with remarkable applications in industrial and scientific domains. However, to the best of authors’ knowledge, this algorithm has never been applied so far in the context of swarm robotics. With the aim to fill this gap, this paper introduces the first practical implementation of the bat algorithm in swarm robotics. Our implementation is performed at two levels: a physical level, where we design and build a real robotic prototype; and a computational level, where we develop a robotic simulation framework. A very important feature of our implementation is its high specialization: all (physical and logical) components are fully optimized to replicate the most relevant features of the real microbats and the bat algorithm as faithfully as possible. Our implementation has been tested by its application to the problem of finding a target location within unknown static indoor 3D environments. Our experimental results show that the behavioral patterns observed in the real and the simulated robotic swarms are very similar.