sisteme multiagent. arhitecturi de agenti 1

7/31/2019 Sisteme multiagent. Arhitecturi de agenti 1

1/64

Modelarea i analizasistemelor multi-agent

2. Arhitecturi de ageni (I)

Florin Leon

Universitatea TehnicGheorghe Asachi 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


2/64

2

Arhitecturi de ageni (I)1. Arhitecturi abstracte

2. Arhitecturi logice

3. MetateM

4. Arhitecturi reactive

5. Arhitectura de subsumare



3/64

3

Arhitecturi de ageni (I)1. Arhitecturi abstracte


3. MetateM





4/64

4

Definiie O arhitectur de ageni este o anumit metodologie

pentru construirea agenilor, care specific n ce modpoate fi un agent descompus ntr-o mulime demodule i cum trebuie s interacioneze acestea.Mulimea total a modulelor trebuie s precizeze nce mod datele de la senzori i starea curent aagentului determin aciunile i urmtoarea stare

intern a agentului. O arhitectur cuprinde tehnicilei algoritmii care stau la baza acestei metodologii.(dup Pattie Maes)



5/64

5

Formalizare: agent imediu Strile mediului

S= { s1, s2, ... }

Aciunile posibile, date de capacitatea efectoric A= { a1, a2, ... }

Un agent standard poate fi vzut ca o funcie: action : S*A

S*este mulimea irurilor de elemente ale lui S

Comportamentul mediului: env : SxA(S)

(S)este mulimea prilor lui S



6/64

6

Determinismul mediului Mediu determinist

env(s,a) are o singur valoare (singleton)

Mediu nedeterminist env(s,a) are mai multe valori



7/64

7

Istoricul Modalitate de reprezentare a interaciunilor

dintre agent i mediu

starea iniial



8/64

8

Proprietate invariant O proprietate invariant a sistemului se

pstreaz n toate istoricele posibile De exemplu:

Agent controller de reactor nuclear

Proprietate invariant: reactorul nu explodeaz



9/64

9

Echivalen comportamental hist(ag, env) = mulimea tuturor istoricelor agentului

agn mediul env

Agenii ag1i ag2sunt echivaleni comportamentaln mediul envdac i numai dachist(ag1, env) = hist(ag2, env)

Agenii ag1i ag2sunt echivaleni comportamentaldac i numai dac hist(ag1) = hist(ag2) pentru toatemediile



10/64

10

Agent pur reactiv Un agent pur reactiv decide aciunile fr a-i

lua n considerare istoricul

action : SA Sn loc de S*

Exemplu: termostatul



11/64

11

Percepia i aciunea see : SP

ieirea funciei see

este un percept precept (principiu,

norm)

action: P*A

s1, s2S, s1s2, dar see(s1) = see(s2) s1i s2sunt stri indistinctibile



12/64

12

Exemplu: stri indistinctibile Pentru un termostat, combinaia de stri:

Temperatura este OK (x)

Ciolo este prim-ministru (y)



13/64

13

Capacitatea perceptiv

Agent fr capacitate perceptiv| E| = 1

Agent omniscient| E| = | S|

E= mulimea strilor diferite perceputeS= mulimea tuturor strilor



14/64

14

Ageni cu stare Agentul pornete cu starea

intern it= i0 Observ starea mediului s

p= see(s)

i actualizeaz starea intern it+1= next(it,p)

Selecteaz o aciune a= action(it+1) Repet de la observare

see: SP

next : Ix PI

Ieste mulimea strilor interne

action: IA



15/64

15

Arhitecturi de ageni La nceput (pn n 1985), aproape toi agenii

proiectai n cadrul cercetrilor de IA au folositraionamentul simbolic Raionament logic explicit pentru a decide aciunile

Problemele legate de raionamentul simbolic auprovocat o reacie mpotriva acestei abordri,micarea agenilor reactivi (dup 1985)

Din 1990, au fost propuse o serie de alternative:arhitecturi hibride, care ncearc s combineavantajele arhitecturilor simbolice i a celor reactive



16/64

16

Arhitecturi de ageni

Patru clase principale de arhitecturi:

DeliberativeAgeni folosind raionamentul deductivAgeni folosind raionamentul practic

Reactive

Hibride



17/64

17

Arhitecturi de ageni (I)

1. Arhitecturi abstracte


3. MetateM





18/64

18

Arhitecturi logice

Abordarea tradiional pentruconstruirea de sisteme

inteligente Reprezentare simbolic a

mediului i comportamentului Formule logice

Manipulare sintactic aacestei reprezentri Deducii logice sau

demonstraii de teoreme



19/64

19

Ageni deliberativi

A delibera = a examina n detaliu, a rezolva,a soluiona

Folosesc formule ale logicii predicative deordin I

