Agentes Físicos Dinámicos Josep Lluís de la Rosa i Esteva Institut d’Informàtica i Aplicacions Universitat de Girona peplluis@eia.udg.es

Orígenes de la Investigación

• Consensus (1993) 
• Supervisión de controladores (1990) 
• CASSD (1998) 
• Diseño de agentes con un equipo robótico FIRA y RoboCup (1996) 
• Situación actual de la investigación 

 

Consensus

• Se toman las decisiones/opiniones de varias fuentes de conocimiento.  También la certeza de dichas opiniones.
• Finalmente toma una decisión consensuada en función de dichas opiniones pero teniendo en cuenta una información a priori que sirve de filtro de la certeza de cada fuente de conocimiento.
• Dicha información a priori se le llama “visión del mundo cooperativo” y consiste en parámetros del tipo “confianza” en la fuente de conocimiento.

Consensus (características)
 

• La principal ventaja del consensus (o fusión sensorial según el área de investigación) es la mejora de la decisión al poder combinar de forma redundante varias opiniones provinientes de diversas fuentes de conocimiento y/o información

• En consecuencia los sistemas de control basados en consensus suelen dar mejor rendimiento.
• El inconveniente reside en no existir un método de cómo asignar los parámetros de confianza.

Supervisión de controladores

Hay precedentes de supervisabilidad:

Cómo aprovechar al máximo las prestaciones de los controladores, una vez diseñados? (Optimización, gain scheduling del área de control de procesos químicos?).

Cómo hacer axiomática de supervisabilidad similar a la controlabilidad (SAMAAN 1989)?

Problemas:

• El conocimiento que se requiere sobre los controladores supervisados es demasiado específico: falta de generalidad en los supervisores.
• La teoría de supervisabilidad no es aún práctica

CASSD

“Computer Aided Supervisory Systems Design”

Su objetivo:

• Proveer a los ingenieros de control con herramientas de ayuda para que diseñen supervisores.
• El enfoque no es metodológico pero ayuda.  El ingeniero cuando “aun se acuerda” cómo diseñó el controlador codifica su conocimiento en un supervisor que rendibilizará al máximo dicho controlador
• Encapsular dicho conocimiento en objetos y abstractores

Problemas

La supervisión local de cada controlador se ha de combinar con la supervisión global.

Los sistemas complejos dispondrán de numerosos pequeños supervisores de controladores.

Posible solución

• Introducir diseño de agentes para solucionar el problema de los numerosos supervisores.

Toolboxes de supervisión

Diseño de Agentes con Robots

El curso de doctorado “IA Distribuida” del bienio 1994-96 yo buscaba un ejemplo adecuado que justificase el uso de agentes cooperantes.

En dicho año se inició los primeros mundiales de la FIRA y Robocup.  En Julio de 1996 construimos el primer equipo de fútbol robótico de la UdG.

Los agentes controlaban cada robot y debían jugar de forma cooperativa en competición contra otros agentes (el equipo contrario).

En el año 1999-2000 somos el único equipo Europeo que ha participado en todos los mundiales y hacemos investigación en dicha plataforma de investigación.

Motivación internacional de la investigación

Los retos de la IA

• Toy problems: el ajedrez entre otros juegos fue utilizado por la IA como benchmarks. Son ejemplos demasiado senzillos que no son extrapolables a problemas reales con suficientes garantías.
• En 1997 Gary Kasparov fue vencido por Deep-Blue: formalmente el ajedrez está superado y la comunidad científica de IA busca otros testbeds.
• Hacer una IA práctica que se pueda aplicar a problemas generales. Se propone la “embedded AI” que requiere de la integración de múltiples paradigmas

Los eternos problemas de la IA

• Se ha de evitar el toy problem: se necesitan testbeds adecuados.
• Se ha de conseguir la integración de múltiples paradigmas: uso de agentes inteligentes.
• Se ha de poder aplicar a problemas reales con interacciones con un entorn físico: uso de agentes SITUADOS, y agentes FÍSICOS.  La percepción de los agentes toma mucha importancia en la IA.

Los agentes inteligentes disponen de un origen múltiple

• Objetos: Hewitt 1977
• Arquitecturas: Smith 1980
• Lógica: BDI (Belief, Desire, Intention): Rao 1987
• Muchos otros: Jennings, Wooldridge, Kohen, Kitano, Steels, etc.

La FIRA y RoboCup

• Proponen el fútbol robótico como el nuevo testbed.
• Reto: conseguir el 2050 que un equipo de robots ganen al mejor equipo humano de futbol en un partido.
• Retos a más corto plazo: agentes físicos.
• Alan Mackworth propuso el futbol robótico en 1992.
• Hiroaki Kitano anunció RoboCup en 1995.
• Jong Hwan Kim anunció MIROSOT en 1996.
• Actualmente hay más de 100 instituciones que participan en dichos eventos.

Particularidades de RoboCup

• 120 instituciones participantes
• Es el mayor y mejor evento científico usando robots.
• Se definen challenges a corto,medio y largo plazo
• 1996: se inició el primer mundial MIROSOT y RoboCup
• Se definen benchmarks para evaluar los equipos aparte de la competición.
• 1999: se introduce preliminares, workshop, finales y postworkshop.
• El 2002 se organizará en Japón y Corea.

La experiencia en CASSD, consensus y diseño de robots motiva:

• El construir herramientas de ayuda para los ingenieros de control para que puedan diseñar agentes que controlen un cuerpo físico. Dichos agentes encapsulan los supervisores y controladores. Cada agente conocerá por INTROSPECCIÓN las características físicas (dinámicas) que rigen su cuerpo físico (AGENTES FÍSICOS).
• DECLARAR el conocimiento disponible sobre las especificaciones de cada controlador (si están disponibles) cuando el ingeniero aún se acuerda cómo lo diseñó y sintetizó.
• DECLARAR el conocimiento que el ingeniero dispone sobre la supervisabilidad del sistema para ayudar al agente a decidir.
• El agente decidirá con dicho conocimiento INTROSPECTIVO y con las opiniones de otros agentes físicos con los que colabora. Se debe DECLARAR el conocimiento sobre el mundo cooperativo.

