DPA2: Una Arquitectura per a Agents Físics Dinàmics

 
Albert Oller i Pujol 
Dep. d'Eng.Elèc.Electrònica i Automàtica. 
Grup de Robòtica i Visió Intel·ligents.
Universitat Rovira i Virgili.
aoller@etse.urv.es
Josep Lluís de la Rosa

Institut d’Informàtica i Aplicacions (IIiA).
Universitat de Girona.
peplluis@eia.udg.es

Resum. En aquest article es presenta una arquitectura per a permetre el disseny d’agents físics amb dinàmica pròpia. Aquesta arquitectura mostra l’agent com a una entitat modular amb tres nivells d’abstracció: mòdul de control, mòdul supervisor i mòdul agent. El funcionament de l’arquitectura es basa en dos processos bàsics per a cada mòdul: el procés d’introspecció i el de control, i en un protocol de diàleg intermodular que permet l’intercanvi d’informació entre els mòduls. També es mostren dos exemples d’aplicació que mostren alguns resultats preliminars.

Paraules clau: Agents Físics, Control, Arquitectura orientada a Agents, Robòtica Mòbil.


1 Introducció

El treball amb sistemes multi-robot és prou ampli com perquè hi tingui cabuda l’aplicació de conceptes de l’etologia animal, de la teoria de l’organització, l’aprenentatge, i de la Intel·ligència Artificial (IA). En concret, la coordinació i la interacció de múltiples robots (comportament col·lectiu) s’està estudiant en el camp de la Intel·ligència Artificial Distribuïda (IAD), a partir del concepte de l’agent software. A la literatura podem trobar diferents definicions del comportament cooperatiu però la clau està en entendre la cooperació com a un ‘associar-se amb els demés’ per obtenir un benefici mutu (recompensa, interés comú, disminució d’un index de cost). És en aquest punt on apareixen diverses qüestions relacionades amb el problema de l’anàlisi i del disseny de sistemes multi-robot (multi-agents autònoms): la descomposició i distribució de tasques, la robustesa i tolerància a les fallades, la correcció de l’evolució del sistema, o la mesura per quantificar la quantitat i/o la qualitat de la cooperació.

