Download Lógica Computacional y Sistemas Multiagente

Lógica Computacional y Sistemas Multiagente.
Situación actual.
Belén Baldonedo del Río
Curso de Lógica Computacional
Doctorado en Computación - 2006
1
1. Introducción
„
„
„
„
Gran auge de la programación orientada a agentes.
Motivo: adelantos tecnológicos:
„ ordenadores cada vez más rápidos y económicos
„ redes rápidas y fiables
„ creciente expansión de Internet
Nuevas áreas de aplicación (p.e. comercio electrónico)
Nuevos problemas:
„ la integración de grandes cantidades de información.
„ la construcción de software complejo
2
1. Introducción
„
Surgen:
„ numerosos talleres, conferencias y publicaciones
(CLIMA).
„ una red europea de excelencia (AgentLink).
„ una organización internacional para la creación de
estándares en este campo: FIPA (Foundation for
Intelligent Physical Agents).
3
1. Introducción
„
Definición de agente: ente computacional (software o
hardware) que posee las siguientes propiedades :
„ Autonomía: capacidad de actuar sin la intervención de
otros agentes.
„ Reactividad: capacidad para percibir su entorno y
responder a cambios en el mismo.
„ Proactividad: capacidad de exhibir comportamiento
dirigido a cumplir sus objetivos.
4
1. Introducción
„
„
Sistema Multi-Agente (SMA): conjunto de agentes que
cooperan para conseguir sus metas individuales y también
metas conjuntas.
Para que un agente funcione en un SMA debe estar dotado
de un comportamiento social, esto es, debe permitir:
„ Comunicación: enviar/recibir información.
„ Cooperación: negociación con otros agentes para
alcanzar metas individuales o colectivas.
„ Revisión de creencias: actualizar su información
(creencias) mediante información proporcionada por
otros agentes.
5
1. Introducción
„
„
„
La computación basada en agentes está relacionada con
otras áreas de computación como son:
„ ingeniería del software
„ computación distribuida
„ interacción hombre-máquina
„ telecomunicaciones
„ inteligencia artificial (IA)
Dentro de la IA han sido propuestas varias aproximaciones
basadas en lógica.
Dos de ellas son BDI (Belief-Desire-Intention) y Agent0.
6
1. Introducción
„
„
En BDI un agente se caracteriza por lo siguiente:
„ creencias (sobre sí mismo y sobre otros agentes)
„ entorno (donde reside)
„ metas, deseos e intenciones
„ planes (que debe ejecutar)
En Agent0 un agente se caracteriza por sus creencias y
obligaciones (reglas de producción referidas a estados del
entorno en el que opera el agente).
7
1. Introducción
„
„
En estas dos aproximaciones la lógica se usaba para
representar los agentes pero su modelo de ejecución no
está basado en lógica: desfase entre teoría y práctica.
En consecuencia se desarrollaron varias propuestas donde
la lógica computacional (LC) se usa tanto para la
representación del conocimiento como para el modelo de
ejecución.
8
1. Introducción
„
Razones para usar LC en sistemas de agentes y SMAs:
„ Los agentes necesitan “razonar” sobre cambios ocurridos
en el entorno y sobre cómo realizar los cambios
deseados.
„ Su rendimiento puede incrementarse si tienen la
capacidad de aprender.
„ Trabajan en entornos donde la información es
incompleta y hay que elegir entre varias acciones.
„ Necesitan modificar dinámicamente sus creencias y, al
mismo tiempo, realizar pruebas de integridad.
„ En un SMA los agentes necesitan “negociar” para
resolver conflictos.
9
1. Introducción
„
Contribuciones de la LC a los SAs y SMAs:
„ razonamiento temporal
„ razonamiento abductivo
„ razonamiento inductivo
„ razonamiento sobre acciones y planificación
„ razonamiento con prioridades y preferencias
„ revisión de creencias y argumentación
10
1. Introducción
„
Conceptos de la LC que usan las propuestas de SMAs
presentadas:
„ programación lógica extendida
„ programación lógica abductiva y restricciones de
integridad
„ formalismos para razonamiento sobre acciones en el
tiempo:
„
„
„
„
cálculo de eventos
lenguaje A
cálculo de situación
Lenguaje GOLOG (formalizado en lógica de segundo orden e
implementado en Prolog)
11
1. Introducción
„
„
A continuación analizaremos algunas de esas propuestas
desde el punto de vista de la representación del
conocimiento.
También haremos un recorrido por los principales lenguajes
de programación para agentes y SMAs
12
2. Propuestas de agentes
basadas en LC
„
Esta parte se centra en analizar:
„ La forma de representar las creencias, deseos/metas e
intenciones de los agentes.
„ Mecanismos empleados para conseguir en los agentes
reactividad y planificación (esto es, comportamiento
proactivo).
13
2. Propuestas de agentes
basadas en LC
Agentes de Kowalski y Sadri:
Las creencias de los agentes se representan mediante:
„ iff-definiciones: “un agente puede tener un objeto sólo si
lo compra o lo roba”
„ restricciones de integridad: son implicaciones para
expresar reglas de condición-acción, obligaciones,
prohibiciones y metas.
„ observaciones
14
2. Propuestas de agentes
basadas en LC
Agentes de Kowalski y Sadri:
Ejemplos de restricciones de integridad:
„ “Los agentes sin dinero no pueden comprar objetos”
(prohibición).
„ “Cada vez que un agente compre una TV debe conseguir
una licencia de TV” (obligación).
„ “Siempre que un agente que esté robando un objeto y
escuche a la policía llamar a la puerta debe huir” (regla
de condición-acción).
„ Si el objetivo es “tener TV” un posible plan sería “comprar
una TV y conseguir su correspondiente licencia”.
15
2. Propuestas de agentes
basadas en LC
Agentes de Kowalski y Sadri:
Los agentes son reactivos en dos sentidos:
„
reconocen la necesidad de replanificación cuando surgen
nuevas observaciones
„
pueden generar dinámicamente nuevas metas mediante la
activación de restricciones de integridad (además de las
metas iniciales).
16
2. Propuestas de agentes
basadas en LC
Agentes de Kowalski y Sadri: :
Ejemplo:
„ Si un agente recibe una notificación de que no tiene dinero,
el plan anterior quedaría invalidado y deberá replanificar.
„ El único plan posible es robar un TV. Si el agente ejecuta
este plan y observa la presencia de la policía → la regla
condición-acción generará un nuevo objetivo: huir (nueva
meta dinámica).
17
2. Propuestas de agentes
basadas en LC
Agentes de Shanahan:
„ Las creencias de los agentes se representan mediante el
cálculo de eventos (“una puerta dada conecta dos
habitaciones” ).
„ Acciones de dos tipos:
„
primitivas (“atravesar la puerta” )
„
compuestas (“pasar de una habitación a otra”) que
pueden describirse en términos de acciones primitivas
(“atravesar la puerta que conecta una habitación con
la otra”).
18
2. Propuestas de agentes
basadas en LC
Agentes de Shanahan:
„ El cálculo de eventos permite la planificación jerárquica que
genera un plan completo, aunque no toda acción en el plan
tiene que estar totalmente descompuesta en acciones
primitivas.
„ La planificación jerárquica permite la planificación
progresiva donde se van generando primero las acciones
del plan que se realizarán antes.
„ Los agentes de Shanahan (al igual que los de Kowalski y
Sadri) incrementan sus creencias mediante observaciones
del entorno.
„ Son agentes reactivos mediante replanificación.
19
2. Propuestas de agentes
basadas en LC
Agentes de Baral and Gelfond:
„ Las creencias de los agentes se expresan mediante teorías
en lenguaje A junto con una historia de observaciones
pasadas.
„ Las metas de los agentes son propiedades que deben tener
en el futuro.
„ La programación lógica se usa proactivamente para
transformar metas en planes.
„ Son reactivos por replanificación.
20
2. Propuestas de agentes
basadas en LC
Agentes de Pereira y Quaresma:
„ Representan las creencias de los agentes mediante estados
que vienen dados por un programa de lógica extendida
compuesto por:
„
una formulación en programación lógica extendida
del cálculo de eventos
„
un conjunto de reglas y restricciones de integridad
(por ej. que una propiedad y su negación explicita no
pueden ser ciertas al mismo tiempo)
„
un conjunto de reglas que describen la transferencia
de creencias entre agentes y la asimilación de nueva
información.
21
2. Propuestas de agentes
basadas en LC
Agentes de Pereira y Quaresma:
„ Son reactivos: pueden revisar sus creencias en respuesta a
observaciones.
„ Ejemplos de reglas lógicas:
„
un agente ingenuo acepta siempre información nueva
que provenga de otro agente que considere sincero.
„
un agente cauto aceptará nueva información de otro
agente sólo si cree que este es sincero y además la
nueva información no contradice sus propias
creencias.
22
2. Propuestas de agentes
basadas en LC
Vivid Agents:
Se caracterizan por tener:
„
metas
„
creencias (en programación lógica extendida)
„
reglas de reacción (que generalizan reglas de tipo
evento-condición-acción) → comportamiento reactivo
„
reglas de acción (similares a las de reacción pero no
disparadas por eventos, de tipo condición-acción) →
comportamiento proactivo (se usan para generar
planes que permitan alcanzar las metas).
23
2. Propuestas de agentes
basadas en LC
Vivid Agents:
„ Ejemplo de regla de reacción para un agente (en una
aplicación carga y descarga de mercancías):
“si un agente A recibe un mensaje de otro agente B de que B
„
tiene una mercancía que debe ser cargada, entonces el
agente A envía un mensaje de respuesta confirmando la
recepción del mensaje”.
Regla de acción: “si está en una posición y quiere dirigirse
al norte entonces debería dar un paso en dirección norte,
es decir, buscar una posición diferente más cercana a su
objetivo”.
24
2. Propuestas de agentes
basadas en LC
IMPACT:
„ Patrocinado por DARPA.
„ Las creencias se representan mediante programas agente:
“Un tanque T1 está obligado a atacar a otro tanque T2 si el
tanque T1 está obligado a seguir una ruta que está siendo
bloqueada por el tanque T2 y este último pertenece al
enemigo”.
„
Las restricciones de integridad especifican situaciones que
no pueden darse o acciones que no pueden ocurrir al
mismo tiempo: “la velocidad de un tanque no debería
superar la velocidad máxima permitida” o “dos aviones no
pueden volar en la misma ruta en el mismo momento”.
25
2. Propuestas de agentes
basadas en LC
INTERRAP:
„ Usa el cálculo de eventos para razonar sobre el tiempo y las
acciones e incorpora planificación jerárquica
„ Estructura las creencias en tres tipos:
„
modelo del mundo (historia del agente y sus
acciones)
„
modelo mental (teoría del cálculo de eventos)
„
modelo social (creencias sobre otros agentes y cómo
interactuar con ellos)
26
2. Propuestas de agentes
basadas en LC
3APL:
„ Combina programación imperativa y lógica.
„ Los agentes en 3APL son entidades con creencias, metas y
reglas de planificación:
„
Las creencias se especifican mediante sentencias de
un lenguaje lógico (de primer orden).
„
Las metas mediante programas de estilo imperativo
formadas por metas primitivas.
„
Las reglas de planificación se proporcionan en estilo
de reglas de programación lógica con metas
primitivas y compuestas
27
3. Lenguajes de programación
lógica orientados a agentes
Características comunes:
„
„
„
„
multi-threading (múltiples que procesos pueden compartir
el mismo espacio de ejecución).
comunicación inter-thread.
reglas de condición-acción/reacción.
movilidad de código sobre una red de ordenadores
28
3. Lenguajes de programación
lógica orientados a agentes
Qu-Prolog:
„
„
„
„
Lenguaje de programación lógica (extensión de Prolog).
Actualmente se utiliza la versión 7.2.
Inicialmente desarrollado para implementar probadores de
teoremas interactivos.
Adecuado para el desarrollo de aplicaciones de IA tales
como SMA’s.
Contiene todas las características del Prolog estándar más
multi-threading y comunicación inter-thread.
29
3. Lenguajes de programación
lógica orientados a agentes
Qu-Prolog:
„
„
Las creencias de los agentes se recogen en una BD
dinámica que puede ser consultada y modificada por los
procesos agente (agent’s threads) y proporciona un
mecanismo de pizarra para comunicación entre procesos
agente.
Los procesos están provistos de un conjunto de reglas de
reacción que especifican de qué modo deben reaccionar a
los mensajes que reciben.
30
3. Lenguajes de programación
lógica orientados a agentes
Jinni:
„
„
„
„
„
Java INference-engine and Networked Interactor.
Permite integrar, en aplicaciones distribuidas, componentes
de procesamiento de conocimiento, basados en Prolog y
objetos Java.
La coordinación entre los procesos se consigue mediante
pizarras.
Se ha utilizado, por ejemplo, para desarrollar un simulador
del mercado de acciones, con agentes inteligentes
programables por el usuario.
Una de las posibles aplicaciones previstas para Jinni es la
asistencia a clientes de aplicaciones inteligentes como TV
via web, teléfonos móviles, ordenadores para coches.
31
3. Lenguajes de programación
lógica orientados a agentes
Ciao Prolog:
„
„
„
„
Subsumido en ISO-Prolog.
Tiene características para implementar software basado en
agentes.
Soporta threads, actualizaciones atómicas sobre una BD
compartida, objetos y comunicación remota de alto nivel
entre procesos (incluyendo interfaces para BDs locales y
remotas y acceso a WWW).
Genera ejecutables multiplataforma basados en compilación
en bytecode lo cual permite la ejecución dinámica del
código en distintas plataformas.
32
3. Lenguajes de programación
lógica orientados a agentes
Eel:
„
„
„
„
Usa una aproximación basada en eventos para procesar
comunicación .
se basa en un modelo limitado de comunicación que
permite solo comunicación síncrona punto a punto .
No implementa los conceptos de envío y recepción de
mensajes sino que utiliza la unificación de mensajes como
método para el intercambio de información entre procesos
concurrentes.
Sintácticamente es similar a Prolog y comparte la semántica
operacional de Prolog excepto por predicados reservados
especiales para sincronizar la comunicación.
33
3. Lenguajes de programación
lógica orientados a agentes
GAEA:
„ Extensión de Prolog con las siguientes características:
„
módulos y herencia entre ellos
„
multi-proceso (multi-threading)
„
comunicación entre procesos (threads) mediante
memoria compartida que permite la sincronización
entre procesos.
„ Equipado con un entorno de desarrollo (tipo X-window) y
una interfaz de red para entornos multiproceso distribuidos.
„ Los procesos ejecutan un programa lógico en un entorno
dado por un conjunto de módulos. Puede aplicarse herencia
y sobrecarga entre módulos. Se utilizó en entornos tipo
RoboCup.
34
4. CLIMA (Computational Logic in
Multi-Agent Systems)
„
„
„
Conferencia en el campo de la lógica computacional
aplicada a SMA’s.
Se organiza anualmente desde Diciembre de 1999 y en ella
se exponen los avances más recientes de la investigación
en el campo de la lógica computacional aplicada a agentes
y SMA’s.
La última conferencia celebrada es CLIMA VII (Mayo-2006,
Japón).
35
4. CLIMA (Computational Logic in
Multi-Agent Systems)
Objetivos:
„ Promover el uso de la Lógica Computacional (LC) en SMAs
donde la LC proporciona un marco de trabajo bien-definido,
general y riguroso para el estudio de la sintaxis, semántica
y procedimientos, aportando implementaciones, entornos,
herramientas y estándares, y permitiendo la especificación
y verificación de propiedades, tanto para agentes
individuales como para SMAs.
„ Discutir y confrontar diferentes técnicas y aproximaciones
basadas en lógica computacional para representación,
programación e implementación de razonamiento en
agentes y SMAs y presentar el estado actual de la
investigación en este campo difundiendo los avances más
recientes entre investigadores y estudiantes.
36
4. CLIMA (Computational Logic in
Multi-Agent Systems)
CLIMA Contest:
„ Competición creada en la anterior edición, CLIMA VI (Junio2005, Londres).
„ Busca estimular la investigación en el área de SMAs pero
siempre haciendo hincapié en el uso de la LC.
„ Trata de establecer un escenario para agentes lo
suficientemente genérico para poder aplicar un amplio
rango de técnicas de lógica computacional pero
suficientemente preciso para poder comparar diferentes
aproximaciones entre sí.
37
4. CLIMA (Computational Logic in
Multi-Agent Systems)
CLIMA Contest VI: Escenario propuesto
„ Se trata de una rejilla donde los agentes pueden moverse a
una casilla vecina si no hay un agente en esa rejilla.
„ Puede aparecer comida en todas las casillas excepto en una
casilla depósito en la cual los agentes pueden dejar su
comida.
„ Un agente puede observar si hay comida en la casilla que
está visitando. Inicialmente la comida puede situarse en
algunas casillas seleccionadas aleatoriamente. Durante la
ejecución puede aparecer comida en casillas adicionales
seleccionadas aleatoriamente excepto en la casilla depósito.
„ Los agentes pueden interpretar diferentes papeles (como
explorador o colector), comunicarse y cooperar para
encontrar y recoger comida de modo eficiente y efectivo.
38
4. CLIMA (Computational Logic in
Multi-Agent Systems)
CLIMA Contest VI: Ganadores (execuo)
„
Simon Coffey and Dorian Gaertner, del Imperial College
London, UK con la propuesta “Implementing PheromoneBased, Negotiating Forager Agents” que describe una
implementación de agentes distribuidos de tipo BDI, que
cooperan eficientemente en el escenario propuesto.
„
Carlos Cares, Xavier Franch and Enric Mayol, de la
Universitat Politècnica de Catalunya, Barcelona, España, y
Universidad de la Frontera, Temuco, Chile con la
propuesta “Extending Tropos for a Prolog
Implementation: A Case Study Using the Food Collecting
Agent Problem” donde trasladan una metodología
orientada al diseño de agentes (Tropos) a una
implementación en LC (en Prolog).
39
4. CLIMA (Computational Logic in
Multi-Agent Systems)
CLIMA Contest VII: Escenario propuesto
„ Se trata de simular dos equipos de buscadores de oro que
se encuentran explorando la misma zona capaces de
esquivar obstáculos (árboles y arbustos) y que deben
competir por las pepitas de oro diseminadas por un bosque.
„ Los mineros de cada equipo deben coordinar sus acciones
para recoger tanto oro como sea posible y entregarlo al
agente situado en un depósito donde se guarda el oro.
40
5. Bibliografía consultada
„
„
„
„
„
“Computational Logic and Multi-Agent Systems: A
roadmap”. Fariba sadri, Francesca Toni. Department of
Computing. Imperial College, UK. 1999.
“An introduction to Multiagent Systems”. Michael
Wooldrige. 2001. Ed. Wiley.
Home page de CLIMA: http://clima.deis.unibo.it/
Página del CLIMA Contest VII:
http://cig.in.tu-clausthal.de/index.php?id=clima7contest
Página de Dorian Gaertner (ganador del CLIMA Contest VI):
http://tweetypie.doc.ic.ac.uk/~dg00/twiki/bin/view/Publicati
ons/WebHome
41