Supervisión y Diseño de Agentes

Que son agentes?

• Un agente se caracteriza por ser proactivo y disponer de percepción del mundo real (environment) y del mundo cooperativo en forma de creencias.
• La arquitectura, lenguaje y ontologías de agentes están por madurar.
• Predominan los enfoques software.  Como aplicar agentes físicos?

Conjetura de Bozzo

• La Inteligencia Artificial robusta (fiable) emergerá en la Internet antes que emerja dentro de un único ordenador (stand alone computer) o robot que se haya creado por una persona, compañía o organización.

Que son AgentesFísicos?

Según [Asada 97]

• Las capacidades sensoriales y las de actuación están altamente ligadas.
• Para el agente ejecutar las tareas encomendadas, los espacios sensoriales y de actuación deben ser abstraídos dentro de los recursos del agente (memoria, potencia de proceso, controladores, etc.).
• Dicha abstracción depende de las interacciones del agente con el entorno.
• Fruto de la abstracción, cada agente tiene un modelo de representación del entorno.
• En el mundo real, tanto las interacciones inter-agentes como agentes-entorno son asíncronas, paralelas y arbitrariamente complejas.  Los agentes físicos evolucionan de forma continuada a tiempo continuo.
• La complejidad natural de las interacciones físicas genera distribuciones fiables de datos para los algoritmos de aprendizaje de los agentes físicos, en comparación a los agentes software.

Retos de los agentes físicos

• Percepción.  Los agentes físicos deben tener capacidad de usar percepción de amplio rango, discriminar otros agentes físicos, estimar sus posiciones y la suya propia, entre otras.  La percepción es una aplicación básica que se extiende en las aplicaciones robóticas.
• Acciones.  El agente físico ha de ser capaz de controlar su cuerpo físico.  En el caso de robots móviles, ha de ser capaz de ejecutar trayectorias, seguir objetivos, los cuales no han de ser necesariamente estáticos.
• Situación y comportamiento.  Aunque las tareas a realizar sean simples, casi infinitas situaciones aparecen debido a los continuados cambios del entorno, como por ejemplo los objetivos móviles, que otros agentes físicos se desplacen en el mismo entorno, etc.
• Tiempo real.  Como que la situación cambia continuamente, hay restricciones de tiempo en la toma de nuevas decisiones, re-planificación de trayectorias, y adecuación de los controles.
• Plataforma.  Qué plataforma de experimentación de los agentes físicos facilita su investigación internacional e interdisciplinaria?

Agentes Físicos Regidos por Dinámica

• Un agente ha de ser SITUADO: la percepción es importante. La percepción que dispone del mundo físico la proporciona el sistema de supervisión, que encapsula la información de los controladores, quienes encapsulan la DINÁMICA que rige el cuerpo físico del sistema controlado.
• Para evitar el toy problem se puede emplear los robots móviles diseñados para RoboCup: el agente debe percibir la dinàmica de su cuerpo físico.  Este hecho se llamará INTROSPECCIÓN.
• Utilizaremos un lenguaje agente AGENT0 [Shoham 93] para interpretar la introspección: las CAPACIDADES.

Agentes Físicos Regidos por DinámicaEstado del Arte

• La robótica móvil hace años (desde 1990 según el LAAS) que aparentemente ha abandonado los estudios de la dinámica de robots móviles (salvo excepciones).
• Sólamente [Mackworth 1993] considera esencial el estudio de la dinámica de los cuerpos físicos para ver su impacto emergente en el mundo cooperativo: “la dinámica de la inteligencia” (aún sin resultados).
• Hay trabajos como [Hogg 1991] sobre la dinámica de ecosistemas de agentes, aunque sólo se ciernen a la dinámica de poblaciones respecto a la acción de elección de fuentes de conocimiento, y no a la emergencia de la dinámica de los cuerpos físicos.
• Otros trabajos son aproximaciones estáticas o probabilistas [Muller 1994].  Parece que [Ollero 1999] trabaja con la dinámica pero no contempla la inclusión de agentes prefiriendo enfoques centralizados.

Cómo superar el estado del arte?

• Supervisabilidad: continuar el trabajo de [Samaan 1989]. Declarar conocimiento de especificaciones de control?
• Agentificabilidad: algoritmos híbridos? Uso de los trabajos de Berkeley
• Introspección: capacidades según el lenguaje AGENT0.  Uso del CBR?
• Decisiones cooperativas: consensus + incerteza.  Agentes situados, donde la percepción requiere de la representación de la incertidumbre. Uso de los trabajos previos de [de la Rosa 1993] y [Torra 1994].
• Adaptación de las decisiones cooperativas
• Estabilizando la dinámica de poblaciones: [Hogg 1991]
• Según los principios de autoorganización de las poblaciones de agentes, refinando su introspección? CBR + genéticos? Colaboración con la CMU.

Ejemplos ilustrativos

• Convoy ->  justificar los agentes físicos desde el punto de vista de incorporar el conocimiento de la dinámica y de los controladores. Idea preliminar de la supervisabilidad. (Coche y avión del futuro).
• Containers -> justificar el uso de agentes desde el punto de vista de la complejidad algorítmica.
• Transporte de equipos -> justificar el uso de supervisores híbridos.
• Exploración de mapas submarinos -> justificar el consensus.
• Pases en el testbed de fútbol robótico -> trabajo cooperativo equivalente al convoy pero en un ejemplo contrastable en RoboCup.
• Ecosistemas de agentes físicos -> justificar el consensus y estabilidad de los agentes físicos.  Aplicación a un péndulo invertido. Como consecuencia: comercio electrónico (servicio de pizzas) ? justificar el estudio de la estabilidad de ecosistemas de agentes, que emerge de la estabilidad de los agentes físicos dinámicos.