Els agents autònoms que porten a terme tasques en entorns multi-agent dinàmics han de cumplir els requisits que imposa el funcionament en temps real i el món real [7]. Alguns d’aquests requeriments són els següents:

  • Saber-se comportar d’acord a les circumstàncies (situated behavior), i reaccionar davant esdeveniments no previstos.
  • Tenir un comportament dirigit cap a un objectiu (goal-directed behavior) i saber seleccionar les accions en funció d’aquests objectius.
  • Les tasques s’han de realitzar amb eficiència tot i tenint en compte les imposicions restrictives del treball en temps real.
  • Han de tenir present la presència d’altres agents.
  • Canal de comportament
    [C-mode à I-mode]
    Canal de Percepció
    [I-mode à C-mode]
    INT Request (A, time) INT Inform(A,END)
    INT Inform(A,EVN, ‘Desc’)
    INT Inform(A,PRB, ‘Desc’)
    Taula I: Llista de missatges d’interrupció: la primera fila indica el canal d’entrada del missatge i el canvi que s’indueix en el mode de funcionament del mòdul receptor.

    Missatges de diàleg: aquests són els missatges que poden intercanviar-se entre dos mòduls veïns i que no provoquen cap canvi directe en el mode de funcionament d’ambdós fins que la conversa ha finalitzat.

    Canal de Percepció Canal de Comportament
    Agree (A, time, m ) Request (A, START, time, m )
    Refuse (A, ‘Reason’) Request(A, STOP)
    Inform (A, time, m ) Query (A, time)*
    Taula II: Llista de missatges de diàleg.

    3.2.1.Descripció dels protocols

    Hem vist que cada mòdul pot funcionar en dues modalitats i que en qualsevol de les dues sempre hi ha o una comanda o una demanda, és a dir, un mòdul pot portar a terme quatre tipus de papers dialectals: ordenant de demanda, receptor de demanda, ordenant de comanda i receptor de comanda. Per tant, només s’han definit dos protocols: un pel diàleg de demanda (QUERY) i un altre pel de comanda (REQUEST), els quals estan basats en els protocols FIPA-query i el FIPA-request establerts per la FIPA’98 [4]:

  • Protocol FIPA-query: el mòdul receptor rep un missatge en què se li demana que faci una acció informativa. En el nostre cas l’acció informativa serà contestar a la pregunta formulada per l’emissor.
  • Protocol FIPA-request: permet que un mòdul demani a un altre que executi una acció. En cas d’acceptació també avisarà quan acabi o si hi ha hagut alguna fallada. El mòdul receptor pot refusar l’ordre d’execució de l’acció i donar els motius del perquè. Aquest refús és indicatiu que té algun problema amb les seves capacitats i, per tant, no pot executar les accions relacionades.

  • 3.3. Activació del sistema

    A partir de l’estructura de l’arquitectura es pot veure que la comunicació entre mòduls pot iniciar-se des d’alt nivell quan l’agent es compromet a executar un rol (activació Top-down), o bé des de baix nivell quan el mòdul de control detecta un event (activació Bottom-up). Aquest segon cas no s’explicarà per raons d’espai.

    3.3.1.Activació Top-down: descripció

    A continuació s’explica el funcionament a partir de l’esquema de la "Fig.9":

      Cal comentar que en el cicle de funcionament s’ha posat un quart mòdul corresponent a la col·lectivitat en què es mou l’agent. Com es pot veure aquest seria un quart mòdul que apareix a l’arquitectura DPA2 de forma natural (veure també "Fig. 6"): la percepció que té la col·lectivitat de l’agent és el grau de compromís que adquireix en acceptar un rol. S’ha posat a la taula per raons de claretat: el temps de cicle per obtenir una decisió depèn també del temps que dedica l’agent a negociar amb la col·lectivitat.

      3.4 Definició de les capacitats modulars

      Com poden definir-se les capacitats d’un agent? Tot depèn del nivell d’abstracció a què es treballi. Per obtenir una definició amb poca ambiguïtat cal basar-la en un llenguatge descriptiu numèric de forma que cal començar als nivells baixos d’abstracció i anar augmentant el grau d’abstracció per anar passant a descripcions més simbòliques. De fet, una raó de pes per començar a definir les capacitats a baix nivell està en el fet que tot agent físic disposa d’uns controladors que el limiten i/o capaciten per executar una certa quantitat d’accions d’una forma més o menys correcte. És a dir, el món lògic de l’agent ha de saber si serà capaç de controlar el seu cos per tal d’assumir un rol concret per a la comunitat multi-agent. De tota manera, a la literatura poden trobar-se moltes definicions de les capacitats a nivell agent, però no ténen en compte aquest contacte amb el món físic.

      Una forma breu de definir les capacitats a nivell de control és la següent:

      Definició 4: una capacitat (a nivell de control), consisteix en ser la percepció de les qualitats d’un controlador. Per tant, les capacitats integren tant la identificació del cos físic com la percepció de l’entorn a través del cos i, en última instància, integren també l’adaptació de l’agent físic a l’entorn, és a dir, l’habilitat de poder aprendre.

      Per tal de formalitzar la definició de les capacitats, anomenem les capacitats de control com a capacitats atòmiques, que són aquelles que l’acció associada pot executar-se directament amb la percepció i l’actuació del nivell més baix, sense interpretar les dades adquirides. És a dir, l’acció es portarà a terme a partir de la mesura de les coordenades generalitzades del propi cos , i dels events i les magnituds externes al cos mesurades amb els sensors del propi agent. Per tant, la definició de les capacitats atòmiques s’ha de fer observant la qualitat d’execució d’aquestes accions amb els diferents controladors implementats en el cos fisic, és a dir, mesurant l’error en estat estacionari, el temps de resposta, l’amplitud d’oscil·lació, etc. Cal tenir present que el grau de sensorització és indicatiu del grau d’autonomia de l’agent, és a dir, serà capaç de realitzar més accions i, per tant, tindrà més capacitats.

      Les capacitats del supervisor s’anomenen capacitats bàsiques, i són aquelles que s’obtenen combinant les atòmiques. El mètode de combinació consisteix en utilitzar les capacitats atòmiques com a estats en una màquina d’estats finits, i en utilitzar les condicions que obliguen a abandonar un controlador i escollir-ne un altre com a transicions. En un llenguatge més formal, el mètode de combinació consisteix en construir un sistema de control híbrid. Cal fer notar que el supervisor pot utilitzar un llenguatge menys numèric i això fa obligatori l’ús d’etiquetes, és a dir, com que el nivell d’abstraccio és més alt l’interpretació del món és més depenent de l’aplicació. Això provoca que pugui haver-hi accions bàsiques que siguin coincidents en la combinació d’accions atòmiques, però no en l’etiquetat que utilitzen.

      En aquest mòdul supervisor, l’avaluació de la qualitat d’execució d’aquestes accions és més complexa ja que el llenguatge descriptiu no és tant numèric com en el nivell d’abstracció del mòdul de control. De tota manera, amb mètodes heurístics es pot avaluar la precisió i/o la dificultat de les execucions de les accions. Per exemple, es pot avaluar l’execució de l’acció (A) calculant un índex del grau de dificultat en funció de les oscil·lacions de la trajectòria optimitzada [10].

      Finalment, les capacitats a nivell agent es defineixen de forma més simbòlica ja que el model del món és molt més abstracte i és completament dependent de l’aplicació que es faci. El mètode de definició és completament escalable al que s’utilitza en el supervisor, és a dir, les capacitats en el nivell d’abstracció del mòdul agent és construeixen a partir de les capacitats bàsiques. De tota manera, l’objectiu del mètode de combinació no és construir un sistema de control híbrid, sinó construir una màquina d’estats finits en què els estat són accions bàsiques i les transicions són les condicions que afavoreixen o no el manteniment de l’execució d’un acció bàsica concreta.


      4 Exemples il·lustratius

      4.1 Dos vehicles autònoms en fila

      La situació que teniem a la secció 2.4 era que el vehicle guia normalment decidia accelerar o frenar sense tenir en compte la dinàmica de l’altre vehicle. Proposem la creació d’un sistema de decisió co-operant que tingui en compte les dinàmiques de frenada d’ambdós vehicles [8][9]. Amb aquest exemple no s’intenta trobar un mètode per solucionar el problema de les col·lisions en les formacions en fila india, sinó que s’ha escollit aquest problema perquè ofereix la problemàtica de la dinàmica dels mòbils: en una cua no hi haurà mai dos vehicles exactament iguals de forma que la forma de la frenada serà diferent en cada cas.

      Per tal poder usar la DPA2, en el mòdul de control s’han definit un conjunt de controladors que permeten obtenir diferents temps de frenada. En el mòdul supervisor s’han definit les capacitats a partir de la classificació del tipus de resposta que s’obté per a cada controlador. Finalment, en el mòdul agent s’han definit només les capacitats de frenar, accelerar i mantenir la velocitat. Així, l’agent pot adquirir el compromís de frenar en un temps determinat a partir de la percepció que rep del mòdul supervisor. Per tant, els dos agents poden acordar l’acció de frenada suficient per a tots dos de forma que, tot i que la dinàmica de (XA-XB) continua sient de 2on ordre, el xoc s’eviti.

      A continuació es presenta un exemple amb la decisió cooperant explicada anteriorment, en què l’agent A decideix parar amb t =0.3s. Després que l’agent B inhibeixi l’execució, negocien un valor t =0.6s. Es pot observar que la distància no s’anul·la, és a dir, s’evita la col·lisió (veure "Fig.11").

      El que es pot veure amb aquest exemple és que l’enginyer que ha de dissenyar l’agent físic amb dinàmica pròpia, s’ha de dedicar fonamentalment a definir les capacitats de cada mòdul.


      Fig.11: Diagrama de la frenada (esquerra), i evolució de la distància XA-XB.(dreta).

      D’aquesta manera, la forma de treballar queda modularitzada i pot dedicar-se, posteriorment, a establir les relacions que hi ha entre les capacitats i les accions en cada nivell d’abstracció.

      4.2 Equip de robots jugant a futbol

      A fi de poder completar la definició de l’arquitectura s’està portant a terme el desenvolupament d’un exemple d’aplicació molt més complert: una plataforma real amb un equip de robots que juguen a futbol. La riquesa d’aquesta plataforma està en la quantitat de problemàtiques que apareixen: en control (no-linealitats, imprecissió), en supervisió (seguiment de trajectòries, canvis de controladors segons les situacions), per l’agent (obstruir, passar la pilota), per la col·lectivitat (atacar, defensar, negociar i resoldre de conflictes).

      A partir del coneixement aproximat del joc del futbol és fàcil entendre que tant a baix nivell d’abstracció (mòdul de control) com a al nivell (mòdul agent i/o col·lectivitat), la definició de les capacitats ha de ser molt més elaborada que en l’exemple anterior. En el mòdul de control cal definir-hi diversos tipus de controladors per tal que l’agent pugui executar moviments diferents tant en precissió com en rapidesa. Aquests controladors hauran d’estar pensats per a executar cadascun d’ells accions que en el mòdul supervisor són, simbòlicament, molt diferents: anar a un punt llunyà, xutar, buscar la pilota amb ajuda de sensors, obtenir una posició i orientació acurades, etc.

      Per concretar més, anem a definir les accions atòmiques. A partir de la mesura de les coordenades del propi cos i de les magnituds externes al cos, algunes accions atòmiques podrien ser ‘(1) anar a una posició’, ‘(2) mantenir una velocitat’, ‘(3) perseguir un objecte’, ‘(4) evitar el xoc amb un objecte’ o ‘(5) colpejar un objecte’. Hem de suposar que tenim definit un conjunt de controladors.

      Com a accions bàsiques podriem definir les següents: ‘(A=(1+2+4)) anar de A a B seguint una trajectòria’, ‘(B=(1+2+5)) xutar la pilota’, ‘(C=(1+2+3)) portar la pilota’, ‘(D=1+2+3) perseguir un contrari’, o‘(E=1+2+3+4) moure’s seguint la paret’. Respecte a les accions C i D. Es pot veure que són coincidents en la combinació d’accions atòmiques, però no en l’etiquetat que utilitzen. En la primera l’etiqueta de l’objecte correspon a ‘pilota’ mentre que en la segona és ‘contrari’.

      Finalment, les capacitats a nivell agent es poden definir com segueix: ‘Passar la pilota’, ‘Marcar un contrari’, ‘Protegir la porteria’, ‘Desmarcar-se’ o ‘Interceptar la pilota’.


      5. Conclusions i treballs futurs

      En aquest treball s’ha presentat una arquitectura per a agents físics amb dinàmica pròpia. Un agent és vist com a una entitat multi-nivell i uniforme en el sentit que els diferents mòduls que el componen interaccionen i funcionen d’una manera uniforme. La diferenciació bàsica entre els mòduls està en la definició de les capacitats. Des d’aquest punt de vista, els mòduls poden considerar-se com a agents en sí mateixos. En aquest treball encara queden qüestions obertes de les quals remarquem:
       



      Agraïments

      Aquest treball ha estat parcialment finançat pel projecte CICYT TAP98-0955-C03-02 "Diseño de agentes físicos (DAFNE)" del MEC i per 1998GR00234 "Grup de Recerca Consolidat de Sistemes Integrats" del CUR.

      Referències

      [1] R.Beckers, O.E.Holland, and J.L.Deneubourg. From Local to global tasks: Stigmergy and collective robotics. Proc. A-Life IV. MIT Press, 1994.

      [2] R.A. Brooks. A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, RA-2:14-23, 1986.

      [3] Y.U.Cao, A.S.Fukunaga, et al. Cooperative Mobile Robotics: Antecedents and Directions. IEEE Transactions in Robotics. pp. 226-234. 1995.

      [4] FIPA’98 Draft Specifications: Part 1. This version may be found on the FIPA web site: http://www.fipa.org

      [5] McFarland. Towards robot cooperation. Proc. Simulation of Adaptive Behavior, 1994.

      [6] A.K.MackWorth. On Seeing Robots. Computer Vision: Systems, Theory, and Application. Pp 1-13, World Scientific Press, Singapore, 1993

      [7] J.P.Müller. The Design of Intelligent Agents. A Layered Approach. Lecture Notes in Artificial Intelligence, Vol. 1177. Ed. Springer-Verlag. 1996.

      [8] A.Oller, E. Del Acebo, J.Ll. de la Rosa. DPA2: Architecture for Co-operative Dynamical Physical Agents. Acceptat al 9th European Workshop on Multi-Agent Systems –MAAMAW 1999.

      [9] A.Oller, J.Ll. de la Rosa, B. Innocenti. Uso de parámetros dinámicos para mejorar la cooperación entre robots móbiles. Aplicación en un convoy de dos robots. Acceptat a Seminario Anual de Automática y Electrónica Industrial 1999 (SAAEI’99).

      [10] A. Oller, J.Ll. de la Rosa, R. García, J.A. Ramon, A. Figueras Micro-Robots Playing Soccer Games: a Real Implementation Based on a Multi-Agent Decision-Making Structure. International Journal on Intelligent Control and Soft Computing. En premsa. 1999.

      [11] L.Parker. Heterogeneous Multi-Robot Cooperation. PhD. Thesis. MIT EECS Dept. February. 1994.

      [12] A.S. Rao and M.P. George_. BDI agents: From theory to practice. In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), pp. 312-319, Menlo Park, California, June 1995. AAAI Press. (pp. 101, 184, 185, 195, 199).

      [13] L.Steels. A case study in the behavior-oriented design of autonomous agents. Proc. Simulation of Adaptive Behavior, 1994.