Introduccion a Los Agentes y Sistemas Multiagentes

Introduccin a los Agentes y Sistemas MultiagenteCsar Llamas Bello Departamento de Informtica Universidad de Valladolid [email protected] 24 de julio de 2000

Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA

1


2

Contenidos 1. Introduccin a los agentes. (a) Arquitecturas de agentes. (b) Arquitecturas de sistemas de agentes. (c) Agentes en Ingeniera del Software (d) Agentes software 2. Sistemas Multiagente. (a) Caractersticas de la agencia. (b) Knowledge Sharing Effort 3. Conclusin.Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 3

AgenteAgente: proceso computacional (a) autnomo, (b) con iniciativa y capacidad de explorar y modificar su entorno y (c) posibilidad de comunicarse con otros agentes. Capacidades deseables: cooperacin, aprendizaje, racionalidad, benevolencia ...Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 4

Antecedentes de los sistemas basados en agentes

Filosofa Sociologa Economa Informtica Inteligencia artificial Computacin orientada al objeto Sistemas distribuidos


5

Capacidades en los agentes Ejemplos de agentes muy Agentes inteligentes dispares: que cooperan sensor de temperatura. planificador de la trayectoria de un vehculo.

aprendizaje

autonoma cooperacin


6

Para qu sirven los agentes

Anlisis de sistemas reales complejos en Sociologa, el comportamiento de una sociedad, ... en Economa, los sistemas de negociacin, ...

Modelado en IA, resolucin de problemas complejos por cooperacin, ... en SD, la construccin de aplicaciones distribuidas, ... en IS, la construccin de aplicaciones complejas, ... en Prog. Conc., la construccin de aplicaciones concurrentes, ...

En s mismos son interesantes.


7

Aspecto de los agentesambiente acta agente

percibe forma de ser

En funcin de la naturaleza del agente ste interacta mediante: sensores y actuadores fsicos, canales de entrada salida, operaciones de lectura y escritura, ...Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 8

Agentes inteligentes Autonoma, movilidad, iniciativa, adaptabilidad ? inteligencia. En IA se persigue estudiar y obtener agentes que exhiban caractersticas de la inteligencia humana (McCarthy, Shoham). Construimos agentes inteligentes cuando (Russell): describimos su comportamiento y el ambiente mediante conocimiento. dispone de iniciativa de explorar el ambiente. incrementa su conocimiento basndose en la experiencia. evala la consecucin de las metas que se le planteen.


9

Agente RacionalLa racionalidad le permite al agente hacer en cada momento lo correcto. Lo correcto son las acciones que conducen al mejor desempeo de su misin, descrita en trminos de: meta. utilidad.

para ser racional necesita ser capaz de medir el desempeo de su misin. tener algn criterio de medida. incorporar los resultados como conocimiento nuevo.

racionalidad omnisciencia


10

Ejemplos de agentes

Agente Diagnosticador mdico Robot clasificador de piezas Asistente de correo electrnico

Percepciones Sntomas, evidencias, respuestas Mapas de pixels

Acciones Preguntas, anlisis, tratamientos Recoger piezas y clasificarlas en cajas Clasificar, borrar, responder correo

Metas

Ambiente

Salud, mnima Paciente, intrusin hospital Poner pieza en la caja correcta Reproducir el comportamien to del usuario Banda transportadora con piezas y cajas Clientes y servidores de correo, usuario

Encabezados y textos de mensajes


11

Arquitecturas de agentes Con respecto a la forma de abordar la construccin del agente, puede ser: arquitectura reactiva agentes reactivos agente con representacin del mundo

arquitectura deliberativa agentes basados en metas agentes basados en la utilidad


12

Arquitectura deliberativa Expresa el comportamiento y el ambiente en trminos de conocimiento representado simblicamente. Las decisiones se toman empleando mecanismos deductivos. pattern matching diversas lgicas.