Exemple:



20/64

20

Comportamentul

L= mulimeapropoziiilor logice deordin I

D= (L) Starea intern a unui

agent este un elemental lui D

Notmdac formula poate fidedus din folosinddoar regulile dededucie

see: SP

next: Dx PD

action: DA



21/64

21

Pseudocod

ncearc apoi sgseasc o aciunecoerent (care nu esteinterzis explicit)

ncearc mai nti s

gseasc o aciune carepoate fi dedus din bazade date



22/64

22

Lumea aspiratorului

Percepte: dirt(murdrie), null Aciuni: forward(un pas nainte), suck(aspir),

turn(ntoarcere la dreapta cu 90)

Predicatele domeniului:



23/64

23

Reguli



24/64

24

Raionalitate computaional

engl. calculative rationality Un program care, dac s-ar executa infinit de rapid,

ar demonstra un comportament perfect raional Un program de ah cu raionalitate computaional

ar alege mutarea optim, dar luarea deciziei ar puteadura un miliard de ani

Demonstrarea de teoreme este lent Dac mediul se poate schimba mai repede dect

viteza de decizie a agentului, raionalitateacomputaional este inacceptabil



25/64

25

Discuie

Avantajele arhitecturilor logice

Semantic simpl, elegant

Formalizare foarte bun

Exist multe sisteme de demonstrare automat a teoremelor

Probleme

Transformarea strilor mediului n reprezentare simbolic

De exemplu extragerea de proprieti declarative din imagini Modele neintuitive, complicate

Complexitatea computaional



26/64

26




3. MetateM





27/64

27

Propoziii temporale

antecedent(despre trecut) consecvent(despre prezent i viitor)

Pe baza informaiilordespre trecut,acioneazn prezent i viitor

MetateM face distincie ntre aciunile

agentului i aciunile mediului



28/64

28

Notaii



29/64

29

Definiii temporale

Since: este satisfcut acum dac este adevrat la un moment n trecut i este adevratla orice moment dup acel moment

Zince(since slab): este satisfcut acum dac ( este adevrat la un moment n trecut ieste adevrat la orice moment dup acel moment) SAU s-a ntmplat ntotdeauna n trecut

Until: este satisfcut acum dac este adevrat la un moment n viitor i este adevrat laorice moment nainte de acel moment

Unless: este satisfcut acum dac ( este adevrat la un moment n viitor i esteadevrat la orice moment nainte de acel moment) SAU se va ntmpla ntotdeauna n viitor



30/64

30

Definiii temporaleeste un ir de stri s1, s2, ...ieste indexul de timp (acum)



31/64

31

Definiii temporale



32/64

32

Teorema separaiei

formul despretrecut

formul despreprezent i viitor

Dac ieste adevrat la momentul de timp n,atunci execut i



33/64

33

Exemplul 1: mbinarea cozilor

Dou cozi la aeroport: ceteni (1) i strini(2) Un singur ghieu al poliiei de frontier

b= coada 1 este mai mare dect coada 2 m1: preia din coada 1

m2: preia din coada 2

Reguli:



34/64

34

Exemplul 2: manager deresurse

Dac o resurs este cerut de un proces,atunci va trebui la un moment dat alocat

acelui proces Dac resursa nu este cerut, atunci nu

trebuie alocat La un moment dat, resursa trebuie alocat cel

mult unui singur proces



35/64

35

Reguli de execuie

Dac un proces a cerut resursa la momentul anterior, i se va aloca cndva n viitor

Dac un proces nu a cerut resursa niciodat (r1 din definiia zince) SAU la un momentdat i-a fost alocat i nu a cerut-o atunci (a1 r1 de dup ) iar din acel moment nu a maicerut-o din nou (r1dinaintea lui ), atunci nu trebuie s-i fie alocatresursa (a1)

Dat fiind orice moment anterior, resursa nu poate fi alocat simultan ambelor proceseFlorin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm


36/64

Limbajul MetateM// The agent that says 'hello' to everyone it knows

type agent;

ability send: metatem.agent.ability.Send;

ability print: metatem.agent.ability.Print;

logging FINE;

ruleblock: {

start => greet ;

greet & in(X,known) => NEXT send(X,hello);

receive(From, Message) => NEXT print("Received message, ", Message, ", from ", From, ".");

}

