Str. Calea Mărășești, nr. 157, Bacău, 600115 [610240]
ROMÂNIA
MINISTERUL EDUCAȚIEI NAȚIOANALE
UNIVERSITATEA Vasile Alecsandri din BACĂU
FACULTATEA DE ȘTIINȚE
Str. Calea Mărășești, nr. 157, Bacău, 600115
Tel. +[anonimizat], tel./ fax +[anonimizat]
www.ub.ro ; e-mail: [anonimizat]
FACULTATEA DE ȘTIINȚE
INFORMATICĂ
INVĂȚĂMÂNT CU FRECVENȚĂ REDUSĂ
Sisteme Multiagent
AUTOR:
Pruteanu Eusebiu
Curs pentru studenții la IFR
OBIECTIVELE DISCIPLINEI
1. introdu cere in problematica agentilor inteligenti si a sistemelor
multi -agent,
2. prezentarea tehnologiilor, caracteristicile specifice folosite în
implementarea agenților inteligenți,
3. cunoașterea bazelor teoretice specifice sistemelor multiagent
(SMA),
4. insușirea metodelor de raționament ale agenților inteligenți,
tehnicilor de căutare distribuită, de planificare mono – și multi –
agent, mecanismelor de coordonare și comunicare între agenți, de
negociere pentru realizarea contractelor,
5. învățarea abordărilor analitic e și numerice în analiza și
implementarea SMA.
COMPETENȚE ASIGURATE PRIN
PARCURGEREA DISCIPLINEI (grila 2 rncis , fisa
disciplinei )
1. cunoașterea noțiunilor de agent software, agent inteligent, sistem
multiagent, programare orientată agent. a tendințel or si noile
posibilități oferite de agentii inteligenti, software si sistemele
multi -agent; cum se dezvoltă sistemele multi -agent și care sunt
principiile lor arhitecturale;
2. utilizarea sistemelor multi -agent in diferite domenii si aplicatii
diverse;
3. elemen te de baza ale programarii in limbajul JAVA;
4. clasificarea agenților și a sistemelor multiagent, definiții,
arhitecturi stratificate, logice, BDI
5. comunicarea în SMA, negocierea, tocmeala, încrederea între
agenți; agenți cu emoții, etc.
FOND DE TIMP ALOCAT, FORME DE
ACTIVITATE, FORME DE VERIFICARE,
CREDITE (fișa disciplinei)
Forma de activitate Număr ore
semestru Număr credite
Lucrări practice/seminar 42
Studiu individual 42
Verificare finală Examen 4
STABILIREA NOTEI FINALE (fișa disciplinei)
Forma de verificare (Examen, Colocviu,
Verificare pe parcurs) Examen
Modalitatea de susținere (Scris și Oral,
Oral, Test grilă, etc.) Scris Puncte sau
procentaj NOTARE Răspunsurile la examen/colocviu/lucrari practice 4(40%)
Activitati aplicative atestate /laborato r/lucrări practice/proiect
etc 2,5(25 %)
Teste pe parcursul semestrului 1,5(15%)
Teme de control 2(20%)
TOTAL PUNCTE SAU PROCENTE 10 (100%)
TIMP MEDIU NECESAR PENTRU ASIMILAREA
FIECĂRUI MODUL
Nr.
Crt. Denumire modul /tema ( obligatoriu,
un modul/ tema are 2 -3 ore) Timp mediu necesar
SI LP Total
1 Agenții inteligenți, utilitatea lor și
poziționarea în cadrul domeniului mai
larg al Inteligenței Artificiale
2 Arhitecturi, tipuri și sisteme de
agenți;
3 Comunicația între agenți si p latformă
4 Sisteme multiagent
5 Inteligența Artificială Distribuită
Timp total necesar
INSTRUCȚIUNI PENTRU PARCURGEREA
RESURSEI DE ÎNVĂȚĂMÂNT
Prezenta resursă de învățare conține toate informațiile necesare
însușirii cunoștințelor teor etice și metodice referitoare la exercițiul fizic și
specificitatea aplicării lui în educație fizică și sport.
Conținutul este structurat în module, în cadrul fiecărui modul
regăsindu -se unul sau mai multe unități de studiu, în așa fel încât să eșaloneze
și să faciliteze parcurgerea materialului și însușirea sa.
Pentru parcurgerea resursei de învățământ se recomandă următoarea
succesiune:
1. Citirea, cu atenție, a fiecărei unități de studiu și, consultarea
recomandărilor bibliografice în legătură cu aceasta.
2. Parcurgerea rezumatului fiecărei unități de studiu.
3. Rezolvarea temelor de autoevaluare (pentru fiecare unitate de studiu).
4. Rezolvarea testului de autoevaluare (pentru fiecare modul).
Cuprins :
CURS PENTRU STUDENȚI I LA IFR ………………………….. ………………. 1
OBIECTIVELE DISCIPLI NEI ………………………….. ……………………….. 2
COMPETENȚE ASIGURATE PRIN PARCURGEREA DIS CIPLINEI
(GRILA 2 RNCIS, FISA DISCIPLINEI) ………………………….. …………… 2
FOND DE TIMP ALOCAT, FORME DE ACTIVITATE, FORME DE
VERIFICARE, CRED ITE (FIȘA DISCIPLINE I) ………………………….. . 3
STABILIREA NOTEI FIN ALE (FIȘA DISCIPLINE I) ……………………. 3
TIMP MEDIU NECESAR P ENTRU ASIMILAREA FIE CĂRUI
MODUL ………………………….. ………………………….. …………………………. 4
INSTRUCȚIUNI PENTRU PARCURGEREA RESURSEI DE
ÎNVĂȚĂMÂNT ………………………….. ………………………….. ……………….. 4
MODULUL I. INTRODUC ERE ÎN TEORIA AGENȚI LOR
INTELIGENȚI ………………………….. ………………………….. ………………….. 7
1. Agenții inteligenți, utilitatea lor și poziționarea în cadrul domeniului mai larg al
Inteligenței Artificiale ………………………….. ………………………….. ………………………….. …………. 7
2. Arhitecturi, tipuri și sisteme de agenți ………………………….. ………………………….. ………… 14
I.2.1. Taxonomia. ………………………….. ………………………….. ………………………….. ……………………… 14
I.2.3. Organizarea task -urilor existente. ………………………….. ………………………….. ……………………. 17
I.2.5. Sisteme multiagent etero gene necomunicative. ………………………….. ………………………….. …. 22
Rezumatul unității de studiu ………………………….. ………………………….. ………………….. 25
Autoevaluare ………………………….. ………………………….. ………………………….. …………… 26
Test de autoevaluare a cunoștințelor din modulul I ………………………….. ……………….. 26
MODULUL II . ARHITECTURI DE AGE NȚI INTELIGENȚI MODI FICS
………………………….. ………………………….. ………………………….. ……….. 28
1. Tipuri, acțiuni și comportament ………………………….. ………………………….. …………………. 28
2. Arhitecturi logice ………………………….. ………………………….. ………………………….. …………… 32
3. Arhitecturi reactive (reflexe) ………………………….. ………………………….. ………………………. 36
4. Arhitecturi BDI -(Beliefs -Desires -Intentions) ………………………….. ………………………….. . 42
5. Arhitecturi stratificate ………………………….. ………………………….. ………………………….. …… 45
Rezumatul unității de studiu ………………………….. ………………………….. ………………….. 50
Autoevaluare ………………………….. ………………………….. ………………………….. …………… 50
Test de autoevaluare a cunoștințelor din modulul I ………………………….. ……………….. 51
Tema de control nr. 1 ………………………….. ………………………….. ………………………….. .. 52
MODULUL III. COMUNIC AȚIA ÎNTRE AGENȚI SI PLATFORMĂ … 53
1. Comunicația între agenți ………………………….. ………………………….. ………………………….. .. 53
2. Mecanisme de cooperare între agenți ………………………….. ………………………….. ………….. 63
Rezumatul unității de studiu ………………………….. ………………………….. ………………….. 67
Autoevaluare ………………………….. ………………………….. ………………………….. …………… 68
Test de autoevaluare a cunoștințelor din m odulul I ………………………….. ……………….. 68
BIBLIOGRAFIE ………………………….. ………………………….. …………………………. 72
Modulul I. Introducere în teoria
Agenților Inteligenți
Obiective operaționale:
introducere în domeniul Inteligenței Artificiale (IA) și tehnici IA;
definiții referi toare la agenții inteligenți ;
prezentare domeniu multiagent;
arhitecturi tipuri si sisteme de agenti;
1. Agenții inteligenți, utilitatea lor și poziționarea în
cadrul domeniului mai larg al Inteligenței Artificiale
Întotdeauna a existat perspectiva de a include sisteme computerizate
autonome în viața de zi cu zi. Acest lucru este acum posibil datorită
progreselor din domeniul Inteligenței Artificiale (IA). În ultimii ani, tehnicile
IA au devenit mult mai robuste și mai complexe. Datorită succeselor obți nute
în acest domeniu, cercetătorii din domeniul IA și -au câștigat dreptul de a
începe să examineze implicațiile sistemelor multiagent asupra lumii reale.
În continuare se vor prezenta câteva definiții referitoare la agenții
inteligenți.
Agentul AIMA al lui Russell și Norvig [SJRSN95] este descris drept
„orice lucru care își poate percepe mediul prin senzori și poate acționa
asupra acelui mediu prin efectori" . Definiția depinde în mare măsură de ce se
înțelege prin mediu, percepție și acțiune. Astfel, dacă mediul asigură intrări
pentru agenți și le primește ieșirile, orice program poate fi considerat agent.
Agentul Maes [Pmaes95]: „Agenții autonomi sunt sisteme
computaționale care populează un anumit mediu dinamic și complex,
acționează autonom în acest med iu și astfel își realizează un set de scopuri
sau sarcini pentru care au fost proiectați." Această definiție adaugă un
element foarte important: autonomia agenților , însă limitează tipurile de
mediu, astfel încât acestea să fie complexe și dinamice.
Deci, se poate considera că un agent este „un sistem computațional
situat într -un mediu de execuție și capabil de acțiune autonomă în acel mediu
pentru a -și îndeplini obiectivele planificate" [GweiB00].
Trebuie remarcat că definiția se referă la agenți în genera l, nu la
agenții inteligenți. Ea nu spune nimic despre tipul de mediu pe care îl ocupă
agenții, deoarece pot exista mai multe tipuri de mediu. În cele mai multe
domenii, de complexitate rezonabilă, agentul nu va avea un control complet
asupra mediului, în general, ci va avea un control parțial asupra mediului,
adică îl va putea influența.
De regulă, un agent are o anumită gamă de acțiuni pe care le poate
efectua. Mulțimea tuturor acțiunilor posibile ale unui agent poartă denumirea
de capacitate efectorică (ec-effectoric capability), adică posibilitatea de a -și
modifica mediul de execuție. Nu toate acțiunile pot fi executate într -o
anumită situație; ele au unele pre -condiții asociate, care definesc stările
mediului în care pot fi îndeplinite. De exemplu , un a gent-expert cu scop de
irigare automată nu va putea efectua jobul, dacă apa conține sulfați cu o
concentrație mai mare de 300mg/l.
Agentul Hayes -Roth [BhaRo95]: „Agenții inteligenți efectuează în
mod continuu trei funcții: perceperea condițiilor dinamice d in mediu,
acțiunea pentru influențarea condițiilor din mediu și raționamentul pentru
interpretarea percepțiilor, rezolvarea problemelor, deducerea inferențelor și
determinarea acțiunilor." Definiția insistă asupra raționamentului necesar
selectării acțiuni lor, însă dacă acest concept este interpretat într -un sens mai
larg, arhitectectura rezultantă permite și acțiuni reflexe pe lângă cele
planificate.
Agentul IBM [SFrGr99]: „Agenții inteligenți sunt entități software
care îndeplinesc anumite operații în num ele utilizatorului sau al altui
program, cu un anumit grad de independență sau autonomie, folosind astfel
cunoștințe sau reprezentări ale scopurilor sau dorințelor utilizatorului."
Această definiție aduce în discuție o altă trăsătură a agenților și anume
cooperarea . De asemenea, se poate deduce că orice agent software este un
program, însă un program nu se consideră agent decât dacă manifestă
anumite caracteristici.
Noțiunea de agent este o abstracțiune software, la fel ca și noțiunile
de metodă clasă sau o biect. Spre deosebire de acestea, un agent software
este o abstracțiune de nivel foarte înalt, care asigură o modalitate
convenabilă de descriere a entităților de mare complexitate.
Un agent nu este definit în termeni de metode sau proprietăți, ci de
compo rtament. Programarea unui sistem bazat pe agenți este în primul rând
o problemă de specificare a comportamentului acestora. Există câteva
caracteristici minimale care definesc un agent software. El trebuie să fie
autonom, adică să fie capabil să opereze ca un proces de sine stătător și să
acționeze fără intervenția utilizatorului. În al doilea rând, trebuie să
comunice cu utilizatorul sau cu alți agenți. De asemenea, agentul trebuie să
perceapă schimbările din mediul său de execuție.
Importanța agenților re zidă în principal în faptul că sunt o soluție
pentru administrarea sistemelor complexe. Datorită autonomiei, ei pot
acționa în numele utilizatorului, fără să aibă doar funcția unei simple
interfețe. De exemplu, pentru găsirea unei informații pe Internet, u tilizatorul
o poate căuta singur sau poate apela la un agent care să realizeze căutarea
în locul lui și să -i returneze apoi paginile cele mai semnificative. De
asemenea, noul val de dezvoltare al tehnologiei și în special Internetul
necesită posibilitatea ca diverse aplicații să comunice și să interacționeze.
Probabil definiția cea mai adecvată pentru agenții inteligenți le
aparține lui Wooldridge și Jennings [MWNRJ95]. Cercetătorii mai sus
menționați, apreciază inteligența drept capacitatea de acțiune auto nomă
flexibilă , unde flexibilitatea presupune reactivitate , proactivitate și abilitate
socială . Ei consideră că un agent inteligent este un sistem hardware sau (mai
ales) software , care se bucură de următoarele proprietăți:
autonomie („autonomy") : se refer ă la posibilitatea unui agent de a -și
controla propriile acțiuni independent de alte entități, putând interacționa
cu acestea doar în cazul în care dorește. De obicei un agent autonom nu
apelează la altcineva (alt agent sau ființă umană) decât dacă nu pose dă
suficiente cunoștințe pentru a îndeplini de unul singur o anumită atribuție.
Agentul operează ca un proces de sine stătător, fără intervenție umană
directă și deține controlul asupra acțiunilor și stării sale interne;
reactivitate („reactivity") : este o proprietate neceseră atunci când agentul
acționează în medii nesigure, care se schimbă mereu. Agentul
reacționează în mod continuu pentru a se adapta modificărilor. În astfel
de medii dinamice, evenimentele externe pot schimba chiar pre -condițiile
conside rate inițial pentru începerea execuției unei acțiuni. Printr -o
continuă reactualizare a informațiilor despre mediu, se poate evita
încercarea de a atinge scopuri imposibile. Dacă însuși scopul se modifică,
atunci nu mai există nici un motiv pentru continua rea procedurii curente.
Se referă la capacitatea agenților de a menține o interacțiune neîntreruptă
cu mediul înconjurător și de a răspunde în timp util la schimbările ce apar
în mediu, adică de a se adapta la acestea. Agentul își percepe mediul (care
poate fi de exemplu lumea fizică, un utilizator prin intermediul unei
interfețe grafice, o colecție de alți agenți, Internet -ul, etc.) și răspunde
promt schimbărilor petrecute în mediul respectiv;
proactivitate („pro -activeness") : se referă la capacitatea unui agent de a
lua inițiativa; el nu este condus de evenimente ci este capabil de a -și
genera scopurile și de a acționa rațional pentru a le îndeplini. Agentul nu
numai că reacționează la schimbările mediului său de execuție, ci este
capabil să manifeste un c omportament orientat spre scop prin preluarea
inițiativei;
Reactivitatea/Proactivitatea se referă la comportamentul orientat spre
scop. Acest concept poate fi exemplificat printr -un simplu program scris
într-un limbaj imperativ. Efectele execuției unei pro ceduri reprezintă
scopul, ceea ce intenționează autorul programului să realizeze. Modelul este
adecvat mediilor statice, însă dacă pre -condițiile se schimbă în timpul
execuției procedurii, rezultatul acesteia va fi imprevizibil și de obicei
eronat.
Constru irea sistemelor pur reactive sau pur proactive nu este foarte
dificilă. Adevărata provocare o constituie găsirea unui echilibru între
comportamentul reflex și cel orientat spre scop. În general, se dorește ca
agentul să încerce să -și atingă în mod sistemat ic scopurile, însă să nu
continue o anumită acțiune în condițiile în care este clar că aceasta nu va
reuși. El trebuie să reacționeze la noua situație și să -și selecteze un nou mod
de comportament. Totuși, agentul nu trebuie să reacționeze în mod continuu
și astfel să nu se mai poată concentra asupra atingerii efective a scopurilor.
abilitate socială („social ability") : al treilea atribut al unui comportament
flexibil, se referă la cooperarea dintre agenți, la partajarea scopurilor. Un
simplu schimb de inf ormații nu poate fi considerat drept comportament
social, care se dovedește mult mai complex. Există cazuri în care
atingerea propriilor scopuri intră în conflict cu interesele altor agenți. În
astfel de cazuri se recurge la negociere, alegerea unor acțiun i alternative,
etc. Agentul interacționează cu alți agenți (sau cu oamenii) printr -un
anumit limbaj de comunicație între agenți.
continuitatea în timp. Această proprietate se referă la capacitatea
agenților de a -și suspenda, termina sau continua execuția, dar dacă starea
unui agent este suspendată, aceasta trebuie să fie memorată într -o anumită
manieră astfel încât să poată fi recreată atunci când agentul este reanimat.
Alte atribute ale agenților:
o adaptarea;
o capacitatea de a comunica și de a coopera cu alți agenți;
o capacitatea de învățare. Agenții pot, în anumite
circumstanțe, să învețe din evenimentele repetitive ce au
loc în mediul înconjurător astfel încât să poată prezice
evenimentele viitoare și în anumite cazuri, să acționeze
asupra mediului;
o mobilitatea reprezintă capacitatea de a se mișca de la un
sistem la altul;
o negociere;
o task-oriented;
o flexibilitate, abilitate socială.
Pentru un numar din ce în ce mai mare de aplicații sunt necesare
sisteme care pot să decidă ce este necesar să facă pent ru a satisface
obiectivele pentru care au fost concepute. Agenții care trebuie să opereze
robust într -un mediu variabil, nesigur sau deschis, unde probabilitatea ca
acțiunile să eșueze este mare, sunt numiți agenți inteligenți sau agenți
autonomi.
Un agent este un sistem care este parte a unui proces de fabricație,
capabil de a acționa autonom în mediul său pentru a indeplini obiectivele
fixate/dorite. În figura 1a, este prezentată o vedere abstractă, de ansamblu a
unui agent.
MediuAgent intrări
ieșiri Figura 1a. Sistem cu
agent.
Agenții preiau informații din mediu și produc acțiuni care afectează
mediul. Această interacțiune se desfășoară în continuu. Exemple de agenți
pot fi:
Un sistem de control. Termostatul este un astfel de exemplu. Senzorul său
este situat în mediu și produce două semnale de ieșire: unul care arată că
temperatura este prea scăzută și altul care arată că temperatura este prea
ridicată. Astfel componenta care are rolul de decizie implementează
următoarele reguli:
temperatura scazută încălzește
temperatură prea ridicată răcește
Un “daemon” software. Acest proces care rulează în fundal
monitorizează sistemul și execută acțiuni pentru a -l modifica.
Este neobișnuit a face asocierea între un termostat sau un “daemon”
software și un ag ent. De aceea se va considera în continuare noțiunea de
agent și mai ales de agent inteligent și se va prezenta o definiție a sa.
Se numeste agent inteligent o entitate fizică sau virtuală care are
următoarele caracteristici:
este capabilă de a acționa în tr-un anumit mediu;
poate comunica direct cu alți agenți;
este condusă de un ansamblu de tendințe (sub forma de obiective
individuale, a unei funcții de satisfacție, sau dorințe de supraviețuire pe
care încearcă să le optimizeze);
are resurse proprii;
este capabilă de a percepe (într -o manieră limitată) mediul în care
evoluează;
dispune de o reprezentare parțială a mediului în care evoluează (există
situații în care agenții nu dispun de reprezentarea mediului);
are anumite competențe și oferă anumite servic ii;
se poate eventual reproduce;
comportamentul său este determinat de tendința de a -și satisface
obiectivele, ținind cont de resursele și de competența de care dispune, în
funcție de percepții, de reprezentarea mediului pe care o deține și de
comunicațiil e în care este implicat.
Faptul că este văzut ca o entitate fizică înseamnă că reprezintă o
entitate care acționează într -o lume reală, deci poate fi: un robot, un avion, o
mașin ă, etc. Ca entitate virtuală poate fi: un modul informatic, o componentă
logică.
Acțiunea este un concept fundamental al agenților inteligenți. Aceasta
este o diferență esențială față de sistemele de inteligență artificială clasice:
agenții realizează anumite acțiuni, care pot modifica mediul în care se află, și
pot comunica între ei, ceea ce implică definirea unui model de interacțiune.
Agenții sunt dotați cu autonomie , ceea ce înseamnă că nu sunt dirijați
de comenzi venite de la utilizator, sau de la un alt agent, ci de un ansamblu de
tendințe proprii, care pot lua diferite forme și pot fi influențate de mai mulți
factori. Agenții au autonomie în ceea ce privește comportamentul și resursele
de care dispun.
Agenții nu au decât o reprezentare parțială a mediului în care se află și
nu au o viziune globală a lumii. Aceștia sunt caract erizați de un anumit
comportament, care se rezumă la modul de comunicație, acțiune,
reproducere, realizarea necesităților și obiectivelor, plecând de la celelalte
elemente de care dispune: percepții, reprezentari, acțiuni, comunicații și
resurse.
Agentul p oate fi astfel văzut ca: element dintr -o organizație colectivă;
organizație de nivel inferior și deci are toate caracteristicile unei organizații.
Ce este un sistem multiagent? Un sistem multiagent este un
sistem format din cel puțin doi agenți intelige nți capabili să interac ționeze
între ei în vederea realizării unor scopuri individuale sau comune (scopuri
globale) și care partajeazã același mediu de lucru.
Sistemele multiagent (Multiagent Systems) – SMA constitue un
subcâmp al IA, a cărui scop este de a furniza principiile pentru construcția de
sisteme complexe incluzând agenți multipli și mecanisme de control a
comportării agenților independenți. Deși capacitatea de a controla
comportarea agenților autonomi este una nouă, acest domeniu (al sistemelor
multiagent) avansează rapid datorită faptului că este construit pe baza unor
informații deja existente și anume acelea din domeniul Inteligenței Artificiale
Distribuite (IAD).
IAD a existat ca un subdomeniu al IA de mai puțin de 2 decade și este
împărțită în două subdiscipline: DPS (Distributed Problem Solving) și SMA
(Multiagent Systems). Principalele teme considerate în DPS sunt problemele
legate de managementul informațiilor, cum ar fi descompunerea task -urilor și
sinteza soluțiilor. De exemplu, o probl emă poate fi descompusă în mai multe
subprobleme, nu total independente, care pot fi rezolvate de diferite
procesoare. Apoi, soluțiile rezultate pot fi sintetizate în soluția problemei
originale.
SMA permite ca aceste subprobleme să fie distribuite agenți lor –
fiecare având interesele și scopurile lui. Și mai mult, au început să fie studiate
domenii cu multiagenți de orice tip, incluzând vehicule autonome și chiar o
serie de agenți umani.
Deși există multe moduri de a clasifica SMA, acest studiu este
organizat ținând cont de două dimensiuni principale: heterogentitatea
agenților și cantitatea de comunicații dintre agenți. Se consideră o întreagă
gamă de posibile sisteme multiagent începând cu cel mai simplu scenariu de
sistem multiagent (agenți omogeni și necomunicativi) și până la cele mai
complexe sisteme multiagent heterogene.
Utilitatea sistemelor multiagent. Motivația utilizării sistemelor
multiagent:
paralelism;
robustețe;
scalabilitate ; programare simplă ;
pentru a studia inteligența ;
rezolvar e eficientă a
problemelor.
Nu se poate pretinde ca SMA să fie utilizate în proiectarea tuturor
sistemelor complexe, dar sunt domenii care cer această soluție. În particular,
un exemplu de domeniu care are nevoie de SMA, este cel medical. Chiar și în
domenii în care se pot folosi sisteme ce nu sunt distribuite, există
posibilitatea de a utiliza SMA. Având agenți multipli, se poate mări viteza de
operare a sistemului, prin utilizarea unei metode de calcul paralel. De
exemplu, un domeniu care poate fi rapid divizat în mai multe componente,
fiecare componentă reprezentând un task independent, poate beneficia de
agenți speciali. Mai mult, paralelismul sistemelor multiagent poate ajuta și
atunci când există limitări impuse de insuficiența timpului avut la dispo ziție.
Paralelismul este obținut prin asignarea diferitelor task -uri unor agenți
diferiți, iar robustețea este un beneficiu al sistemelor multiagent care posedă
agenți redundanți. Dacă controlul și responsabilitățile sunt împărțite între
diferiți agenți, sistemul poate tolera ratări din partea unuia sau mai multor
agenți. Dar, în cazul în care există un singur procesor sau agent care
controlează toată activitatea, o singură greșeală poate duce la căderea
întregului sistem. Deși un sistem multiagent nu are nevoie neapărat să fie
implementat pe mașini cu mai multe procesoare, pentru a furniza o bună
robustețe la erorile ce pot apărea, agenții ar trebui să fie distribuiți pe mai
multe mașini.
Un alt avantaj este acela că este mai ușor să se adauge noi agenți
sistemului, decât să se adauge o nouă capacitate unui sistem monolitic. De
asemenea, de acest avantaj al sistemelor multiagent pot să beneficieze și
sistemele ale căror capacități și parametri pot să necesite o schimbare în timp
sau între agenți. Din persp ectiva programatorului, modularitatea sistemelor
multiagent poate conduce la o mai simplă programare. Decât să se asigneze
întregul task unui agent centralizat, programatorii pot identifica subtask -uri și
asigna controlul acestor subtask uri unor agenți di feriți.
Sistemele multiagent pot fi folosite pentru a studia inteligența.
Gerhard Weib spunea: “ …cel mai bun mod de a dezvolta mașinile inteligente
ar putea fi să începem să creem mașini sociale “ [GWSS96]. Această teorie
este bazată pe teoria socio -biolo gică pe baza căreia inteligența primatelor a
evoluat datorită interacțiunilor sociale.
2. Arhitecturi, tipuri și sisteme de agenți
I.2.1. Taxonomia.
Unele dintre cele mai importante caracteristici ale sistemelor
multiagent sunt ([HVDP96]):
funcția s istemului;
arhitectura agentului (eterogenitatea, reactivitate vs. deliberare);
arhitectura sistemului (comunicații, protocoale, implicarea
omului, etc.).
Cele mai importante caracteristici ale agenților sunt: gradul de
eterogenitate și gradul de comuni cație .
Cele trei combinații de eterogenitate și comunicație (agenți omogeni
și necomunicativi, agenți eterogeni și necomunicativi, agenți eterogeni și
comunicativi) sunt prezentați în ordinea creșterii complexității și puterii
(figura 1b).
Figura 1b. Combinații între agenți.
Proprietățile fiecărei categorii de agenți, menționate mai sus, sunt
prezentate în următorul tabel:
Agenți omogeni
necomunicativi: agenți reactivi vs. agenți deliberativi;
perspectiva locală sau globală;
modelarea stării altor a genți;
modul în care acești agenți pot afecta alți agenți;
Agenți etero geni
necomunicativi: bunăvoință vs. competitivitate;
modelarea acțiunilor, scopurilor și cunoștințelor altora;
managementul resurselor;
convenții sociale;
agenți care evoluează;
Agenți eterogeni
comunicativi: se înțeleg unii pe alții;
planifică acțiuni comunicative;
bunavoință vs. competitivitate;
managementul resurselor;
adevăr în comunicație.
I.2.2. Sisteme cu un singur agent vs. Sisteme Multiagent .
Înainte de a studia și de a clasifica sistemele multiagent trebuie făcută
mai întâi o scurtă prezentare a sistemelor centralizate cu un singur agent care
ia toate deciziile. Se va considera pentru acest studiu un sistem (cu un singur
agent) complex, centralizat, într -un domeniu care ar putea permite și un
sistem multiagent. Un sistem cu un singur agent ar putea avea mai multe
entități, câțiva actuatori sau chiar câțiva roboți. Oricum, dacă fiecare entitate
trimite rezultatele și primește acțiunile, pe care trebuie să le îndeplin ească, de
la un singur proces central, atunci există doar un singur agent al procesului
central. Agentul central modelează fiecare entitate. Secțiunea ce urmează
compară sistemele cu un singur agent cu cele multiagent.
Sisteme cu un singur agent . Deși p oate părea că sistemele cu un
singur agent ar trebui să fie mai simple decât sistemele multiagent, când
există un task complex, sistemele multiagent oferă mai multă ușurință de
lucru. În general, un agent dintr -un sistem cu un singur agent modelează el
însuși mediul și interacțiunile acestuia. Desigur, agentul însuși este parte a
mediului, dar dacă există și alți agenți, aceștia sunt considerați părți ale
mediului (figura 2).
Figura 2. Sistem cu un singur agent, care modelează el însuși mediul
și intera cțiunile acestuia.
Sisteme Multiagent. Sistemele multiagent diferă de cele cu un
singur agent prin aceea că există mai mulți agenți care își îndeplinesc
propriile scopuri și acțiuni. În cele mai complete sisteme multiagent, există o
interacțiune direct ă între agenți, adică aceștia comunică între ei (figura 3).
Deși această interacțiune poate fi văzută ca un stimul din mediu, se va
prezenta comunicația dintre agenți ca fiind separată de mediul înconjurător.
Din perspectiva unui agent individual, sisteme le multiagent diferă de
sistemele cu un singur agent datorită faptului că în primul caz, dinamica
mediului poate fi determinată de alți agenți. Fiecare agent este o parte a
mediului și este modelat ca o simplă entitate. Poate exista un număr variat de
agenți, cu diferite grade de eterogenitate și cu sau fără capacitatea de a
comunica direct. Pornind de la cel mai general caz prezentat aici, se va
elimina, pentru început, comunicația și eterogenitatea pentru a descrie
sistemele multiagent omogene și necomuni cative. Se vor prezenta, după
aceea, sisteme multiagent care posedă aceste proprietăți.
Figura 3. Un scenariu general pentru un sistem multiagent și
interacțiunea dintre agenți (comunicația).
I.2.3. Organizarea task -urilor existente.
În această secțiu ne se vor prezenta câteva tehnici SMA, care au rolul
de a ilustra problemele ce pot apărea în scenariile ce conțin sisteme
multiagent.
În ordinea creșterii ordinului de complexitate, cele 3 scenarii de
sisteme multiagent considerate sunt: agenți omogeni ș i necomunicativi,
agenți eterogeni și necomunicativi, agenți eterogeni și comunicativi. Pentru
fiecare din aceste scenarii, vor fi prezentate problemele apărute, tehnicile
folosite pentru a le rezolva, precum și cazurile de ML (Machine Learning).
Multe te hnici de ML deja existente pot fi aplicate direct în scenariile
de sisteme multiagent prin delimitarea unei părți din acest domeniu, parte
care implică un singur agent. Învățarea multiagent este “învățare care este
făcută de câțiva agenți și care este posi bilă doar dacă aceștia sunt
prezenți“ [GWSS96].
Fiecare scenariu va fi însoțit de un exemplu adecvat din domeniul
“Prădător/Pradă“ (Predator/Prey) sau domeniul “Urmăririi“(“Pursuit “
domain).
Domeniul Prădător/Pradă (“Urmărire“). Acest domeniu este
adecvat pentru ilustrarea sistemelor multiagent deoarece a fost studiat
utilizând o varietate de exemple și prezintă mai multe laturi ce pot fi folosite
pentru ilustrarea diferitelor scenarii de sisteme multiagent. Nu este prezentat
ca un domeniu complex, rea l ci mai mult ca un “toy“ domain, care va ajuta la
concretizarea multor concepte.
Domeniul “urmăririi“ este studiat de obicei cu patru prădători și o
pradă. Domeniul poate varia utilizând alte numere. Scopul prădătorilor este a
de captura prada sau de a o încercui astfel încât să nu se poată mișca pe o
poziție neocupată. O poziție de capturare este prezentată în figura 4. Dacă
spațiul în care are loc urmărirea are patru muchii, mai puțin de patru prădători
pot captura prada prinzând -o într -un colt sau în a propierea unei muchii. Un
alt criteriu posibil de a captura prada este atunci când prădătorul ocupă
poziția pe care se află și prada.
Figura 4. O variantă posibilă pradă/prădător.
(Prădătorii sunt negri și prada este gri. Săgețile indică deplasări posibile ale celor doi
prădători.)
Așa cum este prezentat în figura 4, prădătorul și prada se mișcă în
interiorul unui spațiu format din mai multe pătrate. Deplasarea se face numai
spre o poziție adiacentă, în orice direcție. Alți parametri specificați sunt: dacă
deplasarea are loc simultan sau în etape, cât de mult spațiu pot vedea
prădătorii și dacă aceștia pot comunica.
Domeniul “urmăririi “este unul potrivit pentru exemplificarea SMA,
deoarece este simplu de înțeles și destul de flexibil pentru a il ustra o varietate
de scenarii. Posibilele acțiuni ale prădătorilor și a prăzii sunt limitate și
scopul este bine definit. Acest domeniu nu are neapărat nevoie de SMA dar
în anumite instanțe, el poate utiliza paralelismul , robustețea și simplitatea în
progr amare, oferite de SMA. În domeniul “urmăririi“ există posibilitatea
utilizării unui sistem cu un singur agent. Acesta poate observa poziția celor
patru prădători și decide care prădător trebuie să se deplaseze mai întâi. Atât
timp cât prada se mișcă aleato r, nu este nevoie de un agent pentru a simula
mișcarea ei. Ea este considerată o parte a mediului (figura 5). Oricum, de cele
mai multe ori, prădătorii sunt descriși utilizând agenți independenți cu un
scop comun. De aceea ei formează un sistem multiagent.
Figura 5. Domeniul
“Urmăririi” cu un singur
agent.
Problemele care apar. Unele dintre cele mai relevante
caracteristici ale domeniului prezentat mai sus sunt:
numărul de agenți;
implicarea user -ului;
intervalul de timp ( în timp
real? );
scopul fie cărui agent este
dinamic? acțiunile altor agenți;
costul comunicației;
rezultatul propriilor acțiuni ale
agenților;
costul unei ratări.
Câteva sisteme multiagent includ oameni ca unul sau mai mulți
agenți. În acest caz, proiectantul trebuie să ia în c onsiderare problema
comunicației dintre agenții oameni și agenții computerizați .
I.2.4 Sisteme multiagent formate din agenți omogeni
necomunicativi .
Cel mai simplu scenariu de sistem multiagent implică agenți omogeni
necomunicativi. Toți agenții au acee ași structură internă incluzând scopuri,
cunoștințe despre domeniu și acțiuni posibile. De asemenea ei au aceeași
procedură de alegere a acțiunilor. Singura diferență dintre agenți este dată de
intrările senzoriale și de acțiunile actuale pe care ei le iau ; ei sunt situați pe
poziții diferite în spațiu.
“Urmărirea“ la sistemele multiagent formate din agenți
omogeni și necomunicativi. În acest caz, sunt patru agenți identici care
controlează fiecare prădător în parte. Deși agenții au capacități și procedu ri
de decizie identice, există posibilitatea ca ei să posede informații limitate
despre starea internă a celorlalți, fiind asfel incapabili să prezică acțiunile
celorlalți. Domeniul “urmăririi“ utilizând agenți omogeni este ilustrat în
figura 6.
Figura 6. Domeniul
“Urmăririi” cu agenți
omogeni.
Sisteme multiagent omogene generale. Există câțiva agenți
diferiți cu structură identică (senzori, cunoștințe, funcții de decizie) dar cu
intrări senzoriale diferite. Ei sunt situați diferit în mediu și iau si nguri
deciziile cu privire la acțiunile pe care le execută. În acest scenariu se
presupune că agenții nu pot comunica direct.
Probleme și tehnici. Chiar și în cele mai simple scenarii de
sisteme multiagent, exist ă câteva probleme care se pot întâlni. T ehnicile
prezentate în continuare sunt exemple reprezentative de moduri în care se pot
rezolva aceste probleme și sunt cuprinse în tabelul următor :
Agenți omogeni necomunicativi
Probleme agenți reactivi vs.agenți deliberativi;
perspectiva locală sau globa lă;
modelarea stărilor altor agenți;
modul în care agenții pot interacționa;
Tehnici comportamentul reactiv pentru menținerea formației[KSD87];
folosirea celor mai bune cunoștințe locale [AAAI96];
metoda modelării recursive (Recursive Modeling Method –
RMM) [Tambe95];
sinergia [VRL95];
Oportunități
de învățare validarea altor acțiuni;
date senzoriale – agenți.
Agenți reactivi vs. agenți deliberativi. La proiectarea unui sistem
bazat pe agenți este important de determinat cât de complicată va fi structur a
agenților. Agenții reactivi au o comportare prestabilită similară reflexelor,
fără a -și menține nici o stare internă. Pe de altă parte, agenții deliberativi se
comportă ca și cum ar gândi, cautând într -un spațiu de comportări,
menținându -și starea intern ă și prezicând efectele acțiunilor. Deși linia care
desparte agenții reactivi de cei deliberativi este oarecum confuză, un agent cu
nici o stare internă este cu siguranță reactiv, iar unul care se bazează pe
acțiuni furnizate de alt agent, este deliberativ .
Perspectiva locală sau globală. O altă problemă care trebuie luată în
considerare la proiectarea unui sistem multiagent este cât de multă informație
provenită de la senzori ar trebui să fie disponibilă agenților. Chiar dacă ar fi
posibil să se ofere ag enților o perpectivă globală a lumii, ar putea fi mai
eficient să li se limiteze viziunea la una locală.
Roychowdhury ia în considerare un caz de agenți multipli care împart
un set de resurse identice. Atât timp cât agenții sunt identici și nu comunică,
dacă ei au o viziue globală asupra resurselor, ar putea să acționeze simultan
asupra acelorași resurse. Un efect preferat ar fi acela când agenții ar acționa
asupra unor părți diferite ale resurselor.
Modelarea starii altor agenți. Utilizarea RMM oferă po sibilitatea de
a modela starea internă a unui agent astfel încât să i se poată prezice acțiunile.
Chiar dacă agenții cunosc scopurile și structura altora (ei fiind omogeni), este
posibil să nu știe și acțiunile viitoare ale altor agenți. Partea de informaț ie
lipsă este starea internă (pentru agenții deliberativi) și intrările senzoriale
(pentru agenții reactivi). În cel mai complex scenariu multiagent (ce va fi
prezentat în continuare) agenții o să trebuiască nu numai să modeleze stările
interne ale altor a genți ci și scopurile, acțiunile și capacitățile lor.
Modul în care agenții pot interacționa . Atunci când comunicația nu
este posibilă, proiectanții de sisteme trebuie să decidă cum un agent îl poate
afecta pe altul. Atât timp cât există în același mediu , agenții se pot influența
unul pe celălalt în mai multe moduri. Indirect, agenții pot afecta alți agenți
prin una sau două tipuri de sinergie. “Sinergia activă“ apare atunci când un
agent modific ă mediul astfel încât să afecteze intrările senzoriale ale a ltor
agenți. De exemplu un agent robot poate lăsa un semn în urma lui pentru ca
alt agent să îl observe. “Sinergia pasivă“ implică alterarea mediului, astfel
încât să se modifice efectele acțiunii altor agenți. De exemplu, dacă un agent
oprește electro -valva principală de alimentare cu apă a unei clădiri, atunci
efectul acțiunii altui agent care încearcă să deschidă electro -valva de
alimentare cu apă a căzii de baie, este anulat.
Alte modalități de învățare. O modalitate de învățare care poate fi
aplicată în domenii cu agenți omogeni și necomunicativi este aceea de a -i
învăța pe agenți să acționeze asupra altor agenți. Un agent poate fi învățat să
execute anumite acțiuni care nu îl ajută pe el direct, dar care permit altor
agenți similari să fie mai eficie nți în viitor.
I.2.5. Sisteme multiagent eterogene necomunicative.
Până acum s -au luat în considerare agenții omogeni. Adaugând
posibilitatea de eterogenitate în domeniul sistemelor multiagent, se obțin
sisteme cu un potențial mai ridicat. Agenții pot f i eterogeni în mai multe
moduri: ei pot avea scopuri, acțiuni, cunoștințe diferite. O caracteristică
importantă a agenților eterogeni este aceea că ei pot fi binevoitori sau
competitivi. Chiar dacă au scopuri diferite, ei pot fi receptivi la scopurile
altor agenți sau dimpotrivă ei pot acționa în defavoarea acestora.
Problematica “urmăririi“ la sistemele multiagent eterogene și
necomunicative. Ca și în scenariul precedent (în care agenții erau omogeni),
prădătorii pot fi controlați de agenți separați. D ar acum nu mai este nevoie de
agenți identici: acțiunile, scopurile și cunoștințele lor pot fi diferite. Și mai
mult, prada, a cărei scopuri sunt diferite de cele ale prădătorilor, poate fi
modelată de un agent (figura 7).
Figura 7.
Domeniul “Urmăririi”
cu agenți eterogeni.
Agenții au scopuri și
acțiuni diferte.
Sisteme multiagent eterogene, necomunicative generale. Ca și în
cazul omogenității, agenții sunt situați diferit în mediu, astfe, ei au intrări
senzoriale diferite și deci pot avea acțiuni diferite (figura 8).
Figura 8. Un scenariu general de SMA eterogen. Scopurile, acțiunile
și/sau domeniul de cunoștințe ale agenților diferă și sunt reprezentate prin
fonturi diferite. Scopuri
Acțiuni
Domeniu de cunoștințe
Scopuri
Acțiuni
Domeniu de cunoștințe Scopuri
Acțiuni
Domeniu de
cunoștințe
În acest caz, există diferențe semnificative între agen ți. Ei pot avea
scopuri, acțiuni și/sau cunoștințe diferite. Există o multitudine de avantaje
cauzate de existența eterogenității.
Probleme și tehnici de rezolvare.
Bunavoința vs. competitivitate . Una din cele mai importante
probleme care trebuie consi derate la proiectarea unui sistem multiagent este
dacă agenții vor fi binevoitori sau competitivi. Chiar dacă ei au scopuri
diferite, ei pot fi binevoitori și doritori să ajute alți agenți. Pe de altă parte,
agenții pot fi egoiști, acționând numai pentru a -și îndeplini propriile scopuri.
În partea opusă se află agenții care, în loc să își îndeplinească scopul,
acționează opus altor agenți. Unele persoane optează pentru agenții
competitivi, afirmând că sunt mai eficienți atunci când se proiectează sisteme
reale și mult mai plauzibili din punct de vedere biologic. Bineînțeles, dacă
agenții au aceleași scopuri, se vor ajuta unul pe altul, dar oamenii rareori
gândesc că agenții se pot ajuta unii pe alții aparent fără nici un motiv. În
unele situații poate fi în interesul agentului să coopereze cu alt agent.
Agenți stabili vs.agenți care evoluează. O altă caracteristică importantă
este dacă agenții sunt stabili sau dacă pot evolua. Agenții care evoluează pot
fi folositori în medii dinamice, dar în particular, când sunt folosiți agenți
competitivi cărora li se permite să evolueze, pot apărea complicații.
Modelarea scopurilor, acțiunilor, cunoștințelor altor agenți. Așa cum
RMM este util pentru modelarea stării agenților omogeni, poate fi folosit și
pentru scenarii cu agenți eterogeni. Agenții pot învăța și modele de echipe de
agenți, dar când sunt implicate echipe de agenți, situația poate deveni mai
complicată și este nevoie de modelarea rolului fiecărui agent [Tambe95]. Un
alt motiv pentru care modelarea altor age nți este utilă este acela că uneori
agenții depind unul de altul pentru a -și îndeplini scopul. Pot exista acțiuni
care cer cooperare pentru o execuție reușită.
Managementul resurselor. Atunci când resursele folosite de agenți sunt
limitate, pot apărea pro bleme iar proiectanții de sisteme multiagent trebuie să
decidă cum vor fi împărțite aceste resurse între agenți. Un exemplu, în acest
sens, este reprezentat de traficul pe o rețea atunci când există mai mulți agenți
care transmit date simultan.
2.6. Sist eme multiagent comunicative și eterogene.
Oricum, SMA este mai puternic când li se adaugă agenților și
abilitatea de a comunica unul cu altul, făcând astfel posibilă transformarea
sistemului multiagent în unul care este echivalent cu un sistem inteligent
format dintr -un singur agent .
Comunicația poate fi văzută ca o parte a interacțiunii dintre un agent
și mediu. Cu ajtorul comunicației agenții pot coordona mult mai eficient
decât au fost capabili până acum. Așadar sistemele pot deveni foarte
complexe dar și centralizate (până la punctul în care un singur agent are tot
controlul).
Un scenariu complet de sistem multiagent este prezentat în figura 9.
În acest scenariu gradul de eterogenitate al agenților poate fi oricare (de la
omogenitate până la o completă eterogenitate). Cheia este abilitatea agenților
de a transmite direct informațiile unul altuia. Comunicările pot fi de tip
broadcast , astfel încât să poate fi interpretate de oricine sau pot avea o țintă
precisă.
Figura 9. Un scenariu general de SMA comunicativ. Agenții pot fi
eterogeni pentru orice rang. Informația poate fi transmisă direct între agenți
(indicată de săgeți). Comunicația poate fi atât broadcast cât și point -to-point.
Probleme și tehnici de rezolvare. Atât ti mp cât agenții
comunicativi eterogeni pot alege să fie necomunicativi sau complet omogeni,
multe din problemele ce au apărut la categoriile descrise mai sus pot fi
prezente și aici. Dar capacitatea de a comunica ridică un alt set de probleme
pentru care ex istă alte tehnici de rezolvare.
a) Posibilitatea agenților de a se înțelege unul pe altul. În toate sistemele
multiagent comunicative trebuie să existe un limbaj și un protocol care să
fie utilizat de agenți în momentul când interacționează. Protocoalele
existente sunt: KIF (Knowledge Interchange Format) pentru conținut și
este utilizat pentru transmiterea mesajelor, KQML (Knowlegde Query and
Manipulation Language) pentru formatul mesajelor și COOL
(COOrdination Language) pentru coordonare (acțiunile agențil or sunt
interdependente și pentru atingerea unui scop comun acestea trebuie
coordonate). Scopuri
Acțiuni
Domeniu de cunoștințe
Scopuri
Acțiuni
Domeniu de cunoștințe Scopuri
Acțiuni
Domeniu de
cunoștințe
b) Organizarea căilor (actelor) de comunicație. Odată cu adăugarea
comunicației, ca o proprietate a agenților, este posibil să se considere
această abilitate ca o “acț iune“ care nu este diferită de alta. Când un agent
transmite informații unui alt agent are un efect similar oricărei alte acțiuni
transmise. De aceea, într -un plan de lucru, agenții pot defini condiții
preliminare și efecte pentru actele comunicative.
c) Bunavoința vs. competitivitate. În această secțiune există mai multe
exemple de agenți competitivi. Un prim exemplu este cel al agenților
concurenți care încearcă să câștige controlul întregului sistem. Un alt
exemplu (cu agenți binevoitori) este acela în car e un agent învață alt
agent prin intermediul comunicației. Poate exista un agent instructor care
să îl învețe pe altul ce acțiuni să execute într -o anumită situație, astfel
încât în final agentul care învață să se poata descurca fără a fi ghidat. În
acest mod poate fi redus rolul instructorilor umani. Și mai mult,
cercetatorii au proiectat sisteme bazate pe legea “vânzării \cumpărării“1.
Astfel, a fost implementat un sistem multiagent (cu agenți competitivi)
care controlează temperatura aerului în diferite c amere ale unei clădiri.
Temperatura poate fi fixată la o anumită valoare cu ajutorul termostatului.
În acest caz, în funcție temperatura aerului existentă în acel moment,
agentul camerei încearcă să “cumpere “ fie aer cald, fie aer rece de la o
altă cameră care are în exces. În același timp, un agent poate vinde aerul
în exces unei alte camere. Astfel, în funcție de temperatura camerei,
agenții încearcă să cumpere și să vândă la un preț bun.
d) Posibilități de învățare. Există multe posibilități de a îmbunăt ăți SMA
utilizând ML (Machine Learning). Pentru sistemele multiagent
comunicative eterogene este nevoie de a redefini protocoalele de
comunicație. Oricum, o alternativă interesantă ar fi aceea de a permite
agenților să învețe singuri cum să comunice și cum să interpreteze.
Atunci când se consideră comunicația ca act de vorbire, trebuie să le fie
permis agenților să învețe efectele vorbirii în dinamica globală a
sistemului. În domenii cu lățime de bandă mică sau întârzieri mari
asociate actului de comunicați e, utilitatea comunicației la un moment dat
ar putea fi învățată.
Rezumatul unității de studiu
Un agent este „un sistem computațional situat într -un mediu de
execuție și capabil de acțiune autonomă în acel mediu pentru a -și îndeplini
obiectivele planific ate", este un sistem care este parte a unui proces de
fabricație, capabil de a acționa autonom în mediul său pentru a indeplini
1 A se vedea exemplul vânzător/cumpărător.
obiectivele fixate/dorite.. Mulțimea tuturor acțiunilor posibile ale unui agent
poartă denumirea de capacitate efectorică (ec -effectoric capability).
Un sistem multiagent este un sistem format din cel puțin doi agenți
inteligenți capabili să interacționeze între ei în vederea realizării unor scopuri
individuale sau comune (scopuri globale) și care partajeazã același mediu de
lucru .
SMA este mai puternic când li se adaugă agenților și abilitatea de a
comunica unul cu altul, făcând astfel posibilă transformarea sistemului
multiagent în unul care este echivalent cu un sistem inteligent.
Autoevaluare
Test de autoevaluare a cunoștințel or din modulul I
1. Sunt definite tehnici de coordonare a acțiunilor (pentru evitarea
conflictelor). Care din următorele afirmații reprezintă
compromisul care modelează satisfacțiile și frustrările?
ordonarea priorităților;
tehnici de negociere ;
colaborare coordonată;
competiție individuală pură;
competiție colectivă pură;
simpla colaborare
2 Clasificarea interacțiunilor se face ținând cont de sursele
principale ale interacțiunii. Care din următoarele afirmații nu
reprezintă interacțiune?
• independentă;
• simpla colaborare
• întrepătrundere
• colaborare coordonată
• competiție individuală pură;
• competiție colectivă pură;
colaborare independent ă;
3 Un agent inteligent este un sistem hardware sau (mai ales)
software , care se bucură de următoarele propri etăți: ( realizati
potrivirea corecta )
autonomie („autonomy") : se referă la posibilitatea unui agent
de a-și controla propriile acțiuni independent de alte entități,
putând interacționa cu acestea doar în cazul în care dorește.
reactivitate („reactivity") : este o proprietate neceseră atunci
când agentul acționează în medii nesigure, care se schimbă
mereu.
proactivitate („pro -activeness") : se referă la capacitatea unui
agent de a lua inițiativa; el nu este condus de evenimente ci
este capabil de a -și genera scopurile și de a acționa rațional
pentru a le îndeplini.
4 Agen ții sunt caracterizați de un anumit comportament, care se
rezumă la:
modul de comunicație,
acțiune,
reproducere,
realizarea necesităților,
realizarea obiectivelor,
__________OBIECTI VELOR______________
5 Este adevărat că un sistem multiagent este un sistem format din
cel puțin doi agenți inteligenți capabili să interac ționeze între ei în
vederea realizării unor scopuri individuale sau comune (scopuri
globale) și care partajeazã acel ași mediu de lucru?
6 Care din următoarele reprezintă motivații ale utilizării sistemelor
multiagent:
paralelism;
robustețe;
scalabilitate ;
programare simplă ;
pentru a studia inteligența ;
rezolvare eficientă a problemelor;
7 Figura reprezintă Domeni ul pradă/prădător implementat cu:
agenți eterogeni
agenți omogeni
Modulul II. Arhitecturi de agenți
inteligenți MODIFICS
Obiective operaționale:
acțiunea și comportamentul agenților;
medii de executie a agentilor;
arhitecturi logice, reactive, st ratificate BDI.
1. Tipuri, acțiuni și comportament
Acțiune și comportament . Acțiunea poate fi văzută în mai multe
moduri, ca transformare a stării globale a sistemului (mediului). Inițial se
consideră mediul ca fiind stabil iar i mulțimea stărilor sis temului. Agentul
modifică starea sa rezultând o altă stare stabilă. Acțiunea implică modificare.
Reacția mediului la acțiunea unui agent implică o acțiune care poate avea
diferite rezultate. Fie sS, opOp, Exec -operatorul de execuție a unui alt
operator:
op x SS
Operatorii de tip STRIPS [FREHPN90] sunt folosiți la reprezentarea
acțiunilor realizate de un agent și sunt de forma:
op = < pre, suppr, ajouts >
O nouă teorie în acest domeniu pleacă de la ideea că mediul nu
rămâne într -o stare stabilă, ci evol uează. În cadrul acestei teorii, acțiunea este
modelată ca un sistem de răspunsuri la influențele pe care le produc agenții ca
rezultat al reacției mediului la influențele agentului. Se consideră că agentul
este influențat de mediul în care se află dar și exercită influență asupra
mediului .
Sistemul interacțional – are la bază noțiunea de percepție, definită
ca modalitatea prin care agentul preia informații din mediu. Percepția oferă
agentului posibilitatea să obțină informațiile despre mediul în care se află,
ceea ce îi permite să elaboreze acțiuni pentru a -și urmări țelul.
În filosofie, și nu numai, este stabilită ideea că percepțiile sunt
rezultatul construcțiilor care depind de scheme perceptive anterioare, care
sunt formate progresiv în decursul inter acțiunilor agentului cu mediul, sau/și
al altor agenți și care întăresc punctul de vedere al agentului respectiv.
Percepția contribuie la realizarea unei reprezentări a mediului. Sistemul
perceptiv poate fi:
pasiv – percepțiile sunt ceea ce sesizează în m od direct agentul. (În
sistemele pasive , elementele care captează informațiile generează semnale
elementare care sunt preprelucrate, 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. (În sistemele active sistemul perceptiv captează
informațiile din mediu. Elemen tele care captează informația din mediu
pot fi comandate astfel încât să mențină o reprezentare coerentă a
mediului.)
Sistemul reprezentațional – al unui agent face apel la următoarele
noțiuni: reprezentare, opinie, cunoștințe . Cunoștințele (ca noțiune definită în
inteligența artificială) reprezintă ansamblul de informații (fapte cunoscute,
experiența, concepte) necesare unui individ (sau unei mașini) pentru a se
organiza și a rezolva o sarcină sau o problemă considerată complexă.
Problema cunoașterii es te legată de noțiunile de conceptualizare și
raționament. În cadrul sistemului reprezentațional al agentului, este important
de stabilit care sunt categoriile conceptuale apriori raționamentului agentului
și care sunt diferitele concepte construite de agen t plecând de la cele dinainte
cunoscute, precum și mecanismele practice pe care un agent le folosește
pentru a se putea orienta în mediu sau, a stabili regulile și a rezolva
problemele, a lua deciziile și a -și atinge țelul. Cunoștințele conduc la
elaborare a unui raționament.
Cunoașterea are loc prin interacțiunea agentului cu mediul sau cu alți
agenți cognitivi. Aceste interacțiuni pot fi de natura unor confruntări,
refuzuri, obiecțiuni, cooperări, controverse . Rezultatele acestor cunoștințe
sunt concepte, teorii și legi noi după care se ghidează agentul în acțiunile pe
care le face. Cunoștințele pe care le are un agent nu le au toți ceilalți agenți.
O regulă cunoscută de un agent poate fi infirmată de altă regulă cunoscută de
alt agent. De exemplu:
R1: liber(robot) acțiune(aducePiesa) miscare(x,y)
R2: liber(robot) acțiune(aducePiesa) miscare(x,z)
Aceste două reguli determină un conflict. Pentru a -l rezolva se pot
aplica una din soluțiile următoare:
se aplică numai una dintre reguli – deci se aplică R 1 sau R2;
se elaborează o sinteză locală, care poate fi exprimată sub forma
unei reguli noi R3 – deci se aplică R3.
Fiecare dintre aceste reguli fac parte din teoria unui agent, se poate
spune deci că fiecare agent are o micro -teorie. O micro -teorie este o entitate
particulară, a cărei aplicabilitate este locală și dependentă de acel context.
Reprezentarea cunoștințelor poate fi văzută din următoarele puncte de
vedere: simbolico -cognitivist, conexionist, interacționist.
În inteligența artificială distribuit ă, în cele mai multe cazuri, agenții
care sunt cognitivi, dispun de stări mentale și sunt dezvoltați plecând de la
modele simbolico -cognitiviste. Celelalte două metode sunt aplicate în cazul
agenților reactivi, pentru care problemele stărilor mentale se re duc la selecția
acțiunii pertinente în raport cu percepțiile locale ale agenților.
Ipoteza simbolico -cognitivistă consideră că reprezentările accesibile
unui individ se exprimă sub forma de simboluri, care se referă direct la
entități ale mediului. Aceste simboluri sunt unite prin intermediul unui limbaj
intern, definit de o gramatică formală și de operațiile care le pot fi aplicate.
Un simbol este un element particular, care se referă la ceva anume,
adică la ceea ce reprezintă el de fapt, și care se numeșt e referentul său. De
exemplu, simbolul 2 se referă la al doilea element al numerelor naturale.
Semantica reprezintă capacitatea de a interpreta expresiile în raport
cu ceea ce se numește un model. O expresie nu poate fi evaluată ca fiind falsă
sau adevarat ă fără a ști la ce sunt atașate simbolurile care compun expresia și
mulțimea unde acestea au valori. Asocierea între simboluri și valori ale unui
domeniu D este definită printr -o funcție de interpretare. Pentru a ști dacă o
propoziție este adevarată sau fa lsă într -o interpretare I, se verifică pentru
formulele atomice dacă toate constantele care apar într -un predicat aparțin
domeniului de interpretare al predicatului. Formulele pot fi combinate prin
intermediul unor operatori cum ar fi: , , , , etc. For malizarea logicii
permite existența unor proprietăți generale, asupra sistemelor logice,
independente de interpretarea care se face asupra simbolurilor.
Arhitectura generală a unui agent inteligent.
Mediul de execuție al unui agent este caracterizat de o mulțime de
stări: S= {s1, s2, s3……}. În orice moment, mediul se găsește în una din
aceste stări. Capacitatea efectorică a agentului este reprezentată de o mulțime
de acțiuni: A={a1, a2,…}. În aceste ipoteze, un agent poate fi văzut ca o
funcție:
act: S*→A, (1)
care alege o acțiune de executat în concordanță cu starea mediului. Un agent
modelat de o astfel de funcție e un agent standard [GweiB00].
Un agent inteligent poate însă decide acțiunea următoare și în funcție
de stările mediului pe care le -a traversat până la un moment dat, de
„experiența" acumultată. Prin urmare, și comportamentul mediului poate fi
modelat printr -o funcție:
env: S×A→ (S), (2)
unde: (S) semnifică mulțimea părților lui S (mulțimea de mulțimi care pot
fi formate cu elementele lui S). Valoarea funcției într -o anumită stare a
mediului, adică rezultatul acțiunii agentului, reprezintă o mulțime de stări.
Dacă aceste mulțimi sunt singleton, adică au un singur element, ceea ce
înseamnă că acțiunea rezultă într -o singură stare posibi lă a mediului, acesta
este determinist și comportamentul său poate fi anticipat. În caz contrar,
mediul este nedeterminist. O secvență:
(3)
unde si reprezintă stări ale mediului iar ai acțiuni, și reprezintă o istorie
posibilă a agentului în mediu dacă și numai dacă:
(4)
Comportamentul caracteristic al unui agent în mediu este mulțimea
tuturor istoriilor care satisfac proprietățile menționate. Dacă o anumită
proprietate este caracteristică tuturor acestor istorii, aceasta este o proprietate
invariantă a agentului în mediul său. De exemplu, se consideră un agent care
controlează pH -ul într -un CorpApa. Dacă în nici o istorie posibilă în
secțiunea Sx, pH -ul nu depășește 7,2 sau nu scade sub 6,3, atunci aceste
proprietăți sunt invariante (care nu se schimb ă în urma aplicării unei
tranformări).
Mulțimea istoriilor agentului ag în mediul med se notează hist(ag,
med) .
Doi agenți ag1 și ag2 au comportamente echivalente în raport cu un
mediu, ( med), dacă și numai dacă:
hist(ag1, med) = hist(ag2, med)
Doi agenți ag1 și ag2 au comportamente echivalente dacă și numai
dacă au comportamente echivalente în raport cu toate mediile:
med, hist(ag1, med) = hist(ag2, med)
În general, este interesant studiul agenților care, prin prisma
autonomiei, nu încetează niciodată interacțiunile cu mediul și deci au istorii
infinite.
Luarea deciziilor de către un agent inteligent se bazează, pe această
istorie a interacțiunilor cu mediul. Concret, acest lucru este modelat prin
introducerea unor stări interne. După observarea mediulu i, agentul își
actualizează starea internă iar acțiunea următoare este selectată în funcție de
această stare, după care întregul ciclu se reia.
Un agent este un sistem cibernetic care primește informații din mediu
și acționează la rândul său asupra acestui a. Analiza unei arhitecturi generale
presupune studierea separată a celor două componente. În cele ce urmează, se
va face referire la funcțiile de percepție ale unui agent, care trebuie să -și
observe mediul pentru a lua deciziile de acțiune.
În cazul unui agent care acționează în lumea reală, cum ar fi de
exemplu un robot, funcția de percepție poate fi implementată hard (o cameră
video sau diverși alți senzori). Un agent software trebuie să dispună de
mecanisme de examinare a mediului -direct, prin accesarea unei variabile sau
a unei zone de memorie, sau indirect, prin intermediului unor mesaje.
Funcția de percepție poate fi definită astfel:
See: S→P (5)
unde P este o mulțime de elemente de percepție, sau percepte (percepts). În
acest caz, funcția de acțiune poate fi redefinită astfel:
act: P*→A (6)
Procesul de luare a deciziilor de acțiune în funcție de percepția
mediului poate fi reprezentat ca în figura 1:
Corp(apa) Figura 1.
Percepția și
acțiunea unui
agent.
Uneori este posibil ca două stări distincte s1 și s2 ale CorpX -lui să
provoace același percept. Se presupune că un agent măsoară CCOCr
(Consumul chimic de oxigen prin metoda bicromat de potasiu). Este posibil
să crească încărcarea organică a CorpX -lui de apă de natură biochimică
(CBO 5), corpX trecâ nd în s2. Mulțimea perceptelor posibile ale agentului va
rămâne aceeași, deoarece acesta nu are capacitatea de a detecta CBO 5. Dacă
pentru aceeași poziție a agentului, același obiect are în starea s 1 valoarea V1
pentru CBO 5 iar în starea s 2 valoarea V2, at unci s 1≠s2, însă see(s 1)=see(s 2).
Din punctul de vedere al agentului, stările s 1 și s 2 sunt indistinctibile. Dacă:
s1,s2 S: s 1≠ s2, see(s 1) ≠see(s 2), (7)
adică agentul poate distinge toate stările mediului, agentul este omniscient
(un agent este omnisc ient dacă funcția sa de percepție este injectivă) . La
cealaltă extremă, dacă:
s1,s2 S: see(s 1)=see(s 2), (8)
adică toate stările mediului provoacă același percept, agentul nu are
capacitate de percepție. El nu poate distinge nici o stare; pentru el toat e stările
mediului sunt identice.
2. Arhitecturi logice
Considerații teoretice. Abordarea tradițională în ceea ce privește
construirea sistemelor artificiale inteligente se referă la înzestrarea acestora
cu reprezentări simbolice ale domeniului în care acestea funcționează.
Concretizând, agenții ar trebui astfel să aibă o descriere a mediului la nivel de
formule logice, iar rezultatul acțiunilor ar corespunde unei deducții logice
[GweiB00].
Ideea ca un sistem bazat pe agenți să -și îndeplinească obiectiv ele în
forma unei demonstrații de teoreme este foarte atrăgătoare și a fost aplicată
cu succes în ultimii ani. În mod normal, o problemă de o anumită
complexitate este divizată progesiv în probleme din ce în ce mai simple, care
pot fi rezolvate cu ușurință (metoda „divide et impera"). În cazul agenților
care acționează ca demonstratori de teoreme, acest proces nu are loc; o
teoremă este o specificație executabilă, care este executată direct pentru a
produce un anumit comportament.
Agenții bazați pe logică a u stările interne organizate sub forma unei
mulțimi de formule predicative de ordinul întâi, de forma:
ClasaCalitateI(CBO5,5mg O 2/l)
ClasaCalitateV(CCOCr,50 mg O 2/l)
ConcentrațiaLimită(Mercur, 0,1 g/l)
ApeUzateDin(zootehnie) ApeUzateDin(petrochimica,
cauci ucuri)
Culoare(SulfatCupru, albastru)
Culoare(DDD, alb)
ConcentrațiaLimită(Antracen,
0,02g/l)
Fie L mulțimea propozițiilor predicative de ordinul întâi și D= (L)
baza de date formată din mulțimea mulțimilor de formule L. Starea internă a
unui agent bazat pe logică este un element al mulțimii D. Luarea unei
decizii este determinată de o mulțime de reguli de inferență, . Se notează cu
faptul că formula poate fi derivată din numai prin regulile de
inferență . Algoritmul următor prezintă procesul de cizional al unui agent
bazat pe logică [GweiB00]:
function act( : D): A
begin
foreach aA do
if
Do(a) then return a
endif
endfor foreach aA do
if
Do(a) then return a
endif
endfor
return null
end
Pe baza regulilor de inferență și a formulelor pr edicative, agentul
încearcă să determine acțiunea următoare a pe care trebuie să o efectueze:
Do(a). În prima buclă for, agentul încearcă să deriveze o acțiune posibilă din
starea internă A. Dacă acest lucru este posibil, funcția va returna acțiunea
respec tivă și agentul o va selecta pentru execuție.
Dacă nu reușește să găsească așa ceva, agentul caută o acțiune
consistentă cu baza de cunoștințe și cu regulile de inferență, adică o acțiune
care nu este interzisă în mod explicit, astfel încât non(Do(a)) să n u poată fi
derivată. În final, dacă nici o acțiune corectă nu poate fi găsită, se returnează
acțiunea nulă.
Exemplu de agent bazat pe logică : aplicația Virtual Cleaner
Agent . Un exemplu de agent bazat pe logică îl constituie aplicația Virtual
Cleaner Age nt. Programul simulează comportamentul unui aspirator virtual
care traversează după anumite reguli o cameră și îndeplinește anumite
acțiuni.
Figura 2. Agentul Virtual Cleaner Figura 3. Traseul agentului Virtual
Cleaner
Mediul (camera) este discret, o matrice cu trei linii și patru coloane.
Fiecare din aceste elemente poate avea două stări: e „curat" sau „prăfuit".
Pentru simplitate, se presupune că aspiratorul nu poate părăsi camera și poate
îndeplini numai trei acțiuni:
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).
În figura 2 se observă a gentul (orientarea sa este dată de marginea sa
roșie, aici, el se îndreptă spre vest) și stările mediului (celulele albe sunt
„curate" iar cele cu textură verde „au praf”). Programul asigură periodic
setarea unor celule ca „având praf, o dată pe secundă, c u o probabilitate de
25%. Formulele predicative utilizate sunt:
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 unu l din cele patru
puncte cardinale.
Acțiunile posibile ale agentului, ale căror semnificații s -au amintit
anterior, sunt:
Do(clean) – curățare: EnvHasDust(x,y) devine fals;
Do(forward) -înaintare: coordonatele (x,y) se modifică în funcție de orientarea ag entului;
Do(turn) – rotire la dreapta: orientarea agentului se schimbă.
Prima regulă de inferență este:
if Isln(x,y) and EnvHasDust(x,y) then Do(clean) (9)
Această regulă definește scopul agentului și trebuie să se afle la
începutul mulțimii regulilor d e decizie, pentru a fi selectată cu prioritate. În
continuare, se vor elabora reguli pentru mișcarea înainte a agentului. Pentru a
asigura parcurgerea constantă și eficientă a mediului, sa impus ca agentul să
traverseze camera în maniera prezentată în figu ra 3. Regulile de inferență
corespunzătoare sunt:
(10)
În final, dacă în căsuța în care se află agentul nu există praf și nici nu
are orientarea necesară pentru a se mișca înainte, trebuie să se rotească până
când va avea o direcție recunoscută de una d in regulile (10). Regulile de
rotire sunt de forma:
(11)
În celulele (0,3) și (2,3), regulile corespunzătoare din (11) se aplică de
câte trei ori, deoarece este permis un singur tip de rotație, la stânga. Pentru
continuarea traseului, agentul trebuie să se rotească o dată la dreapta
(imposibil) sau de trei ori la stânga.
Analiza programului. În cele ce urmează, se va schița o analiză a
programului, din perspectiva proprietăților descrise mai sus. În primul rând,
agentul se bucură de autonomie , deoarece e ste conceput ca un thread (fir de
execuție) separat, care rulează în paralel cu thread -ul principal. Reactivitatea
este determinată de analiza stării mediului și deducerea acțiunii următoare.
Proactivitatea se referă la urmărirea scopului principal: căutar ea „prafului" și
curățarea sa. Agentul nu are abilități sociale , deoarece nu acționează într -un
sistem multiagent.
Mediul de execuție este discret (o matrice cu 12 elemente), foarte
simplu: fiecare celulă din rețea are numai două stări posibile. Agentul po ate
obține informații complete despre starea curentă a mediului, deci acesta este
accesibil. Deși simplu, mediul este pe ansamblu nedeterminist și dinamic,
deoarece starea sa viitoare nu depinde numai de acțiunea agentului, într –
adevăr, agentul determină c urățarea sigură a unei celule, însă „adăugarea
prafului" nu depinde de el, ci de thread -ul principal care acționează în mod
aleatoriu în acest sens. Cu toate acestea, acțiunile agentului sunt infailibile,
pentru că vor produce întotdeauna efectele scontate . De asemenea, se are de -a
face cu un mediu episodic, deoarece performanțele agentului nu depind de
istoria sa.
3. Arhitecturi reactive (reflexe)
Considerații teoretice. Arhitecturile bazate pe logică, în care
luarea deciziilor este un proces de deducț ie, sunt arhitecturi elegante și clare
deoarece comportamentul agenților este definit explicit. Însă complexitatea
inerentă a acestora este un dezavantaj evident, mai ales în cazul mediilor
complexe, dinamice. Apar de asemenea și probleme de extensibilitat e și
robustețe iar atingerea scopurilor multiple aflate în competiție este dificilă. O
abordare diferită este adusă de arhitecturile reactive sau reflexe.
Agenți pur reactivi. Una dintre cele mai cunoscute arhitecturi pentru
agenți reactivi este arhitectur a de subordonare [BrooRA91]. Sunt două
caracteristici esențiale în cazul acestei arhitecturi.
Decizia este realizată printr -un set de module comportamentale.
Fiecare dintre acestea pote fi vazută ca o funcție acțiune individuală care în
mod continuu preia intrarea sesizată și conform acesteia determină acțiunea
ce trebuie executată. Modulele nu folosesc reprezentarea simbolică. În cele
mai multe implementări, aceste module sunt implementate sub forma unor
reguli de forma:
situație acțiune specifică
Mai mu lte module pot avea dreptul de a fi active la un moment dat și
de aceea trebuie să existe un mecanism care să facă selecția între ele. Brooks
[BrooRA91] propune organizarea modulelor într -o ierarhie de subordonare
cu mai multe nivele. Nivelele inferioare a u posibilitatea de a inhiba
activitatea nivelelor superioare deoarece au prioritate mai ridicată.
O pereche comportamentală (c, a), cu c P, este un set de percepții
denumit condiție, iar aA este o acțiune. Un comportament (c, a) va fi activ
cînd mediul se află în starea sS dacă percepție(s) c. Fie Com={(c, a) | c P
și aA} un set de astfel de reguli. Asociat cu setul de reguli ale agentului
RCom este o relație binară de inhibare care acționează pe setul
Com: RR (c, a)(c’, a’) dacă ((c, a), (c’, a’) ) și (c, a) inhibă (c’,
a’).
Funcția acțiune este definită astfel:
Functie actiune(c:P):A
var activa : (R)
var selectata :A
activa:={(c,a)|(c,a) R și pc}
pentru fiecare (c,a) activa executa
daca ((c’, a’)activa a.î. (c’, a’) (c, a)) atunci
returneaza a
sfarsit -daca
sfarsit -pentru -fiecare
returnează NULL
sfarsit
Comparând această abordare cu cea a agenților bazați pe logică, din
punct de vedere al complexitații, metoda este mai bună, asigurând în cazul
cel mai rău O(n2) , unde n este maximum dintre numărul de percepții sau de
elemente ale mulțimii Com . Câteva din avantajele acestei arhitecturi sunt:
simplicitate, robustețe, complexitate redusă . Dezavantajele sale sunt: agenții
trebuie să aibă suficient de multe informații disponibi le în mediul local
pentru a determina acțiunea pe care să o urmeze; agenții nu pot învăța din
experiență; deciziile sunt luate numai pe baza informațiilor locale și de aceea
este considerată ca decizie pe termen scurt.
În ceea ce privește terminologia, în literatura română de specialitate se
preferă denumirea de „agent reflex" pentru traducerea sintagmei „reactive
agent" din literatura anglo -saxonă. Deși sensurile celor două cuvinte sunt
foarte apropiate, s -a preferat folosirea termenului „reactiv", deoare ce aceeași
noțiune se referă și la proprietatea de „reactivitate" a unui agent, pentru care
expresia „reflexivitate" ar fi oarecum improprie.
Spre sfârșitul anilor '90, cercetătorii au început investigarea unor
alternative pentru paradigma simbolică clasic ă a inteligenței artificiale. Ideea
centrală în aceste abordări este faptul că acțiunile raționale inteligente sunt în
strânsă legătură cu mediul în care acestea au loc. Inteligența este astfel un
produs al influențelor reciproce dintre agent și mediu. Com portamentul
inteligent rezultză din interacțiunile unor comportamente mai simple
[GweiB00].
Una dintre cele mai cunoscute arhitecturi reactive este așa -numita
arhitectură de subsumare (subsumption architecture), care îi aparține lui
Rodney Brooks [RABro86, RABro91]. Există două caracteristici definitorii
ale acestei arhitecturi. În primul rând, agentul ia deciziile prin intermediul
unei mulțimi de comportamente adecvate îndeplinirii sarcinii. Fiecare
comportament poate fi gândit ca o funcție de acțiune indi viduală, care preia
intrarea perceptivă și generează o acțiune. În al doilea rând, se consideră că
mai multe comportamente se pot activa (sau „aprinde") simultan. De aceea,
trebuie să existe un mecanism de selecție a unei acțiuni unice la un moment
dat. Br ooks a propus existența unei ierarhii, comportamentele fiind așezate pe
diferite niveluri de competență. Nivelurile inferioare din ierarhie pot inhiba
nivelele superioare – cu cât un nivel este mai scăzut, cu atât are o prioritate
mai mare. Se poate spune că nivelele superioare reprezintă comportamente
mai abstracte.
În arhitecturile reactive există o strânsă legătură între funcția
perceptivă și cea acțională – intrarea senzorială nu este transformată sau
prelucrată foarte mult și nici nu se încearcă transf ormarea percepțiilor în
reprezentări simbolice. Funcția de decizie act se realizează printr -o mulțime
de comportamente posibile împreună cu o relație de inhibiție între acestea.
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. Un comportament (c, a) se va activa
când mediul este în starea s S dacă și numai dacă funcția de percepție,
see(s) c.
Fie Beh mulțimea tuturor astfel de reguli („behaviour",
comportament):
(12)
Cu mulțimea de regu li de comportament ale agentului R Beh este
asociată o relație de inhibiție binară definită pe mulțimea de comportamente:
RxR, tranzitivă, nereflexivă și antisimetrică :
b1, b2, b3 R, dacă b 1 b2 și b 2 b3, atunci b 1 b3, (13)
astfel încât b b (14)
b1, b2, R, dacă b 1 b2 și b 2 b1, atunci b 1=b3, (15)
Dacă pentru două comportamente b 1 și b 2 există (b 1,b2), se spune
că „b 1 inhibă pe b 2" sau „b 1 are prioritate față de b 2" și se scrie b 1b2.
Algoritmul de alegere a funcției de acțiune este urmă torul [GweiB00]:
function act(p: P): A
var fired: (R)
var selected: A
begin
fired = {(c, a)|(c, a) R pc}
foreach (c,a) fired do
if (
(c’, a’) fired \ (c' , a') (c, a)) then
return a
endif
endfor
return nuli
end
Se calculează mai î ntâi toate comportamentele care se pot activa, și
apoi pentru fiecare comportament se determină dacă există un comportament
cu prioritate mai mare. Dacă un astfel de comportament nu există, se
returnează acțiunea a corespunzătoare comportamentului. Dacă ni ci un
comportament nu se activează, se returnează o acțiune nulă (în momentul
următor agentul nu va efectua nici o acțiune). Complexitatea algoritmului
este în cazul cel mai defavorabil O(n2), unde n este maximum dintre numărul
de comportamente și numărul de elemente de percepție (percepte).
Arhitectura propusă de Brooks [RABro91] se referă în principal la
agenți robotici. În acest caz, nivelele de competență pot avea semnificațiile
din exemplul următor [KBERG98]:
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 d e control al obiectelor din mediu
și reconsiderarea în consecință a planurilor existente.
Comportamentele amintite pot fi dispuse în ierarhia următoare:
Nivelul 0 Nivelul 1 Nivelul 2 Nivelul 3 Nivelul 4 Nivelul 5 Nivelul 6
Nivelul 7 (16)
Avan tajele principale ale acestei arhitecturi se referă la simplitate,
economie în ceea ce privește resursele și robustețe în acțiune. Ea are drept
model lumea reală, evitând în acest mod păstrarea unui model intern al
mediului. Dificultățile care țin de dinam ica mediului sunt evitate prin
înlăturarea oricăror încercări de predicție, mai ales că modelul presupune
existența unor elemente de percepție eronate (de exemplu, senzori care se
defectează) [BrooBa91].
Însă există și unele probleme nerezolvate legate de arhitecturile pur
reactive. Deoarece agenții nu au un model al mediului, ei trebuie să aibă
suficiente date locale pentru selectarea unei acțiuni acceptabile. De asemenea,
este dificilă înzestrarea unor agenți reactivi cu abilitatea de a învăța și de a -și
îmbunătăți performanțele în timp [GweiB00].
Unii cercetători au încercat unificarea arhitecturilor rațională și
reactivă [RkoFS97]. În acest caz, raționalitatea este dobândită prin utilizarea
definițiilor pentru reducerea scopurilor la o mulțime de scopuri mai simple.
Reactivitatea intervine prin folosirea constrângerilor de integritate pentru
simularea regulilor situație -acțiune și prin formularea procedurilor de
demonstrare a teoremelor în așa fel încât să poată fi întrerupte pentru
efectuarea de observații și executarea de acțiuni.
Exemplu de agent reactiv : aplicația Spell -Checker Agent.
Aplicația Spell -Checker Agent este un exemplu de agent reactiv (reflex).
Scopul său este de a semnala cuvintele ortografiate eronat dintr -un text, c hiar
în timp ce utilizatorul îl scrie. În funcție de modul în care este clasificat de
agentul de verificare, 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.
Figura 4. Interfața programului Spell -Checker Agent.
Când textul se schimbă, cuvintele noi sunt marcate ca neverificate.
Agentul de verificare acționează ca un thread separat, în paralel cu firul de
execuție pri ncipal ce permite utilizatorului să -și scrie textul în controlul de
editare. Pentru fiecare cuvânt ne -examinat, agentul parcurge dicționarul în
căutarea formei respective. Dacă aceasta este găsită, înseamnă că avem de -a
face cu un cuvânt ortografiat corect ; în caz contrar, acesta este considerat
eronat. Desigur, acest lucru nu demonstrează că forma nu este corectă în
limba considerată, ci doar faptul că ea nu se regăsește în dicționarul utilizat.
Arhitectura programului este detaliată în figura 5:
Figura 5. Arhitectura programului Spell -Checker Agent.
Modulul de prelucrare a textului poate fi considerat de asemenea
drept agent. Deși aparține thread -ului principal, el are un comportament
reactiv, fiind declanșat de evenimentul OnTextChanged al controlului de
editare RichTextBox, adică în momentul când se tastează, se șterge ceva sau
se încarcă un text nou dintr -un fișier. Acest modul împarte textul în cuvinte și
separatori, care constituie de fapt codomeniul funcției de percepție a
agentului de verificare. Se poate considera chiar că mediul agentului este
mulțimea cuvintelor din text împreună cu atributele acestora (neverificat,
corect, incorect). Chiar dacă agentul determină și modificarea aspectului
textului din control, el acționează în principal asupra a cestei liste de cuvinte
și atribute.
Programul dispune de un dicționar vast, de aproximativ 100.000 de
cuvinte. Se impuneau deci unele încercări de optimizare a procesului de
căutare. În primul rând, agentul are un index al cuvintelor din dicționar;
atunci când trebuie să verifice un anumit termen, el nu parcurge întreaga listă,
ci numai formele care încep cu aceeași literă. Metoda de indexare poate fi
îmbunătățită prin tehnici specifice de căutare în bazele de date. În al doilea
rând, modulul de descompune re a textului cercetează dacă un anumit cuvânt
nu a fost prelucrat anterior. În acest caz, el preia direct valoarea respectivă,
deoarece nu ar avea nici un rost parcurgerea din nou a unei părți din dicționar
când rezultatul este deja cunoscut. Modul de fun cționare al agentului este
determinat de o serie de comportamente de tip reactiv:
Nivelul 0 : Evită accesarea mediului în același timp cu utilizatorul. Cele
două fire de execuție rulează în paralel. Textul poate fi considerat o
resursă critică și poate fi a ccesată în mod exclusiv. În caz contrar, s -ar
putea pierde informații, unele fragmente ar putea fi șterse sau suprascrise;
Nivelul 1 : Ignoră cuvântul în curs de editare. De cele mai multe ori, acesta
va fi considerat incorect. Prin urmare, nu ar avea rost actualizarea
permanentă a mediului pentru un cuvânt incomplet, fapt care l -ar putea
incomoda și pe utilizator;
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. Actualizează aspectul controlului de
editare prin colorarea cuvintelor marcate și afișarea textului. În tot acest
timp, controlul este blocat. Important este ca acest interval să fie cât mai
scurt, astfel încât să nu deranjeze utilizat orul.
Ierarhia comportamentelor menționate este următoarea:
Nivelul 0 Nivelul 1 Nivelul 2 Nivelul 3 (17)
Analiza programului. În continuare, se vor analiza caracteristicile
agentului și ale mediului de execuție.
1. Caracteristicile agentului.
Autonom ia sa este asigurată de faptul că acționează într -un thread separat
de programul principal.
Reactivitatea este evidentă, el răspunde schimbărilor din mediu, adică
apariției noilor cuvinte, prin verificarea și marcarea corespunzătoarea a
acestora. Deși con ceput ca un agent reactiv, comportamentul său global
poate fi considerat proactiv: evidențierea greșelilor de ortografie din text.
Abilitățile sociale nu pot fi studiate, deoarece nu este un sistem
multiagent.
2. Caracteristicile mediul de execuție este accesibil, agentul poate
obține informații complete despre starea sa curentă. De asemenea, este
dinamic și nedeterminist , schimbările și incertitudinea fiind introduse de
utilizator; agentul nu poate ști ce cuvânt va fi introdus în momentul următor.
Mediul este episodic : modalitatea de tratare a unui cuvânt nu depinde de
acțiunile anterioare ale agentului. De asemenea, mediul este discret . Deși
numărul de cuvinte care pot fi analizate este practic infinit, totuși mulțimea
acestora este o submulțime a mulțimi i cuvintelor nevide, A+, peste mulțimea
caracterelor alfanumerice A: A+ = {…, 0, 1,…, A, B,… a, b,…, aa, ab,…, aaa,
aab,…}.
4. Arhitecturi BDI -(Beliefs -Desires -Intentions)
În acest tip de arhitectură, propusă de Rao și Georgeff [ARaGE91],
starea agentului este definită de trei caracteristici: convingeri („beliefs"),
dorințe („desires") și intenții („intentions").
Modelul încearcă o adaptare în domeniul agenților a filosofiei
raționamentului practic, care presupune mai întâi stabilirea scopului , printr –
un proces deliberativ, și apoi evidențierea mijloacelor disponibile pentru
atingerea acelui scop.
Într-un proces rațional de urmărire a unui scop pot fi identificate
câteva etape, deduse în principal din analiza unui comportament uman optim
de lua re a deciziilor. În primul rând, trebuie identificate dorințele, adică
mulțimea scopurilor de atins. Se presupune, de exemplu, un agent care,
acționând în numele unui utilizator uman, dorește să găsească unele
informații în diverse baze de date de pe Inter net. Se consideră că unele baze
de date sunt mai mari și mai complete, însă pot fi accesate doar contra cost,
iar altele, mai numeroase dar cu mai puține informații, pot fi consultate
gratis.
Agentul trebuie să determine opțiunile disponibile , în funcție d e
posibilitățile de acțiune. Dacă utilizatorul nu are destui bani, bazele de date
complete nu pot fi utilizate. Rămâne opțiunea bazelor de date gratuite, care
necesită un efort mai mare de căutare, deoarece probabilitatea găsirii
informațiilor este mai red usă. Alegerea acestei alternative semnifică intenția
agentului.
În același timp, trebuie să existe convingerea că scopul poate fi atins.
Agentul trebuie să considere că există șanse pentru descoperirea datelor.
Dacă probabilitatea ar fi evaluată la 0, adic ă dacă agentul ar avea convingerea
că realizarea scopului în acest mod este imposibilă, urmărirea în continuare a
intenției curente ar fi irațională.
În continuare, dacă agentul are motive să -și mențină o anumită
intenție, trebuie să facă un efort acceptab il pentru împlinirea acesteia. Dacă o
direcție de acțiune eșuează, este necesară reluarea acesteia sau selectarea unei
alte direcții. De exemplu, dacă o bază de date este inaccesibilă momentan
(este închis serverul pe care se află ea), agentul poate încerc a din nou, mai
târziu. Dacă situația se repetă, agentul poate trage concluzia că aceste
încercări sunt inutile, că este o pistă greșită și în consecință va elimina din
lista sa baza de date respectivă. El va consulta în continuare celelalte baze de
date ră mase.
Este important ca, în timp ce se urmărește o anumită intenție, să nu se
încerce acțiuni care intră în conflict cu aceasta. În cazul considerat, agentul
trebuie să se concentreze asupra regăsirii datelor utile. Dacă s -ar încerca
simultan și descărcare a unor filme sau piese muzicale, acest lucru ar însemna
o irosire a resurselor, ceea ce ar determina un timp de răspuns mult mai mare.
Intențiile trebuie să fie persistente. Dacă agentul ar renunța după
primul eșec, nu și -ar mai îndeplini niciodată sarcini le complexe. El trebuie să
facă toate eforturile pentru găsirea posibilităților încununate de succes. Cu
toate acestea, dacă devine clar că scopul nu poate fi atins, agentul trebuie să
poată renunța la intenție. De exemplu, dacă după consultarea tuturor ba zelor
de date, informațiile nu au fost găsite, este logic ca agentul să îl anunțe pe
utilizator despre acest lucru, deși teoretic ar fi posibilă o actualizare ulterioară
a unei baze de date, în care să fie adăugate informațiile dorite.
De asemenea, dacă di spare motivul care stă la baza unei intenții,
aceasta trebuie abandonată. Dacă utilizatorul nu mai are nevoie de datele
cerute, nu mai are rost ca agentul să continue căutarea. Sintetizând, un agent
BDI (Beliefs -Desires -Intentions) efectuează următoarele f uncții [Tnorm95]:
Generarea unei liste de opțiuni, mijloacele alternative pentru satisfacerea
intențiilor curente. Noile opțiuni sunt generate pe baza convingerilor și
dorințelor agentului;
Selectarea unei submulțimi din aceste opțiuni, pe baza convingeril or,
dorințelor și intențiilor curente. Noile intenții, adică opțiunile selectate
pentru aplicare, sunt adăugate structurii de intenții;
Structura de intenții are o organizare ierarhică, pe diferite nivele de
abstracțiune. Agentul BDI își rafinează treptat intențiile, ajungând la
acțiuni primitive care pot fi executate imediat. Dacă există o asemenea
acțiune atomică în structura de intenții, ea este executată;
Dacă agentul și -a îndeplinit intenția sau a decis că intenția nu poate fi
îndeplinită, aceasta este abandonată. Se poate spune că agentul renunță la
o intenție dacă aceasta nu mai este justificabilă [PcoLe90];
Convingerile agentului sunt actualizate și algoritmul se reia.
După cum s -a menționat, pentru agenții cu această arhitectură este
important echil ibrul dintre situațiile în care ei trebuie să -și mențină și să -și
urmărească intențiile curente, chiar în urma unui eșec, și situațiile în care
trebuie să -și reanalizeze și eventual să -și abandoneze intențiile. Un agent care
nu se oprește niciodată să -și reconsidere acțiunile va continua execuția chiar
și atunci când este clar că încearcă imposibilul. Un agent care încearcă în
permanență să -și evalueze scopurile și intențiile nu va avea suficient timp să
acționeze efectiv pentru îndeplinirea lor. Este evide nt că în proiectarea unui
agent BDI trebuie să se realizeze un compromis între aceste două tendințe.
Kinny și Georgeff [KiMGe91] au efectuat un număr de experimente
într-un cadru de agenți BDI numit dMARS. Ei au analizat modul în care se
comportă agenții î ndrăzneți („bold") și cei prudenți („cautious") în medii cu
rata schimbărilor y variabilă. S -a constatat că atunci când rata y era mică
(mediul nu se schimba prea repede), agenții îndrăzneți au avut evoluții
superioare, deoarece nu pierdeau timpul reanaliz ându -și mereu obiectivele.
Când y era mare (mediul se schimbă des), agenții prudenți se comportau mai
bine, pentru că se puteau adapta modificărilor frecvente.
Concluzia este că în mediile statice sunt mai potriviți agenții cu un
comportament proactiv, ori entat spre scop, în timp ce în mediile dinamice
necesită un comportament reactiv, care să modifice permanent intențiile
curente în funcție de situație.
Pentru a formaliza componentele unei arhitecturi BDI, fie Bel
mulțimea tuturor convingerilor, Des mulțim ea tuturor dorințelor iar Int
mulțimea tuturor intențiilor posibile. În general, aceste mulțimi sunt compuse
din formule logice de ordinul întâi. Starea unui agent BDI, la un moment dat,
este o tripletă (B, D, I), unde BBel, DDes și IInt.
În figura 6 se prezintă schematic modul de selecție al unei acțiuni [GweiB00].
Figura 6.
Diagrama
unei
arhitectur
i BDI.
Funcția de revizuire a convingerilor (belrev ) are rolul de a actualiza
mulțimea convingerilor pe baza perceptelor și covingerilor curente:
belrev :(Bel)×P→ (Bel) (18)
Funcția de generare a opțiunilor (optgen ) are rolul de a decide cum
vor fi atinse obiectivele:
optgen : (Bel) × (Int)→(Des) (19)
Această funcție trebuie să recunoscă oportunitățile apărute în mediul
de execuție și să ofere agentu lui noi modalități de a -și îndeplini intențiile sau
posibilitatea de a atinge obiective care nu puteau fi atinse anterior.
Procesul deliberativ al agentului este modelat de o funcție filtru
(filter ), care actualizează mulțimea intențiilor pe baza intenții lor prealabile și
a convingerilor și dorințelor curente:
filter: (Bel)×(Des)×(Int)→(Int) (20)
Această funcție filtru (filter ) trebuie să asigure:
abandonarea intențiilor irealizabile sau pentru care costul de realizare este
mai mare decât beneficiul a sociat cu îndeplinirea lor;
menținerea intențiilor nerealizate încă, dar despre care se presupune că
pot aduce un câștig;
adoptarea de noi intenții, pentru realizarea intențiilor existente sau pentru
exploatarea noilor circumstanțe favorabile apărute.
Filtrul nu poate introduce de la sine noi intenții. Acestea sunt ori
intenții anterioare, ori opțiuni nou adoptate:
B(Bel), D(Des), I(Int), filter(B,D,I) ID (21)
Funcția de execuție (exec) returnează o intenție atomică executabilă:
exec: (Int) → A (22
Funcția de selecție a acțiunii următoare este de forma:
act: P → A (23)
și rezultă pe baza algoritmul următor [GweiB00]:
function act(p: P): A
begin B = belrev(B, p)
D = optgen (D, I)
I = filter(B, D, I) return exec(I)
end
În practică, repreze ntarea intențiilor printr -o mulțime nestructurată
este prea simplistă. De aceea, se poate asocia fiecărei intenții o anumită
prioritate, care să indice importanța sa relativă. De asemenea, intențiile pot fi
implementate sub forma unei stive. Când este adop tată o intenție, aceasta este
introdusă în stivă. Când este îndeplinită, este extrasă din stivă. Intențiile mai
concrete se vor găsi mai aproape de vârful stivei, iar cele mai abstracte – în
partea inferioară a acesteia.
Arhitectura BDI este un model intui tiv de simbolizare a procesului de
decizie, oferind și o descompunere funcțională clară a problemei pe care
trebuie să o rezolve agentul. Modelul este interesant și datorită efortului
susținut de formalizare a sa. Astfel, Rao și Georgeff [ARaGe92] au dezvo ltat
o serie de logici BDI, pentru definirea unor proprietăți axiomatice ale
agenților raționali.
5. Arhitecturi stratificate
Comportamentele de tip reactiv și proactiv de care trebuie să dispună
un agent inteligent, pot fi asigurate prin descompunerea t ipurilor amintite în
subsisteme separate, care să propună acțiuni specifice. Ideea care stă la baza
acestui tip de arhitectură este existența mai multor straturi care
interacționează, fiecare cu un anumit caracter. În funcție de modul în care se
realizează controlul și transmiterea informațiilor, se pot deosebi două mari
categorii de arhitecturi stratificate:
Stratificare orizontală : Nivelurile software sunt fiecare direct conectate
la intrări și la ieșiri cu senzorii și efectorii acțion ând în paralel . Fiec are
nivel acționează ca un agent, prezentând propriile sugestii în ceea ce
privește următoarea acțiune care trebuie executată. Acestea oferă
simplitate, în sensul că existența unui nou nivel nu implică modificări
semnificative. Totuși, deoarece nivelele po t acționa în același timp este
posibil ca agentul să aibă un comportament inconsistent. Pentru a asigura
consistența trebuie inclus un mediator care are rolul de a decide cine are
controlul asupra agentului la un anumit moment. Aceasta implică faptul
că to ate interacțiunile posibile trebuiesc considerate.
Stratificare verticală : Senzorii și efectorii sunt administrați de cel mult
un nivel fiecare. În arhitecturile verticale, controlul se propagă de la un
nivel la altul. Sunt posibile două cazuri:
Fluxul de informație parcurge nivelele de jos în sus, iar fluxul de control
le parcurge în sens invers;
Fluxul controlului parcurge toate nivelele pînă la nivelul superior, care
generează acțiunea.
Avantajul principal al stratificării orizontale este simplitatea
conceptuală: dacă un agent trebuie să manifeste n tipuri de comportament,
atunci vor fi implementate n straturi (figura 7). Totuși, deoarece straturile
concurează pentru generarea de sugestii privind acțiunile, trebuie asigurată
coerența comportamentală pe an samblu [GweiB00]. De regulă, se introduce o
funcție de mediere, care decide ce strat deține controlul la un moment dat.
Însă proiectarea acestei funcții poate fi foarte dificilă – pentru n straturi care
pot propune fiecare m acțiuni, funcția trebuie să fie capabilă să trateze mn
variante posibile.
Figura 7.
Stratificare
orizontală.
Aceste probleme sunt atenuate într -o stratificare verticală (figura 8).
Acest tip de arhitectură poate fi divizat în două subcategorii, din punctul de
vedere al modului de co ntrol [GweiB00]:
Control cu trecere simplă („one pass control") : controlul parcurge
secvențial nivelele, până când ultimul nivel generează o acțiune;
Control cu trecere dublă („two pass control") : primul pas constă în
trimiterea informațiilor spre nivelele superioare, iar al doilea pas
reprezintă trimiterea deciziei de acțiune înapoi spre straturile inferioare.
Acest tip de control se aseamănă cu procesul luării deciziilor într -o
organizație cu o ierarhie bine definită.
Figura 8. Stratificare verticală.
În ambele cazuri, complexitatea interacțiunilor dintre straturi este mai
redusă în comparație cu arhitecturile stratificate orizontal. Dacă fiecare strat
poate sugera m acțiuni și există n-1 interfețe între cele n nivele, numărul
maxim posibil de interacți uni este m2(n -1). Dezavantajul acestei abordări
constă în reducerea flexibilității – informațiile și deciziile trebuie să parcurgă
toate straturile. O eroare la un anumit nivel se va propaga, afectând
performanțele agentului.
În cadrul SMA, care sunt forma te din agenți cognitivi, fiecare agent
dispune de o bază de cunoștințe care cuprinde informațiile necesare realizării
sarcinii sale și gestiunii interacțiunilor cu ceilalți agenți și cu mediul în care
se află. Agenții sunt “conștienți”, adică au scopuri și planuri explicite pentru
a le realiza.
Sistemele multi -agent constituite din agenți reactivi se bazează pe
principiul că nu este absolut necesar ca agenții să fie “inteligenți” individual
deoarece sistemul are un comportament global inteligent. Agenții a cționează
conform unui mecanism de reacție la evenimentele externe, iar deciziile lor
se bazează în întregime pe starea prezentă a mediului, fară nici o referire la
trecut. Acest mecanism nu ține cont nici de explicitarea scopurilor, nici de
mecanisme de p lanificare.
Formal comportamentul unui agent reactiv poate fi reprezentat prin
funcția descrisă de ecuația (24). Un astfel de agent poate reprezenta un
termostat a cărui funcție este:
scazuta ra temperatus daca ridicata ra temperatus )(incalzestedaca racestes actiune
(24)
În realitate, clasificarea agenților în ag enți cognitivi și reactivi se
poate face urmărind două caracteristici, care generează două axe.
Conduita agenților este generată de diferențele între comportamentul
dirijat către scopuri explicite și comportamentul reflex, dirijat de percepții.
Prin defini ție, toți agenții sunt îndemnați la acțiune de tendințele lor.
Tendințele pot proveni din mediul în care se află agenții, sau agenții le pot
avea explicit exprimate. În primul caz, se poate vorbi de comportament
reflexiv, iar în cel de -al doilea de comport ament predefinit.
Relația între agent și mediul în care se află pune problema de a ști
dacă agentul dispune de o reprezentare simbolică explicită a mediului său,
dacă poate raționa, plecând de la această reprezentare, sau dacă această
reprezentare se situe ază la nivel sub -simbolic, adică este integrată în
capacitățile sale senzo -motorii. În primul caz, agenții sunt cognitivi, în cel de –
al doilea caz, agenți sunt reactivi. Aceste două caracteristici, combinate
determină patru tipuri de agenți (tabelul 1).
Tabelul 1. Cele patru tipuri de agenți.
Conduita /Relația cu mediul Agenți cognitivi Agenți reactivi
Predefinită Agenți bazați pe logică Agenți pur reactivi
Reflexă Agenți intenționali Agenți hibrizi
Agenți bazați pe logică. Pentru acești agenți deciz ia este realizată
prin deducție logică, iar starea internă este o bază de date de formule în logica
predicatelor de ordinul întîi: Deschide (valoare 255)
Temperatura (reactor 7, 300)
Presiune (rezervor 3, 25)
Dacă L este setul de propoziții, D=(L) este m ulțimea de baze de
date, iar 1, 2,….sunt submulțimi ale D. Procesul de decizie al unui agent
este modelat prin mulțimea de reguli implicite . poate fi scris dacă
formula poate fi demonstrată din folosind numai regulile implicite .
Funcția a cțiune a unui agent poate fi definită astfel:
Funcție acțiune ( : D) : A
pentru fiecare a A execută
dacă Do(a) atunci
returnează a
sfîrșit_dacă
sfîrșit_pentru_fiecare pentru fiecare a A execută
dacă Do(a)
atunci
returnează a
sfîrșit_dacă
sfîrșit_pentru_fiecare
returnează NULL
sfîrșit_funcție
Setul de regului de deducție și baza de date pentru un agent este
concepută astfel încât, dacă o formulă Do(a) poate fi derivată, atunci a este
cea mai bună acțiune care poate fi executată. Dacă Do(a) nu poate fi dedusă,
se încearcă găsirea unei acțiuni care este consistentă cu regulile bazei de date,
adică o regulă care nu este interzisă. Dacă o astfel de acțiune nu poate fi
găsită, atunci nici o acțiune nu este selectată.
Pentru agenții bazați pe logică, luarea unei decizii este văzută ca
deducție. Realizarea unor agenți într -o astfel de abordare este elegantă și este
o abordare clară. Dezavantajele acestei abordări sunt complexitatea de calcul
mare și faptul că abordarea poate fi aplicată în medii mai puțin dinamice, în
care mediul nu se modifică semnificativ în timp ce agentul ia decizia și deci o
acțiune care este rațională când procesul de decizie a început va rămâne
rațională și când aceasta este executată.
Agenți intenți onali. Acești agenți se bazează pe teoria BDI
(believe -desire -intention) [ARaGe91], care pornește de la filosofia rațiunii
practice [BMEPME88]. Aceasta implică două procese esențiale: decizia
scopurilor care trebuiesc îndeplinite și cum pot fi acestea înde plinite .
Primul proces este cunoscut sub denumirea de deliberare și cel de -al doilea
means -end reasoning .
Procesul de decizie începe prin a înțelege care sunt opțiunile
existente, ceea ce duce la generarea unui set de alternative. După generarea
setului d e alternative, se face selecția între ele și angajarea pentru o
alternativă. Aceasta devine intenție care determina acțiunile agentului.
Starea unui agent BDI la un anumit moment este dată de (C, D, I) ,
unde C este un element din mulțimea credințelor, CCredințe , D este un
element din mulțimea dorințelor, DDorințe , iat I este un element din
mulțimea intențiilor, IIntenții .
Funcția de revizuire a credințelor agentului este definită ca:
frc: (Credințe) P (Credințe)
și determină noul set de credințe p e baza percepțiilor curente și a credințelor
curente.
Funcția de generare a opțiunilor face corespondența între setul de
credințe și intenții și setul de dorințe:
opțiuni: (Credințe) (Intenții) (Dorințe)
Procesul deliberativ al agentului poate fi de scris de funcția:
filtrare: (Credințe) (Dorințe) (Intenții) (Intenții)
Funcția execută este definită pentru a determina ce acțiune trebuie
executată pentru a realiza o anume intenție. Funcția de decizie a agentului
poate fi astfel implementată:
Funcție acțiune(p : P) : A
C:= frc(C, p)
D:= opțiuni(D, I)
I:= filtrează(C, D, I)
returnează execută(I)
sfârșit_funcție
Avantajele unei astfel de arhitecturi sunt: este intuitivă, și este
posibilă o descompunere funcțională clară care să indice subs istemele
necesare pentru a concepe un agent. Printre dezavantaje trebuie enumerat
faptul că nu se poate realiza ușor implementarea eficientă a acestor funcții.
Nivelul n
Nivelul 2
Nivelul 1
Modul Mediator Modul intrări Modul Actiuni Intrări
Ieșiri
Figura 9.
Reprezentare
a abstractă a
unui agent
hibrid cu
nivele
orizontale.
Agenți hibrizi. Dacă, pentru un agent, cerințele sunt de a avea un
comportament reactiv dar și pro -activ, se pot implementa subsisteme separate
care să îndeplinească cele două caracteristici cerute. Aceasta conduce la
implementarea agenților utilizînd o arhitectură cu mai multe nivele ( orizontal
și vertical ) figura 9.
Rezumatul unității de studiu
Se consideră că agentul este influențat de mediul în care se află dar
și exercită influență asupra mediului. Percepția contribuie la realizarea unei
reprezentări a mediulu i. Sistemul perceptiv poate fi: pasiv si activ;
Cunoștințele (ca noțiune definită în inteligența artificială) reprezintă
ansamblul de informații (fapte cunoscute, experiența, concepte) necesare unui
individ (sau unei mașini) pentru a se organiza și a rezolva o sarcină sau o
problemă considerată complexă. Problema cunoașterii este legată de noțiunile
de conceptualizare și raționament.
Un agent inteligent poate însă decide acțiunea următoare și în
funcție de stările mediului pe care l e-a traversat până la un moment dat, de
„experiența" acumultată.
Agenții bazați pe logică au stările interne organizate sub forma unei
mulțimi de formule predicative de ordinul întâi
În funcție de modul în care se realizează controlul și transmiterea
infor mațiilor, se pot deosebi două mari categorii de arhitecturi stratificate:
orizontala si verticală;
În cadrul SMA, care sunt formate din agenți cognitivi, fiecare agent
dispune de o bază de cunoștințe care cuprinde informațiile necesare realizării
sarcinii sale și gestiunii interacțiunilor cu ceilalți agenți și cu mediul în care
se află.
Sistemele multi -agent constituite din agenți reactivi se bazează pe
principiul că nu este absolut necesar ca agenții să fie “inteligenți” individual
deoarece sistemul are un comportament global inteligent.
Autoevaluare
Test de autoevaluare a cunoștințelor din modulul I
8 Sistemul reprezentational al unui agent face apel la următoarele noțiuni:
reprezentare, opinie, cunoștințe . Cunoștințele (ca noțiune definită în
inteligența artificială) reprezintă ansamblul de informații (fapte
cunoscute, experiența, concepte) necesare unui individ (sau unei
mașini) pentru a se organiza și a rezolva o sarcină sau o problemă
considerată complexă.
9
Sistemul interacțional – are la bază noțiu nea de percepție, definită ca
modalitatea prin care agentul preia informații din mediu. Percepția oferă
agentului posibilitatea să obțină informațiile despre mediul în care se
află, ceea ce îi permite să elaboreze acțiuni pentru a -și urmări țelul.
Sistemul reprezentațional – al unui agent face apel la următoarele
noțiuni: reprezentare, opinie, cunoștințe . Este important de stabilit care
sunt categoriile conceptuale apriori raționamentului agentului și care
sunt diferitele concepte construite de agent plecân d de la cele dinainte
cunoscute, precum și mecanismele practice pe care un agent le folosește
pentru a se putea orienta în mediu sau, a stabili regulile și a rezolva
problemele, a lua deciziile și a -și atinge țelul. Cunoștințele conduc la
elaborarea unui r aționament.
10 ____________ reprezintă capacitatea de a interpreta expresiile în raport
cu ceea ce se numește un model. O expresie nu poate fi evaluată ca
fiind falsă sau adevarată fără a ști la ce sunt atașate simbolurile care
compun expresia și mulțimea unde acestea au valori.
Semantica;
Simbol;
Model;
Expresie;
11 Fie aplicația Virtual Cleaner Agent .
Potriviți descrierea cu termenii cunoscuți referitor la agenți și
mediu:
autonomie – este concepută ca un thread (fir de execuție) separat, care
rulea ză în paralel cu thread -ul principal.
reactivitatea – este determinată de analiza stării mediului și deducerea
acțiunii următoare.
proactivitatea – se referă la urmărirea scopului principal: căutarea
„prafului" și curățarea sa.
abilități sociale – acțio nează într -un sistem multiagent.
mediul de execuție – este discret (o matrice cu 12 elemente), foarte
simplu: fiecare celulă din rețea are numai două stări posibile
(curat/murdar).
mediu episodic – performanțele agentului nu depind de istoria sa.
12 Arhit ecturi BDI -(Beliefs -Desires -Intentions)
În arhitectura BDI starea agentului este definită de trei
caracteristici: convingeri („beliefs"), dorințe („desires") și intenții
(„intentions"). În figură se prezintă schematic modul de selecție al unei
acțiuni?
DA
13 Arhitecturi stratificate
În funcție de modul în care se realizează controlul și transmiterea
informațiilor, se pot deosebi două mari categorii de arhitecturi
stratificate. In figură se prezintă?
Stratificare orizontală;
Stratificare verticală;
Tema de control nr. 1
Exemplificați arhitectura BDI cu aplicații practice.
Modulul III. Comunicația între agenți si
platformă
Obiective operaționale:
Protocoalele de comunicație la diferite niveluri;
Protocoale de interacțiune între agenți;
Luarea deciziei în mod distribui;
Criterii de evaluare;
Mecanismul de licitație;
Mecanismul de negociere;
1. Comunicația între agenți
Agenții comunică pentru a -și realiza scopurile proprii sau pentru a
realiza scopurile comune . Comunicația permite agenților să -și coordo neze
acțiunile și comportamentul ceea ce face ca sistemul multi -agent să fie mai
coerent. Agenții pot trimite și recepționa mesaje folosind rețeaua de
comunicație. Mesajele pot fi: afirmații și interogări . Protocoalele de
comunicație sunt specificate în mo d normal la diferite niveluri:
nivelul de specificare al metodei de interconexiune;
nivelul de specificare a formatului sau sintaxei informației
care este transferată;
nivelul de specificare a semanticii informației.
Există protocoale binare și protocoale n-are. Protocoalele binare
presupun comunicația între doi agenți, iar cele n-are implică un agent care
transmite informație și mai mulți agenți care recepționează informația.
KQML (Knowledge Query and Manipulation Language) a fost dezvoltat ca
protocol pen tru schimbul de informații și de cunoștințe între agenți
[TFDMF92]. Pentru reprezentarea cunoștințelor în mediile multi -agent s -a
dezvoltat limbajul KIF (Knowledge Interchange Format). În afară de limbajul
KIF, care poate fi folosit într -un mesaj KQML, pot fi folosite și limbajele
PROLOG, LISP, SQL sau orice alte limbaje de comunicație între agenți.
Protocoalele de comunicație constituie nivelul cel mai de bază,
necesar într -un sistem multi -agent. Protocoalele de nivel superior care sunt
necesare a fi defin ite într -un sistem multi -agent se bazează pe protocolul de
comunicație.
Efectul comunicației între agenți asupra opiniilor acestora.
Agenții au informații despre o anumită stare a mediului, dar mediul
evoluează și starea se modifică. În aceste situații, agenții trebuie să -și
revizuiască cunoștințele pe care le au dacă anumite fapte sunt modificate. În
urma revizuirii opiniilor, se formează alte opinii, teorii, etc. Agentul face
observații asupra mediului în care evoluează și prin interacțiunile sale cu
acesta și cu alți agenți. Pentru rezolvarea surselor de incertitudine a
consistenței globale, agenții își comunică ipotezele pe care le -au formulat
plecând de la cunoștințele pe care le au și eventual probele care susțin aceste
ipoteze (depinzând de nivelul de abstractizare al informațiilor comunicate).
Descrierea Teoriei Logicii Implicite (TLI) . Logica implicită are
un rol important în domeniul aplicațiilor dezvoltate în medii incomplet
specificate și furnizează un mijloc de a completa într -un mod consiste nt setul
incomplet de cunoștințe despre acel mediu, bazat pe presupuneri care trebuie
revizuite sau înlăturate în urma unor observații ulterioare. Pentru
reprezentarea logicii implicite bazate pe presupunere se propune logica TLI
[Florea97]. Teoria logică implicită, este formată de o pereche (,), unde
este un set de formule în logica predicatelor de ordinul întâi și un set de
reguli de inferență implicită, având forma:
d: [].
Se folosesc notațiile: Baza (d) este , Pres (d) este ; Baza
()={Baza(di) | di }, Pres()={Pres(di) | di }.
O formulă F este consecință logică implicită a unei logici TLI, cu
un set consistent, dacă există un subset a regulilor de inferență implicite
(generale sau instanțe) D astfel încât:
Baza (D) F și setul Baza(D) Pres (D) este satisfăcătoare.
O extensie a unei logici TLI este setul tuturor consecințelor logice implicite a
subteoriei maximale a (, ), cu D .
O logică TLI poate avea mai multe extensii, corespunzătoare
diferitelor seturi de ipoteze (opinii) pe care agentul le are despre mediul
incomplet specificat în care trebuie să raționeze bazându -se pe presupuneri.
Pentru a se putea impune criterii intuitive sau semantice pentru selecția unei
anumite extensii dintre extensiile unei teo rii de bază TLI, se introduce o
relație de preferință între seturile de reguli de inferență implicită.
O relație de preferință asupra unui set de reguli de inferență implicită
este o relație parțială, ireflexivă și tranzitivă definită pe o partiție a set ului
de relații , notată <, și < Part() x Part (). Dacă 1 < 2, cu 1 , 2,
Part (), atunci toate regulile din 1 sunt preferate celor din 2 , iar toate
regulile dintr -o partiție sunt la fel preferate.
Extinzând o logică TLI cu această relație de preferință, construirea
extensiilor logicii pot fi modificate prin adăugarea unei relații de preferință
asupra extensiilor.
Includerea opiniilor altui agent. Logica TLI poate fi folosită
pentru a descrie structura internă, comportamentul și logica agenți lor, în
cadrul sistemului. Opiniile unui agent a A, caracterizat de teoria (a, a),
sunt date de setul:
Bela = { | este demonstrabilă în teoria TLI ( a, a) a agentului a }
O formulă Ba() este adevarată dacă Bela. Setul de opinii ale
agentului su nt reprezentate de o extensie a teoriei sale implicite. Agentul
poate avea mai multe seturi de opinii alternative corespunzătoare diferitelor
seturi de extensii ale logicii TLI (a, a). Aceste seturi diferite corespund
interpretărilor pe care agentul le f ormulează despre mediul în care evoluează.
Poate fi adăugată teoriei agentului o relație de preferință (a, a ,<a) și se
pot specifica mai multe modalități prin care opiniile unui agent influențează
opiniile altui agent:
completarea setului de opinii ale acestuia și permite obținerea
altora;
aduce posibilitatea selecției între seturile alternative de opinii
ale agentului;
permite detectarea inconsistențelor între opiniile unui grup de
agenți sau la nivelul sistemului multi -agent;
creează bazele formării co alițiilor.
În [EDVLC87] este definit un set de axiome de relaționalitate
conform cărora un agent a poate include opiniile altui agent B.
A1. BaBb()Ba(); Axioma specifică faptul că dacă agentul
A consideră opiniile agentului B ca adevărate le include în setul său de opinii
a. Folosirea acestei axiome generează ocazional inconsistențe între opiniile
agentului A. Altă posibilitate este ca agentul A să includă în setul său de
opinii, opiniile agentului B sub forma unei ipoteze revizuite, adică printr -o
regulă de inferență implicită în a folosind următoarea axiomă.
A2. BaBb()Ba(db:[]); Astfel, opiniile agentului A
sunt completate cu ipotezele agentului B formând posibile extensii ale teoriei
agentului A. Regulile implicite obținute pe baza opinii lor agentului B sunt
notate ab, A având acum setul de reguli de inferență implicită
a`=aab. Axioma A2 poate fi îmbunătățită, dacă este asociată o relație
de preferință pe a` care poate impune preferința asupra regulilor implicite
ale agentului A asup ra regulilor obținute de la agentul B folosind axioma A2.
Aceasta relație se poate exprima astfel:
a < ab
Este posibil ca a și ab să fie preferate în aceeași măsură.
Faptul că agentul A consideră a<ab se poate formaliza astfel:
Pa (db, prefb),
iar dacă nu există o relație de preferință a agentului A între a și ab se poate
formaliza astfel:
Pa (db, prefa).
Folosind aceste convenții, axioma A2 poate fi modificată astfel:
A2`. BaBb() Ba(db: [ ] ) Pa (db, prefa),
A2”. BaBb() Ba(db: [ ] ) Pa (db, prefb).
Aceste axiome sunt numite axiome comportamentale, adică A1 este
axioma ascultării, A2` este axioma încrederii , A2” este axioma
circumspecției . Aceste axiome se modifică în cazul în care agentul A are
definită o relație de pref erință asupra opiniilor proprii sau dacă agentul A
încearcă să includă opinii de la mai mulți agenți B1, B2,…Bn.
Extinderea setului de opinii ale agenților prin comunicație.
Agenții își transmit mesaje prin care își comunică opiniile (extensii ale te oriei
proprii) pentru soluționarea inconsistențelor. În funcție de mesajul primit, un
agent execută diferite acțiuni. În [TFDMF92] sunt specificate primitive ale
limbajului de comunicație între agenți KQML. Din setul de primitive de
comunicație specificate de KQML vor fi folosite următoarele primitive:
ASK_IF (a, ) – agentul B întreabă agentul A dacă aparține setului său
de opinii;
TELL (a, ) – agentul care transmite, B, comunică agentului A opinia
sa, , (Bb());
ACHIVE (a, ) – agentul B cere agentu lui A să includă în setul său de
opinii;
DENY (a, ) – agentul care transmite mesajul comunică agentului A
faptul că nu crede în ipoteza (Bb());
INCONS (a, ) – transmițătorul cere agentului A să verifice dacă este
consistentă cu setul său de opin ii (detectând setul posibil
de inconsistențe);
REPLY (a, ) – agentul B trimite răspuns agentului A, răspuns care poate
fi da sau nu.
Includerea opiniilor unui alt agent în setul propriu de opinii, se face, utilizând
setul de axiome specificat mai sus. P roblema care apare este de selecție a
uneia dintre axiome, dintre cele trei. Se consideră două criterii de selecție:
bazată pe tipul de informație transmisă, bazată pe credibilitatea pe care o
are agentul .
Primul criteriu presupune că un agent transmite ce luilalt opinia sa și
modul în care și -a format opinia pe care o transmite. Agentul care primește
informația urmărește și tipul informației primite. Astfel, primitiva de
comunicație TELL este modificată:
TELL (a, , tip),
unde tipul este:
tip = cert – dacă transmițătorul B are b sau este
justificată bazându -se numai pe elementele din b;
tip = ext – dacă transmițătorul B justifică bazându -se pe
elemente din b ( aparține unei extensii a teoriei
agentului B);
tip = toate_ext – dacă aparține tutur or extensiilor teoriei
agentului B.
Efectul mesajului TELL asupra opiniilor agentului care îl primește în
funcție de parametrul tip, specificat anterior, este prezentat în tabelul 1:
Tabelul 1. Efectul comunicației între agenți.
Agentul B comunică agentul ui A Efectul comunicației
TELL (a, , cert) BaBb () ax. Ascultării
TELL (a, , ext) BaBb () ax. Circumspecției
TELL (a, , toate_ext) BaBb () ax. Încrederii
TELL (a, , ext) DENY (a, ) BaBb () ax. Încrederii
Altă posibilitate de a sel ecta axioma comportamentală pe care să o
folosească este de a lua în considerare credibilitatea agentului care transmite
informația. Credibilitatea unui agent este apreciată în funcție de calificarea sa
sau de onestitatea sa. Într -un sistem închis credibil itatea unui agent este
stabilită în faza de concepție a sistemului, iar într -un sistem deschis
credibilitatea poate fi modificată și este calculată dinamic. Dacă agentul B
este nou intrat în sistem, și transmite agentului A un mesaj, agentul A, care
primeș te informația începe prin a fi circumspect față de agentul B. Dacă se
observă că aproape totdeauna agentul A este de acord cu opiniile agentului B
(nu sunt inconsistente), atunci agentul A începe să devină încrezător în B sau
chiar ascultător.
Interacțiu nea între agenți. Interacțiunea reprezintă stabilirea unei
relații dinamice între doi sau mai mulți agenți prin intermediul unor acțiuni
reciproce. Situațiile în care agenții interacționează sunt: ajutor reciproc,
schimb de date, punerea în comun de cunoșt ințe pentru rezolvarea unei
probleme, repartiția sarcinilor pe mai multe procesoare. Interacțiunile sunt
rezultatul acțiunilor efectuate de mai mulți agenți în același timp. Acestea
sunt un element necesar constituirii unei organizații sociale. Interacțiun ea
este o componentă de bază a unei organizații. Surse ale interacțiunii pot fi:
Scopuri compatibile și incompatibile (în cazul agenților
cognitivi);
Relații asupra resurselor.
Relativ la relația între agenți, scopurile pot fi:
Compatibile, dacă agenții s unt în relații de cooperare;
Incompatibile, dacă agenții sunt în relații antagoniste.
Scopurile agenților A și B sunt incompatibile dacă agenții au ca scop
așteptarea stărilor q și respectiv p, iar p q sau satisfacere (scop(A,p))
satisfacere (scop(B, q)).
În cazul agenților reactivi, obiectivele sunt compatibile dacă
comportamentul de supraviețuire al unuia nu îl afectează pe alt agent. Situația
de cooperare înseamnă că viabilitatea unuia nu afectează în mod negativ un
alt agent.
Resursele reprezintă toate elementele din mediu și materialele utile
necesare pentru realizarea unei activități. Folosirea resurselor din sistem
generează conflicte. Conflictele sunt interacțiuni perturbatoare, adică mai
mulți agenți au nevoie de aceleași resurse în același ti mp și cu aceleași
drepturi. Sunt definite tehnici de coordonare a acțiunilor (pentru evitarea
conflictelor):
ordonarea priorităților;
tehnici de negociere (compromis care modelează
satisfacțiile și frustrările).
Capacitățile agenților în raport cu sarcinil e reprezintă competențele
agenților. Clasificarea interacțiunilor se face ținând cont de sursele principale
ale interacțiunii.
Interacțiunile se clasifică astfel:
independentă;
simpla colaborare caracterizează sistemul de comunicație
(interacțiunile sun t date de alocarea sarcinilor și
partajarea cunoștințelor);
întrepătrundere agenții se “tachinează” între ei în rezolvarea
sarcinilor date;
colaborare coordonată se realizează coordonarea acțiunilor pentru
realizarea sarcinilor și alocării resurselor;
competiție individuală
pură agenții au scopuri incompatibile și negociază
pentru realizarea lor (competiție în care au
aceleași resurse și sunt situați în situații inițiale
identice);
competiție colectivă pură se realizează o grupare pentru satisfacerea
scopurilor.
Protocoale de interacțiune între agenți. Protocoalele de
interacțiune descriu mecanismele prin care agenții schimbă o serie de mesaje.
În cazul în care agenții au scopuri care sunt în conflict sau în cazul în care
agenții sunt necooperanți ob iectivul protocolului este de a maximiza răsplata
agenților. În cazul în care agenții au scopuri similare sau probleme comune,
obiectivul protocolului este de a menține performanța coerentă globală a
agenților fără a viola autonomia lor.
Definirea situ ațiilor de interacțiune între agenți. Rezolvarea în
mod distribuit a problemelor este unul dintre subdomeniile inteligenței
artificiale în care agenți cooperanți sunt organizați pentru a lucra împreună în
rezolvarea problemelor care necesită efort colectiv . Datorită faptului că
resursele, cum ar fi cunoștințe, capabilitate, informații, experiență sunt
distribuite între agenți, un agent într -un sistem distribuit de rezolvare a
problemelor nu este capabil de a -și îndeplini sarcinile singur, sau le va
îndeplin i mai bine în cooperare cu alți agenți. În astfel de cazuri, cele mai
importante aspecte includ găsirea unei soluții pentru: determinarea
scopurilor, determinarea task -urilor comune, evitarea conflictelor, interogarea
pentru a obține noi cunostințe și prob e.
Luarea deciziilor în mod distribuit este considerată un alt subdomeniu
al inteligenței artificiale în care sunt folosiți agenți, în acest caz, agenții pot fi
necooperanți sau pot avea scopuri diferite. În aceste cazuri, fiecare agent
încearcă să își max imizeze profitul propriu, dar prin înteracțiunea dintre
agenții din sistem, care au strategiile proprii, se ajunge la o decizie acceptată
de toți.
Situațiile menționate anterior pot de fapt fi văzute ca două moduri de
coordonare în sistemele multi -agent, c ooperare și competiție și vor fi
analizate în continuare.
Coordonarea în sistemele multi -agent. Coordonarea este o
proprietate a sistemului multi -agent. Gradul de coordonare este dat de gradul
în care se pot evita activități nedorite prin reducerea uti lizării acelorași
resurse, evitarea deadlock -urilor și menținerea unor condiții de siguranță.
Coordonarea în sistemele multi -agent este necesară din următoarele motive:
Prevenirea haosului. Nici unul dintre agenți nu are o
vedere globală asupra întregului grup din care face parte;
Existența constrângerilor globale;
Agenții posedă diferite capacități și posibilități de
expertiză;
Acțiunile pe care le execută agenții sunt adesea
interdependente.
Interacțiune conflicteInteracțiuni
suplimentare
generare conflicte rezolvare conflicte
Coordonare
Cooperare Competiție
Planificare Negociere
Planificare
distribuită Planificare
centralizată
Figura 1. Clasificarea modurilor de coordonare între agenți.
Cooperarea reprezintă coordonarea între agenții care nu se află în
competiție, iar negocierea reprezintă coordonarea între agenții care sunt în
competiție sau agenți necooperanți (figura 1). Pentru a exista o coordonare,
agenții trebuie să mențină modelul celorlalți agenți și, de asemenea, să
dezvolte un model pentru interacțiuni viitoare. Coerența reprezintă gradul în
care sistemul se comportă ca un tot unitar. Una din problemele sistemelor
multi -agent este menținerea coerenței globale fără a exista un control global
explicit. Cooperarea poate fi văzută din două puncte de vedere:
din interior – ca o atitudine intențională – este valabilă pentru agenții
cognitivi;
de la nivelul observatorului – ceea ce duce la stabilirea unui indice de
cooperare.
Funcțiunile cooperării sunt: ameliorarea supraviețuirii individului
(capacitatea sa într -un anumit mediu este definită în funcție de bilanțul
energetic) sau a grupului; creșterea performanțelor; rezolvarea confl ictelor.
Interacțiunile suplimentare necesită definirea (existența) unor tehnici
de negociere, arbitraj și utilizarea unui regulament.
Protocoale de cooperare. Principalele forme de cooperare în
inteligența artificială distribuită sunt: partajarea task -urilor și partajarea
resurselor.
Repartiția task -urilor și a resurselor comune constituie unul dintre
domeniile majore de aplicații ale SMA. Descompunerea și alocarea task –
urilor se poate realiza prin mecanismele organizaționale prin care agenții pot
să pun ă în comun competența lor pentru realizarea unui obiectiv comun. O
strategie comună multora dintre protocoalele de cooperare este de a
descompune și apoi de a distribui task -urile. Scopul acestei strategii este de a
reduce complexitatea task -urilor, astfel agenții au nevoie de mai puține
resurse și de capabilități mai reduse.
Criterii de descompunere a task -urilor. Sistemul poate decide între
alternative de descompunere, iar procesul de descompunere a task -urilor
trebuie să considere resursele și capabilită țile agenților. Descompunerea task –
urilor poate fi făcută spațial, conform organizării și situării surselor de
informații și a punctelor de decizie, sau funcțional, conform capabilităților
agenților disponibili. Există câteva criterii de descompunere a pro blemelor.
Ideea constă în faptul că problemele pot fi în genere analizate prin nivelul
abstractizării (de la general la detaliat), dar este necesar a fi luate în
considerație și alte constrângeri cum ar fi controlul, datele sau resursele .
Criterii de repar tiție a task -urilor . După ce task -urile au fost
descompuse, sunt distribuite după următoarele posibile criterii [CNLV91] :
evitarea supraîncărcării resurselor critice;
task-urile sunt atribuite agenților care au capabilitățile necesare execuției
lor;
agenții care au capabilități speciale pot avea sarcina de a atribui task -urile
altor agenți;
atribuirea de responsabilități care se suprapun agenților pentru a asigura
coerență;
atribuirea de task -uri strâns dependente agenților care sunt în vecinătate
spațială sau semantică;
task-urile care au prioritate sau urgență ridicată pot fi reasignate.
Următoarele mecanisme sunt utilizate pentru distribuirea task -urilor:
o mecanisme de piață: task-urile sunt atribuite agenților printr -un proces de
selecție mutuală s au acord global;
o planificare multi -agent: agenții de planificare au responsabilitatea
atribuirii task -urilor;
o negociere: task-urile sunt atribuite agenților printr -un proces de acord
între agenții interesați;
o structură organizațională: agenții au responsab ilități bine determinate de
rezolvare a unor anumite task -uri;
o blackboard: mecanism de rezolvare a problemelor în care agenții din
sistem își expun cunoștințele individuale asupra unei probleme pentru a fi
considerate în găsirea unei soluții.
Luarea deciz iei în sistemele multi -agent . Sistemele multi -agent pot fi
văzute ca o colecție de funcționalități care sunt realizate prin intermediul
cunoștințelor despre anumite tipuri de probleme, dar și despre mediul în care
operează agentul. Prin aceasta, agentul po ate interacționa la o schimbare a
mediului, dar poate și interacționa cu alți agenți în căutarea unei soluții
pentru problemele sale. În astfel de situații este nevoie de coordonare între
agenți. Coordonarea între agenți se poate realiza în mod centralizat , în care
este desemnat un agent coordonator, responsabil pentru detectarea
interdependențelor între agenții locali la diferite grade de abstractizare.
În metoda descentralizată, agenții sunt înzestrați cu inteligența
necesară pentru a descoperi inconsist ențele între acțiunile pe care le execută
și comunică prin mesaje pentru a -și adapta deciziile locale, astfel încât să se
ajungă la un plan sau la un set de planuri de control local consistente. În
metoda descentralizată, sistemele sunt mai ușor de constru it, deoarece este
necesar ca modelul să fie definit exact numai la nivel local.
Luarea deciziei în mod distribuit . Diferite mecanisme pot fi folosite
pentru luarea deciziilor printr -o metodă descentralizată, în cazul rezolvării
problemelor într -un mediu m ulti-agent. În cele mai multe cazuri, agenții din
sistem sunt necooperanți, iar coordonarea dintre ei este de tip competiție.
Mecanisme de coordonare între agenți pot fi:
Votarea – este mecanismul prin care agenții își expun convingerile și
intențiile asup ra unei probleme, prin acordarea unui vot, iar
soluția este aleasă pe baza voturilor tuturor agenților.
Licitația – este mecanismul prin care se ajunge la un acord între un agent
care oferă un serviciu și alți agenți care cer acel serviciu iar
fiecare dore ște obținerea unui acord cât mai profitabil pentru
el.
Mecanisme de piață – sunt caracterizate de faptul că agenții cooperează
pentru a ajunge la un echilibru în cadrul sistemului între
agenții care produc și cei care consumă diferite servicii.
Negocierea – este un mecanism prin care se ajunge la o decizie comună
între doi sau mai mulți agenți, fiecare încercând satisfacerea
unui scop sau obiectiv individual.
Formarea de coaliții – este mecanismul prin care agenții negociază
formarea unor organizații sau gr upări pe baza scopurilor pe
care le au, scopuri care pot fi mai bine satisfăcute prin
existența coaliției.
Criterii de evaluare . Aceste criterii se aplică îndeosebi în cazurile în
care decizia trebuie luată într -un sistem în care agenții sunt interesați sa u
necooperanți. Mecanismele pot fi evaluate conform mai multor criterii, cum
ar fi:
Bunăstarea socială reprezintă suma tuturor utilităților agenților pentru o
soluție dată. Acest criteriu poate fi utilizat pentru a compara diferite
mecanisme comparând solu țiile oferite de acele mecanisme.
Eficiență Pareto. Și acest criteriu poate fi utilizat pentru a compara diferite
mecanisme, comparând soluțiile oferite de acele mecanisme. O
soluție x este eficientă Pareto dacă nu există nici o altă soluție x’,
astfel înc ât cel puțin un agent este mai satisfăcut în x’ decât în x, și
nici un agent nu este mai nesatisfăcut în x’ decât în x.
Raționalitate individuală. Participarea într -o negociere este individual
rațională (IR) pentru un agent dacă răsplata agentului în urma
participării nu este mai mică decât dacă nu ar fi participat. Un
mecanism este IR dacă este IR pentru toți agenții.
Stabilitate. Uneori mecanismele au o strategie dominantă. Aceasta
înseamnă că un agent este favorizat dacă folosește o strategie
specifică, indiferent de strategiile celorlalți agenți.
În sistemele în care o strategie dominantă nu există, criteriul de
stabilitate este echilibrul Nash (EN). În EN, fiecare agent alege o strategie
care este considerată a fi cel mai bun răspuns la strategiile celo rlalți agenți.
Profilul strategiei între agenții A
) ,….,,(*
||*
2*
1*
A A S SS S este în EN dacă
pentru fiecare agent i,
*
iS este cea mai bună strategie a agentului ca răspuns la
strategiile alese de alți agenți
) ,..,, ,….,(*
||*
1*
1*
2*
1 A i i S SS SS .
Sunt do uă probleme principale în aplicarea echilibrului Nash. Există
cazuri când echilibrul Nash nu se poate determina sau cazuri pentru care
multiple seturi de strategii îndeplinesc condiția de echilibru Nash.
Eficiență computațională . Mecanismele ar trebui să f ie concepute astfel
încât, atunci când sunt utilizate, să fie necesară cât mai puțină putere
computațională. Deci este necesar un compromis între calitatea soluției
obținută prin intermediul unui anumit mecanism și costul computațional .
Eficiență în comuni cații și în distribuire . Dacă, prin alte caracteristici,
protocoalele au aceleași calități, protocoalele distribuite sunt preferate,
deoarece se evită problemele care apar în cazul defectării elementului
central din sistem și de asemenea se evită problemel e de performanță
scăzută datorate existenței unui element central. În același timp, este de
dorit minimizarea fluxului de comunicații necesar pentru a îndeplini un
anumit scop.
2. Mecanisme de cooperare între agenți
Mecanismul de votare. În mecanismul de votare toți agenții își
exprimă alegerea, iar soluția găsită este determinată de alegerile făcute de
agenții din sistem. Scopul general este de a găsi o regulă de alegere socială
(globală) care ordonează soluțiile în funcție de ordinea aleasă de fiecare
dintre agenți. Se consideră că mulțimea agenților este A, iar O este mulțimea
posibilelor soluții. Se consideră că fiecare agent iA are o relație asimetrică
și tranzitivă de preferință i pe O . O regulă generală de preferință consideră
ca intrare relații le de preferință ale agenților (1 ,…., |A|) și determină
relația globală de preferință *.
Este necesar ca următoarele caracteristici să fie îndeplinite:
relație globală de preferință * ar trebui să existe pentru toate
preferințele individuale;
* ar trebui definită pentru fiecare pereche o, o’O;
* ar trebui să fie asimetrică și tranzitivă pe O;
toți agenții trebuie să fie egali în stabilirea relației globale de
preferință.
În cele mai multe cazuri nu pot fi satisfăcute toate caracteristicile
mențio nate. Protocolul poate fi un protocol n-ar pentru care toate
alternativele sunt comparate simultan și cea care are cele mai multe voturi
este cea aleasă. În cazul protocolului binar alternativele sunt comparate două
câte două, alternativa mai slabă este în lăturată, iar cea câștigătoare este în
continuare comparată ca altă alternativă. În cazul protocolului binar, ordinea
în care sunt comparate perechile, denumită agendă, poate influența rezultatul
final. În exemplul din figura 2 este prezentat un caz în car e patru agende
diferite determină rezultate diferite.
a b c c c c c c c c
c c c
c c c
a a a
a a a
a
a a a a
a b
b
b b b b
b b
b b b b
d d d
d d d d d
d d d d d d d 35% din agenți au relația de preferință c dba
33% din agenți au relația de preferință a cdb
32% din agenți au relația de preferință b acd
Figura 2. Exemplificare a mecanismului de votare folosind protocol binar.
Se observă că, în cazul ultimei agende, alternativa d este câștigătoare,
chiar dacă fiecare din ag enți preferă c în locul lui d. Preferința generală
dominantă în acest caz este Pareto. Dezavantajul acestei metode este că în
cazul unui număr mare de perechi, metoda este lentă.
În cazul prezentat anterior s -a considerat că toate preferințele
agenților su nt cunoscute. În cele mai multe cazuri, agenții declară preferințele
lor și pot fi sinceri sau nesinceri în declararea preferințelor. În anumite
sisteme se poate considera că agenții sunt nesinceri dacă profitul lor este mai
mare astfel.
Mecanismul de li citație. Mecanismul de licitație este întîlnit în
cazurile în care licitatorul dorește să vândă ceva și să obțină cel mai mare preț
posibil, iar mai mulți agenți doresc să cumpere la cel mai mic preț posibil.
Spre deosebire de mecanismul de votare în care profitul este pentru toți
agenții, în mecanismul de licitație profitul se decide între doi agenți:
licitatorul și ofertantul. Există trei tipuri diferite de licitații, în funcție de felul
în care agentul determină valoarea obiectului pe care îl vinde:
licitație cu valoare privată, în care valoarea depinde numai de preferințele
agentului;
licitație cu valoare comună, în care valoarea depinde total numai de
evaluarea dată de alți agenți;
licitație cu valoare corelată, în care valoarea depinde parțial de prefe rința
agentului și parțial de evaluarea dată de ceilalți.
Protocoalele mecanismului de licitație determină următoarele tipuri
de licitație:
Licitație de tip prim -preț așteptare deschisă în care fiecare ofertant poate
depune oferta, iar licitația se închide când nu mai există alți ofertanți.
Licitația este câștigată de ofertantul care a oferit cel mai bun preț.
Licitație de tip prim -preț ofertă necunoscută în care fiecare ofertant
depune oferta fără a cunoaște oferta celorlalți. Licitația este câștigată de
ofertantul care a oferit cel mai bun preț.
Licitație descrescătoare în care licitatorul scade prețul continuu până
când un agent devine ofertant la prețul curent.
Licitație de tip preț secundar ofertă necunoscută (licitație Vickrey) , în
care fiecare ofertan t depune o ofertă fără a cunoaște ofertele celorlalți.
Licitația este câștigată de ofertantul care a oferit cel mai bun preț, dar
prețul este al următoarei oferte celei mai bune.
Toate cele patru metode sunt Pareto eficiente, selectând ofertantul
care a of erit cel mai bun preț.
Mecanisme de piață. Mecanismele de piață sunt îndeosebi
utilizate în cazurile în care este necesară coordonarea într -un sistem cu un
număr necunoscut de agenți [MTWMP95], fiind o metodă pentru alocarea de
resurse sau bunuri între a genți.
Astfel, se consideră că există n>0 tipuri de obiecte e, numărul fiecărui
tip fiind nelimitat. Este definită mulțimea p=(p 1, p2,…., pn), unde pe este prețul
obiectului e. În sistem există două tipuri de agenți: producători și
consumatori. Fiecare c onsumator i are o funcție de utilitate care determină
preferința sa asupra diferitelor mulțimi de elemente
T
in i i i x xx x ) ,…,,(2 1 ,
unde
iex este alocarea obiectelor e de către consumatorul i. Fiecare
consumator i are o înzestrare iniția lă
T
in i i i e ee e ) ,….,,(2 1 , unde
iee este
înzestrarea agentului i cu obiecte de tip e.
Producătorii pot utiliza anumite obiecte pentru a produce altele. Fie
T
jn j j j y yy y ) ,….,,(2 1
vectorul de producție unde
jey este ca ntitatea de
obiecte de tip e pe care producătorul j le produce. Capacitatea unui
producător de a produce alte obiecte este caracterizată de mulțimea
posibilităților sale de producție
jY , care este o mulțime de vectori de
producție. Pro fitul producătorului j este
jyp , unde
j jYy . Profitul
producătorului este împărțit între consumatori conform unor proporții
predeterminate. Fie
ij fracțiunea producătorului j pe care consumatorul i o
deține. Prețurile se pot schimba, iar agenții își pot schimba planurile de
consum sau de producție, dar de fapt producția și consumul au loc numai
atunci când piața a ajuns la un echilibru general. Se consideră că
),,(* * *yxp
este un echilibru general dacă:
jj
ii
ii y e x* *
,
fiecare consumator i își maximizează preferințele fiind date prețurile:
)( max arg * * *|*
ii yp epxpRx i xu x
j jij i in
i
și fiecare producător j maximizează profitul său având prețurile:
jyp
j jYyjy
*maxarg*
.
Motivația folosirii mecanisme lor de piață este că agenții pot determina o
soluție comună eficientă, care ia în considerare tranzacții între agenți și faptul că
valoarea, pentru un agent, a diferitelor servicii poate fi interdependentă, iar
soluția poate fi determinată fără a centraliz a informațiile sau controlul.
Mecanismele de piață cu echilibru general presupun că agenții sunt competitivi,
de aceea agenții pot acționa în mod strategic și pot supraestima sau subestima
anumite servicii sau bunuri pentru care negociază. Astfel de strate gii, numite
strategii speculative, au fost analizate [STHY97] și determinat beneficiul adus
prin speculație .
Mecanismul de negociere. Negocierea este o formă de
coordonare frecvent întâlnită în sistemele multi -agent. Agenții mai întâi își
comunică poziț iile, care pot fi în conflict, dar încearcă să ajungă la un acord
făcând concesii sau căutând alternative. Principalele caracteristici ale
negocierii sunt: limbajul utilizat de agenții care participă la negociere;
protocolul folosit de agenți în negociere; procesul de decizie pe care îl
urmărește fiecare agent pentru a -și determina pozițiile, concesiile și criteriile
pentru acord.
Au fost dezvoltate diferite tehnici de negociere. Tehnicile pot fi:
centrate pe mediu sau centrate pe agent. Tehnicile centrate pe mediu au pornit
de la ideea: “cum pot fi regulile unui mediu proiectate, astfel încât agenții
care acționează, indiferent de originea lor, de capabilități sau intenții, vor
interacționa productiv și onest?” . Tehnicile centrate pe agent pornesc de la
ideea: “având un mediu în care agenții operează, care este cea mai bună
strategie pe care o pot urma?” .
Protocolul rețea contractuală. Protocolul rețea contractuală este un
protocol de coordonare între agenți folosit pentru rezolvarea în mod distribuit și
cooperant a problemelor. Acest protocol este considerat ca fiind o formă de
negociere și a fost la început folosit pentru partajarea sarcinilor [SmithR80]. Acest
protocol furnizează soluția pentru așa -numita “problema conexiunii” : determinarea
agentului co respunzător pentru un anumit task. Agentul care dorește a avea task -ul
rezolvat este denumit manager , iar agentul care poate executa task -ul este denumit
contractor . Aceste roluri nu sunt dinainte stabilite, ci un agent care este într -o etapă
manager poate fi contractor în altă etapă. Flexibilitatea face posibilă descompunerea
în continuare a task -urilor și un contractor pentru un anume task poate acționa ca
manager, solicitând alți agenți pentru a executa părți din task.
Din perspectiva managerului , proto colul constă în următoarele etape:
Anunță un task care trebuie executat;
Primește și evaluează oferte de la potențiali contractori;
Acordă contractul contractorului care corespunde cel mai bine;
Primește și sintetizează rezultate.
Din perspectiva contr actorului , protocolul constă din următoarele etape:
Primește anunțuri de task -uri;
Evaluează capacitatea proprie de a executa task -urile anunțate;
Răspunde, primind sau rejectând task -urile acordate;
Execută task -ul dacă oferta a fost acceptată;
Raporte ază rezultatele.
Au fost dezvoltate variante ale protocolului inițial rețea contractuală, care
conduc la unele rezultate îmbunătățite sau fac posibilă utilizarea sa pentru agenți
necooperanți.
Rezumatul unității de studiu
Comunicația permite agenților să -și coordoneze acțiunile și
comportamentul ceea ce face ca sistemul multi -agent să fie mai coerent.
Agenții pot trimite și recepționa mesaje folosind rețeaua de comunicație.
Mesajele pot fi: afirmații și interogări.
Se consideră două criterii de selecție a axiomelor pentru a fi incluse
in setul propriu de opinii: bazată pe tipul de informație transmisă, bazată pe
credibilitatea pe care o are agentul.
Conflictele sunt interacțiuni perturbatoare, adică mai mulți agenți au
nevoie de aceleași resurse în același timp și cu aceleași drepturi. Sunt definite
tehnici de coordonare a acțiunilor (pentru evitarea conflictelor):
• ordonarea priorităților;
• tehnici de negociere (compromis care modelează satisfacțiile
și frustrările).
Modurile de coordonare în sistemele mu lti-agent sunt cooperare și
competiție;
Coordonarea în sistemele multi -agent este necesară pentru
prevenirea haosului, deoarece nici unul dintre agenți nu are o vedere globală
asupra întregului grup din care face parte;
Cooperarea reprezintă coordonarea î ntre agenții care nu se află în
competiție, iar negocierea reprezintă coordonarea între agenții care sunt în
competiție sau agenți necooperanți;
O strategie comună multora dintre protocoalele de cooperare este de
a descompune și apoi de a distribui task -urile. Scopul acestei strategii este de
a reduce complexitatea task -urilor, astfel agenții au nevoie de mai puține
resurse și de capabilități mai reduse.
Descompunerea task -urilor poate fi făcută spațial, conform
organizării și situării surselor de informați i și a punctelor de decizie, sau
funcțional, conform capabilităților agenților disponibili.
Principalele caracteristici ale negocierii sunt: limbajul utilizat de
agenții care participă la negociere; protocolul folosit de agenți în negociere;
procesul de d ecizie pe care îl urmărește fiecare agent pentru a -și determina
pozițiile, concesiile și criteriile pentru acord.
Tehnicile pot fi: centrate pe mediu sau centrate pe agent. Tehnicile
centrate pe mediu au pornit de la ideea: “cum pot fi regulile unui mediu
proiectate, astfel încât agenții care acționează, indiferent de originea lor, de
capabilități sau intenții, vor interacționa productiv și onest?”. Tehnicile
centrate pe agent pornesc de la ideea: “având un mediu în care agenții
operează, care este cea mai bună strategie pe care o pot urma?”
Autoevaluare
Test de autoevaluare a cunoștințelor din modulul I
14 Agenții comunică pentru a -și realiza scopurile proprii sau pentru a
realiza scopurile comune . Comunicația permite agenților să -și
coordoneze acțiunile ș i comportamentul ceea ce face ca sistemul multi –
agent să fie mai coerent. Agenții pot trimite și recepționa mesaje
folosind rețeaua de comunicație. Mesajele pot fi: __________ și
interogări .
afirmații
15 Includerea opiniilor unui alt agent în setul propr iu de opinii, se face,
utilizând setul de axiome specificat mai sus. Problema care apare este
de selecție a uneia dintre axiome, dintre cele trei. Se consideră două
criterii de selecție. Care criteriu nu este valabil?
bazată pe tipul de informație transmis ă;
bazată pe credibilitatea pe care o are agentul;
bazată pe cantitatea de informație transmisă;
16 Este corectă afirmația? Dacă agentul B este nou intrat în sistem, și
transmite agentului A un mesaj, agentul A, care primește informația
începe prin a fi c ircumspect față de agentul B. Dacă se observă că
aproape totdeauna agentul A este de acord cu opiniile agentului B (nu
sunt inconsistente), atunci agentul A începe să devină încrezător în B
sau chiar ascultător.
DA
17 Resursele reprezintă toate elementele din mediu și materialele
utile necesare pentru realizarea unei activități. Folosirea resurselor din
sistem generează conflicte. Conflictele sunt interacțiuni perturbatoare,
adică mai mulți agenți au nevoie de aceleași resurse în același timp și
cu aceleaș i drepturi. Sunt definite tehnici de coordonare a acțiunilor
(pentru evitarea conflictelor):
ordonarea priorităților;
tehnici de negociere (compromis care
modelează satisfacțiile și frustrările).
18 Clasif icarea interacțiunilor se face ținând cont de sur sele principale ale
interacțiunii.
Potriviti interactiunile cu descrierea lor…
simpla colaborare – caracterizează sistemul de comunicație
(interacțiunile sunt date de alocarea sarcinilor și partajarea
cunoștințelor);
întrepătrundere – agenții se “tachine ază” între ei în rezolvarea
sarcinilor date;
colaborare coordonată – se realizează coordonarea acțiunilor pentru
realizarea sarcinilor și alocării resurselor;
competiție individuală pură – agenții au scopuri incompatibile și
negociază pentru realizarea lor (competiție în care au aceleași
resurse și sunt situați în situații inițiale identice);
competiție colectivă pură – se realizează o grupare pentru
satisfacerea scopurilor.
19 Sistemul poate decide între alternative de descompunere, iar procesul
de descom punere a task -urilor trebuie să considere resursele și
capabilitățile agenților. Descompunerea task -urilor poate fi făcută:
spațial, conform organizării și situării surselor de informații și a
punctelor de decizie;
funcțional, conform capabilităților agenț ilor disponibili;
20 Criterii de repartiție a task -urilor
Următoarele mecanisme sunt utilizate pentru distribuirea task –
urilor:
o mecanisme de piață: task-urile sunt atribuite agenților printr -un
proces de selecție mutuală sau acord global;
o planificare mul ti-agent: agenții de planificare au responsabilitatea
atribuirii task -urilor;
o negociere: task-urile sunt atribuite agenților printr -un proces de
acord între agenții interesați;
o structură organizațională: agenții au responsabilități bine
determinate de rezo lvare a unor anumite task -uri;
o blackboard: mecanism de rezolvare a problemelor în care agenții
din sistem își expun cunoștințele individuale asupra unei probleme
pentru a fi considerate în găsirea unei soluții.
21 Luarea deciziei în mod distribuit
_____ ________ este mecanismul prin care agenții își expun
convingerile și intențiile asupra unei probleme, prin acordarea unui vot,
iar soluția este aleasă pe baza voturilor tuturor agenților.
Votarea;
Licitația;
Mecanisme de piață;
Negocierea;
Formarea de coal iții;
22 Luarea deciziei în mod distribuit
______________ este mecanismul prin care se ajunge la un acord între
un agent care oferă un serviciu și alți agenți care cer acel serviciu iar
fiecare dorește obținerea unui acord cât mai profitabil pentru el.
Votarea;
Licitația;
Mecanisme de piață;
Negocierea;
Formarea de coaliții;
23 Luarea deciziei în mod distribuit
Mecanisme de coordonare între agenți pot fi:
Mecanisme de piață – sunt caracterizate de faptul că agenții
cooperează pentru a ajunge la un echilib ru în cadrul
sistemului între agenții care produc și cei care consumă
diferite servicii.
Negocierea – este un mecanism prin care se ajunge la o decizie
comună între doi sau mai mulți agenți, fiecare încercând
satisfacerea unui scop sau obiectiv individual.
Formarea de coaliții – este mecanismul prin care agenții negociază
formarea unor organizații sau grupări pe baza scopurilor pe care le
au, scopuri care pot fi mai bine satisfăcute prin existența coaliției.
24 Criterii de evaluare .
Aceste criterii se apl ică îndeosebi în cazurile în care decizia
trebuie luată într -un sistem în care agenții sunt interesați sau
necooperanți. Mecanismele pot fi evaluate conform mai multor criterii,
cum ar fi:
Bunăstarea socială – reprezintă suma tuturor utilităților agenților
pentru o soluție dată. Acest criteriu poate fi utilizat pentru a
compara diferite mecanisme comparând soluțiile oferite de
acele mecanisme.
Eficiență Pareto – acest criteriu poate fi utilizat pentru a compara
diferite mecanisme, comparând soluțiile oferit e de acele
mecanisme. O soluție x este eficientă Pareto dacă nu există
nici o altă soluție x’, astfel încât cel puțin un agent este mai
satisfăcut în x’ decât în x, și nici un agent nu este mai
nesatisfăcut în x’ decât în x.
Raționalitate individuală – Participarea într -o negociere este
individual rațională (IR) pentru un agent dacă răsplata
agentului în urma participării nu este mai mică decât dacă nu
ar fi participat. Un mecanism este IR dacă este IR pentru toți
agenții.
Stabilitate – Uneori mecanismele a u o strategie dominantă. Aceasta
înseamnă că un agent este favorizat dacă folosește o strategie
specifică, indiferent de strategiile celorlalți agenți.
25 Mecanismul de licitație
Există trei tipuri diferite de licitații, în funcție de felul în care
agentu l determină valoarea obiectului pe care îl vinde:
licitație cu valoare privată , în care valoarea depinde numai de
preferințele agentului;
licitație cu valoare comună , în care valoarea depinde total numai
de evaluarea dată de alți agenți;
licitație cu valoa re corelată , în care valoarea depinde parțial de
preferința agentului și parțial de evaluarea dată de ceilalți;
26 Mecanismul de licitație
Ce fel de licitație este licitația în care fiecare ofertant depune oferta fără
a cunoaște oferta celorlalți. Licitaț ia este câștigată de ofertantul care a
oferit cel mai bun preț.
Licitație de tip prim -preț așteptare deschisă;
Licitație de tip prim -preț ofertă necunoscută ;
Licitație descrescătoare;
Licitație de tip preț secundar ofertă necunoscută (licitație Vickrey);
27 Protocolul rețea contractuală.
Protocolul rețea contractuală este un protocol de coordonare între agenți
folosit pentru rezolvarea în mod distribuit și cooperant a problemelor.
Protocolul constă în următoarele etape:
Din perspectiva managerului :
Anunț ă un task care trebuie executat;
Primește și evaluează oferte de la potențiali
contractori;
Acordă contractul contractorului care corespunde cel
mai bine;
Primește și sintetizează rezultate.
Din perspectiva contractorului :
Primește anunțuri de task -uri;
Evaluează capacitatea proprie de a executa task -urile
anunțate;
Răspunde, primind sau rejectând task -urile acordate;
Execută task -ul dacă oferta a fost acceptată;
Raportează rezultatele.
28 Au fost dezvoltate diferite tehnici de negociere. Tehnicile pot fi:
Tehnicile centrate pe mediu: “cum pot fi regulile unui mediu
proiectate, astfel încât agenții care acționează, indiferent de originea
lor, de capabilități sau intenții, vor interacționa productiv și onest?” .
Tehnicile centrate pe agent: “având un mediu în care agenții
operează, care este cea mai bună strategie pe care o pot urma?” .
BIBLIOGRAFIE
[CBuiu99] C. Buiu: Distributed Artificial Intelligence,
http://www.cl.inf.tu –
dresden.de/compulog/Iectures/winter99/lpisa/mod_l_07.htm l, 1999
[CBuiu99] C. Buiu: Multi -Agent Systems, Univ. Politehnica București,
http://www.cl.inf.tu –
dresden.de/compulog/lectures/winter99/lpisa/mod_l_08.htrnl , 1999
[FLGDa02] F. Leon, G. Dan, „Stadiul actual al cercetărilor în domeniul agenților
inteligenți”, referat 2002.
[GWeiB00] G. WeiB (ed.): Multiagent Systems – A Modern Approac h to Distributed
ArtificialIntelligence, The MIT Press, Cambridge, Massachusetts, 2000
[GWSS96] G. Weiß and S. Sen, eds., Adaptation and Learning în Multiagent Systems.
Berlin: Springer Verlag, 1996.
[NituL01I] Nitu, Loredana, Distributed Scheduling and Control System for Flexible
Manufacturing, International Conference SACCS -2001, Iasi, 2001.
[NituL02] Nitu, Loredana, Conceptual Agent Models for Manufacturing Control with
Multi -Agent Systems, International Conference DAS‘02, Suceava, May 2002.
[RichE83 ] Rich E. , Artificial Intelligence, McGraw -Hill Book Company, 1983.
[SFrGr99] S. Franklin, A. Graesser: Is it an Agent, or just a Program?: A Taxonomy for
Autonomous Agents, Institute for Intelligent Systems, University of
Memphis, http://www.msci.memphis.edu/~franklin/AgentProg.html
[TKQML93] The DARPA Knowledge Sharing Inițiative, Externai Interfaces Working
Group: Specification of the KQML, Agent -Communication Language ,
http://www.cs.umbc.edu/kqml/papers/kqmlspec.ps , 1993
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Str. Calea Mărășești, nr. 157, Bacău, 600115 [610240] (ID: 610240)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.