En estos trminos, las componentes del agente se deben representar en trminos lgicos.Un ejemplo exitoso: BDI (Belief, Desire, Intention) (Rao, Georgeff) Creencias: modelo del mundo y del resto de agentes. Deseos: metas. Intenciones: plan de accin.


13

Arquitectura reactiva Un razonamiento explcito sobre los efectos producidos por acciones de bajo nivel es demasiado costoso para producir una conducta en tiempo real. (Suchmann, Rosenschein, Kaebling -1990: autmatas situados) El comportamiento inteligente se generar sin tener que usar modelos simblicos, y emerger en ciertos sistemas complejos. (Brooks - 1991: arquitectura de subsuncin) Estas arquitecturas manejan jerarquas de tareas en funcin de niveles de abstraccin.


14

Arquitecturas hbridas

Combinan agentes de tipo reactivo y deliberativo. reactivo: reacciona a los eventos del entorno sin invertir razonamiento. deliberativo: planifica (distribuye las metas ms simples) y realiza tareas de nivel de abstraccin superior. Este tipo de tareas se agrupan tpicamente en dos niveles: de manipulacin de la informacin a nivel abstracto. contiene una representacin simblica del ambiente. de comportamiento social y planificacin de alto nivel.

Se organizan: horizontalmente: las capas tienen acceso a sensores y actuadores. verticalmente: una capa actua de interfaz con sensores y actuadores.Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 15

Agente reactivo sin estado

agente

sensoresCmo es el mundo

Reglas: Condicin -> accin

Qu hacer

efectores


ambiente

16

Agente dirigido por metas explcitas

agente agente estado cmo evoluciona el mundo qu producen mis acciones

sensorescmo es el mundo

cmo mejorar La situacin utilidad qu hacer

efectores


ambiente

qu efecto produciran mis acciones

17

Ambientes Accesible / inaccesible: Es posible explorar toda la informacin necesaria?

Determinista / no determinista: La evolucin del entorno se sigue de un cmputo o hay actores que responden de forma no previsible?

Episdico / no episdico: La accin del agente se produce bajo demanda o el agente ha de ser pro-activo ?

Esttico / dinmico: Cambia el entorno aunque no entre en accin el agente?

Discreto / contnuo: El modelo del ambiente es contnuo o discreto (simblico)?Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 18

Arquitecturas de sistemas de agentes (Ferber)

tipo Modular horizontal Pizarra Subsuncin

aproximacin Funcional horizontal funcional Funcional vertical

tipo componente mdulo tarea tarea primitiva tarea + acciones primitivas Regla neurona formal

estructura de subordinacin Jerrquica jerrquica(meta) jerrquica jerrquica (competitiva) jerrquica igualitaria

estructura de Acoplamiento

constitucin

Fija (progresiva) predefinida variable predefinida fija variable evolutiva fija (por peso) predefinida predefinida predefinida predefinida

Tareas Funcional vertical competitivas Reglas produccin funcional

Conexionista Funcional vertical Sistema dinmico Multiagente Funcional vertical objeto / funcional

Estmulo/respuesta igualitaria Agente igualitaria

fija (progresiva) emergente variable emergente


19

Agentes en la Ingeniera del Software La tecnologa basada en agentes se puede emplear en situaciones donde se observe modularidad, descentralizacin, mutabilidad, dificultades de estructura, complejidad,


20

Descentralizacin de los agentes Un agente puede ser un ente pro-activo: con iniciativa propia. monitoriza el ambiente ejerce cambios en el ambiente y se comunica con otros agentes.

Es til en sistemas donde aparecen procesos autnomos. Los sistemas descentralizados permiten mayores tasas de fiabilidad y robustez que los sistemas centralizados


21

Sistemas cambiantes Los sistemas basados en agentes animan a la reutilizacin: es posible modificar sistemas basados en agentes sobre la marcha pieza a pieza. ciertos tipos de descentralizacin desacoplan las dependencias de los agentes.


22