Convoy

• Tenemos dos agentes físicos A y B.  Cada uno dispone de una dinámica diferenciada tal como describe la siguiente gráfica

• El agente B sigue al agente A, tratando de mantener una distancia D como consigna.
• La estructura de control es la siguiente:

• En una frenada de por ejemplo de 4m/s a 0m/s del líder A, el agente físico B responderá con la siguiente dinámica:

• Si tenemos sólo en cuenta la estática podremos colocar el agente a una distancia de 5m , pero las oscilaciones que se producen vaticinan un choque.

Soluciones:

• Solución ESTÁTICA: aumentar la distancia de seguridad D a 6m.
• Solución DINÁMICA: Que los agentes negocien las condiciones de frenada en función de este conocimiento dinámico.

 

Agente 1 Decelera: 0.0, 0.3   No Decelera: 0.0, 0.6 Sí: adelante!

Agente 2 0.0, 0.3, 0.527633 0.0, 0.6, 0.77687

Negotiation Algorithm

1. Agent A decides to change the speed and sends a request message to Agent B as follows:

request ( agent_A, agent_B, initial_speed, final_speed, time);

2. Agent B receives the message and looks in it base of capacities, for one that fulfil the requirements.

IF CAPACITY exists
  THEN
     inform ( Agent_B, Agent_A, final_speed, certainty);
 ELSE
      inform ( Agent_B, Agent_A, final_speed, 0.0);
END

3. Agent A receives the answer:

IF certainty > threshold
 THEN
         inform ( Agent_A, Agent_B, DO_ACTION);
Agent B starts to do the action.
 do (agent_A, final_speed, controller_parameters);
  ELSE

4. Agent A looks in its base of capacities for one where the final and initial speeds match with the requirements, but using another controller, so the specified time changes.

  IF CAPACITY exists
  THEN
       request ( Agent_A, Agent_B, final_speed,time);

5. The algorithm goes to step 2.

  ELSE
     inform ( Agent_B, Agent_A,DO_NOT_ACTION);

6. End of the negotiation.

END

Aquí tenemos la tabla de capacidades sobre las que hemos basado este razonamiento

• Aquí están algunos resultados experimentales.  Se puede apreciar que la decisión deliberativa es mejor que la reactiva.  La cooperación con introspección promete buenos resultados.

Transporte de Containers

• Veremos que lautilidad del uso de agentes también se puede argumentar desde el punto de vista de la complejidad temporal
• Ejemplo: transporte de containers dentro de un gran puerto [Alami 1998].

• Se debe optimizar la función FitFunction, que mide la “urgencia” asociada en la entrega de contenidores a su destino.
• El procedimiento de decisión LOCAL de cada agente es:

Conjunto de posiciones     A={(x, y) | x? [1...MaxX], y? [1...MaxY]} Conjunto de contenedores         C={c1, c2,..., cn} Posición          pi = (pxi , pyi )? A Destinación         di = (dxi , dyi )? A  Deadline         t? R Velocidad        vi ? R

procedure Simulation(var Sim:Simulation); begin Initialize(Sim); repeat      for each robot r in Sim.Robots do          begin            ChooseDirection(Sim,r);           // Recoger y entregar containers           DoThings (Sim,r); end; until finished (Sim); end;

• Este problema es más general que el problema del viajante:
• Según Gruska J.,“Foundations of Computing” Thomps on Computer Press 1997
• El viajante debe recorrer todas las ciudades al menos una vez con la menor distancia de recorrido posible.  Su complejidad es de n!, donde n es el número de ciudades a recorrer.  Es un problema NP-Hard, lo que significa que no hay algoritmo de tiempo polinomial que lo resuelva.
• Introducimos que el viajante no tenga que volver a casa una vez visitadas todas las ciudades ? el problema sigue siendo NP-Hard.

• Introducimos estas restricciones  para reducirlo al problema anterior:
• Si consideramos que los contenedores se deben entregar al mismo lugar donde se encuentran localizados.
• Si sólamente hay un robot  que se mueve a velocidad 1y su posición inicial es la de unos de los contenedores.
• Si todos los contenedores tienen la misma deadline D.

• Entonces cada ejemplo del problema de los contenidores subsume la complejidad del problema del viajante de comercio -> es también problema NP-Hard.

• A pesar de ser de complejidad n!, cuando se aplicala decisión local el tiempo de resolución es comparable a n2.
• Entonces existe solución de complejidad polinómica, aunque no la solución será subóptima. Esta solución está basada en decisión local.
• Para conseguir el óptimo se debe combinar la decisión local con algoritmos de optimización estocásticos o evolucionarios que garantizan (de forma probabilista) el óptimo.

• USAR AGENTES SOLUCIONA PROBLEMAS INTRATABLES.

• Se puede modificar las interacciones de los agentes modificando su visión del mundo cooperativo.

Transporte de Equipos

• Hemos de transportar equipos hacia un almacén.  Un solo agente no puede transportarlos y requiere de la ayuda de otros.

• Desde el punto de la dinámica, un robot ha de saber si puede o no empujar la mesa sólo.  Para ello es posible que la aplicación de algoritmos de supervisión híbrida resuelva la representación de estados discretos guiados por eventos y pueda saber qué controladores aplicar.

• Hemos de implementar la siguiente cooperación:

El lenguaje agente para la cooperación es el de [Shoham93]

