: MODELOS DE COORDINACIÓN PARA INTELIGENCIA ARTIFICIAL DISTRIBUIDA

Proyecto DAMMAD, Diseño y Aplicación de Modelos Multiagente para Ayuda a la Decisión, TIC2000-1370-C04-02

Informe Técnico: MODELOS DE COORDINACIÓN PARA INTELIGENCIA ARTIFICIAL DISTRIBUIDA

Junio, 2001. Universidad de Málaga


Indice

1 Introducción 2
2 Mecanismos de Cooperación: Interacciones Multi-Agente Cooperativas 4
2.1 Características 4
2.2 Técnicas deCoordinación 4
2.2.1 Estructuras Organizacionales 6
2.2.2 Planificación Multi-Agente 8
2.2.2.1 Planificación Multi-agente en Entornos Estáticos 9
2.2.2.2 Planificación Multi-Agente en Entornos Dinámicos 9
2.2.2.3 Planificación en Equipo 11
2.2.3 Redes de Contratos 12
2.2.4 Cooperación Funcionalmente Exacta 14
3 Mecanismos de Negociación: InteraccionesMulti-Agente Autointeresadas 14
3.1 Características 14
3.2 Técnicas de Coordinación 15
3.2.1 Mecanismos de Mercado 17
3.2.2 Teoría del Regateo 18
3.2.2.1 Teoría del Regateo Axiomática 18
3.2.2.2 Teoría del Regateo Estratégica 21
3.2.3 Formación de Coaliciones 23
3.2.3.1 Generación de la Estructura de Coaliciones 24
3.2.3.2 Resolución del Problema deOptimización de cada Coalición 24
3.2.3.3 División de Pagos 24
3.2.4 Votación 26
3.2.5 Subastas 29
3.2.5.1 Tipos de Subastas 29
3.2.5.2 Protocolos de Subastas 29
3.2.5.3 Eficiencia de la Asignación Resultante 31
3.2.6 Asignación de Tareas entre Dos Agentes 32
4 Selección en Tiempo de Ejecución de los Mecanismos de Coordinación 34
5 Soporte Operacional paralos Mecanismos de Coordinación 37
5.1 Agentes Intermediarios 37
5.2 Lenguajes de Comunicación de Agentes 38
6 Referencias 39


1 Introducción

La coordinación es tal vez uno de los problemas clave en Inteligencia Artificial Distribuida (IAD). Se denomina así al proceso por el cual un agente razona acerca de sus acciones locales y las acciones (anticipadas) de losotros, en un intento de asegurar una comunicación que permita a los agentes llevar a cabo sus acciones y comportamientos de forma coherente. Una coordinación efectiva es esencial si diferentes agentes autónomos quieren alcanzar sus objetivos dentro de un Sistema Multi-Agente (SMA). Dicha coordinación requiere gestionar las diferentes formas de dependencia que se producen cuando los agentes tienen:1) objetivos inter-enlazados, 2) comparten un entorno común, ó 3) hay recursos compartidos [Bourne et al, 2000].

Lógicamente, y con el fin de alcanzar dicha coordinación se han desarrollado hasta la fecha una gran diversidad de mecanismos. Quizás antes de pasar a enumerarlos, sería interesante analizar las teorías y principios que guían esta actividad, y que nos van a permitir obtener una mejorcomprensión de los mismos, así como una visión de conjunto. En la literatura de los SMA podemos encontrar diferentes análisis que modelan el problema de la coordinación de formas distintas. A continuación mostramos los tres enfoques que nos han parecido más interesantes, y han sido más ampliamente aceptados en esta comunidad.

Compromisos y Convenciones [Jennings, 96]. Jennings modela lascomunidades de agentes usando un formalismo de búsqueda de objetivos distribuida, y argumenta que los compromisos (promesa de acometer un curso de acción específica) y las convenciones (medios de gestionar los compromisos en circunstancias cambiantes) son las bases de la coordinación en todos los sistemas de IAD. De alguna manera los compromisos proporcionan la estructura necesaria para lasinteracciones predecibles, las convenciones proporcionan la flexibilidad necesaria para operar en entornos dinámicos, y las convenciones sociales proporcionan un grado de soporte mutuo entre ambas (los agentes necesitan convenciones sociales que especifiquen cómo comportarse con respecto a los otros miembros de la comunidad cuando se alteran sus compromisos).

Según este análisis la mayoría de los...