Empleo de agentes en sistemas difcilmente estructurables En los sistemas donde las relaciones entre los componentes se deciden sobre la marcha. Se disean agentes, cuyo dilogo se establece a posteriori en funcin del empleo que se d. Ejemplo: Electronic Data Interchange (EDI). un contratante puede actuar como cliente y proveedor en relaciones que pueden involucrar varias partes. el agente es siempre el mismo, cambia el entorno de ejecucin.

El diseo del agente se puede hacer pensando en la interaccin con el entorno, ms que en la interaccin con agentes concretos.Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 23

Agentes para entornos complejos Un sistema software que opere en un entorno complejo debe realizar muchas y variadas tareas. Ejemplo: clula de fabricacin flexible existen diversas mquinas cada una de las cuales ofrece varias posibilidades. la fabricacin de una pieza involucra varias mquinas en diferentes estados. El nmero de comportamientos diferentes crece exponencialmente con el nmero de mquinas disponibles.

el comportamiento de cada elemento del sistema se puede remplazar por un agente, del que puede haber varios ejemplares.


24

Agentes y objetos Principales conceptos que definen la orientacin a objetos: relacin clase /instancia; herencia; mecanismo de mensajes

polimorfismo.

Principales conceptos que definen a un agente autonoma (procesos ejecutndose en paralelo), iniciativa (que utilizan en perseguir metas), mecanismo de comunicacin de alto nivel.

La POA puede considerarse una especializacin del paradigma de la POO (Shoham, 1993). Un objeto puede considerarse cierto tipo de agente simplificado.


25

Agentes y objetos

objetomtodo mtodo mtodo

peticiones

respuestas


26

Agentes y objetos (ii)

agente servicio

objetivos

Actos de comunicacin


27

Modelado orientado a agentes Los mecanismos de abstraccin del modelado conceptual usual en POO se aplican en POA: clasificacin / instanciacin, agregacin / descomposicin, generalizacin / especializacin, agrupacin / individualizacin.

La POO incorpora su acervo a las futuras metodologas de desarrollo de agentes.


28

Agentes software En la prctica es posible encontrar, entre otros, Agentes mviles. Agentes de Internet. Agentes de interfaz y asistentes personales.


29

Agentes mviles Los agentes mviles son agentes con capacidad de migracin. El agente se sita donde radican los datos con el fin de evitar sobrecarga de comunicacin, ejecutarse en el contexto apropiado, obtener recursos de los que no se dispone.

problemas importantes seguridad: hacen lo que dicen que hacen? confidencialidad, autentificacin, estandarizacin: MASIF: Mobile Agent System Interoperability Facility (OMG) FIPA ACL.

Plataforma Grasshopper (Hft, Magedanz, Quantz)Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 30

Agentes de Internet y mediacin Especializados en la bsqueda de informacin en internet. Navegan por la red buscando y organizando informacin (robots de bsqueda). Tambin se subscriben en estos trminos los agentes de mediacin (middleware), que cumplen misiones de facilitacin rutadores, tablones de anuncios, Brokers

y tambin, de mediacin para proporcionar acceso uniforme a recursos diversos. Un uso posible es proporcionar acceso uniforme a bases de datos variadas.


31

Agentes de interfaz y asistentes personales Son agentes flexibles que exhiben capacidades de adaptacin al medio. liberan al usuario de tareas repetitivas habituales. se basan en la idea de delegacin.

Pueden actuar por iniciativa propia en lugar del usuario. Se aplican con xito en despacho de correo electrnico interfaces con gran cantidad de informacin: bolsa, salas de control, salas de emergencia asistentes de planificacin de agendas, agendas compartidas, etc.


32

Sistema Multiagente Sistema Multiagente (MAS): conjunto de agentes autnomos, generalmente heterogneos y potencialmente independientes, que trabajan en comn resolviendo un problema. Caractersticas de estos agentes, vinculado con la nocin de agente inteligente capaz de tomar la iniciativa, capaz de compartir conocimiento, capaz de cooperar y negociar, capaz de comprometerse con metas comunes.

El estudio de MAS se encuadra dentro de la Inteligencia Artificial Distribuida (DAI).


