Larga raspîndire a sistemelor distribuite a dus la aparitia unor noi domenii ale informaticii. Astfel, în ciuda faptului că multe din problemele „clasice" de inteligentă artificială nu au (încă) solutii satisfăcătoare, multi specialisti în domeniu si-au îndreptat deja atentia spre inteligenta artificială în sisteme distribuite. Noua disciplină are la rîndul ei două directii fundamentale de studiu, corespunzînd celor două mari tipuri de sisteme distribuite existente: cu si fără un coordonator central.
În cazul existentei unui coordonator central se presupune că diversii agenti inteligenti participă la rezolvarea unei probleme globale si de interes comun. În această situatie solutiile sînt oarecum mai usor de găsit deoarece se bazează pe faptul că proiectantii sistemului sînt capabili să influenteze în mod direct comportarea fiecărui agent în parte.
În cazul sistemelor distribuite fără coordonator central, problemele devin mult mai complexe. În astfel de sisteme, agentii inteligenti pot fi implementati si „programati" de grupuri de persoane avînd interese proprii si nu neaparat convergente. Astfel, agentii nu mai au un interes comun, ba chiar dimpotrivă, scopurile lor riscă să fie conflictuale. Într-un asemenea sistem, numit si „sistem multi-agent" [1], interactiunea dintre agenti poate lua diferite forme, de la competitia pentru resurse si „reusită" pînă la colaborarea în vederea optimizării „efortului" depus de fiecare agent în parte. În cele ce urmează ne vom concentra asupra sistemelor multi-agent si vom încerca să analizăm posibilitătile de negociere si colaborare între mai multi agenti.
În ciuda eterogenitătii si a posibilelor conflicte de interes care le caracterizează, sistemele multi-agent pot deseori beneficia de colaborarea dintre agenti. Stabilirea unei relatii de colaborare între agenti avînd interese diferite este o problemă delicată, a cărei rezolvare depinde în mod fundamental de protocolul pe baza căruia diversii agenti comunică între ei. O excelentă definitie a unui protocol de negociere este cea a lui Jeffrey Rosenschein [3]: „Prin protocol întelegem regulile publice pe baza cărora diversii agenti pot 'cădea de acord'. Un protocol descrie atît tipul de întelegeri ce se pot stabili între agenti, cît si secventele de oferte si contra-oferte ce pot fi făcute de respectivii agenti". Cu alte cuvinte, pe baza unui set de reguli de comunicare, mai multi agenti pot conveni asupra unui „comportament social" care să usureze sarcina fiecărui agent în parte.
Evident, pentru ca diversii agenti să poata coopera (sau, cel putin, să poate încerca să coopereze!), este nevoie ca toti să folosească acelasi protocol. Prin urmare, un scenariu realist ar fi următorul: proiectantii agentilor inteligenti încep prin a stabili un protocol unic, bine-definit, pe baza căruia agentii vor comunica unul cu celălalt. Odată protocolul stabilit, fiecare agent poate fi implementat astfel încît să negocieze pe baza unei strategii proprii, necunoscute celorlati agenti.
Există mai multi factori în functie de care un protocol poate fi caracterizat ca fiind mai mult sau mai putin performant. Spre exemplu, un protocol trebuie să asigure eficienta colaborării, adică să ducă la găsirea celei mai bune solutii pentru agentii implicati.
Un alt criteriu fundamental de caracterizare a unui protocol este acela al stabilitătii: protocolul trebuie proiectat de asa manieră încît agentii să nu aibă nici un interes să devieze de la strategia stabilită. Dacă un protocol permite obtinerea de „beneficii" prin „înselarea" partenerilor de negociere, eforturile proiectantilor riscă să se bazeze pe deviza „Scopul scuză mijloacele!", fapt ce va pune sub semnul întrebării însusi sensul existentei unui astfel de sistem multi-agent.
Alte atribute importante ale unui protocol de negociere ar fi simetria si simplitatea. Primul se referă la solutiile în care nici un agent nu joacă un rol deosebit (de „master" sau de coordonator), iar cel de al doilea este legat de mentinerea costurilor negocierii la un nivel cît mai scăzut din punctul de vedere al comunicatiei între agenti, al timpului necesar negocierii si al efortului computational.
Este evident că nu există un protocol care să îndeplinească toate conditiile de mai sus si să fie aplicabil în rezolvarea oricărei probleme. Eforturile cercetătorilor se axează în special pe definirea unor clase de probleme pentru care să fie realizabile cît mai multe dintre dezideratele amintite. Este fundamental ca avînd o clasă de probleme, să stim exact dacă pentru respectiva clasă este posibilă identificarea unui protocol care să fie, de exemplu, stabil si eficient.
Să presupunem că un grup de persoane este interesat în stabilirea unor întîlniri (sedinte) între unii membrii ai grupului. O astfel de întîlnire este caracterizată de ora de începere, durata sedintei, locul de desfăsurare, subiectul discutiei si persoanele care participă la întrunire. Să mai presupunem că fiecare persoană din grup este reprezentată de un agent inteligent (o „secretară electronică") si că în urma unei propuneri de „meeting" lansată de unul dintre membrii grupului, agentii fiecărui participant încep să negocieze ora si locul întîlnirii.
Această problemă poate avea diferite solutii în functie de obligativitatea, respectiv ne-obligativitatea, stabilirii unei întîlniri. Astfel, dacă membrii grupului sînt angajatii unei firme si întîlnirea este „în interes de servici", există o certa obligatie de a participa la sedintă. Dacă, în schimb, grupul în cauză este format din elevii unei clase si întîlnirea se referă la o excursie la munte, nu există nici o constrîngere prin care elevii să poata fi obligati să participe la întrunire. În primul caz este vorba de un sistem de negociere „închis", pe cînd în cea de a doua situatie avem de a face cu un sistem de negociere „deschis" [2].
Un exemplu de protocol pentru negocieri în sisteme „închise" este „Clark Tax Mechanism" [2], care permite alegerea „de comun acord" a unei alternative dintr-un set de candidati. Ideea de bază a acestui protocol consta în a-i oferi fiecărui participant posibilitatea de a-si manifesta preferintele într-o manieră cît mai flexibilă. Fiecare agent inteligent dispune de o „zestre" de puncte cu care poate „vota" pentru una sau alta dintre alternative. Astfel, în exemplul nostru, dacă persoana A preferă întrunirile de dimineata, ea poate utiliza toate punctele disponibile pentru a „vota" meeting-urile matinale. Similar, dacă persoanei B îi displac discursurile nesfîrsite ale lui C, B poate vota pentru întîlnirile programate la sfîrsitul zilei de lucru, deoarece meeting-urile nu se pot „întinde" peste program.
Pe lîngă flexibilitatea deosebită, protocolul amintit mai are încă un avantaj remarcabil: persoanele care influentează decisiv alegerea unei anume întîlniri sînt penalizate pentru acest lucru prin micsorarea zestrei de puncte. Spre exemplu, să presupunem că în urma votării se stabileste întîlnirea M1, dar că în lipsa votului agentului A întîlnirea stabilită ar fi fost M2 (adică A a votat „decisiv" pentru M1). În această situatie lui A i se va micsora numărul de puncte disponibile într-o manieră care să reflecte votul sau decisiv.
Pentru a întelege detaliile protocolului schitat mai sus, vom face cîteva simplificări si vom analiza un scurt exemplu. Astfel, vom considera că agentii inteligenti îsi vor manifesta preferintele doar în functie de ora la care are loc întîlnirea, ignorînd toate celelalte detalii (subiect, durată, loc de desfăsurare sau participanti). Procesul votării se va efectua într-un singur pas: fiecare agent primeste o listă a întîlnirilor-candidat (adică o listă ale cărei elemente reprezintă data si ora de începere a fiecărei posibile sedinte) si îsi distribuie punctele disponibile în functie de preferinte. Apoi se adună numărul de puncte votate pentru fiecare întîlnire-candidat si se alege optiunea care a acumulat cele mai multe puncte.
Toate aceste operatii sînt ilustrate în cadrul tabelului Varianta 1. În exemplul ales, avem trei agenti (A1, A2 si A3) care-si manifestă preferintele pentru cele trei posibile date de întîlnire (M1, M2 si M3). Analizînd partea de tabel intitulată „votul real", observăm că agentului A1 i-a fost indiferent momentul întîlnirii si, în consecinta, a votat în mod egal (cîte 10 puncte) pentru fiecare dintre posibilităti. Agentul A2 si-a manifestat o preferintă puternică pentru M2 (25 de puncte), un total dezinteres pentru M3 (0 puncte) si o vagă preferinta pentru M1 (5 puncte). În fine, desi agentul A3 prefera pe M3 lui M2 si pe M2 lui M1, distributia punctelor indica faptul că preferintele lui au fost foarte apropiate (12 puncte, respectiv 10 puncte si 8 puncte). În urma cumulării voturilor corespunzînd fiecărei întruniri, va fi aleasă întîlnirea-candidat M2, care a totalizat un numar de 45 de puncte (scrierea cu rosu a lui 45 indică faptul că M2 este meeting-ul „cîstigător").
Odată procesul votării încheiat, urmează faza de calculare a penalizărilor. Această etapa începe prin analizarea rezultatului votului fără participarea fiecărui agent în parte. Astfel, în lipsa votului agentului A1, M1 ar fi totalizat 13 puncte (5 de la A2 si 8 de la A3), M2 ar fi cumulat 35 de puncte (25 de la A2 si 10 de la A3), iar M3 ar fi atins un total de 12 puncte (toate obtinute prin votul lui A3). Cum tot M2 întruneste numărul maxim de puncte, votul lui A1 nu a influentat „decisiv" alegerea întrunirii si deci A1 nu va fi penalizat.
Reluînd acelasi calcul pentru cazul în care A2 nu ar fi votat, observăm că M1 ar fi avut 18 puncte (10+8), M2 ar fi obtinut 20 de puncte (10+10), iar M3 ar fi totalizat 22 de puncte (10+12). Prin urmare, în lipsa votului lui A2 ar fi fost ales M3. Deci A2 a votat „decisiv" pentru M2, ceea ce duce la penalizarea lui după cum urmează: din zestrea de puncte a lui A2 va fi scazută diferenta dintre cele 22 de puncte „realizate" de M3 („noul" meeting ales) si cele 20 de puncte ale lui M2 (meeting-ul real). Deci A2 va fi penalizat cu 2 puncte si, prin urmare, la stabilirea viitoarelor întîlniri va dispune de o zestre de puncte mai mică decît cea a partenerilor de negociere.
Repetînd calculele precedente pentru cazul în care A3 nu ar fi votat, obtinem o penalizare nulă pentru A3, deoarece în lipsa votului său ar fi fost ales tot M2.
Se poate observa că mecanismul descris mai sus este gîndit astfel încît să „stimuleze" fiecare agent „să spună adevărul" în ceea ce priveste preferintele sale. De exemplu, să presupunem că agentul A1 se decide să „mintă" prin supralicitarea votului său pentru întîlnirea M1. Acest fapt poate provoca alegerea întrunirii în cauză, dar riscă să ducă la penalizarea lui A1 cu un numar de puncte mai mare decît ar fi dispus să piardă. După cum se vede si din tabelul refăcut pentru cazul în care A1 „minte" si îl voteaza pe M1 cu toate cele 30 de puncte disponibile, noul meeting ales va fi M1. În consecintă, A1 va fi penalizat cu 22 de puncte, fapt deloc convenabil avînd în vedere că în realitate lui A1 îi era indiferent care dintre cele trei meeting-uri urmează să fie ales.
Este important de observat că agentul A2 nu-si poate micsora penalizarea prin scăderea numărului de puncte asignate lui M2 deoarece „amenda" se calculează independent de votul sau. În consecintă, dacă M2 acumulează numărul maxim de puncte, A2 va fi penalizat cu exact două puncte, indiferent de modul în care îsi distribuie votul. În schimb, dacă A2 îsi ascunde preferinta pentru M2 si votează mult „sub" preferinta reală, apare riscul ca M2 să nu mai acumuleze numărul maxim de voturi.
După cum am văzut, nici supra-licitarea si nici sub-licitarea nu pot aduce beneficii unui agent. Mai mult decît atît, un vot neconform cu realitatea riscă să ducă fie la penalizări nedorite, fie la ratarea sansei de a stabili o întîlnire într-un moment avantajos. Prin urmare, cea mai bună strategie a unui agent constă în a vota conform preferintelor reale ale „stăpînului" său.
Un mare avantaj al lui „Clark Tax Mechanism" constă în faptul că nu e manipulabil. Cu alte cuvinte, chiar dacă agentul A1 ar cunoaste absolut toate voturile tuturor celorlalti agenti, el nu are cum folosi aceste cunostinte pentru a influenta alegerea unui meeting anume fără a „plăti" exact aceeasi penalizare ca si în cazul în care nu ar avea nici o informatie despre votul celorlalti. Stabilitatea acestui mecanism este dublată si de extrema lui simplitate: votarea se efectuează într-un singur „tur de scrutin", iar costurile de comunicatie sînt minime. În consecintă, putem spune că „Clark Tax Mechanism" este un protocol care îmbină în mod fericit stabilitatea cu simplitatea.