Ediciones ENI Editorial | líder en informática
Sistemas multi-agentes
Presentación del capítulo
Este capítulo presenta los sistemas multi-agentes, 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 multi-agentes, 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 C#. 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 sus comportamientos sociales, sí se han actualizado los grandes principios.
La mayoría de insectos (cerca del 90% de las especies) son solitarios. Cada insecto vive por su lado, con pocos o incluso ningún vínculo con sus vecinos. Es el caso, por ejemplo, de la mayoría de 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. Presentan 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 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 los huevos (se fertiliza...
Sistemas multi-agentes
Todas las técnicas clasificadas como sistemas multi-agentes 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 reside en la percepció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, una percepción localizada) o tener un mapa registrado previamente de toda la planta con la posición en la que se encuentran (por ejemplo, mediante un GPS, una percepción total).
Además, cuando poseen una cámara, en el caso de una visión simbólica, pueden tener 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 producto de la percepción, tener que interactuar en función de las imágenes brutas (tal y como se obtienen a través de la cámara).
Los investigadores de sistemas multi-agentes tienen preferencia por las percepciones localizadas, pero les cuesta elegir entre un enfoque simbólico...
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 multi-agente 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, como 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 multi-agentes 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, permitiendo así 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, ya sean guerreros, jugadores, animales... Estas simulaciones se utilizan en el mundo del ocio, puesto que permiten obtener animaciones a 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 las siguientes películas (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...
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 WPF para Windows.
Tras la creación de dichos proyectos en Visual Studio, se crean los archivos App.config, App.xaml y App.xaml.cs. Estos no se modifican. Por el contrario, los archivos MainWindows.xaml y MainWindows.xaml.cs sí se modifican, y se proporciona su código.
El modelo MVVM no se ha respetado, voluntariamente, para mantener el código más ligero y simplificar su comprensión.
1. Banco de peces
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 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 a evitar
Antes de codificar los propios agentes, vamos a codificar una primera clase que puede ser utilizada a la vez por los objetos y los agentes. Esta, llamada ObjectInWorld, 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 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.
using System;
public class ObjectInWorld
{
public double PosX;
public double PosY;
public ObjectInWorld() {}
public ObjectInWorld(double _x, double _y)
{
PosX = _x;
PosY = _y;
}
}
Se agrega un método que permite calcular la distancia entre el objeto y otro objeto del entorno.
public double...Resumen
Los sistemas multi-agentes 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 como 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 emerge y no es el resultado de 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 multi-agentes contienen un entorno en el que se encuentran objetos y agentes. No existen más que unas pocas reglas a seguir, y cada problema puede tener una o varias modelizaciones posibles.
Existen, sin embargo, algunos algoritmos más conocidos entre los sistemas multi-agentes. 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...