• Tiempo: lenguaje temporal puntual lineal (discreto, muestreado)
• Acción: instantánea
• Creencia: en el tiempo t el agente a cree en la frase j (definida recursivamente).
• Ejemplo:          : El agente a cree en el tiempo 3, que el agente b cree en el tiempo 10 que al agente a le gusta el agente b en el tiempo 7.
• Obligación: en el tiempo t el agente está obligado al agente b sobre j.
• Decisión (elección): Es una noción de libertad: está definido como una obligación consigo mismo.
• Capacidad: en el tiempo t el agente a es capaz de j.
• Ejemplo:           : El robot sabe en el tiempo 5 que puede abrir la puerta en el tiempo 8.
• La versión inmediata de CAN es ABLE y la diferencia reside en que ABLE  es al mismo tiempo, por ejemplo:
•  El robot sabe en el tiempo 5 que puede abrir la puerta en el mismo tiempo 5.

Características del lenguaje orientado a agentes AGENT0

• Consistencia Interna: las creencias y obligaciones son internamente consistentes. No hay contradicciones entre ellas.
• Buena Voluntad: los agentes se comprometen a hacer sólo lo que se creen capaces de.
• Introspección.
• Persistencia del estado mental

El lenguaje puede ser ejecutado con el siguiente intérprete de agentes

Condiciones

hay_mesa()
Tengo_mesa()
Tengo_compañero()
Estoy_en_el_almacén()

Acciones

buscar_mesa
transportar_mesa
entregar_mesa

agent name a1

initial beliefs
     beliefs that hay_mesa at 0
     beliefs that not Tengo_mesa(a1) at 0
     beliefs that not Tengo_compañero(a1) at 0

capabilities
    can do buscar_mesaif beliefs that not Tengo_mesa(a1) at T
    can do transportar_mesaif beliefs that Tengo_compañero(a1) at T
    can do entregar_mesa if beliefs that Estoy_en_el_almacén(a1) at T

commitment rule 1
        message conditions
                informed by A that not Tengo_compañero(A) at T
        mental conditions
                beliefs that not Tengo_compañero(a1) at T and differents(A,a1)
        actions  in time T
                        inform A that Tengo_compañero(A) at T and
                        inform a1 that Tengo_compañero(a1) at T
commitment rule 2
        message conditions
                true
        mental conditions
                beliefs that hay_mesa at T and
                beliefs that not Tengo_mesa(a1) at T
        actions  in time T
                        do buscar_mesa and
                        inform everybody that Tengo_mesa(a1) at T

commitment rule 3
        message conditions
                true
        mental conditions
                beliefs that Tengo_mesa(a1) at T and
                beliefs that not Tengo_compañero(a1) at T
        actions  in time T
                 inform others that not Tengo_compañero(a1) at T
commitment rule 4
        message conditions
                true
        mental conditions
                beliefs that Tengo_compañero(a1) at T
        actions
                in time T do transportar_mesa and
                inform a1 that not Tengo_compañero(a1) at T and
                inform a1 that not Tengo_mesa(a1) at  T
end a1

Traza de ejecución

| ?- reset_time.
yes
| ?- cycle.
Asserting  cmt(a1,a1,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a1))))
Retracting  cmt(a1,a1,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a1))))
Asserting  m(a1,a1,inform(fact(0,Tengo_mesa(a1))))
Asserting  m(a2,a1,inform(fact(0,Tengo_mesa(a1))))
Asserting  m(a3,a1,inform(fact(0,Tengo_mesa(a1))))

Asserting  b(a2,fact(0,Tengo_mesa(a1)))
Asserting  cmt(a2,a2,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a2))))
Retracting  m(a2,a1,inform(fact(0,Tengo_mesa(a1))))
Retracting  cmt(a2,a2,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a2))))
Asserting  m(a1,a2,inform(fact(0,Tengo_mesa(a2))))
Asserting  m(a2,a2,inform(fact(0,Tengo_mesa(a2))))
Asserting  m(a3,a2,inform(fact(0,Tengo_mesa(a2))))

Asserting  b(a3,fact(0,Tengo_mesa(a1)))
Asserting  b(a3,fact(0,Tengo_mesa(a2)))
Asserting  cmt(a3,a3,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a3))))
Retracting  m(a3,a1,inform(fact(0,Tengo_mesa(a1))))
Retracting  m(a3,a2,inform(fact(0,Tengo_mesa(a2))))
Retracting  cmt(a3,a3,0,do(fetch_table) and inform(everybody,fact(0,Tengo_mesa(a3))))
Asserting  m(a1,a3,inform(fact(0,Tengo_mesa(a3))))
Asserting  m(a2,a3,inform(fact(0,Tengo_mesa(a3))))
Asserting  m(a3,a3,inform(fact(0,Tengo_mesa(a3))))
yes

| ?- cycle.
Retracting  b(a1,fact(0,not Tengo_mesa(a1)))
Asserting  b(a1,fact(0,Tengo_mesa(a1)))
Asserting  b(a1,fact(0,Tengo_mesa(a2)))
Asserting  b(a1,fact(0,Tengo_mesa(a3)))
Asserting  cmt(a1,a1,0,inform(others,fact(0,not Tengo_compañero(a1))))
Retracting  m(a1,a1,inform(fact(0,Tengo_mesa(a1))))
Retracting  m(a1,a2,inform(fact(0,Tengo_mesa(a2))))
Retracting  m(a1,a3,inform(fact(0,Tengo_mesa(a3))))
Retracting  cmt(a1,a1,0,inform(others,fact(0,not Tengo_compañero(a1))))
Asserting  m(a2,a1,inform(fact(0,not Tengo_compañero(a1))))
Asserting  m(a3,a1,inform(fact(0,not Tengo_compañero(a1))))

