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