33

Inteligencia Artificial Distribuida Rama de la IA que estudia la solucin de problemas mediante procesamiento descentralizado. Resolucin distribuida de problemas (DPS): Se descompone el problema en procesos cooperantes que comparte conocimiento, para un problema concreto. MAS Inteligencia Artificial Paralela (PAI): Desarrollo de algoritmos y aplicaciones paralelas, con nfasis en prestaciones.


34

Agentes Inteligentes vs. Agentes no Inteligentes Agentes no inteligentes: Ausencia de estructura social entre agentes: interaccin predefinida. Universo estable, predecible y observable. Consecuencia: sistemas poco flexibles frente a entornos cambiantes.

Agentes inteligentes: Actan en entornos cambiantes, inciertos e impredecibles. Actan con conocimiento incompleto. Pueden cooperar para resolver problemas ms complejos.


35

Sociedad humana: modelo de agencia La sociedad humana es un modelo til para obtener MAS. La mayora de las actividades humanas relacionadas con el comportamiento inteligente son de carcter social, al menos en origen. El ser humano necesita la sociedad para vivir mejor, est en contnua interaccin con el resto. La mayor parte del conocimiento es colectivo.

Los modelos terico/prcticos de MAS permiten estudiar fenmenos sociales reales.


36

Caractersticas de la agencia En los MAS aparecen conceptos de gran interes actividades conjuntas y cooperacin; conflictos, cmo se resuelven; negociacin; compromisos y planificacin de actividades; modelo del conocimiento, y su comunicacin.


37

Cooperacin Cooperacin: es el proceso por el que ciertos agentes participantes generan deberes mutuamente dependientes en actividades conjuntas (planes).1. 2. 3. 4. Se recibe un problema en cierto nivel de abstraccin. El agente resuelve localmente aquello que es posible. Recurre a otros agentes del mismo nivel para el resto de las tareas. Recurre a otros niveles de abstraccin para el resto de las tareas.


38

Conflictos Los conflictos surgen cuando al resolver un problema hay una o varias de las siguientes circunstancias el conocimiento local es incorrecto o incompleto, coexisten metas diferentes y divergen en algn momento, hay difierentes criterios de evaluacin de soluciones, los recursos estn limitados.

Aspecto positivo se intercambia informacin mejora la robustez e integracin se llega a soluciones globalmente ptimas.

Los conflictos se resuelven o evitan mediante mecanismos de prevencin y evitacin, sistemas de pizarra, negociacin.Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 39

Negociacin La negociacin se resuelve en un plan comn; que es ptimo cuando se da una situacin de paridad conjunta. Negociacin estricta: negociacin de un plan comn; ejecucin estricta del plan.

Negociacin generalizada: entrelazamiento de negociacin y ejecucin.

Existen esquemas conocidos de negociacin y relajacin de metas (Zlotkin y Rosenschein, 1990). Existen mecanismos de arbitraje bien conocidos (Lesser -1988, Durfee, Sycara -1989).Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 40

Proceso de negociacin El proceso de negociacin es iterativo los agentes afectados ofrecen propuestas o posturas ninguna de estas propuestas es ms exigente que la anterior

La negociacin finaliza cuando hay acuerdo: se crea un plan conjunto. hay interbloqueo: no hay acuerdo y se requiere otro procedimiento de solucin o negociacin. se produce una apelacin: un agente coordinador puede modificar metas o relajar las restricciones.


41

Compromisos Los compromisos forman un conjunto de restricciones sobre las acciones y creencias de cada agente. Se representan mediante conocimiento compartido y local de cada agente con respecto al resto. Dan forma a la nocin de agencia: son el fundamento de la cooperacin, negociacin, y planes y metas conjuntas; cohesionan la agencia.

Alternativas: Compromiso como eleccin individual, temporal y local. Compromiso como nocin distribuida o social.


42