Retracting  b(a2,fact(0,not Tengo_mesa(a2)))
Asserting  b(a2,fact(0,Tengo_mesa(a2)))
Asserting  b(a2,fact(0,Tengo_mesa(a3)))
Asserting  b(a2,fact(0,not Tengo_compañero(a1)))
Asserting  cmt(a2,a2,0,inform(a1,fact(0,Tengo_compañero(a1))) and inform(a2,fact(0,Tengo_compañero(a2))))
Asserting  cmt(a2,a2,0,inform(others,fact(0,not Tengo_compañero(a2))))
Retracting  m(a2,a2,inform(fact(0,Tengo_mesa(a2))))
Retracting  m(a2,a3,inform(fact(0,Tengo_mesa(a3))))
Retracting  m(a2,a1,inform(fact(0,not Tengo_compañero(a1))))
Retracting  cmt(a2,a2,0,inform(a1,fact(0,Tengo_compañero(a1))) and inform(a2,fact(0,Tengo_compañero(a2))))
Asserting  m(a1,a2,inform(fact(0,Tengo_compañero(a1))))
Asserting  m(a2,a2,inform(fact(0,Tengo_compañero(a2))))
Retracting  cmt(a2,a2,0,inform(others,fact(0,not Tengo_compañero(a2))))
Asserting  m(a1,a2,inform(fact(0,not Tengo_compañero(a2))))
Asserting  m(a3,a2,inform(fact(0,not Tengo_compañero(a2))))
Retracting  b(a3,fact(0,not Tengo_mesa(a3)))
Asserting  b(a3,fact(0,Tengo_mesa(a3)))
Asserting  b(a3,fact(0,not Tengo_compañero(a1)))
Asserting  b(a3,fact(0,not Tengo_compañero(a2)))
Asserting  cmt(a3,a3,0,inform(a1,fact(0,Tengo_compañero(a1))) and inform(a3,fact(0,Tengo_compañero(a3))))
Asserting  cmt(a3,a3,0,inform(a2,fact(0,Tengo_compañero(a2))) and inform(a3,fact(0,Tengo_compañero(a3))))
Asserting  cmt(a3,a3,0,inform(others,fact(0,not Tengo_compañero(a3))))
Retracting  m(a3,a3,inform(fact(0,Tengo_mesa(a3))))
Retracting  m(a3,a1,inform(fact(0,not Tengo_compañero(a1))))
Retracting  m(a3,a2,inform(fact(0,not Tengo_compañero(a2))))
Retracting  cmt(a3,a3,0,inform(a1,fact(0,Tengo_compañero(a1))) and inform(a3,fact(0,Tengo_compañero(a3))))
Asserting  m(a1,a3,inform(fact(0,Tengo_compañero(a1))))
Asserting  m(a3,a3,inform(fact(0,Tengo_compañero(a3))))
Retracting  cmt(a3,a3,0,inform(a2,fact(0,Tengo_compañero(a2))) and inform(a3,fact(0,Tengo_compañero(a3))))
Asserting  m(a2,a3,inform(fact(0,Tengo_compañero(a2))))
Asserting  m(a3,a3,inform(fact(0,Tengo_compañero(a3))))
Retracting  cmt(a3,a3,0,inform(others,fact(0,not Tengo_compañero(a3))))
Asserting  m(a1,a3,inform(fact(0,not Tengo_compañero(a3))))
Asserting  m(a2,a3,inform(fact(0,not Tengo_compañero(a3))))
yes

| ?- cycle.
Retracting  b(a1,fact(0,not Tengo_compañero(a1)))
Asserting  b(a1,fact(0,Tengo_compañero(a1)))
Asserting  b(a1,fact(0,not Tengo_compañero(a2)))
Asserting  b(a1,fact(0,not Tengo_compañero(a3)))
Asserting  cmt(a1,a1,0,do(transportar_mesa) and inform(a1,fact(0,not Tengo_compañero(a1))) and inform(a1,fact(0,not Tengo_mesa(a1))))
Retracting  m(a1,a2,inform(fact(0,Tengo_compañero(a1))))
Retracting  m(a1,a2,inform(fact(0,not Tengo_compañero(a2))))
Retracting  m(a1,a3,inform(fact(0,Tengo_compañero(a1))))
Retracting  m(a1,a3,inform(fact(0,not Tengo_compañero(a3))))
Retracting  cmt(a1,a1,0,do(transportar_mesa) and inform(a1,fact(0,not Tengo_compañero(a1))) and inform(a1,fact(0,not Tengo_mesa(a1))))
Asserting  m(a1,a1,inform(fact(0,not Tengo_compañero(a1))))
Asserting  m(a1,a1,inform(fact(0,not Tengo_mesa(a1))))

Retracting  b(a2,fact(0,not Tengo_compañero(a2)))
Asserting  b(a2,fact(0,Tengo_compañero(a2)))
Asserting  b(a2,fact(0,not Tengo_compañero(a3)))
Asserting  cmt(a2,a2,0,do(transportar_mesa) and inform(a2,fact(0,not Tengo_compañero(a2))) and inform(a2,fact(0,not Tengo_mesa(a2))))
Retracting  m(a2,a2,inform(fact(0,Tengo_compañero(a2))))
Retracting  m(a2,a3,inform(fact(0,Tengo_compañero(a2))))
Retracting  m(a2,a3,inform(fact(0,not Tengo_compañero(a3))))
Retracting  cmt(a2,a2,0,do(transportar_mesa) and inform(a2,fact(0,not Tengo_compañero(a2))) and inform(a2,fact(0,not Tengo_mesa(a2))))
Asserting  m(a2,a2,inform(fact(0,not Tengo_compañero(a2))))
Asserting  m(a2,a2,inform(fact(0,not Tengo_mesa(a2))))

