sisteme multiagent. arhitecturi de agenti 2

Upload: enrollinfo

Post on 04-Apr-2018

230 views

Category:

Documents


0 download

TRANSCRIPT

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    1/74

    Modelarea i analizasistemelor multi-agent

    3. Arhitecturi de ageni (II)

    Florin Leon

    Universitatea TehnicGheorghe Asachi din IaiFacultatea de Automatici Calculatoare

    http://florinleon.byethost24.com/curs_masma.htm

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    2/74

    2

    Arhitecturi de ageni (II)1. Arhitectura BDI

    2. Arhitectura PRS

    3. Arhitecturi stratificate

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    3/74

    3

    Arhitecturi de ageni (II)1. Arhitectura BDI

    2. Arhitectura PRS

    3. Arhitecturi stratificate

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    4/74

    Raionamentul practic Raionamentul teoretic (speculativ) reprezint utilizarea raiunii

    pentru a decide ce s crezi Dac agentul credepi crede cp q, atunci crede q

    Raionamentul practic reprezint utilizarea raiunii pentru a decidecum s acionezi Dac agentul trebuie s ajung n locaiax, atunci pornete spre

    locaiax

    Raionamentul practic este o modalitate de a cntri consideraii

    conflictuale pentru i mpotriva unor opiuni aflate n competiie,unde consideraiile relevante sunt furnizate de ceea ce dorete/preuiete agentul i de ceea ce crede agentul(Bratman)

    4Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    5/74

    Raionamentul practic Const n dou procese principale:

    A decide cescopuri trebuie atinse

    Deliberarea

    Rezultatul deliberrii este o intenie

    A decide cumse pot atinge aceste scopuri

    Analiza mijloace-scopuri (engl. means-ends analysis /reasoning)

    Rezultatul analizei mijloace-scopuri este un plan

    5Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    6/74

    Inteniile: exemplu Mihai (Michael W. )termin facultatea cu note bune Are mai multe opiuni pentru alegerea carierei Alege s rmn n nvmntul superior Se angajeaz s urmeze aceast direcie Acioneaz n vederea atingerii scopului, de exemplu

    ncearc s intre la doctorat ncearc din nou dac eueaz Nu va selecta opiuni care vin n contradicie cu intenia

    curent, de exemplu s petreac n fiecare noapte i menine intenia ct timp acest lucru este raional

    6Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    7/74

    Rolurile inteniilor Inteniile conduc analiza mijloace-scopuri

    Cnd un agent are o intenie, va ncerca s o ndeplineasc Dac o modalitate eueaz, agentul va ncerca diferite

    alternative

    Inteniile constrng deliberrile viitoare Agentul nu va lua n calcul opiuni ce pot intra n conflict cu

    inteniile curente

    7Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    8/74

    Rolurile inteniilor Inteniile sunt persistente

    Agentul nu trebuie s renune fr un motiv ntemeiat Inteniile persist:

    pn cnd sunt ndeplinite

    pn cnd este clar c nu pot fi ndeplinite

    pn cnd dispare motivul pentru care au fost adoptate

    Inteniile influeneaz convingerile despre viitor Agentul poate planifica presupunnd c inteniile vor fi

    ndeplinite

    8Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    9/74

    9

    Analiza mijloace-scopuri O tehnic deseori folosit de oameni pentru rezolvarea

    problemelor

    Primul program de inteligen artificial care a implementat

    procedura a fost General Problem Solver, realizat de AllenNewell i Herbert Simon n 1959 la Universitatea CarnegieMellon

    Putea rezolva, n principiu, orice problem simbolic formalizat:demonstrare de teoreme, probleme de geometrie, turnurile din

    Hanoi etc. Explozie combinatoric a strilor intermediare

    A evoluat n arhitectura Soar

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    10/74

    10

    Analiza mijloace-scopuri Se bazeaz pe un set de reguli care pot transforma o

    stare a problemei n alta

    Regulile se reprezint sub forma unei pri stngi,care descrie precondiiile (condiiile de aplicare) io parte dreapt care descrie schimbrile din stareaproblemei ca urmare a aplicrii regulii

    n acest scop se elaboreaz o tabel de diferene,n care se precizeaz ce operaie este aplicabilpentru fiecare stare a problemei

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    11/74

    11

    Exemplu S considerm modul n care poate cltori cineva:

    Dac distana care trebuie parcurs este mai mare de20 km, ia trenul

    Dac distana este ntre 2 i 20km, ia autobuzul Dac distana este mai mic de 2km, merge pe jos

    Tabela de diferene este urmtoarea:

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    12/74

    12

    Exemplu S presupunem c o persoan X din Iai vrea s-i

    viziteze un prieten Y din Bucureti

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    13/74

    Planificarea Analiza mijloace-scopuri este o metod de planificare Agentul primete:

    O reprezentare a strii curente a mediului O reprezentare a scopului care trebuie atins

    O reprezentare a aciunilor care pot fi ndeplinite (operatori)

    Agentul trebuie s genereze un plan (o secvende aciuni) care, plecnd din starea curent,s ndeplineasc n final scopul

    13Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    14/74

    14

    Limbaje de reprezentare STRIPS (STanford Research

    Institute Problem Solver)

    Fikes & Nilsson, 1971

    Robotul Shakey i blocurile

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    15/74

    15

    Reprezentarea strilor O stare este o conjuncie de termeni pozitivi,

    propoziionali sau de ordin nti Valide:

    Invalide:

    Presupunerea lumii nchise(engl. closed-world assumption) Orice condiie care nu este menionat ntr-o stare

    este considerat fals

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    16/74

    16

    Reprezentarea scopurilor

    O conjuncie de termeni pozitivi De exemplu

    O stare propoziional ssatisface scopul gdacea conine toi atomii din g(i posibil alii)

    Stareasatisface scopul

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    17/74

    17

    Reprezentarea aciunilor

    Scheme de aciuni Precondiii Postcondiii (efecte)

    lista de adugarelista de tergere

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    18/74

    18

    Exemplu

    Starea curent

    satisface precondiia aciunii Fly(aciunea este aplicabil):

    cu substituiile

    Aciunea concret

    Rezultat (starea urmtoare).

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    19/74

    19

    Presupunerea STRIPS

    Problema cadrului (engl. frame problem) Reprezentarea logic a numrului mare de non-efecte

    obinuite, implicite, ale unei aciuni

    Exemplu:

    Trebuie adugate explicit unele axiome de cadru:

    Presupunerea STRIPS (engl. STRIPS assumption)evit aceast problem Orice termen care nu este menionat n efect rmne

    neschimbat

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    20/74

    20

    Exemplu: Lumea blocurilor

    On(b,x)

    Move(b,x, y)

    Clear(x)

    Block(b)

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    21/74

    21

    Exemplu: Lumea blocurilor

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    22/74

    22

    Planuri

    Un plan este o secven de aciuni= (a1, ....., an),care determin starea urmtoare a mediului,n

    Un plan este corect dac: 0este starea iniial a mediului Precondiiile fiecrei aciuni aisunt satisfcute n starea

    anterioar a mediului,i-1 neste starea final (scopul)

    Generarea unui plan este o problem de cutare Prin progresie

    Prin regresie

    Euristic

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    23/74

    23

    Biblioteci de planuri

    n multe implementri ale raionamentuluipractic, agentului i se d o o bibliotec

    (o colecie) de planuri Precondiii Corpul planului

    Postcondiii

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    24/74

    24

    Arhitectura BDI

    Rao & Georgeff (1991)

    Beliefsconvingeri Informaiile agentului despre mediu(inclusiv agenii din mediu)

    Desiresdorine Obiectivele sau strile de lucruri pe care agentul le-ar dori realizate

    (ntr-o lume ideal) De exemplu: a gsi preul cel mai bun, a merge la petrecere, a deveni bogat

    Scopuri: dorinele adoptate de agent pentru a fi urmrite Scopurile trebuie s fie necontradictorii: a merge la petrecere sau a sta acas

    (ambele pot fi dorine, dar numai una poate fi un scop)

    Intentionsintenii Dorinele pe care agentul s-a angajat s le realizeze

    A nceput execuia unui plan

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    25/74

    25

    Pseudocodul general

    Implementarea unui agent cu raionament practic

    while truedo

    observe the world

    update internal world model

    deliberate about what intention to achieve next

    use means-ends reasoning to get a plan for the intentionexecute the plan

    end while

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    26/74

    Timpul de calcul

    Deliberarea i planificarea au un cost computaional,necesit timp

    La finalul procesului de deliberare, exist riscul caintenia aleas s nu mai fie optim La fel i pentru planificare

    Implementarea agentului este optim dac:

    Deliberarea i planificarea sunt suficient de rapide Mediul este static

    26Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    27/74

    Formalizare

    Actualizarea convingerilor Funcia de revizuire a convingerilor

    (engl. belief revision function) brf :(Bel) x P(Bel)

    Procesul de deliberare deliberate:(Bel) (Int)

    Procesul de planificare plan :(Bel) x(Int) Plan

    27

    P= mulimea perceptelor

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    28/74

    28

    Pseudocodul generalformalizat

    B:= B0 // B0sunt convingerile iniiale

    while truedo

    get next percept

    B:= brf(B, )

    I:= deliberate(B)

    := plan(B, I)

    execute()

    end while

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    29/74

    Funciile de deliberare

    Agentul delibereaz evalund opiunile disponibile ialegnd ntre ele

    Funciile de deliberare pot fi descompuse n doucomponente Generarea opiunilor: agentul i genereaz o mulime de

    alternative posibile (dorine) options: (Bel) x(Int) (Des)

    Filtrarea: agentul alege ntre alternativele aflate ncompetiie, generndu-i inteniile filter :(Bel) x(Des) x(Int) (Int)

    filter(B,D,I) ID(inteniile curente sunt ori intenii existentedeja ori opiuni nou adoptate, nu pot aprea de nicieri)

    29Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    30/74

    Arhitectura generic BDI

    B:= B0// B0sunt convingerile iniiale

    I:= I0 // I0sunt inteniile iniiale

    while truedo

    get next percept

    B:= brf(B, )

    D:= options(B, I)

    I:= filter(B, D, I)

    :=plan(B, I)

    // aciunile planului sunt executate una cte unaexecute()

    end while

    30Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    31/74

    31

    Probleme

    Bucla de control este supra-angajat Agentul rmne angajatn executarea unui plan pn cnd

    acesta este complet executat, chiar dac planul nu

    funcioneaz Agentul nu se oprete s-i reconsidere inteniile, chiar dac

    o intenie devine imposibil de ndeplinit sau apar noioportuniti

    Dac un plan eueaz, este necesar replanificarea Este important i reconsiderarea inteniilor

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    32/74

    Strategii de angajament

    1. Angajament orb (fanatic) Agentul i menine o intenie pn cnd crede c aceasta a

    fost ndeplinit

    2. Angajament singular (engl. single-minded) Agentul i menine o intenie pn cnd crede c:

    a fost ndeplinit sau este imposibil de ndeplinit

    A determina dac un scop este imposibil de ndeplinit poatenecesita foarte multe resurse de calcul Se pot revizui convingerile, dar nu i scopurile

    32Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    33/74

    Strategii de angajament

    3. Angajament deschis (engl. open-minded) Agentul i menine o intenie pn cnd crede c:

    a fost ndeplinit sau este imposibil de ndeplinit sau scopul nu mai exist

    Se pot revizui i convingerile i scopurile Pot aprea noi scopuri, de exemplu noi cereri sau revocarea

    unor cereri anterioare

    Se rein doar angajamentele compatibile cu scopurile curente Agentul are angajamente att pentru scopuri (strile dorite)

    ct i pentru mijloace (mecanismele prin care dorete s lendeplineasc)

    33Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    34/74

    34

    Dac un planeueaz, ncearcaltul, pn cndun plan a fostexecutat cu successau nu mai existplanuri aplicabile

    1. Angajamentul orb

    hd() = prima aciune a planuluitail() = restul aciunilor, de la a douasound() = dac planul este corect

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    35/74

    35

    Reconsider

    inteniile cndintenia curent afost ndeplinit,cnd este imposibilde ndeplinit saucnd nu mai existplanuri aplicabile

    2. Angajamentul singular

    (

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    36/74

    36

    Reconsiderarea inteniilor

    Agentul trebuie s verifice dac inteniile au fostndeplinite sau dac sunt imposibil de ndeplinit

    Agentuli va reconsidera inteniile (n buclaexterioar) numai cnd: A executat complet un plan pentru ndeplinirea inteniilor

    curente

    Crede c i-a ndeplinit inteniile curente

    Crede c inteniile curente nu se mai pot ndeplini Dac apar noi oportuniti? Algoritmul poate fi modificat pentru a reconsidera

    inteniile dup executarea fiecrei aciuni

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    37/74

    37

    Reconsiderinteniile dupfiecare aciune

    3. Angajamentul deschis

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    38/74

    38

    Cnd trebuie reconsiderate inteniile

    Reconsiderarea inteniilor este costisitoare din punctde vedere computaional

    Dilem: Un agent care nu le reconsider destul de des va ncerca

    ndeplinirea lor chiar i cnd nu pot fi ndeplinite sau nu maiexist niciun motiv pentru ndeplinirea lor

    Un agent care le reconsider permanent s-ar putea s nuaib suficient timp s le i ndeplineasc

    Se poate include o componentde control meta-nivelcare decide cnd s fie reconsiderate inteniile

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    39/74

    39

    Control meta-nivel

    Angajament deschiscu un control meta-nivel

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    40/74

    40

    Funcia reconsiderse comport optim dac inumai dac atunci cnd alege s delibereze,agentul i schimb inteniile

    Interaciuni posibile ntre componenta de controlmeta-nivel i componenta de deliberare:

    Interaciuni posibile

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    41/74

    41

    Strategii de reconsiderare

    Kinny & Georgeff (1991) au investigatexperimental eficacitatea strategiilor de

    reconsiderare a inteniilor S-au folosit dou tipuri de strategii:

    Ageni ndrznei (engl. bold): nu se oprescniciodat s-i reconsidere inteniile

    Ageni precaui (engl. cautious):se opresc s-ireconsidere inteniile dup fiecare aciune

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    42/74

    42

    Dinamismul mediului

    Dinamismul mediului este reprezentat de rataschimbrilor

    Dac este mic (mediul se schimb rar), atunciagenii ndrznei se comport mai bine Agenii precaui pierd timp reconsidernd angajamentele Agenii ndrznei lucreaz pentru atingerea inteniilor

    Dac este mare (mediul se schimb frecvent),

    atunci agenii precaui se comport mai bine Agenii precaui pot recunoate situaiile cnd inteniile trebuie

    modificate i pot profita de ocaziile favorabile care apar

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    43/74

    43

    Formalizare

    Arhitectura BDI este fundamentatpe teoriaaciunilor raionale ale oamenilor

    Arhitectura a fost formalizat riguros ntr-o familie delogici BDI

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    44/74

    Aplicaii

    PRS, prima arhitectur care a ncorporatparadigma BDI, a fost implementat i utilizatcu succes n diverse aplicaii complexe: OASIS: Sistem de control al traficului aerian la

    aeroportul din Sydney

    SWARMM: Un sistem de simulare pentru foreleaeriene australiene

    SPOC: Un sistem de management al proceselor deafaceri (Single Point of Contact, Agentis Solutions)

    44Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    45/74

    45

    Arhitecturi de ageni (II)

    1. Arhitectura BDI

    2. Arhitectura PRS

    3. Arhitecturi stratificate

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    46/74

    Planuri PRS

    Context (precondiiile) Scop (postcondiiile)

    Corp (reeta planului, cursul de aciune) Component a unei biblioteci de planuri precompilate Pe lng mulimea de aciuni primitive, corpul poate

    include scopuri intermediare, scopuri disjuncte saubucle

    Cunotinele sunt reprezentate cu ajutorul logiciipredicatelor de ordin I

    46Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    47/74

    Sistemul de raionament procedural

    47Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    48/74

    Mdul de lucru

    Agentul pornete cu un scop de nivel nalt (~main) Scopul este introdus ntr-o stiv de intenii

    Planurile pentru care precondiiile sunt ndeplinitei postcondiiile sunt scopuri devin opiuni Agentul trebuie s selecteze dintre planurile

    disponibile pe cel mai bun, folosind:

    Planuri meta-nivel (planuri despre planuri) Utiliti ale planurilor

    Planul selectat este executat

    48Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    49/74

    49

    Bibliotec de planuripentru lumea blocurilor

    Scopuri:

    ON Block3 Tablesatisfcut

    ON Block2 Block3 plan: Stackblocks that are already clear, carefolosete dou invocri ale planuluiClear a block

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    50/74

    50

    OASIS

    Sistem de management al traficului aerian: prototip la aeroportul dinSydney

    Ageni pentru fiecare aparat de zbor Ageni pentru modelarea vntului, verificarea traiectoriei, coordonare,

    secveniere Belief-accessible worlds: traiectorii posibile, n funcie de viteza

    vntului, viteza i altitudinea minim i maxim Desire-accessible worlds: ETA calculat = ETA dorit (timpul estimat de

    sosire)

    Intention-accessible worlds: cele mai bune traiectorii dorite din punctde vedere al consumului de carburant, performanele aparatului dezbor etc.

    Agentul secveniator delibereaz pentru a determina secvena optimde aterizri

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    51/74

    51

    Naveta spaial Discovery

    Sistem pentru monitorizarea defeciunilor n timp real Arhitectura unui modl PRS:

    O baz de date ce cuprinde convingerile curente alesistemului despre mediul de execuie

    O mulime de scopuri curente O bibliotec de planuri (sau proceduri) numite arii de

    cunotine (engl. Knowledge Areas, KA), care descriusecvene de aciuni i teste care trebuie efectuate pentru aatinge scopuri sau pentru a reaciona la unele situaii

    O structur de intenii, cu o mulime (parial) ordonat deplanuri alese pentru execuie

    Mai multe instane ale sistemului pot rula n paralelFlorin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    52/74

    Sistemul de raionament procedural

    52Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    53/74

    53

    Bucla principal a PRS

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    54/74

    54

    Exemplu: izolarea scurgerilor

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    55/74

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    56/74

    Arhitecturile stratificate

    Pentru multe probleme, nu sunt potrivite niciabordrile pur deliberative, de exemplu cu planificarecomplet, i nici cele pur reactive

    Arhitecturile stratificate (hibride) ncearc s combineaceste dou metode

    Au mai multe straturi, cel puin: Un strat reactiv, care nu implic raionamente complexe Un strat deliberativ, bazat pe un model simbolic al mediului

    Straturile sunt dispuse ntr-o ierarhie, cu diferiteniveluri de abstractizare

    56Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    57/74

    Straturile

    Trei straturi sunt suficiente pentru majoritateasituaiilor Pot exista ns oricte straturi

    Nivelul inferior: strat reactiv De obicei, implementare asemntoare cu aceea din

    arhitectura lui Brooks

    Nivelul mediu: stratul cunotinelor Reprezentarea simbolic a mediului

    Nivelul superior: stratul social Reprezentarea altor ageni cu scopurile, convingerile lor etc.

    57Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    58/74

    Tipuri de stratificare

    Stratificarea orizontal Fiecare strat are acces la

    percepii i aciuni

    Stratificarea vertical Percepiile i aciunile sunt

    tratate de un singur strat

    Control cu o trecere sau cudou treceri

    58Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    59/74

    Stratificarea orizontal

    Straturile concureaz pentru determinarea aciunii

    Este nevoie de un mediator, care decide stratul care

    controleaz agentul la un moment dat Mediatorul poate fi greu de proiectat: pentru n

    straturi i maciuni, exist mninteraciuni posibile De exemplu: 3 straturi, 2 aciuni, 23= 8 interaciuni

    (fiecare strat poate alege orice aciune)

    59Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    60/74

    Stratificarea vertical Prezint similariti cu modul n care funcioneaz organizaiile

    Informaiile se trimit spre nivelurile superioare

    Deciziile de execuie se trimit spre nivelurile inferioare

    Complexitatea interaciunilor dintre straturi este mai redus:m2(n-1)posibiliti n-1interfee ntre nstraturi, fiecare strat poate propune maciuni

    iar perechile de straturi adiacente pot propune m2combinaii deaciuni

    Scade tolerana la defecte Defectele dintr-un strat pot afecta ntregul comportament al

    agentului

    60Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    61/74

    TouringMachines

    61

    Ferguson, 1992

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    62/74

    Straturile

    Arhitectura const n trei niveluri deproducere a activitilor(engl. activity

    producing layers) Stratul reactiv Stratul de planificare

    Stratul de modelare

    Scenariul iniial: vehicule autonome

    62Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    63/74

    Stratul reactiv

    Are ca scop evitarea obstacolelor

    Poate trata doar starea curent n partea dreapt sunt doar aciuni, nu i alte predicate Exemplu de regul reactiv:

    63Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    64/74

    Stratul de planificare

    Asigur comportamentul proactiv al agentului,ce trebuie s fac agentul n mod normal

    Folosete o bibliotec de planuri, numitescheme

    Schemele sunt planuri organizate ierarhic ipot conine sub-scopuri

    64Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    65/74

    Stratul de modelare

    Reprezint diferitele entiti din mediu Agentul nsui

    Ali ageni ncearc s prezic i s rezolve conflictele Noile scopuri generate sunt trimise stratului

    de planificare, care i folosete biblioteca deplanuri pentru a ncerca s le satisfac

    65Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    66/74

    Subsistemul de control

    Conine reguli care decid ce strat controleaz agentul Regulile de control pot suprimainformaii senzoriale sau

    cenzura aciuni Exemplu de regul de cenzur (stratul reactiv nu mai tie

    c a fost detectat un obstacol iar tratarea acestei situaiitrebuie fcut de un strat superior):

    66Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    67/74

    InteRRap

    67

    Mller, 1997

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    68/74

    Straturile

    Stratul de comportament: reactiv

    Stratul de planuri: planificarea curent Stratul de cooperare: interaciuni sociale Fiecare strat are o baz de cunotine: reprezentarea

    mediului pentru acel strat

    Straturile au reprezentri cu niveluri diferite deabstractizare Comportament: informaii senzoriale brute despre mediu Planuri: planurile i aciunile agentului nsui Cooperare: planurile i aciunile altor ageni

    68Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    69/74

    Interaciunile

    Straturile interacioneaz Tipuri de interaciuni:

    Activare de jos n sus Un strat trimite informaiile mai sus pentru c nu are

    competena necesar s le trateze

    Execuie de sus n jos Un strat superior folosete un strat inferior pentru a-i

    atinge scopurile

    69Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    70/74

    Funciile straturilor

    Fiecare stratndeplinete dou funciigenerale:

    Recunoaterea situaiilor i activarea scopurilor Similar cu funcia optionsdin BDI Planificare i programare (engl. scheduling)

    Selectarea planurilor de executat

    70Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    71/74

    Stanley

    Vehicul autonom care actigat competiia DARPAGrand Challenge din 2005 211 km parcuri prin deertul

    Mojave din Nevada

    Premiu de 2.000.000 USD

    43 de echipe nscrise, 23 definaliti, doar 5 vehicule auterminat cursa

    Stanley a terminat traseul n6 ore i 53 minute, cu o vitezmedie de 30 km/h

    71

    Thrun, 2005

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    72/74

    72

    Arhitectura lui Stanley

    30 de module independente, organizate n 6 straturi

    Stratul de interfa senzorial Primete datele de la senzori i le adaug marcaje temporale

    (time stamps) Datele vin cu frecven ridicat, de exemplu 5 lasere trimit date

    de 100 de ori pe secund

    Stratul de percepie Transform datele senzoriale cu marcaje temporale n modele

    interne, reprezentnd starea vehiculului/agentului i starea mediului Starea vehiculului: 15 variabile de stare, de exemplu poziie, vitez,

    orientare, acceleraie etc. Starea mediului: cartografierea terenului, identificarea drumului etc.

    Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    73/74

    Arhitectura lui Stanley

    Stratul de planificare i control Gsirea cii, orientarea volanului, accelerare i frnare

    Stratul de interfa cu vehiculul

    Interfaa dintre sistemul de control i actuatori Stratul de interfa cu utilizatorul

    Ecran cu atingere tactil (touch-screen) pentru pornireasistemului

    Stratul de servicii globale

    Servicii folosite de toate modulele, de exemplu stocarea deinformaii n fiiere, ceasul sistemului etc.

    Dificultatea principal a fost legat de percepie: construireasenzorilor i interpretarea informaiilor senzoriale

    73Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

  • 7/31/2019 Sisteme multiagent. Arhitecturi de agenti 2

    74/74

    Avantaje i dezavantaje

    Arhitecturile stratificate permit o descompunerenatural a funcionalitilor

    Sunt soluii pragmatice Claritatea semantic este mai redus dect n

    abordarea logic

    Interaciunile dintre straturi trebuie luate nconsiderare