Interacciones entre agentes Las interacciones en sistemas MAS obedecen a la coexistencia de planes elaborados, preferentemente, de forma distribuida. Generacin de operaciones candidatas, seleccin, relevancia en la obtencin del resultado, ejecucin. Planificacin clsica, planificacin reactiva, sistemas combinados, planificacin distribuida.

Categoras de planificacin:

El modelo PGP (Partial Global Planning) aborda el problema de la planificacin distribuida (Lesser, Durfee).Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 43

Comparticin de conocimiento Requisitos para lograr la comparticin y comunicacin de conocimiento: Modelo de representacin del conocimiento comn. incluye lenguaje de representacin de conocimiento comn ( lenguaje de representacin de conocimiento)

Representacin de conocimiento comn ( ontologas) Lenguaje de comunicacin comn ( lenguaje de comunicacin entre agentes) Un esfuerzo en este sentido es el de FIPA (Foundation for Intelligent Physical Abstracts -CE), as como KSE (Knowledge Sharing Effort -ARPA), entre otros.


44

Knowledge Sharing Effort Interlingua: Lenguaje comn para expresar el contenido de una base de conocimiento KIF (Knowledge Ingerchange Formalism). KRSS (Knowledge Representation System Specification): Definicin de estructuras comunes en las familias de lenguajes de representacin SRKB (Shared, Reusable Knowledge Bases): Facilita el consenso sobre contenidos de bases de conocimeinto compartibles (metodologas y herramientas). External Interfaces: Interacciones entre sistemas basados en conocimiento KQML (Knowledge Query and Manipulation Language). http://www.cs.umbc.edu/kse


45

Formalismo de representacin de conocimiento KIF KIF facilita un iterlingua entre bases de conocimiento. Es una versin prefija del clculo de predicados de primer orden, con extensiones de soporte para definiciones y razonamiento no monotnico. Alternativa a lenguajes especializados: STEP, SQL, OQL, SGML, MSEC. existen traductores desde/hacia KIF y los anteriores. Semntica con modelo terico para definir y caracterizar axiomaticamente un vocabulario (objetos, relaciones, funciones). Permite expresar conocimiento sobre funciones y relaciones y sobre conocimiento. Ejemplo:( (transitiva ?r) (=> (holds ?r ?x ?y) (holds ?r ?y ?z) (holds ?r ?x ?z)))


46

Lenguaje de comunicacin de agentes KQML KQML es un lenguaje de comunicacin entre procesos con construcciones de alto nivel. Las primitivas son actos de comunicacin con contenido semntico. bsicas: evaluate, ask-if, ask-one,... de informacin general: tell, achieve, cancel, ... de definicin de capacidades: advertise, subscribe, monitor, import,... de red: register, forward, broadcast, ... ...

KQML no define el formato de la informacin que se enva.


47

KQML (i)

F

subscribe(ask(x))

Ftell(x) tell(x)

ask(x)

Atell(x)

B

A

B

Ejemplo de agente facilitador (F) actuando como monitor de una base de conocimiento.


48

KQML (ii)

broker( ask(x))

F 2tell(x)

advertise( ask(x)) ask(x)

1 A

1 B

4tell(x)

3

Ejemplo de agente facilitador (F) actuando como broker (rutando la informacin)


49

KQML (iii)

recruit( ask(x))

F 2

advertise(ask(x))

1 4 Atell(x)

ask(x)

3 B

Ejemplo de agente facilitador (F) actuando como reclutador (poniendo en contacto)Sistemas basados en Agentes y SMA - (c) Csar Llamas Bello - UVA 50

KQML (iv)(subscribe :content (stream-all: content (PRECIO IBM ?precio)))

pide se tenga al da de los futuros cambios a la consulta(monitor :content (PRECIO IBM ?precio)))

es una abreviatura de lo anterior(advertise :ontology NYSE-TICS :language LPROLOG :content (monitor :content (PRECIO ?x ?y)))

mensaje concerniente a aspectos pragmticos del protocolo del mensaje anterior.


51

Documents

Introduccion a Los Agentes y Sistemas Multiagentes