( http://www.csc.liv.ac.uk/~anthony/metatem.html )

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


37/64

37




3. MetateM





38/64

38

Caracteristici

Comportamentul este definit de reguli de tipul:situaie aciune

Mai multe comportamente se pot aprinde(engl. fire) simultan De exemplu regulile CLIPS/Jess sau Jason

Comportamentele sunt aranjate pe straturi

Cu ct un strat este mai jos, cu att are prioritate mai mare Straturile inferioare pot inhiba straturile superioare

Exemplu: dac i se apropie cuiva o musc de ochi, nchideochii din reflex, chiar dac atunci era concentrat s citeasco carte



39/64

39

Comportamentul

Comportamentul este o pereche (c, a)

cPeste o condiie, aAeste o aciune

Comportamentul se va aprinde dac:see(s) c, cu sS

Beheste mulimea tuturor perechilor (c, a)

Relaie de inhibiie:

Rx R, cu RBeh Notaie: b1b2dac (b1, b2)

b1inhib b2



40/64

40

Pseudocod



41/64

41

Exemplu

Explorarea unei planete i colectarea unor roci Reguli:

1. Dacdetectezi un obstacol, atuncischimb direcia 2. Dactranspori roci i eti la baz, atuncidescarc rocile 3. Dactranspori roci i nu eti la baz, atuncimergi n

sensul creterii gradientului semnalului de la baz 4. Dacdetectezi o roc, atunciridic-o

5. Dac(adevrat), atuncimergi aleatoriu Ierarhia de comportamente:

1 2345

Comportamentul global este emergent



42/64

42

Cooperare

Rocile pot fi grupate n anumite locuri

Agenii las urme de particule radioactive

cnd gsesc roci i se ntorc la baz Ali ageni le urmeaz n sensul descresctor

al gradientului semnalului i ridic particule

Intensitatea urmei scade



43/64

43

Cooperare

Noi reguli:

6. Dactranspori roci i nu eti la baz, atunci

las 2 particule i mergi n sensul creteriigradientului semnalului de la baz

7. Dacpercepi particule atunciridic 1 particuli mergi n sensul descreterii gradientuluisemnalului de la baz

Ierarhia de comportamente:

1 26475



44/64

Discuie Avantaje

Simplitate, economie, calcule mai rapide, robustee, elegan

Dezavantaje

Neavnd modele ale mediului, agenii trebuie s aib suficienteinformaii locale. Implicit vor gndi pe termen scurt Nu este evident cum ar putea nva agenii din propria experien Emergena implic dificultatea de nelegere a comportamentului

global

Nu exist o metodologie clar pentru construirea unor astfel de sisteme Metodancercare i eroare

Sunt greu de constuit ageni cu multe straturi de comportament(de exemplu > 10)

Dinamica interaciunilor devine prea complex Posibil soluie: ageni care evolueaz



45/64

45




3. MetateM4. Arhitecturi reactive




46/64

46

Arhitectura de subsumare

engl. subsumption architecture

Propus de Rodney Brooks n 1986 pentru roboi A Robust Layered Control System for a Mobile Robot

Extins ntr-o nou perspectiv asupra inteligeneiartificiale

Intelligence without Reason

Intelligence without Representation



47/64

47

Musca i robotul O musc probabil:

Nu i construiete odescriere 3D a obiectelor

Nu raioneaz asupraameninrii unui om cu opalet sau despreconvingerile i scopurileacestuia

Nu i construiete teorii

fizice elementare asupraaterizrii pe tavan

ns musca probabil: Are legturi strnse ntre

senzori i efectori Are modele pre-cablate de

comportament

Are tehnici de navigaiesimple

Funcioneaz aproape ca omain determinist

i totui se descurc maibine n lumea real dectmuli roboi inteligeniconstruii de om pn acum



48/64

48

Metode anterioare de controlpentru roboi

Foloseau o abordaredivide-et-impera Percepie (senzori) modelareplanificareexecuie

control motoraciune (efectori)

Opinia lui Brooks: Inteligena de nivel uman este foarte dificil de implementat

i nu este singurul tip de inteligen Abordarea divide-et-impera a condus la blocaje n

rezolvarea unor probleme irelevante

Modelul rezultat nu are robostee Toatesubsistemele sunt necesare pentru ca robotul s

funcioneze



49/64

49

Motivaie

Brooks consider comportamentul uman doaraparent raional Acesta ar fi expresia extern a unor comportamente

independente fr control central

Se urmeaz calea evolutiv a inteligenei Se ncepe cu o inteligen simpl, mai uor de implementat

dect inteligena uman

Dup asigurarea succesului, modelul se extinde cu nivelurimai nalte de inteligen

Model robust deoarece straturile inferioare pot funciona ncontinuare chiar i atunci cnd straturile superioare eueaz



50/64

50

Idei de baz

Comportamentul inteligent:

Nu necesit reprezentri explicite

Nu necesit raionamente abstracte (simbolice)

Emerge din interaciunea unor comportamente simple

Raionalitatea necesit un mediu

Scopul lui Brooks era s dezvolte creaturi artificiale

complete, capabile s acioneze n lumea real, nuntr-un mediu simplificat



51/64

51

Arhitectura de subsumare

Metodologie stratificat pentru sisteme de control al roboilor Straturile inferioare sunt asemntoare reflexelor Straturile superioare permit atingerea unor scopuri de nivel mai

nalt



52/64

52

Automate finite augmentate

Fiecare strat este format din procesoare simple conectate:automate finite augmentate (engl. augmented finite statemachines) Automate finite completate cu cronometre


l


53/64

53

Aspecte importante aleautomatelor

Ieirile sunt funcii simple de intrri i starea intern

Intrrile pot fi suprimate (suppressed)

Ieirile pot fi inhibate (inhibited) Aceasta permite straturilor superioare s subsumeze

funciile straturilor inferioare Pentru ca o situaie s fie tratat pe un strat superior,

intrarea unui strat inferior este suprimat i acesta nu maitie de existena situaiei

Straturile inferioare continu s funcioneze la fel can absena straturilor superioare



54/64

Subsumarea

Fiecare strat are acces direct la informaiile senzoriale dinmediu

Fiecare strat are propriul scop

Straturile lucreaz concurent i asincron Suprimarea substituie semnalul de intrare al unui automat

dintr-un strat inferior cu semnalul dat de pe un nivelsuperior

Inhibiia elimin semnalul de ieire al unui automatdintr-un strat inferior Noi straturi pot fi adugate deasupra unora existente, fr

a fi nevoie de modificarea straturilor inferioare



55/64

Caracteristici

Nu exist o ierarhie clasic a straturilor de tipulsubsistemelor, subrutinelor etc.

Nu exist sincronizare Mesajele pot fi pierdute fr notificare Trebuie retrimise de mai multe ori

Straturile funcioneaz n paralel Se poate folosi mediul extern pentru comunicare

Strile automatelor se schimb cnd primesc mesajesau cnd expir perioada de timp desemnat Robotul Herbert: o stare dureaz maxim 3 secunde



56/64

Roboii lui Brooks

Allen Evit obstacolele i sendreapt ctre o locaie

Herbert Gsete cutii de suc i le aduce la locaia de start



57/64

Allen

Stratul 0 Evit obstacolele, fuge dac se apropie ceva

Stratul 1 Se adaug deplasarea aleatorie

Stratul 2 Se adaug urmrirea unui obiectiv ndeprtat


St t l 0


58/64

58

Stratul 0 Evit obiecte statice sau n micare Folosete 12 sonare cu ultrasunete: 12 msurtori pe secund,

cu zgomot puternic Calculeaz o for de respingere rezultant pe baza ponderilor

proporionale cu 1 / d2

Aciuni: st pe loc sau fuge


St t l 1


59/64

59

Stratul 1 Deplasare cu un unghi aleatoriu, schimbat o dat la 10 secunde Direcia aleas d o for de atracie



60/64

Stratul 2

Asigur explorarea la distan Inhib micarea aleatorie din stratul 1 Suprim intrarea n modulul avoid, pentru a injecta

noua comand de direcie pathplancomand direcia integrateasigur actualizrile pentrupathplan,

folosind un motor de diferene: foreaz robotul s sedeplaseze n direcia dorit, compensnd modificriledate de evitarea obstacolelor



61/64



62/64

Herbert

Dispozitive

Scanner cu laser pentru a gsi cutiile

Senzori de proximitate cu infrarou pentru a identifica pereii

Busol magnetic pentru a se orienta Senzori pe mn pentru apucarea cutiilor

Nu exist comunicare direct ntre straturile interne Cnd se opresc roile, pornesc senzorii pentru cutii

Cnd o cutie este ntre degete, apuc i trage mna

Reguli diferite nainte i dup gsirea unei cutii Pe baza condiiei de separare a degetelor

Navigare pentru a se ntoarce n locaia iniial: dup ce treci de ou mergnd spre sud, ntoarce-te la stnga



63/64

Toto (Mataric)

Robotul construiete un graf intern, corespunztorhrii mediului

Se aloc autonom noduri noi pentru repere noi i se

actualizeaz relaiile de vecintate Pentru deplasarea la o anumit locaie, se produce o

excitaie n graful intern a locaiei scop Excitaia se rspndete pn la locaia curent,

analog cu un plan

Cnd robotul se mic, se schimb i reprezentarealocaiei



64/64

Aspecte tipice ale arhitecturii

Sistemele cu subsumare pot face predicii, planuri ipot avea scopuri, fr reprezentri centralizate,manipulabile i simbolice

Nu necesit modele ale lumii reale Nu exist comunicare de nivel nalt ntre straturi

Nu exist memorie comun

Lumea real este folosit drept model Lumea real este propriul su model

Acuratee

Nu sunt necesare calcule pentru actualizare

sisteme multiagent. arhitecturi de agenti 1

Documents