Retracting  b(a3,fact(0,not Tengo_compañero(a3)))
Asserting  b(a3,fact(0,Tengo_compañero(a3)))
Asserting  cmt(a3,a3,0,do(transportar_mesa) and inform(a3,fact(0,not Tengo_compañero(a3))) and inform(a3,fact(0,not Tengo_mesa(a3))))
Retracting  m(a3,a3,inform(fact(0,Tengo_compañero(a3))))
Retracting  m(a3,a3,inform(fact(0,Tengo_compañero(a3))))
Retracting  cmt(a3,a3,0,do(transportar_mesa) and inform(a3,fact(0,not Tengo_compañero(a3))) and inform(a3,fact(0,not Tengo_mesa(a3))))
Asserting  m(a3,a3,inform(fact(0,not Tengo_compañero(a3))))
Asserting  m(a3,a3,inform(fact(0,not Tengo_mesa(a3))))
yes

Poder o no poder

• Se trata que los agentes puedan aceptar los retos basando sus capacidades en un conociento de su cuerpo físico y de los controladores que tengan implementados

Autómatas híbridos

Sistemas híbridos
Un sistema dinámico híbrido que llamaremos Automata Híbrido, H, es una colección (X,U,Y,I,f,E,h), donde:

Un automata híbrido permite representar un sistema continuo con diferentes fases.
 

f: determina la evolución del estado continuo
E: evolución discreta del estado
h: determina la evolución de la salida

Poder o no poder: capacidades observadas de los supervisores híbridos

• El movimiento coordinado requiere de controladores específicos que ambos agentes físicos deben conoceer

Supervisabilidad y Supervisores híbridos

Conclusiones de los ejemplos de Convoy y Transporte de Equipos:

• El poder explicitar conocimiento físico en forma de capacidades para el agente físico conduce a mejor rendimiento de las deciciones (? consignas) tomadas.
• En el ejemplo del convoy el agente físico usaba el conocimiento dinámico de los controladores que disponía, seleccionaba uno y planteaba al otro agente lo que podía o no hacer.
• En el ejemplo de la mesa el agente físico intenta hacer lo mismo, pero al haber TANTO CONTROLADORES necesita de un supervisor que le seleccione los controladores sobre los cuales entablar el protocolo de decisión -> los supervisores híbridos parecen una buena solución para dicha tarea pues incorporan condiciones y eventos, importantes para saber qué controlador aplicar.

Exploración de Fondos Submarino
 

• Vemos como el conocimiento sobre la dinámica de los agentes físicos implementados como submarinos és útil para crear mapas

• Los submarinos tienen problemas de localización absoluta.
• Cada submarino dispone de su controlador.
• Con dicho controlador se puede crear un “software-sensor”.

• Cada submarino construye su mapa.  La falta de fiabilidad en la localización absoluta genera mapas diferentes de la realidad.
• Por qué? Esta imprecisión o incerteza es debida al sensor soft:
• Deriva: típico problema igual al de odometria de robots móviles.
• El controlador se queda obsoleto ante cambios frecuentes de la dinámicadel robot submarino.  Por tanto también el sensor soft.

Mapa original                                                                                        Mapa generado
 

• La calidad del mapa depende de la calidad del software sensor.
• Se puede consensuar cada mapa combinando las propuestas de varios robots submarinos.
• Cuanto más conocimiento tenga el agente físico sobre su cuerpo físico (la calidad de su software sensor) mejor será el mapa consensuado.

• Dicho conocimiento sobre la dinámica ha permitido mejores mapas (más fidedignos).

Pases en el Fútbol Robótico

• Vemos como con el fútbol robótico se pueden representar los problemas anteriores, especialmente el convoy.

• Dos robots deben cooperar pasandose la pelota.  El robot pasador sería equivalente al robot A del ejemplo del convoy y el recibidor sería el robot B, quien debe adecuar su comportamiento físico a ladinámica de la pelota y el pasador

• Entrenamos con redes neuronales los pases y finalmente se implementan en los robots reales. Esta solución es como la CMU  [Veloso 1997].

• Cada controlador tiene especificaciones. Cada robot sabe si puede o no llegar al pase. Con dicho conocimiento negocia las condiciones del pase con el robot pasador.

• La cooperación entre los robots para hacer un pase correcto, basándose en la dinámica debe mejorar los resultados enfrente al simple “chutar pelota y esperar que el otro robot la capture”

Ecosistemas de Agentes

• El futuro depara que haya agentes software y físicos en una “sopa de agentes”.  Evolucionamos hacia el comercio electrónico, donde los agentes físicos serán útiles en el comercio electrónico del sector productivo.

• Estabilidad de ecosistemas de agentes [Hogg 1991]
• Cada agente elige la información de una fuente de información o conocimiento.  Si dicha información/conocimiento le produce buen resultado entonces tenderá a consultarla otra vez.
• La información/conocimiento al ser adquirida del mundo real puede sufrir retrasos que modelizan:
• El retraso propio en toda propagación de información.
• La dinámica del mundo real, que tarda cierto tiempo en estabilizarse y por tanto tarda en dar un rendimiento.
• En la siguiente fórmula se modeliza la tendencia a elegir una fuente 1 frente a la fuente 2.  Gi modeliza el rendimiento obtenido con dicha fuente, fi modeliza la tasa de agentes que consulta la fuente i.  La incertidumbre de dicha elección lo recoge el parámetro ?.

La dinámica de Hogg:

Mejoras sobre Hogg:

• Dar un sentido a la función de elección: utilizar consensus para modelizar la fusión de datos (data fusion), y poder propagar las funcionesde rendimiento hacia atrás para verificar la bondad de las informaciones/conocimiento de las fuentes.
• Dar sentido a los retrasos pero incluyendo el tiempo propio de estabilización de un sistema físico sobre el cual actúan los ecosistemas de agentes: incluimos la noción de agente físico.
• Dar mecanismos adicionales para crear diversidad no sólo basados en diferentes retrasos de acceso a la információn sinó a la variedad de visiones del mundo cooperativo mediante los parámetros de consensus.

• Entonces la función de rendimiento se reformula como sigue:

