Ediciones ENI Editorial | líder en informática
Sistemas multiagentes
Presentación del capítulo
Este capítulo presenta los sistemas multiagentes, que permiten responder a una gran variedad de problemáticas. En estos sistemas, varios agentes, con comportamientos individuales simples, trabajarán de manera conjunta para resolver problemas mucho más complejos.
Estos algoritmos están inspirados en observaciones realizadas en biología (y particularmente en etología). Existen colonias de insectos capaces de resolver problemas complejos (como crear un hormiguero), mientras que cada insecto individualmente no posee grandes capacidades. Este capítulo empieza presentando las principales características de estos insectos sociales.
A continuación se presentan las características mínimas de un sistema para que pueda considerarse como formado por multiagentes, así como las diversas categorías de agentes.
Algunos algoritmos son particulares y constituyen un campo de estudio en sí mismos. El capítulo los presenta a continuación: algoritmos de manadas, colonias de hormigas, sistemas inmunitarios artificiales y autómatas celulares.
Se proporcionan también varias implementaciones en Java. Por último, este capítulo termina con un resumen.
Origen biológico
Los insectos han interesado a los investigadores en biología y etología (la ciencia que estudia el comportamiento) desde hace mucho tiempo. Incluso aunque todavía no se conocen todos los comportamientos sociales, sí se han actualizado los grandes principios.
La mayoría de los insectos (cerca del 90 % de las especies) son solitarios. Cada insecto vive por su lado, con pocos o incluso sin vínculos con sus vecinos. Es el caso, por ejemplo, de la mayoría de las arañas, mosquitos, moscas... Los contactos se limitan a la búsqueda de comida (por ejemplo, en el caso de las moscas), a las zonas de vida (como las larvas de los mosquitos, presentes en muchas aguas estancadas) o a los periodos de reproducción.
Existen, también, insectos sociales, que van desde sociedades muy simples hasta sociedades muy complejas y organizadas. Los que presentan la mayor organización son los llamados insectos eusociales y tienen las siguientes características:
-
La población se divide en castas; cada casta tiene un rol preciso.
-
La reproducción está limitada a una casta particular.
-
Las larvas y los jóvenes se educan juntos en el seno de la colonia.
Los insectos eusociales no representan más que el 2 % de las especies existentes, ¡aunque en masa representan el 75 % del conjunto de los insectos! Esto pone de relieve que estas sociedades permiten mantener a un gran número de individuos.
Las tres especies eusociales más conocidas son las abejas, las termitas y las hormigas.
1. Las abejas y la danza
La mayoría de las especies de abejas son solitarias. Sin embargo, la especie Apis mellifera (la abeja de las colmenas que produce la miel) es una especie eusocial.
Cada colmena es una sociedad completa. Encontramos una reina, encargada de poner...
Sistemas multiagentes
Todas las técnicas clasificadas como sistemas multiagentes tienen como objetivo implementar esta inteligencia social, que se denomina en informática inteligencia distribuida. Para ello, encontramos:
-
Un entorno.
-
Objetos fijos o no, que son los obstáculos o los puntos de interés.
-
Agentes, como comportamientos simples.
Realmente, el objetivo del algoritmo no se codifica jamás, y la solución va a emerger de la interacción de todos los elementos entre sí.
1. El entorno
Los objetos y los agentes se encuentran en un entorno. Este puede ser más o menos complejo: puede tratarse de un espacio delimitado (como un cobertizo o un bosque), de un grafo o incluso de un espacio puramente virtual.
El entorno se corresponde, por lo tanto, principalmente con el problema que queremos resolver.
Este entorno debe poder evolucionar con el paso del tiempo: los agentes pueden desplazarse, y los objetos, modificarse.
2. Los objetos
El entorno posee objetos con los que los agentes pueden interactuar. Estos pueden corresponderse con fuentes de alimento, bloques de construcción, ciudades que visitar, obstáculos...
Nada impone que los objetos sean o no transportables, que sean temporales o permanentes. En este caso, hay que adaptarlos al problema.
En ciertos sistemas no existe ningún objeto, sino solamente los agentes. Su presencia es, de este modo, opcional.
3. Los agentes
Los agentes van a vivir...
Clasificación de los agentes
Los agentes pueden ser de tipos muy diferentes en función de ciertas características.
1. Percepción del mundo
La primera diferencia se produce en la precepción del mundo que tendrán los agentes. Podrán tener una visión de conjunto de todo el mundo (percepción total) o únicamente de lo que se encuentra a su alrededor (percepción localizada). Además, pueden tener una visión simbólica o únicamente aquella derivada de la percepción.
Por ejemplo, si tomamos robots que se desplazan por la planta de un edificio, pueden conocer lo que ven (la habitación que los rodea, percepción localizada) o tener un mapa registrado previamente de toda la planta con su posición encima (por ejemplo, mediante un GPS, percepción total).
Además, cuando poseen una cámara, pueden tener, en el caso de una visión simbólica, algoritmos de reconocimiento de imágenes que les permitan reconocer ciertos objetos (pomos de puertas, botones, destinos...) o, en el caso de una visión resultado de la percepción, interactuar en función de las imágenes brutas (tal y como se obtienen por la cámara).
Los investigadores de sistemas multiagentes tienen preferencia por percepciones localizadas, y están muy repartidos entre un enfoque simbólico y un enfoque puramente basado...
Principales algoritmos
Existen algunos algoritmos particulares más conocidos que otros, que presentan entornos, objetos y agentes definidos. Aquí se presentan cuatro: los algoritmos de manadas, la optimización por colonias de hormigas, los sistemas inmunitarios artificiales y los autómatas celulares.
En el capítulo dedicado a los metaheurísticos, el algoritmo de optimización por enjambre de partículas podía haberse visto como un sistema multiagente en el que cada solución tenía una visión global de todas las demás soluciones y una memoria (la mejor solución encontrada hasta el momento). Se desplazaban en el espacio de soluciones que servía como entorno. No había objetos. Sin embargo, esta técnica se aleja de la noción de agentes reactivos.
1. Algoritmos de manadas
Partiendo de algunas reglas sencillas, es posible simular los comportamientos de manadas o de grupos. Craig Reynolds creó, así, en 1986 los boids, criaturas artificiales que evolucionan en grupo.
Para ello, las criaturas poseen tres comportamientos, vinculados a la presencia de otros individuos en su proximidad:
-
Un individuo muy cercano va a provocar un comportamiento para evitarse mutuamente (para evitar invadir a otro individuo): es el comportamiento de separación.
-
Un individuo próximo modifica la dirección de la criatura, que tiene tendencia a alinearse en la dirección de su vecino: es el comportamiento de alineamiento.
-
Un individuo a una distancia media va a provocar un acercamiento. En efecto, si una criatura ve a otra, irá hacia ella: es el comportamiento de cohesión.
También es posible agregar un "ángulo muerto" tras el boid simulando el hecho de que no puede ver detrás de sí.
En función de los parámetros, en particular de las distancias configuradas, podemos observar individuos completamente aislados o, por el contrario, individuos que se desplazan en manada y que pueden encontrarse tras un objeto, a la manera de los bancos de peces o las nubes de pájaros o de insectos.
Se observa, por tanto, una estructura emergente a partir de algunas reglas muy simples. Además...
Dominios de aplicación
Los dominios de aplicación de los sistemas multiagentes son muy numerosos, gracias a la diversidad de los algoritmos.
1. Simulación de multitudes
El primer uso es la simulación de multitudes. Muchas aplicaciones utilizan agentes para simular personas que se desplazan en un lugar, lo que permite comprender la reacción en caso de evacuación y descubrir zonas de posibles aglomeraciones.
Encontramos esta simulación en el dominio de la planificación del tráfico, para comprender y simular las modificaciones introducidas por cambios como el hecho de agregar semáforos o reducir la velocidad en ciertos tramos.
Es posible, también, simular tropas, bien sean guerreros, jugadores, animales... Estas simulaciones se utilizan en el mundo del ocio, puesto que permiten realizar animaciones con bajo coste.
Así es como la aplicación MASSIVE, líder en el mercado, ha servido para crear muchos anuncios (como Adidas, Coca Cola, Pepsi...) y sobre todo muchas películas, para simular el movimiento de multitudes (y reducir el gasto en figurantes). La aplicación se ha utilizado también en los siguientes films (entre otros): El amanecer del planeta de los simios (2014), World War Z (2013), Godzilla (2014), Pompeya (2014), Tron Legacy (2010), El Señor de los Anillos (2003), I, Robot (2004)...
En los dibujos animados o los videojuegos, estos algoritmos...
Implementación
A continuación se implementan varios ejemplos. Por su funcionamiento, estos algoritmos son principalmente gráficos; aquí presentamos también el código que, si bien es genérico para las clases de base, son aplicaciones gráficas Java que utilizan Swing.
El modelo MVC no se ha respetado, voluntariamente, para mantener el código más ligero y simplificar su comprensión. Se crearán dos clases gráficas para cada simulación:
-
una que hereda de JPanel que gestiona la visualización gráfica y la actualización de la aplicación.
-
una que contiene el main y que ejecuta la ventana principal agregándole el panel previamente creado.
1. Banco de peces 2D
La primera aplicación es una simulación de un banco de peces, inspirado en los boids de Reynolds, en dos dimensiones.
Vamos a ver un conjunto de peces, representados como trazos, desplazándose por un océano virtual y evitando zonas peligrosas en su interior (que pueden ser obstáculos físicos o zonas con depredadores).
El comportamiento del banco se obtendrá únicamente por emergencia.
a. Los objetos del mundo y las zonas que es preciso evitar
Antes de codificar los propios agentes, vamos a codificar una primera clase que puede utilizarse a la vez por los objetos y los agentes. Esta, llamada simplemente Objeto, contiene dos atributos posX y posY que indican las coordenadas del objeto. Se trata de campos públicos, para optimizar su acceso. En efecto, se realizarán muchos accesos posteriormente y la llamada a un método (con la creación de su contexto) sería una pérdida de tiempo notable.
La base de nuestra clase es la siguiente. Se crean dos constructores, uno por defecto y otro que permite inicializar ambos atributos.
public class Objeto {
public double posX;
public double posY;
public Objeto() {}
public Objeto(double _x, double _y) {
posX = _x;
posY = _y;
}
} Se agregan dos métodos que permite calcular la distancia entre el objeto y otro objeto del entorno.
El primero devuelve la distancia al cuadrado, lo que simplifica los cálculos...
Resumen
Los sistemas multiagentes permiten resolver un gran número de problemas, tanto en la simulación de multitudes, en la planificación y la búsqueda de rutas o en la simulación de problemas complejos, para comprenderlos mejor y ayudar en su estudio.
Se basan, todos ellos, en observaciones realizadas sobre los insectos eusociales, que son capaces de resolver tareas muy complejas a partir de reglas muy simples. La solución aparece mediante emergencia, y no según un plan preprogramado. Las abejas encuentran nuevas fuentes de alimento, las hormigas se comunican mediante feromonas para optimizar el acceso al alimento y las termitas construyen enormes termiteros climatizados.
En informática, los sistemas multiagentes contienen un entorno en el que se encuentran objetos y agentes. No existen más que unas pocas reglas que seguir, y cada problema puede tener una o varias modelizaciones posibles.
Existen, sin embargo, algunos algoritmos más conocidos entre los sistemas multiagentes. Podemos citar los algoritmos que simulan el comportamiento de manadas basadas en boids, la optimización por colonias de hormigas y sus feromonas artificiales, los sistemas inmunitarios artificiales que permiten detectar y reaccionar a ataques o amenazas y autómatas de estados finitos; entre ellos, el más conocido es el juego de la vida de Conway.
En todos los casos, es la multiplicación de agentes y los vínculos...
