11/29/2015 1 Universitatea ”Vasile Alecsandri” din BACĂU Departamentul E.S.C. Sisteme Multiagent MODELE ARHITECTURALE DE AGENŢI “Intamplarea este singurul stăpân legitim al Universului.” Napoleon Models of agency and architectures 14 Bacău 29.11.2015 [email protected]pruteanue.ub.ro xyz 2 2 3 4 Arhitecturi Abstaracte. Structura conceptuala a agentilor Arhitecturi de agenti cognitivi Arhitecturi de agenti reactivi Arhitecturi stratificate 1 puteanue.ub.ro 1. Arhitecturi abstracte. Structura concptulă a agenților Scop: proiectarea unui algoritm/functie/program care realizeaza corespondenta sensori - efectori Agent = architectura + program Definitie Arhitecturi abstracte I masura a performantei: Structura conceptuala a agentilor Schema generala a unui agent mobil Sistemul perceptiv poate fi: pasiv - percepţiile sunt ceea ce sesizează în mod direct agentul; (În sistemele pasive, elementele care captează informaţiile generează semnale elementare care sunt pre-prelucrate, segmentate, ceea ce formează faptele elementare care conduc la recunoaşterea obiectelor, scenelor, cuvintelor, frazelor.) activ - percepţiile sunt rezultatul construcţiilor care depind de scheme perceptive anterioare, care sunt construite progresiv prin interacţiunile cu alţi agenţi sau cu mediul. percepţie, definită ca modalitatea prin care agentul preia informaţii din mediu
Transcript
11/29/2015
1
Universitatea ”Vasile Alecsandri” din BACĂU
Departamentul E.S.C.
Sisteme Multiagent
MODELE ARHITECTURALE DE AGENŢI
“Intamplarea este singurul stăpân legitim al Universului.”
A delibera = a examina in detaliu, a rezolva, a solutiona
decizia este realizată prin deducţie logică
starea internă este o bază de date de formule în logica
predicatelor de ordinul întîi:
Exemple:
• Open(electrovalva, 08)
• Temperatura(rezervor, 05, 56)
• Presiune(rezervor, 07, 21)
Exemplu de agent bazat pe logică:
Virtual Cleaner
• curăţarea unei celule din reţea;
• înaintarea către o celulă vecină;
• rotirea la dreapta cu 90°.
Proprietăţile agentului se referă la:
poziţia curentă în reţea (linia şi coloana unde se găseşte
la un moment dat);
orientarea curentă (spre nord, est, sud sau vest).
Tra
seu
l agen
tulu
i
Vir
tual
Cle
an
er
Isln(x,y) - agentul este în căsuţa de pe linia x şi coloana y;
EnvHasDust(x,y) - elementul de pe coloana x şi linia y este curat
sau nu;
Faces(orientation) - agentul este orientat înspre unul din cele patru
puncte cardinale.
Formulele predicative utilizate sunt:
Do(clean) - curăţare: EnvHasDust(x,y) devine false;
Do(forward) -înaintare: coordonatele (x,y) se modifică în funcţie de
orientarea agentului;
Do(turn) - rotire la dreapta: orientarea agentului se schimbă.
Acţiunile posibile ale agentului, ale căror semnificaţii s-au amintit
anterior, sunt:
if Isln(x,y) and EnvHasDust(x,y) then Do(clean)
Prima regulă de inferenţă este:
Bacău 29.11.2015 1. 36
SISTEME
MULTIAGENT
II. Arhitecturi reactive (Brooks, 1986)
B. Arhitecturi de subsuare
Genlități despre Arhitecturi reactive A
Mo
del
are
agen
ti
11/29/2015
6
Nu folosesc reprezentari simbolice sau rationament.
Unitati de prelucrare simple care percep mediul (cu senzorii) si
reactioneaza la schimbarile din mediu (cu efectori);
Comportamentul rational este legat intrinsec de mediu;
Comportamentul inteligent - Inteligenta rezulta din
interactiunea entitatilor cu mediu, nu este situata la nivel
individual ci la nivelul sistemului si este distribuita in sistrm–
“emergence” (emerge din combinarea mai multor
comportamente rationale simple);
Mo
del
are
agen
ti
b) Arhitecturi reactive (Brooks)
function action(p: P): A
var fired: (R)
var selected: A
begin
fired := {(c,a) | (c,a) R şi p c}
for each (c,a) fired do
if ( (c',a') fired a.î. (c',a') (c,a)) then
return a
end if
end for
return null
end function action
Agenţi pur reactivi
situaţie acţiune specifică
Fie Beh mulţimea tuturor astfel de reguli („behaviour", comportament):
Un comportament este o relaţie (c, a), unde cP este o mulţime
de percepţii numite condiţii, iar aA este o acţiune
Cu mulţimea de reguli de comportament ale agentului RBeh este
asociată o relaţie de inhibiţie binară definită pe mulţimea de
comportamente: RxR, tranzitivă, nereflexivă şi antisimetrică:
MEDIU
AGENT SEE ACTION
MEDIU
AGENT SEE ACTION
NEXT STARE
Age
nt
pur
reac
tiv
Age
nt
cu s
tări
Nivelul 0: evitarea coliziunilor cu obiecte statice sau în mişcare;
Nivelul 1: mişcarea aleatorie cu evitarea coliziunilor;
Nivelul 2: explorarea împrejurimilor şi marcarea locurilor inaccesibile;
Nivelul 3: alcătuirea unei hărţi a mediului şi stabilirea rutelor dintre diverse
locaţii;
Nivelul 4: recunoaşterea schimbărilor din mediu;
Nivelul 5: recunoaşterea obiectelor şi sarcinilor aferente acestora;
Nivelul 6: formularea şi executarea planurilor pentru schimbarea mediului într-o
manieră semnificativă;
Nivelul 7: conceperea unor modalităţi de control al obiectelor din mediu şi
reconsiderarea în consecinţă a planurilor existente.
Arhitectura propusă de Brooks se referă în principal la agenţi
robotici. În acest caz, nivelele de competenţă pot avea
semnificaţiile din exemplul următor:
Problema inteleptilor (The wise men problem)
Regele marcheaza pe fruntea robilor cate o pata alba si spune ca
„cel putin o pata este alba” și fiecare trebuie să determine culoarea
petei de pe fruntea lor. După puțin timp cel mai înțelept anunță că
pata albă se află pe fruntea lui.
11/29/2015
7
Problema prazilor si vanatorilor
(The problem of pray and predato r)
Exemplu de agent reactiv:
un cuvânt poate apărea într-una din următoarele culori (figura 4):
• negru - cuvântul este corect;
• violet - cuvântul nu se găseşte în dicţionar;
• albastru - cuvântul nu a fost încă verificat.
Interfaţa programului Spell-Checker Agent
Bacău 29.11.2015 1. 54
SISTEME
MULTIAGENT
Arhitectura programului Spell-Checker Agent.
Modul de funcţionare al agentului este determinat de o serie de
comportamente de tip reactiv:
Nivelul 0: Evită accesarea mediului în acelaşi timp cu utilizatorul
Nivelul 1: Ignoră cuvântul în curs de editare
Nivelul 2: Ignoră cuvintele deja verificate şi separatorii
Nivelul 3: Caută în dicţionar forma cuvântului şi schimbă atributul
corespunzător în corect sau incorect
Ierarhia nivelelor: Nivelul 0 < Nivelul 1 < Nivelul 2 < Nivelul 3
Analiza programului. - se vor analiza caracteristicile agentului
şi ale mediului de execuţie.
1. Autonomia sa este asigurată de faptul că acţionează într-un
thread separat de programul principal.
2. Reactivitatea - răspunde schimbărilor din mediu, adică apariţiei
noilor cuvinte, prin verificarea şi marcarea corespunzătoarea a
acestora. Deşi conceput ca un agent reactiv, comportamentul său
global poate fi considerat proactiv: scoaterea în evidență a greşelilor
de ortografie a textului.
3. Abilităţile sociale - nu este un sistem multiagent (nu pot fi
studiate).
comportarea in colectivitate a entitatilor din sisteme descentralizate si cu auto-organizare;
Agenti reactivi, emergenta comportarii colective
– Furnici; pasari; albine; colonii salbatice;
ACO = (at colony optimization) = algoritm de optimizare pentru rezolvarea problemelor de optimizare bazat pe colonii de furnici artificiale care folosesc depunerea de feromoni artificiali
Proiectul Swarm http://www.swarms.org/
Swarm intelligence Avantaje
Simplitate, robusteţe, economie, calcule mai rapide;
Dezavantaje
trebuie să aibă informaţii consistente locale despre
mediu, deoarece nu au un model al mediului;
dinamica interacţiunilor devine prea complexă;
agenţii nu prea pot învăţa din propria experienţă;
metodologia nu este clară pentru construirea acestor
sisteme;
metoda se bazeaza pe „încercare şi eroare”;
„gândesc” pe termen scurt;
agenţi cu multe straturi de comportament sunt greu de
construit in special daca este (> 10);
dificultate la înţelegere comportamentului global;