• Siendo Jj  el rendimiento del sistema físico, y          la certeza revisada mediante los parámetros de consensus, dentro de una ventana temporal Tw que contiene la estabilización del sistema físico sobre el que actua el ecosistema de agentes.
• De esta manera se replantea la función de elección de Hogg usando los parámetros de consensus . Siendo Pj el prestigio y Nj la necesidad. La ecuación queda tal como sigue:

• Siendo  la certeza de la afirmación enviada por la fuente i. La  es un parámetro de velocidad de convergencia

• Ejemplo de ecosistema estable. Retardo =0.1 s.  Vemos que se estabiliza hacia 0.71, que significa que el 71% de los agentes de este ecosistema utiliza el recurso 1

Si los retardos son = 10s o bien de = 40s vemos que aparecen oscilaciones, y hasta incluso el sistema se vuelve caótico: los agentes dudan sobre qué recurso consultar la información/conocimiento.

Vemos que la interacción entre los ecosistemas tiene un efecto estabilizador.  Dicha estabilización ha de redundar en seguridad y mejor rendimiento del ecosistema.

Ejemplo de aplicación a un péndulo invertido.  Hay dos recursos que deciden la acción de control del péndulo, sobre la que se aplica consensus

• Se crean 4 tipos de ecosistemas:  creientes, indecisos, incrédulos, necesitados, etc

• slcp.mdl se puede encontrar en el fuzzy toolbox de MATLAB 5.1. Los valores de los elementos son longitud del péndulo=1.0m, masa=0.1Kg,  masa del carrito=1.0Kg, aceleración de la gravedad= 9.8m/s2
• alfa =5, sigma =1, =0.1
• Se estabiliza el rendimiento y se consigue mejorarlo
• Por ejemplo el ecosistema 3 se estabiliza y da mejor rendimiento:

Rendimiento J1

Rendimiento J3 estabilizado

Poblaciones 1, 2 y 3 estabilizadas

Situación actual de la investigación

• Se han desarrollado 25 proyectos fin de carrera: 4 de tecnología de robots, 5 de visión, 3 de control, 2 de planificación de trayectorias, 2 de sistemas integrados, 4 de juegos, 1 de experimentos, 3 de consesus, 1 de agentes en Matlab.
• Control predictivo: Paco Gamero.
• Consensus: en simulacion con el Javasoccer 1.9 (1998) y con el Soccerserver 5.24 (1999).
• Especificaciones de control (1999): Josep Lluís Martí.
• Passes mediante redes neuronales (1999): Xevi Diumé.
• Arquitectura y planteamiento del problema de los agentes físicos dinámicos (2000): tesis de Albert Oller.
• Los robots ja se comportant con dinámica.
• Hay 7 tesis en curso con temáticas relacionadas.
• Introspección: definición y captura de capacidades; Bianca Innocenti.
• Ecosistemas de agentes físicos: Israel Muñoz.
• Aprendizaje desde el mundo cooperativo de las capacidades, mediante CBR y algoritmos evolucionarios: Miquel Montaner.
• Concepción y desarrollo de experimentos.
• Comercio electrónico, los agentes físicos y la supervisión: ?
• Introspección: Agentificabilidad; Híbridos; Josep Antoni Ramon.
• Introspección: supervisabilidad; Albert Figueras.

Objetivos metodológicos de la plataforma

• Seguir persistentemente una pelota:
• Estática y lentamente.
• Estática y rápidamente.
• Moviéndose y rápidamente.
• Estática, con obstáculos estáticos, y rápidamente.
• Estática, con obstáculos dinámicos, y rápidamente.
• Moviéndose, con obstáculos estáticos, y rápidamente.
• Moviéndose, con obstáculos dinámicos, y rápidamente.
• Trabajo cooperativo: pasarse la pelota;
• Sin obstáculos.
• Con obstáculos estáticos.
• Con obstáculos móviles.
• Los robots se han de mover con dinámica clara y coloreable.

Otros resultados residuales

• Tecnológicas e Innovación
• Hardware de visión a 50 frames/s + un filtro de Kalman para predicción: gracias a Rafel Garcia.
• Colaboramos con el departamento de diseño de la UdG (Josep Maria Tresserras) para la generación del 2000 y 2001.
• Incorporamos Pentium 133MHz formato PC104
• Incluiremos VxWorks?Gracias a Quim Salvi y Pere Ridao.
• Los robots podrán comunicarse entre sí: token ring o wireless ethernet?
• Dinamización de la investigación y formación
• Tenemos conocimiento práctico sobre una plataforma relativamente robusta.  Llevamos los experimentos de la simulación a la práctica. Progresamos de forma apreciable año tras año.
• Hemos conseguido prestigio en nuestra universidad así como a escala nacional e internacional.
• Formamos ingenieros en la plataforma que luego los colocamos en otros proyectos de innovación en la industria.

Agradecimientos

• A los estudiantes de doctorado de los cursos 1995-96 hasta 1996-97: Albert Jové, Santi Esteva, Inès Ferrer, Antoni Fernández, y Esteve del Acebo, que ayudaron en los inicios del equipo robótico, en especial a Albert Oller, así como a Pepsi (Josep Sitjà).
• A todos los proyectistas tanto de la UdG, UAB, como los SOCRATES que han trabajado en la plataforma.
• Al profesor Pitu Reixach por sus constantes innovaciones.
• A Albert Figueras y Josep Antoni Ramon por haber hecho buena chatarra. A Rafa Garcia por ser el vision-man.
• Al actual equipo RoGi 2000 Team: en especial a Bianca Innocenti, Josep Lluís Martí, Miquel Montaner, Israel Muñoz y Xevi Diumé por todos los esfuerzos y demostraciones.
• A Jeffrey Johnson por usar nuestros resultados.  A Dominique Duhaut, Manuela Veloso y Tucker Balch por aceptar estancias de investigación.
• A la Fundación “Girona-Universitat i Futur”.  A la FIRA y RoboCup.
• Y muy especialmente, a la CICYT por sus constantes ayudas, en especial el proyecto DAFne (1998-2001)

