Post on 01-Dec-2020
transcript
1
SO 2.3.2004−1−
La Coordinación en los Sistemas Multiagente
Sascha OssowskiGrupo de Inteligencia Artificial
Dep. de Informática, Estadística y TelemáticaUniversidad Rey Juan Carlos
SO 2.3.2004−2−
La Coordinación en los Sistemas Multiagente
1. Introducción
2. Dimensiones de la Coordinación
3. Un Ejemplo: Sociedades de Agentes
4. Conclusiones
Indice:
2
SO 2.3.2004−3−
¿Qué es la Coordinación?
• Concepto “universal”:– Ciencias Sociales, Economía, Biología, …– Robótica, Ingeniería del Software, Lenguajes de Programación,
Inteligencia Artificial (Distribuida), …
• Semántica “borrosa”:– Múltiples definiciones– ¡Esto no es coordinación!
• Coordinación en los Sistemas Multiagente (SMA):– la coordinación es un problema clave en la construcción de SMAs– la capacidad para coordinarse es una característica esencial de un agente
SO 2.3.2004−4−
La coordinación en los SMA: perspectivas diferentes
Diseño a nivel macroDiseño a nivel micro
Varios diseñadores de agentes Un diseñador de agentes
Interés del diseñador en la coordinación
Un diseñador de agentes– agentes benévolos– diseñar todo un sistema de
resolución de problemas“La coordinación es la integración y el ajuste
del trabajo individual con el fin de alcanzar una meta mayor”
(B. Singh)
Diseño a nivel macro– construir sistemas de múltiples
agentes con características deseadas
3
SO 2.3.2004−5−
Coordinación a nivel macro: Resolución Dist. de Problemas
• Ejemplo: Gestión de tráfico rodado
– red de autopistas urbanas
– Construir un sistema que genere planes de señalización en función del estado del tráfico
SO 2.3.2004−6−
Arquitectura TRYS (Cuena et al.):
• agentes de resolución de problemas– cada agente es responsable de un
área problema– genera planes alternativos de
señalización local y los comunica al agente coordinador
• agente coordinador – resuelve las interdependencias entre
los planes locales– envía los planes locales adaptados a
los agentes para su ejecución
Coordinación a nivel macro: Resolución Dist. de Problemas
4
SO 2.3.2004−7−
La coordinación en los SMA: perspectivas diferentes
Diseño a nivel micro
Varios diseñadores de agentes
Interés del diseñador en la coordinación
Un diseñador de agentes– agentes benévolos– diseñar todo un sistema de
resolución de problemas
Diseño a nivel macro– construir sistemas de múltiples agentes
con características deseadas
Diseño a nivel micro– en un entorno abierto con
múltiples agentes– diseñar un agente adicional
con características deseadas
“La coordinación es una forma de adaptarse al entorno”
(von Martial)
SO 2.3.2004−8−
Coordinación a nivel micro
Ejemplo:
• Agente R1 ha de vigilar una zona
– existen dos puntos de observación (P1 y P2)
– suponen un valor (altura) y un coste (distancia)– acciones: A1 (ir a P1), A2 (ir a P2) y N (nada) Coste: 1
P1 P2
R1
Valor: 2 Valor: 4
Coste:2
• Mundo multiagente junto con R2:– Utilidad: URi(Ai) = valor ({Pi,Pj}) – coste(Ai)– R1 conoce sus tres acciones alternativas y sus consecuencias– R1 no sabe si R2 es consciente de tener la alternativa A2
Coste: 1
R2
5
SO 2.3.2004−9−
1
4
11/3
[1/3, 1/3, 1/3]
0 4 05 3 3
2 4 0
A1A2N
A1 A2 NR1
R2
[0.5, 0.5]
0 – 0– – –
2 – 0
A1A2
N
A1 A2 NR1
R2
Modelo de R1 de su propia situación
R1 no sabe qué modelo R2 tiene de él
Modelo de R1 sobre las posibles acciones de R2
1 5 1
4 2 22 4 0
A1A2
N
A1 A2 N
R1
R2
[0.25, 0.75]
p=0.75p=0.25
R2 no sabe de P2 R2 sabe de P2
Coordinación a nivel micro
Método RMM (Gmytrasievicz y Durfee):
SO 2.3.2004−10−
La coordinación en los SMA: perspectivas diferentes
Diseño a nivel micro
Varios diseñadores de agentes
Interés del diseñador en la coordinación
Un diseñador de agentes– agentes benévolos– diseñar todo un sistema de
resolución de problemas
Diseño a nivel micro– en un entorno abierto con
múltiples agentes– diseñar un agente adicional
con características deseadas
Diseño a nivel macro– construir sistemas de múltiples agentes
con características deseadas
“Coordinar es gobernar la interacción”(Wegener )
Varios diseñadores de agentes– no se puede ejercer un control
directo sobre los agentes– diseñar el contexto del sistema
6
SO 2.3.2004−11−
Coordinación a nivel macro: Sociedades de Agentes
• Mecanismo de subasta:
– un agente usuario comunica las características de la llamada a los distintos agentes empresa
– cada agente empresa contesta con una oferta (precio por minuto)
– el agente usuario elige una oferta en base a una convención
• Ejemplo: Comercio Electrónico (Rosenschein y Zlotkin):
– asignación de llamadas telefónicas a compañías de telecomunicación– objetivo: evitar comportamiento estratégico entre compañías
SO 2.3.2004−12−
• Convención 1:– elegir la mejor compañía y pagar
el precio de la oferta más baja– problema: promociona el
comportamiento estratégico
• Convención 2:– elegir la mejor compañía y pagar el
precio de la segunda oferta más baja– elimina incentivos para el
comportamiento estratégico
Coordinación a nivel macro: Sociedades de Agentes
7
SO 2.3.2004−13−
La Coordinación en los Sistemas Multiagente
1. Introducción
2. Dimensiones de la Coordinación
3. Un Ejemplo: Sociedades de Agentes
4. Conclusiones
Indice:
SO 2.3.2004−14−
Coordinar es Gestionar Dependencias
8
SO 2.3.2004−15−
Coordinar es Gestionar Dependencias
Tareas de coordinación: • definición del contexto de coordinación: agentes, metas, tareas, capacidades, etc.• detección de dependencias: recursos compartidos, productor/consumidor etc.
• decisión de gestión: secuenciación temporal, selección de recursos etc.
t1 t2 t3
t
t1,1 t1,2 t1,3 t3,3t3,2t3,1
t'1 t'2
t'
t'1,1 t'1,2 t'1,3 t'2,1 t'2,2 t'2,3
Agente 1 Agente 2
localtype A
type B
Coordinación: gestión de dependencias (Malone y Crowston)
SO 2.3.2004−16−
Mecanismos de Coordinación: Dimensiones
• coordinación centralizada:– agente coordinador destacado
• coordinación descentralizada:– “coordinación emergente”
Centralizado frente a descentralizado:
• grado de distribución de las tareas de coordinación
9
SO 2.3.2004−17−
Directo frente a mediado (Omicini):• los mecanismos mediados requieren agentes intermediarios o
distinguidos medios de coordinación• los mecanismos directos son de igual a igual (“peer-to-peer”)
Entrelazado (“coupled”) frente a desenlazados (“uncoupled”) (Tolksdorf):
• los mecanismos entrelazados requieren asunciones respecto al comportamiento de otros agentes
• los mecanismos desenlazados no hacen asunciones sobre el comportamiento de los demás
Mecanismos de Coordinación: Dimensiones
SO 2.3.2004−18−
Mecanismos de coordinación: Dimensiones
Cualitativo frente a cuantitativo (Ossowski):
• representación de las dependencias que guían las tareas de coordinación
• mecanismos cualitativos: representación explícita de las dependencias– para su detección: dependencias del dominio– para la toma de decisiones: dependencias sociales
(Conte & Castelfranchi, Sichman & Demazeau)
• mecanismos cuantitativos: las dependencias se compilan en una función de utilidad multiatributo– Ejemplo del Comercio Electrónico (Zlotkin & Rosenschein)
( ) ( ) ( ) <∧<−
=contrariolode
ppppsicppppU BTTelDTTelTelTel
BTDTTelTel 0,,
10
SO 2.3.2004−19−
Gobernado frente a ingobernable (Papadopoulos):
• posibilidad del diseñador de influir en las tareas de coordinación
• gobernado en tiempo de diseño (entornos cerrados):– los comportamientos de todos los agentes se fijan a priori
• ingobernable (entornos abiertos):– comportamientos inesperados– frecuencias inesperadas de comportamientos conocidos
• gobernado en tiempo de ejecución:– coordinación supervisada de forma dinámica– ejemplo: coordinación como un servicio
Mecanismos de Coordinación: Dimensiones
SO 2.3.2004−20−
Subjetivo frente a objetivo (Schumacher):
• punto de vista acerca de las tareas de coordinación
• coordinación subjetiva:
– guiada por los intereses de un agente individual (“desde dentro”)– gestión de tráfico rodado: minimizar demoras en un área problema
• coordinación objetiva:
– guiada por los intereses del diseñador global (“desde fuera”)– gestión de tráfico rodado: maximizar la fluidez global del tráfico
Mecanismos de Coordinación: Dimensiones
11
SO 2.3.2004−21−
La Coordinación en los Sistemas Multiagente
1. Introducción
2. Dimensiones de la Coordinación
3. Un Ejemplo: Sociedades de Agentes
4. Conclusiones
Indice:
SO 2.3.2004−22−
La Coordinación en Sociedades de Agentes
SMA como Sociedades de Agentes:
• enfoque construccionista en el diseño: agentes autónomos + coordinación
Problema: asegurar una suficiente calidad global de la coordinación• Sólo subjetivo:
– modificar el concepto de racionalidad de los agentes– “we-intentions” (Tuomola), altruismo (Brainov),
racionalidad social (Jennings&Campos), ….
• Subjetivo + objetivo:– preservar la autonomía de los agentes (racionalidad individual)– sesgar el resultado de la coordinación auto-interesada
Ejemplo: cooperación estructural (Ossowski)– sociedades de agentes para resolución de problemas– dominios de coordinación reactivos
12
SO 2.3.2004−23−
El Dominio Síncrono de los Bloques
Plan Operations Capab. Exec.π1 [move(2,table),move(3,2)] α1 trueπ3 [move(2,table),NOP] α1, α2 trueπ4 [move(1,table),NOP] α1, α2 trueπ7 [move(1,table),move(2,table)] α1, α2 trueπ9 [move(2,table),move(4,2)] α2 falseπ10 [move(1,2),move(4,1)] α2 trueπ11 [move(2,1), move(3,2)] α1 trueπε [NOP,NOP] α1, α2 true
4
1
32
2231
41
Estados idealesα1: distancia 3
... ... ... ...
Situación inicial Algunos planes:α1 α2
α2: distancia 4
SO 2.3.2004−24−
Cooperación Estructural: Coordinación Subjetiva
Coordinación subjetiva :
• Modelar el comportamiento “racional” en diferentes contextos
– contexto individual: se considera un sólo agente
– contexto social: se considera el entorno multiagente
– contexto normativo: se consideran normas sociales como estructuras coercitivas adicionales
• Cooperación estructural: modelo cualitativo
13
SO 2.3.2004−25−
Coordinación subjetiva: el contexto individual
• Selección de acciones de forma individualmente racional:– un agente elige el plan más preferido que pueda llevar a cabo y que
sea ejecutable en la situación actual
4
1
2
3
1 234
α1 elige π1 α2 elige π7
SO 2.3.2004−26−
4 1 23
1 234
preferido por α2preferido por α1
El dominio síncrono de los bloques
Un mundo multiagente:
• multiplan µ : ejecución simultánea de varios planes individuales
• interdependencia con respecto a la posibilidad de la ejecución (exec)
• interdependencia con respecto al resultado de la ejecución (res)
ji ππ oKo
multiplan multiplan
α1: aproximación 2α2: aproximación 1
α1: aproximación 0α2: aproximación 3
41 ππ o 94 ππ o
14
SO 2.3.2004−27−
( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )
( ) ( ) ( ) ( )),(),(
,,, ,,,),(),(
,,, ,,,,,, ,,,
,,, ,,,
sressres
tinterferenprepprepfavourssressres
tinterferenprepprephindersarycomplementprepprepenables
ntinconsisteprepprepprevents
ssss
ssss
ssss
ssss
µππ
µπµγπαµγπαπµπ
µπµγπαµγπαµπµγπαµγπα
µπµγπαµγπα
α
α
opp
ppo∧∧∧⇔
∧∧∧⇔∧∧⇔∧∧⇔
Coordinación subjetiva: el contexto social
( )( )
),(),( ),(),(),( ),(
),(),(),(),( ),(),(),(
),(),(),(),( ),(
sexecsexecntinconsistesexecsexecarycomplement
sressressexecsexectinterferensexecsexec
sressressexecsexectindifferen
s
s
s
s
µππµπµππµπ
πµπµππµπµππ
πµπµππµπ
oo
ooo
oo
¬∧⇔∧¬⇔
≠∧∧⇔¬∧¬∨
=∧∧⇔
• Relaciones de dominio entre planes
• Relaciones de dependencia entre agentes
SO 2.3.2004−28−
• Tipos de dependencia entre agentes:
• Grados de dependencia entre agentes:
• Estructura de dependencia:– el conjunto de todas las relaciones de dependencia social entre agentes
( ) ( ) ( )( ) ( )( ) ( )µγπαµγπα
µγπαµγπαµγπαµγπαµγπα
,,, . ,,,,, . ,,
,,,,,, . ,,
ss
ss
sss
favoursdepposhindersdepneg
preventsenablesdepfeas
∃⇔−∃⇔−
∨∃⇔−
feas-dep neg-dep pos-dep
Coordinación subjetiva: el contexto social
15
SO 2.3.2004−29−
• Prescripciones normativas:– prohibiciones para ejecutar un multiplan
– preparación (prep): capacidad + ausencia de prohibiciones
– las prescripciones modifican la estructura de dependencia “natural”
• Estructura social:
– estructura de dependencia + prescripciones normativas
Coordinación subjetiva: el contexto normativo
SO 2.3.2004−30−
Coordinación subjetiva: • emergerán complejos patrones de interacción
– cooperación para determinar las relaciones entre planes– negociación sobre la decisión de coordinación
• asegurar el cumplimiento de las prescripciones:– gobernar la interacción en tiempo de diseño: programa de agente
– gobernar la interacción en tiempo de ejecución: infraestructura de coordinación
Coordinación objetiva:• modelo para predecir el resultado global de la coordinación subjetiva• mecanismo para sesgar dicho resultado en una dirección deseada• cooperación estructural: modelo cuantitativo
Coordinación subjetiva y Coordinación objetiva
16
SO 2.3.2004−31−
• Modelo de cooperación :– Vector de utilidad de un multiplan:
la reducción de la distancia a los estados ideales de cada agente
– Multiplanes mixtos: distribución de probabilidad sobre un conjunto de multiplanes legalmente ejecutables
– Utilidad esperada de un multiplan mixto: suma ponderada de las utilidades de los multiplanes componente
– Conjunto S: todos los vectores de utilidad que se puedan alcanzar
Coordinación objetiva: modelo de cooperación
SO 2.3.2004−32−
• Modelo conflicto:– utilidad conflicto: mejor opción
individual de un agente, suponiendo que todos los demás se vuelven contra él de forma conjunta
– punto de desacuerdo :vector de las utilidades conflicto
• Escenario de regateo:
conjunto de regateo+
punto de desacuerdo
dr
dr
( )dSr
,
Coordinación objetiva: modelo conflicto
17
SO 2.3.2004−33−
Coordinación objetiva: modelo del resultado
• Propiedades deseables para una solución al escenario de regateo :
– Racionalidad individual:
– Optimalidad de Pareto:
– Simetría: misma posición de regateo.
– Invariabilidad de escala :
– Independencia de contracción:
• Teorema (de Nash):El único vector que cumple todos estos axiomas es maximizador de la función
( ) ( )∏=
−=n
iii dxxN
1
r
ϕr
ϕr ( )dS
r,
ϕrr
≤d
., ϕrrr
≠∈¬∃ xSx
ji ϕϕ =
( )., dSasoluciónr
λλϕλ λϕϕλrr
=
( ).,,, dSasoluciónSdSSrrr
′′′∈⊆′ ϕ ϕϕϕrrr
=′⇒∈ S
xrr
≤ϕ
SO 2.3.2004−34−
4
1
32
2231
41
α1 α2
... ... ... ...
Situación inicial: Resultados Pareto-optimales:α1 α2
4 1 2
3
1 234
Estados ideales: 1 2 3 4
preferencia de α2
preferencia de α1
compromiso
El dominio síncrono de los bloques
18
SO 2.3.2004−35−
Coordinación objetiva: el resultado
• Efectos de la estructura de dependencia :– El grado de dependencia modifica el punto de desacuerdo
: no se puede usar Ui(π) como utilidad conflicto: sólo Ui(πoµ) < Ui(π) puede usarse como utilidad conflicto: se puede usar Ui(π) como utilidad conflicto
• Efectos de las prescripciones normativas :– las prohibiciones pueden impedir que un grupo lleve a cabo un plan que
afecte la efectividad de un plan π de un agente αi
– es posible que mejore la utilidad conflicto de αi
( )( )( )γπα
γπα
γπα
,,
,,
,,
is
is
is
deppos
depneg
depfeas
−
−
−
SO 2.3.2004−36−
Monotonía del punto de desacuerdo
19
SO 2.3.2004−37−
La Coordinación en los Sistemas Multiagente
1. Introducción
2. Dimensiones de la Coordinación
3. Un Ejemplo: Sociedades de Agentes
4. Conclusiones
Indice:
SO 2.3.2004−38−
Resumen
• Coordinación en Sistemas Multiagente:– dependiente de los requerimientos (interés y posibilidades del diseñador)– clasificación y ejemplos
• Dimensiones de la coordinación:– centralizado/descentralizado, mediado/directo, entrelazado/desenlazado– métodos cualitativos / métodos cuantitativos– gobernada en tiempo de diseño / gobernada en tiempo de ejecución/ ingobernable – coordinación objetiva / coordinación subjetiva
• Coordinación en Sociedades de Agentes– Ejemplo: Cooperación estructural
20
SO 2.3.2004−39−
La coordinación en los SMA: perspectivas diferentes
Interés del diseñador en la coordinación
Diseño a nivel micro– en un entorno abierto con múltiples
agentes– diseñar un agente adicional con
características deseadas
Diseño a nivel macro– construir sistemas de múltiples agentes
con características deseadas
Varios diseñadores de agentes– no se puede ejercer un control
directo sobre los agentes– diseñar el contexto del sistema
Un diseñador de agentes– agentes benévolos– diseñar todo un sistema de
resolución de problemas
subjetivo
objetivo
SO 2.3.2004−40−
Coordinación: Líneas futuras
Mecanismos de coordinación en sociedades abiertas
Coordinación como un servicio• eligiendo el servicio, el agente acepta
sus condiciones• controlado por el proveedor / el medio
de coordinación
Coordinación por normas sociales• conocimiento común de las normas sociales• cumplimento en base al control social,
modelos de confianza, “gossip”, ...
Coordinación por “selección”• las estrategias cooperativas (coordinadas)
suelen sobrevivir en interacciones repetidas• sesgar el entorno modificando las
frecuencias de tipos de agentes
Coordinación por “evolución cultural”• coevolución de leyes/normas sociales y tipos/frecuencias
de comportamientos individuales
21
SO 2.3.2004−41−