Referencias Bibliográficas

• Asada M., Kuniyoshi Y., et al. (1997): The RoboCup Physical Agent Challenge, First RoboCup Workshop in the XV IJCAI-97 International Joint Conference on Artificial Intelligence, pp.51-56
• Cohen P.  and Levesque H.  (1990): Intention is choice with commitment. Artificial Intelligence, 42:213-261.
• Corera J. M., et al (1996): Using Archon, Part 2: Electricity Transportation Management, IEEE Expert and Intelligent Systems, Vol 11, n. 6, pp. 70-79
• Jennings N.R.  et al (1996): Using Archon to Develop Real-World DAI Applications, Part 1, IEEE Expert and Intelligent Systems, Vol 11, n. 6, pp. 64-70
• Kitano H., Veloso M., et al. (1997): The RoboCup Synthetic Agent Challenge 97, XV IJCAI-97 International Joint Conference on Artificial Intelligence, Vol 1, pp.24-29
• de la Rosa J. Ll., Oller  A., et al. (1997):  Soccer Team based on Agent-Oriented Programming, Robotics and Autonomous Systems. Ed. Elsevier, Vol 21, pp. 167-176. October  1997.
• Shoham Y. (1990): Agent-oriented programming. Technical Report STAN-CS-1335-90, Computer Science Department, Stanford University, Stanford, CA.
• Stone P. and Veloso M. (1997): A layered approach to learning client behaviors in the robocup soccer server, to appear in Applied Artificial Intelligence.
• Varaiya P. and Deshpande A. (1995): Viable Control of Hybrid Systems: Hybrid Systems II, Lecture Notes in Computer Science, Springer Verlag. 1995.
• Wooldridge M., Jennings N.R. (1995): Intelligent Agents: Theory and Practice, The Knowledge Engineering Review, Vol 10:2, pp. 115-152
• Agha, G. (1986): ACTORS: A Model of Concurrent Computation in Distributed Systems. The MIT Press. Cambridge, MA.
• Aguilar J. (1994): Knowledge-based Real Time Supervision of Dynamic Processes: Basic Principles and Methods, Applied Control: Current Trends and Applied Methodologies, Ed. Marcel Dekker, Inc., 1993.
• Del Acebo E., Oller A., de la Rosa J. L. (1997): Three Criteria for Fuzzy Systems Quality Evaluation, Workshop on Automation 2001, pp. 265-274, June 12-15, 1997, Viena, Austria.
• Cohen, P. R. and Levesque, H. J. (1990): Intention is choice with commitment. Artificial Intelligence, 42:213-261.
• Durfee E.E., Lesser V.R., and Corkill D.D.. "Trends in cooperative distributed problem solving". IEEE Transactions on Knowledge and Data Engineering, 1(1):63-83,  1989.
• Fisher, M. (1994): A survey of Concurrent MetateM - The language and its applications. In Gabbay, D. M. and Ohlbach, H. J., editors, Temporal Logic - Proceedings of the first International Conference (LNAI Volume 827), pages 480-505. Springer-Verlag: Heidelberg, Germany.
• Hewitt, C. (1977): Viewing control structures as patterns of passing messages. Artificial Intelligence, 8(3):323-364.
• Jennings, N. R. (1993): Commitments and conventions: The foundation of coordination in multi-agent systems. Knowledge Engineering Review, 8(3):223-250.
• Kripke, S. (1963): Semantical analisis of modal logic. Zeitschrift für Matematsche Logik und Grudlagen der Mathematik, 9:67-96.
• Maes P. (1994): Social interface agents: Acquiring competence by learning from users and other agents. In Etzoni O. editor, Software Agents - Papers from the 1994 Spring Symposium, pp. 71-78, AAAI press.
• Maes P. (1989): The dunamics of action selection. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), pages 991-997, Detroit, MI.
• Meléndez J., de la Rosa J. Ll., et al (1995): Embedding Objects into Matlab/Simulink for process Supervision, IEEE International Symposium on CACSD, pp: 20-25, Dearborn, Michigan, USA, Sept. 15-18, 1996.
• Oller A., García R., Ramon J. A., Figueras A., de la Rosa J. L. (1997): Co-operation among Robots by Means of Multi-Agent Decision Making Framework under MATLAB-SIMULINK, Workshop on Automation 2001, pp. 71-80, June 12-15, 1997, Vienna, Austria
• de la Rosa J. Ll., Serra I., and Aguilar-Martin J. (1992): Outline of a Heuristic Protocol among Cooperative Expert Systems,  IEEE Conference on Systems, Man, and Cybernetics,  Vol. 2 pp. 905-910, September 1992
• de la Rosa J. Ll., Serra I., and Aguilar-Martin J. (1994): Heuristics for Co-operation of Expert Systems.  Application to Process Control, Ed. PIAR.
• de la Rosa J. Ll., J. Meléndez, J. Colomer et al. (1995): An Application of heuristic co-operation to process control, 3rd IEEE Mediterranean Symposium on New Directions in Control and Automation, Limassol, Vol 1, pp 232-237 (Cyprus), July 1995.
• Rosenschein, S. and Kaelbling, L. P. (1986): The synthesis of digital machines with provable epistemic properties. In Halpern, J. Y., editor, Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning About Knowledge, pages 83-98. Margan Kaufmann Publishers. San Mateo, CA.
• Steels, L. (1990): Cooperation between distributed agent through self organization. In Demazeau, Y. and Müller, J.-P., editors, Decentralized AI - Proceedings of the Third European Workshop on Modelling Autonomous Agents and Multi-Agent Worlds (MAAMAW-91), pages 175-196. Elsevier Science Publishers B. V. Amsterdam, The Netherlands.