Sisteme multi-agent

1

13. SISTEME MULTI-AGENT

Un sistem multi-agent (SMA) este un sistem distribuit format dintr-o colecie de ageni autonomi care interacioneaz ntr-un mediu comun, fiecare agent avnd cunotine, capaciti de aciune i scopuri proprii [FERBER, 94].

Un sistem multi-agent este definit ca un sistem compus din elementele urmtoare:

1. Un mediu E, adic un spaiu prevzut cu o metric; 2. Un ansamblu de obiecte O. Fiecrui obiect din O i se poate asocia un anumit loc (o

poziie) n E. Aceste obiecte sunt pasive, n sensul c ele pot fi percepute, create, distruse i modificate de ctre ageni;

3. Un ansamblu A de ageni care sunt obiecte particulare (A O) i care reprezint entitile active ale sistemului;

4. Un ansamblu de relaii R care unete obiectele (i deci i agenii) ntre ele; 5. Un ansamblu de operaii Op permind agenilor lui A s perceap, produc, transforme i

manipuleze obiectele din O; 6. Operatori avnd sarcina de a reprezenta aplicarea acestor operaii i reacia lumii la

aceast tentativ de modificare, denumit regula universului.

Exist un caz particular n care A = O i E este mulimea vid. In acest caz, relaiile R definesc o reea: fiecare agent este legat direct la un ansamblu de ali ageni care sunt denumii "legturi" ale celui dinti. Acest tip de sisteme poart numele de sisteme multi-agent pur comunicante i sunt des ntlnite n inteligena artificial distribuit. Domeniile n care pot fi aplicate sunt cele ale cooperrii ntre module logice a cror funcie este de a rezolva o problem sau de a elabora/realiza o expertiz (cum ar fi interpretarea semnalelor) pornind de la module specializate, ca n cazul unui sistem de control distribuit; aceste sisteme se caracterizeaz prin faptul c interaciunile sunt comunicaii intenionate i modul de lucru este asemntor celui al unui organism social.

In situaia n care agenii sunt situai, E este n general un spaiu metric i agenii sunt capabili de a percepe propriul mediu, adic de a recunoate obiectele din mediu n funcie de capacitile lor perceptive, i de a aciona, adic de a transforma starea sistemului prin modificarea poziiilor i relaiilor existente ntre obiecte [FERBER, 94].

13.1 Problematica sistemelor multi-agent

Un aspect important al arhitecturii unui SMA este facilitatea cu care se pot aduga sau terge (elimina) ageni din respectivul SMA [CHAFIN, 92].

Se definete arhitectura static, arhitectura n care toate componentele SMA, ca i intrrile i ieirile sale sunt definite n specificaia proiectului. Intr-o arhitectur dinamic, componentele nu sunt toate cunoscute, iar specificaia i proveniena intrrilor, ca i destinaia ieirilor pentru fiecare component, nu sunt fixe.

In timp ce n arhitectura static trebuie s fie prezente toate elementele pentru ca sistemul s funcioneze, n arhitectura dinamic unii ageni pot participa sau nu o oarecare perioad de timp i, de asemenea, pot intra sau abandona participarea la sistem. Totui, pentru ca acest lucru s fie posibil, trebuie s existe suficiente suprapuneri ale domeniilor tratate; n caz contrar aciunea cerut nu se va executa niciodat.

Sisteme multi-agent

2

13.1.1 Criterii de proiectare a sistemelor multi-agent

In construcia sistemelor multi-agent s-a impus o nou paradigm metodologic de programare, propus de Shoham, respectiv programarea orientat pe ageni (AOP=Agent-Oriented Programming). Programarea orientat pe ageni poate fi vzut, din punct de vedere ingineresc, ca o specializare a paradigmei programrii orientate pe obiecte. Intuitiv, n timp ce programarea orientat pe obiecte (OOP=Object-Oriented Programming) propune considerarea unui sistem de prelucrare ca o colecie de module care comunic ntre ele prin transmitere de mesaje, AOP specializeaz acest model prin fixarea strilor (numite acum stri mentale) acestor module (numite acum ageni), stri care sunt compuse din componente mentale (convingeri, intenii, obligaii, angajamente, decizii etc.). In acest context, obiectele sunt specializate n module intenionale. O prelucrare ntr-un astfel de model const n aciunile acestor ageni, aciuni prin care agenii cer sau ofer informaii, asist sau intr n competiie cu ali ageni existeni n sistem. Comunicarea ntre ageni difer n funcie de tipul de comunicare intenionat, iar efectele acesteia sunt diferite n funcie de inteniile particulare [FLOREA, 98].

Modelele de coordonare ordoneaz cunotinele dispersate, disponibilitile i planurile unor ageni inteligeni, astfel nct ei s poat s-i cumuleze aciunile sau s rezolve o problem. Intr-un sistem multi-agent un operator trebuie s se coordoneze cu un sistem de control, acesta trebuind s ndeplineasc rolul care i-a fost ncredinat. Deci, trebuie s fie definit un model de coordonare adaptat acestei condiii. In particular, trebuie s se dea operatorului posibilitatea s interacioneze pe mai multe nivele de decizie. Operatorul trebuie s fie capabil s identifice cu uurin pe ce nivel de decizie este situat i, pe acest nivel, s-i substituie decizia cu aceea a sistemului de control (modul consultant) sau s-i orienteze decizia ntr-un mod diferit (modul de supraveghere). Controlul de nivel inferior trebuie s fie automat n totalitate, operatorul interacionnd cu sistemul n modul de supraveghere.

Criteriile pentru alocarea activitilor (aciunilor) corespund n mod direct scopurilor de proiectare:

se aloc activitile agenilor astfel nct s minimizeze comunicarea inter-agent i s maximizeze coeziunea agentului;

alocarea aciunilor independente i a aciunilor care completeaz resursele agentului de la diferii ageni trebuie s exploateze concurena i dependenele activitilor;

alocarea activitilor pentru ageni trebuie fcut astfel nct s permit operatorului s identifice centrele de decizie i nivelele de decizie. Operatorul trebuie s neleag unde i cum este luat fiecare decizie. Sistemul trebuie s fie transparent pentru operator.

In modelele bazate pe cooperare, toate deciziile vor fi descentralizate i subcomponentele vor interaciona direct ntre ele. In aceste aplicaii decizia nu va fi centralizat, ci se va distribui. De obicei, se consider c un sistem de control descentralizat este preferabil unui sistem de control autonom. Distribuia deciziilor permite operatorului s identifice unde, cum i care decizie este luat. In sistemele complet descentralizate, decizia este ascuns de interaciunile inter-agent.

13.2 Coordonarea n cadrul sistemelor multi-agent

Coordonarea este esena unui SMA fr de care nu exist nici un beneficiu al interaciunii ntre ageni, iar n aceste condiii, grupul de ageni degenereaz rapid ntr-o colecie de ageni individuali cu un comportament haotic.

Sunt cteva motive pentru care agenii au nevoie s fie coordonai:

Sisteme multi-agent

3

n primul rnd, pentru a preveni haosul. Nici un agent nu posed o viziune global asupra ntregului grup din care face parte, lucru foarte probabil n orice comunitate cu o complexitate rezonabil;

n al doilea rnd, agenii ntlnesc constrngeri globale. Agenii care realizeaz managementul de reea pot s rspund unor eventuale eecuri n timpi de ordinul secundelor sau de ordinul orelor. Coordonarea comportamentelor agenilor este prin urmare esenial la apariia unor astfel de constrngeri;

agenii n SMA posed diferite capaciti i posibiliti de expertiz. Acesta este unul din motivele utilitii coordonrii agenilor;

aciunile agenilor sunt foarte des interdependente i, prin urmare, un agent trebuie s atepte un alt agent s-i completeze task-ul nainte de a-i executa propriul task. Astfel de activiti independente trebuie s fie coordonate.

13.2.1 Coordonarea organizaional

Cea mai uoar cale de a asigura un comportament coerent i de a rezolva conflicte const n a furniza grupului un agent care s aib o perspectiv mai larg asupra sistemului, printr-o structur organizaional sau ierarhic. Aceasta este cea mai simpl tehnic de coordonare i const n arhitectura clasic master/slave sau client/server pentru task-uri i alocarea resurselor pentru agenii slave de ctre un agent master. Agentul care deine controlul poate capta informaia de la agenii grupului, poate face planuri i atribui task-uri agenilor individuali, pentru a asigura coerena global. Unele sisteme folosesc o arhitectur de tip tabel pentru a realiza coordonarea, cum ar fi sistemul DFI Werkman i sistemul Sharp Multi-Agent Kernel (SMAK) [OLIMOU2, 93]. In astfel de scheme, resursele arhitecturii tip tabel sunt nlocuite de ageni care trimit ctre i citesc dintr-o tabel general. Agentul master programeaz citirile/ scrierile agenilor din/ n tabel.

13.2.2 Modelul de organizare i coordonare

De cele mai multe ori, ntr-o reea semantic, agenii se identific cu nodurile acesteia. Exist deci o ierarhie cu dou tipuri de ageni: ageni de siguran i ageni de conducere a sistemului. Aceast relaie ierarhic definete un mod de interaciune client-server [TURGAI, 98][TURTUR1, 97]. Agenii de nivel superior selecteaz agenii de nivel inferior pentru a executa activiti. Acest proces este prezentat n figura 13-1.

Fiecare agent prezint o opinie asupra controlului sistemului. Agenii de nivel superior selecteaz agenii de nivel inferior pentru a executa activiti n mod independent, neexistnd cooperare ntre ageni pentru luarea deciziilor. Fiecare subsistem este asociat unui agent subsistem care l conduce. Datorit faptului c pot apare conflicte de utilizare a sistemului, aceast arbitrare este fcut, n mod natural, de ctre agenii de conducere a sistemului, conform prioritilor agenilor de supraveghere.

13.2.3 Colaborarea i repartiia task-urilor

Repartiia task-urilor i a resurselor constituie, n acelai timp, unul dintre domeniile majore ale sistemelor multi-agent i una din principalele lor contribuii aduse informaticii. Punnd accentul pe alocarea distributiv a resurselor, pe noiunile de contractare i angajare, ele se disting de formele clasice utilizate anterior, indiferent c este vorba de problema afectrii mainilor sau a repartiiei proceselor pe un procesor.

Sisteme multi-agent

4

13.2.3.1 Modul de alocare a task-urilor

Alocarea (sau repartiia) task-urilor are loc prin definiia mecanismelor organizaionale prin care agenii pot s pun n comun competena lor, n scopul de a realiza un obiectiv colectiv. Este vorba despre descrierea modalitii de atribuire a task-urilor tiind c posibilitile unui agent depind de aptitudinile sale intrinseci (arhitectura de care dispune, capaciti cognitive, tipuri de comunicare avute n vedere), a mijloacelor energetice de care dispune (timpul de calcul i autonomia energetic), a resurselor externe (instrumente, surse de energie) i a constrngerilor de mediu.

Task-urile care reclam mai multe mijloace, de lucru sau de pricepere, pe care un singur agent nu este capabil s le furnizeze, trebuie s fie descompuse mai nti n mai multe subtask-uri, apoi repartizate unor diferii ageni. Aceste dou operaii sunt evident legate, deoarece descompunerea task-urilor trebuie adesea s ia n consideraie competena agenilor prezeni i s faciliteze astfel repartiia care urmeaz.

Selecteaz agenipentru execuia

task-urilor

SERVER

Execuie task

Accept sau refuz deexecutare a task-ului

CLIENT

Rezultate

figura 13-1. Activiti distribuite n modul client-server

13.2.3.2 Criterii de descompunere a task-urilor

Bond, Gasser i Hill [BONGAS, 88] au prezentat cteva criterii de descompunere a problemelor. Ei indic faptul c, dac problemele pot fi analizate prin nivelul abstractizrii (lucrnd de la general la detaliat), este necesar s se ia n considerare i alte constrngeri, cum ar fi controlul, datele sau resursele. Pentru a diminua coordonarea este necesar a considera task-urile independente unele de altele. In particular, se va cuta micorarea cantitii de informaii pe care task-urile trebuie s i le transmit n vederea utilizrii resurselor locale, n scopul diminurii conflictelor legate de resurse.

Dar, chiar dac activitile de descompunere sunt la fel de importante ca i cele ale repartiiei, ele sunt, n general, efectuate de ctre fiine umane, dar acestea nu dispun de cunotinele necesare pentru descompunerea task-urilor. Din aceast cauz, cercetrile s-au orientat spre repartiia automat a task-urilor, lsnd deoparte problema descompunerii lor n subtask-uri.

13.2.3.3 Rolurile unui agent

Sisteme multi-agent

5

Un sistem de alocare automat a task-urilor trebuie s fie capabil s pun n ordine agenii care au nevoie de o informaie sau doresc s realizeze un task, clienii sau reclamanii, agenii capabili de a furniza un serviciu, furnizorii sau distribuitorii. Adesea, aceeai ageni pot fi n acelai timp clieni i furnizori, calitatea de client sau de furnizor fiind determinat de maniera dinamic din timpul funcionrii unui sistem multi-agent. Agenii vor lua atunci rolul de client sau de furnizor. Pot fi definite i alte roluri, cum ar fi cele de mediator, agenii cu acest rol fiind cei care se ocup de punerea n contact a clienilor i furnizorilor.

13.2.3.4 Tipuri de alocare a task-urilor

Repartiia task-urilor se poate efectua fie centraliznd procesul de alocare, fie distribuindu-l ansamblului de ageni cureni. Intr-un mod de alocare centralizat, se prezint dou cazuri:

1. In cazul n care structura subordonrii este ierarhic, superiorul va cere unui subordonat s-i execute task-ul. Se poate vorbi atunci de alocarea rigid sau definit. Acest mod de alocare este caracteristic unui apel de procedur n programarea clasic, el nefiind ntlnit dect n organizrile fixe;

2. Dac structura este egalitar, repartiia are loc prin definirea agenilor mediatori, care genereaz ansamblul proceselor de alocare centraliznd cererile clienilor i ofertele de serviciu ale furnizorilor, pentru a pune n coresponden aceste dou categorii de ageni, ceea ce permite aplicarea modurilor centralizate la o organizaie variabil.

Intr-un mod de alocare distribuit, fiecare agent se ocup individual de obinerea de la furnizori a serviciilor care pot s-i fie utile pentru realizarea proiectelor sale. Aceste moduri nu se aplic dect organizaiilor variabile. Se disting dou mecanisme de alocare distribuit n organizrile predefinite:

1. Modul alocrii prin reeaua de legturi, care presupune c clienii trebuie s dispun de o reprezentare a altor ageni i a capacitilor acestora. Nu este necesar ca agenii s cunoasc toate capacitile tuturor celorlali ageni pentru a putea rezolva o problem, dar este necesar ca reeaua format de ansamblul legturilor s fie conex (adic s existe un drum de la oricare agent spre oricare alt agent) i coerent (reprezentrile competenei legturilor unui agent corespund competenei efective a altor ageni);

2. Modul alocrii prin cerere de ofert, care este cunoscut n inteligena artificial distribuit sub numele de reea contractual sau reea de contracte. El prezint avantajul dinamismului i se dovedete foarte uor de pus n practic.

13.3 Cooperare, negociere i rezolvarea conflictelor

13.3.1 Cooperare Fiecare agent al unei comuniti multi-agent realizeaz dou tipuri de activiti: local i

social. In timp ce activitatea local const n realizarea task-urilor proprii, activitatea social implic o interaciune cu ali ageni ai comunitii. Pentru ca interaciunea s fie efectiv [JENMAM, 92] este necesar ca fiecare agent s fie caracterizat de consisten, relativ nu la existena sa, ci mai ales la activitile sale. Interaciunea ntre diferii ageni ai unei comuniti poate avea ca obiective competiia sau cooperarea, acestea nefiind antagonice din punctul de vedere al sistemului global. Ca urmare, n sistemele multi-agent pentru aplicaii industriale, n care agenii sunt construii pentru a colabora n rezolvarea unei probleme date, tipul de interaciune predominant este cooperarea [BELNEV, 95].

Principalele dou forme de cooperare n IAD sunt partajarea task-urilor i partajarea rezultatelor [BONGAS, 88]. Partajarea task-urilor [EIITOK, 91] este un tip de cooperare n care

Sisteme multi-agent

6

nodurile locale de rezolvare a problemelor se bazeaz pe partajarea posibilitilor de calcul n execuia subtask-urilor problemei globale. Partajarea rezultatelor este un mecanism de cooperare prin intermediul cruia, rezultatele produse de un nod sunt trimise ctre alte noduri care pot beneficia de aceste rezultate ce nu au fost cerute anterior (rezultatele sunt furnizate voluntar).

Cooperarea de tip partajare a task-urilor se verific atunci cnd un agent detecteaz c nu are informaie suficient pentru a executa un anumit task. Agentul trebuie deci s stabileasc relaii de cooperare cu ali ageni. Utiliznd cunotinele despre cooperare, agentul va verifica n modelul agenilor cunoscui dac exist ageni capabili s l ajute. Dac exist unul sau mai muli ageni ce pot s-i ofere ajutor, primul pas este de a intra n negociere cu ei. Se numete agent organizator, agentul care iniiaz o negociere i ageni colaboratori - agenii care rspund cererii de negociere. Obiectivul negocierii este ncrcarea i responsabilizarea unuia sau mai multor colaboratori pentru executarea unui task dat, venind astfel n ajutorul organizatorului.

In figura 13-2 este ilustrat aceast form de interaciune, partajarea task-urilor reprezentate prin numere i ordonarea temporal a evenimentelor.

Selecia agentuluictre care se va trimitecererea de execuie a

task-ului

Agent organizator

Rezultate

Detecie necesitate departajare

Execuie task

Accept sau refuz deexecutare a task-ului

Agent colaborator

1

2

3

45

3

figura 13-2. Interaciune prin partajare de task-uri Cooperarea de tip partajare de rezultate se verific atunci cnd un agent dispune de un

anumit tip de informaie i verific n propriul model de ageni cunoscui c exist unul sau mai muli ageni interesai n acest tip de informaie. Dac exist ageni interesai, aceast informaie le este transmis voluntar.

In figura 13-3 este prezentat aceast form de interaciune, partajarea rezultatelor, n care, ca i n figura anterioar, numerele reprezint ordonarea temporal a evenimentelor.

In continuare, sunt expuse situaiile n care un agent iniiaz o form de cooperare [OLIMOU1, 93].

13.3.1.1 Cooperarea de tip partajare de task-uri

Un agent poate iniia o cooperare de tip partajare de task-uri, fie n calitate de organizator, fie n calitate de colaborator.

Ca organizator: un agent iniiaz o cooperare de tip partajare de task-uri, ca organizator, atunci cnd, la descompunerea unui task (descompunere destinat realizrii sale) unul sau mai multe task-uri nu pot fi executate local, sau dac anumite date de intrare pentru acest task nu pot fi obinute local.

Sisteme multi-agent

7

In calitate de colaborator: n cooperarea de tip partajare de task-uri, un agent ndeplinete rolul de colaborator cnd primete un mesaj de anun al unui task i i rspunde, sau cnd un agent primete direct o cerere de execuie a unui task i ncearc s execute acel task.

In cazul n care exist mai mult dect un agent colaborator, agentul organizator anun n primul rnd task-ul i apoi evalueaz propunerile de execuie a lui, pe baza crora selecioneaz unul dintre agenii colaboratori care va ndeplini cererea de execuie a task-ului.

Selecia agenilorinteresai

Agent ofertant deinformaie (voluntar)

Informaie intern

Utilizareainformaiei n

rezolvareaproblemelor

Evaluare utilitateinformaie

Agent carerecepioneaz

informaie

1

2

3

figura 13-3. Partajarea rezultatelor

13.3.1.2 Cooperare de tip partajare de rezultate

La fel ca i la partajarea task-urilor, cooperarea de tip partajare de rezultate poate fi iniiat de ctre un agent n 2 situaii i, corespunztor, se pot distinge 2 tipuri de ageni:

Agent ofertant voluntar de informaie: agentul va verifica dac ali ageni pot beneficia de acest rezultat. Dac da, atunci acest rezultat va fi expediat ctre acetia.

Agent care reacioneaz la recepia de informaie voluntar: un agent primete date n mod voluntar de la orice alt agent (nu rspunsuri la ntrebrile prealabile sau informaie de coordonare). Datele primite sunt pstrate n partea dinamic a modelului agenilor cunoscui. Dac datele recepionate fac parte din datele de intrare ale unui task n execuie sau care a fost deja executat, i dac sunt mai de ncredere dect cele eventual existente, atunci respectivul task este reiniializat sau executat din nou. Dac datele recepionate completeaz toate datele de intrare necesare pentru un anumit task, eventual cumulate cu datele deja existente,, starea acestui task se modific la "ready" fiind deci gata de execuie.

13.3.2 Clasificarea situaiilor de cooperare i conflict

Enumerarea diferitelor tipuri de situaii n care agenilor le este necesar cooperarea, incluznd situaiile necesare pentru rezolvarea posibilelor conflicte ntre ei, conduce la o clasificare generic a cazurilor de cooperare i conflict (CCC) [OLIMOU1, 92][OLIMOU1, 93]. Aceast clasificare determin elaborarea de politici corespunztoare, ct mai independente de domeniu, pentru tratarea unor astfel de tipuri de situaii. Cteva din aceste situaii necesit diferite grade de negociere, n timp ce n cazul altora este necesar aplicarea tehnicilor de rezolvare a conflictelor.

Sisteme multi-agent

8

Cooperarea este indispensabil cnd exist diferite forme pentru ageni ce-i partajeaz activitile (necesit task-uri, necesit rezultate).

Convenional, se va utiliza simbolul NM pentru reprezentarea relaiei: "numr de organizatori numr de colaboratori"

Situaiile de cooperare i conflict sunt prezentate n tabelul 13-1.

tabelul 13-1. Situaii de cooperare i conflict

CCC1 - un agent cere ajutorul altui agent determinat i acesta din urm este liber (nu are nici un task n execuie). Aceasta este o cooperare de tip partajare de task-uri pentru care poate fi stabilit un protocol de tip client/server. Se face referire la o relaie 11.

CCC2 - un agent cere ajutor unui alt agent determinat, iar acesta din urm nu este liber i are n agenda sa cteva task-uri de executat. Acest tip de cooperare, partajarea task-urilor, este nc o relaie 11 care poate fi stabilit prin protocol client/server. Ca urmare, negocierea ntre cei doi ageni trebuie s in cont de prioritatea atribuit task-ului i de timpul estimat pentru execuia task-ului.

CCC3 - un agent are nevoie s cear un anumit serviciu i exist mai muli ageni care l pot furniza. In acest caz exist mai muli colaboratori poteniali pentru un organizator, relaia ce se stabilete fiind 1M i negocierea trebuie s se realizeze printr-un protocol de tip reea contractual ("contract net") [DAVSMI, 83].

CCC4 - mai muli ageni avnd rolul de organizatori ncearc s negocieze execuia de task-uri cu un anumit agent care are rolul de colaborator. Aceast situaie de partajare de task-uri este de tipul N1. Pentru acest caz se pot deosebi multiple posibiliti de interaciune: 4.1. - organizatorii cer simultan agentului colaborator executarea unor anumite

task-uri; 4.2. - organizatorii cer simultan agentului colaborator s execute acelai task.

Not: n aceste prime dou cazuri fiecare organizator efectueaz o cerere ctre agentul colaborator;

4.3. - se poate ntmpla, de asemenea, ca aceste negocieri ntre diveri organizatori i un anumit colaborator s reprezinte numai o parte din negocierile generale ntre aceti organizatori i ali colaboratori.

In acest caz, se poate vorbi de o relaie de tip NM. Din punctul de vedere al unui colaborator va fi de tipul N1 i din punctul de vedere al unui organizator va fi de tip 1M.

CCC5 - la un agent sosesc rezultate referitoare la acelai tip de informaie de la diferii ageni. Se consider cazul n care aceste rezultate coincid. Acesta reprezint cazul unei cooperri de tip partajare de rezultate. 5.1. - dac rezultatele sunt disponibile n acelai timp, ele putnd fi luate n

considerare, atunci credibilitatea acestei informaii este ridicat; 5.2. dac rezultatele sosesc n momente diferite i primul rezultat a fost deja

utilizat, celelalte pot fi ignorate sau utilizate numai pentru actualizarea temporal i stabilirea indicelui de credibilitate a informaiei deja salvat (provenit de la primul rezultat primit i utilizat).

Sisteme multi-agent

9

CCC6 - rezultatele (rspunsuri la cereri anterioare sau informaie primit voluntar prin partajarea rezultatelor) asupra aceluiai tip de informaie, provenite de la mai muli ageni, sunt diferite. Aceast situaie de cooperare poate fi descompus n mai multe tipuri: 6.1. - rezultatele sunt n conflict i sunt complet antagonice. Agentul receptor

trebuie s fac o alegere a unei alternative n concordan cu anumii algoritmi euristici (de exemplu, evaluarea credibilitii agenilor care au produs informaia);

6.2. - rezultatele sunt n conflict deoarece conin un oarecare tip de inconsecven. Aa cum s-a specificat anterior, se poate realiza o negociere ntre agenii implicai n scopul obinerii unei soluii unice. Realizarea acestei negocieri poate determina reexecutarea unui subtask pentru cel puin un agent sau relaxarea anumitor restricii;

6.3. - rezultatele primite, dei diferite, sunt interpretate ca fiind complementare i ca urmare, pot fi combinate ntr-un rezultat unic.

CCC7 - un agent nu obine o informaie pe care o sper (rspuns al unui alt agent la o cerere anterioar) n termenul stabilit. Organizatorul trebuie s aib capacitatea s depeasc aceast situaie, alegnd, de exemplu, un alt plan pentru task-ul n discuie.

CCC8 - un agent renun la a fi interesat de o informaie cerut anterior unuia sau unor ageni. Aceast nou situaie trebuie s fie comunicat agenilor care au fost contractai pentru executarea task-ului respectiv.

CCC9 - un agent deduce c nu poate ndeplini un task ce i-a fost cerut, n termenul stabilit de ctre organizator. Aceast informaie trebuie trimis organizatorului, deoarece el poate ncerca o rezolvare alternativ a problemei.

CCC10 - detecia unui blocaj. Aceast situaie poate apare n cazul unei incorecte descompuneri a problemei. Situaia poate fi depit alegnd o alternativ pentru task-ul ce trebuie executat.

CCC11 - cooperarea se realizeaz ca o consecin a datelor primite voluntar pentru unii ageni. Aceste mesaje, la recepia lor, pot declana execuia unui nou task, sau pot servi la actualizarea informaiei deja disponibile. Aceast actualizare poate implica o aciune de reexecutare sau reiniializare a unui task care a fost deja executat sau care este n execuie, aciune ce va fi determinat de agentul care a recepionat informaia.

Aceast clasificare, fiind independent de o anumit aplicaie, este util pentru identificarea situaiilor de cooperare i conflict n aplicaii concrete.

13.3.3 Negociere

Negocierea ntre doi sau mai muli ageni [ROSZLO2, 94] reprezint un schimb de mesaje bazat pe un protocol, ce este destinat stabilirii unui acord asupra efecturii unei forme date de cooperare.

De exemplu, pentru ca doi sau mai muli ageni s efectueze o cooperare de tip partajare a rezultatelor, agentul care deine rezultatul l trimite agenilor interesai n acest tip de informaie. Pentru a efectua acest tip de cooperare nu este necesar realizarea unui anumit tip de negociere, deoarece fiecare agent tie c trebuie s trimit voluntar informaia ctre agenii interesai, dac acetia exist. Mai explicit, un agent oarecare A1 i asum tacit c, relativ la un tip dat de informaie I1 (care este unul din rezultatele execuiei sale i pentru care din modelul propriu de ageni cunoscui

Sisteme multi-agent

10

tie c exist ali ageni care sunt interesai n acest tip de informaie) trebuie s trimit acelor ageni rezultatul obinut pentru I1, iar aceti ageni interesai trebuie s o primeasc. Aceast comunicare de informaie este bazat pe un protocol determinat pentru cooperarea de tip partajare de rezultate, dar neimplicnd negociere privat i nefiind necesar s se ia o decizie asupra formei de cooperare, deoarece aceasta este asumat implicit.

Pe de alt parte, pentru ca doi sau mai muli ageni s efectueze o cooperare de tip partajare de task-uri, agentul care pretinde ca alt agent sau ali ageni s realizeaze un task dat, ncepe efectuarea unei negocieri cu acest sau aceti ageni, cu obiectivul de a nsrcina cel puin unul dintre acetia s realizeze acest task. Acest tip de negociere este o negociere prin partajare de task-uri i se pot distinge urmtoarele dou mecanisme:

Reea contractual [OLIMOU2, 92] ("Contract Net"): este procesul de negociere iniiat de un agent dat A1, care pretinde a fi ajutat n realizarea unui task dat T1, i, prin intermediul consultrii modelului de ageni cunoscui, acest agent A1 verific dac exist mai mult de un agent cu capacitatea de a realiza acest task T1. Aceast negociere se bazeaz pe un protocol specific care const ntr-un ansamblu de schimburi de mesaje ntre agentul A1 i ali ageni cu capacitatea de a realiza T1, cu scopul de a ncredina unuia din aceti ageni, realizarea task-ului T1. Rezultatul negocierii poate fi nsrcinarea unui anumit agent cu realizarea task-ului pretins T1, dar poate fi, de asemenea, verificarea c nici un agent nu reuete (nu este dispus) s realizeze acest task T1 n condiiile restriciilor impuse. In acest ultim caz, agentul organizator al negocierii concluzioneaz c nu reuete s obin ajutor pentru realizarea acestui task T1 cu respectarea restriciilor impuse i c trebuie s ia o decizie asupra modificrii activitii sale (ncercarea unui plan alternativ pentru obinerea aciunilor pretinse sau relaxarea restriciilor impuse pentru realizarea task-ului). Aceast negociere este destinat determinrii posibilitii de realizare sau nu a cooperrii i, n caz afirmativ, determinrii formei concrete prin care se va realiza cooperarea (care agent va cere altui agent s efectueze task-ul);

Client/Server: este procesul de negociere iniiat de un agent dat A1 care pretinde a fi ajutat n realizarea unui task dat T1 i, prin intermediul consultrii modelului de ageni cunoscui, acest agent A1 verific dac exist un agent cu capacitatea de a realiza acest task T1. Aceast negociere const dintr-un schimb de mesaje ntre agentul A1 i alt agent avnd capacitatea de a realiza T1, cu scopul de a nsrcina acest agent cu realizarea task-ului T1. In acelai mod ca i n cazul anterior, rezultatul negocierii poate fi nsrcinarea acestui agent cu realizarea task-ului pretins T1, dar poate fi, de asemenea, verificarea faptului c acest agent nu reuete (sau nu este dispus) s realizeze acest task T1 cu ndeplinirea restriciilor pretinse. Aceast negociere este destinat determinrii posibilitii de realizare sau nu a cooperrii.

S-au abordat dou tipuri de colaborare, partajarea task-urilor i partajarea rezultatelor, i s-a artat c pentru prima form de cooperare nu este necesar negociere, dar pentru a doua, negocierea este destul de important.

In definiia dat mai sus pentru negocierea n SMA, ca fiind un schimb de mesaje destinat stabilirii unui acord pentru efectuarea unei forme de cooperare, se consider un sens larg pentru noiunea de cooperare. Astfel, situaiile de cooperare sunt nu numai o partajare a task-urilor i a rezultatelor, ci, de asemenea, o rezolvare de conflicte ce pot apare ntr-un SMA.

In cazul SMA pentru aplicaii industriale, aceste situaii de interaciune sunt situaii de cooperare. Totui, pentru alte SMA se pot ntlni situaii de interaciune ce includ competiia, asocierea n grup etc. [FONOLI, 96][ROSZLO, 94]. De asemenea, n aceste situaii, negocierea este util, dei se caracterizeaz prin obiective i metodologii diferite.

Sisteme multi-agent

11

13.3.4 Negocierea pentru partajarea task-urilor

Negocierea pentru partajarea task-urilor [OLIMOU2, 92][JENOLI, 92] este o capacitate foarte important pe care agenii trebuie s o posede pentru a putea prezenta un comportament adecvat n cazul n care un agent nu poate executa local un subtask dat i exist ageni care-l pot ajuta.

Cnd un agent formuleaz o cerere n scopul obinerii de ajutor de la ali ageni, este necesar iniierea unei negocieri i stabilirea protocolului corespunztor cu posibilii colaboratori la aceast cerere. Protocolul stabilit permite schimbul de informaie ntre agentul care formuleaz cererea i posibilii colaboratori. In cadrul acestui protocol, organizatorul informeaz colaboratorii despre restriciile asociate acestei cereri (n principal termenul) i ei rspund dac accept sau nu realizarea task-ului, sau informeaz organizatorul asupra timpului pe care l estimeaz a fi necesar pentru execuia task-ului i calitii ateptate a rspunsului, prin intermediul unei propuneri pentru execuia task-ului.

13.3.5 Protocoalele de negociere client/server i reea contractual

Cnd un agent detecteaz c are nevoie de ajutor, din cauz c nu este capabil s execute singur un task, el consult modelul agenilor cunoscui pentru a vedea dac exist un agent capabil s execute acel task. Dac agentul organizator deduce din modelul de ageni cunoscui c numai un agent poate executa acel task, atunci el va ncerca s stabileasc o negociere client/server trimindu-i acestuia un mesaj.

Aceast negociere utilizeaz un protocol avnd acelai nume, protocolul client/server. Nu trebuie s se confunde acest protocol cu protocolul master/slave, deoarece agentul colaborator nu este subordonat agentului organizator, ci posed suficient autonomie pentru a refuza propunerea de negociere.

Dac exist mai mult de un agent capabil de a executa acel task, organizatorul va stabili cu aceti ageni o negociere de tip reea contractual trimind ctre acetia un mesaj. Agentul colaborator trebuie s verifice dac poate accepta realizarea task-ului cerut i pentru aceasta trebuie s determine o estimaie a timpului n care va executa task-ul, n cazul unui accept.

Calculul estimativ al timpului necesar pentru a fi executat un task de ctre un agent dat va fi prezentat n subcapitolul Error! Reference source not found. i este rezumat n urmtoarele etape:

se calculeaz prioritatea pe care ar avea-o task-ul n ideea acceptrii executrii lui; considernd noul task introdus n agend (figura 13-4), se calculeaz noile valori ale

estimaiilor timpilor necesari pentru execuie, att pentru noul task, ct i pentru acele task-uri care vor fi ntrziate datorit faptului c vor avea prioritate mai mic dect noul task;

se verific posibilitatea de respectare a termenelor de execuie pentru noul task, ca i pentru task-urile care vor fi ntrziate ca urmare a introducerii noului task n agenda agentului. Dac pentru oricare din aceste task-uri nu se verific posibilitatea respectrii termenului de execuie, noul task, aflat n evaluare, nu poate fi acceptat pentru execuie.

Mesajele trimise de ctre agentul colaborator ctre agentul organizator, corespunztoare deciziilor luate asupra posibilitii acceptrii task-ului, depind de tipul de negociere ce va avea loc. Dac va exista un rspuns la o negociere de tip client/ server, atunci mesajul va conine o informaie asupra acceptului sau refuzului de execuie a task-ului.

Sisteme multi-agent

12

Task 1 (prioritate maxim)

Task k+1

Task n (prioritate minim)

Task nou

Task k

figura 13-4. Introducerea unui nou task n agend

Dac tipul de negociere este reea contractual, agentul colaborator, care a verificat sau nu posibilitatea ndeplinirii termenului de execuie cerut, trimite un rspuns cu propunerea de execuie a task-ului, n care poate indica estimaia timpului necesar pentru execuia task-ului i indicatorul de calitate sperat ca urmare a execuiei task-lui. (Dei acest indicator de calitate va fi static, o posibilitate de mbuntire a sistemului const n actualizarea dinamic a unui factor de ponderare a acestei valori. Astfel, un agent organizator ar putea verifica dac task-urile la a cror execuie au participat i ageni colaboratori au fost bine executate i s le atribuie acestor ageni un indice de fiabilitate n concordan cu participarea lor la execuia corect a task-urilor).

De notat c nu a fost luat n considerare posibilitatea apariiei unor noi cereri i necesitatea unor noi calcule ale prioritilor nainte de apariia cererii.

In cadrul negocierii de tip reea contractual agentul organizator evalueaz propunerile primite i alege, pornind de la toate rspunsurile al cror timp estimat de execuie este mai mic dect termenul cerut, agentul care va conduce ctre un indice de calitate mrit n urma execuiei task-ului. Agentului selectat i se va trimite un mesaj cu o cerere de execuie a acestui task.

Agentul care primete mesajul va calcula din nou prioritatea pe care task-ul o va avea n cazul acceptrii i apoi va verifica posibilitatea ndeplinirii termenului de execuie. Dac task-ul este acceptat, el va fi inclus n agenda agentului i agentul organizator este informat de acceptul sau refuzul cererii de realizare a task-ului.

Dac agentul organizator primete informaia c task-ul a fost acceptat pentru execuia acestuia, atunci va atepta rspunsul. Dac, dimpotriv, este informat de ctre agentul selecionat (ca urmare a celei mai bune propuneri) de refuzul execuiei task-ului, agentul organizator va reveni la alegerea celei mai bune propuneri din cele recepionate (cu excepia celei refuzate). Noului agent colaborator i se va trimite un mesaj cu cererea de execuie a task-ului. Acest proces se poate repeta pn la eventuala gsire a unui agent capabil s execute task-ul.

Att n cazul negocierii client/ server, ct i a celei de tip reea contractual, dac nu este posibil gsirea unui alt agent care s poat executa un task pe care agentul respectiv nu l poate executa el nsui, atunci execuia eueaz i agentul va trebui s ncerce un plan alternativ. In caz contrar, va eua i planul n execuie.

In final, att n cazul negocierii de tip client/server, ct i al celei de tip reea contractual, atunci cnd un agent colaborator va termina execuia task-ului, va trimite ctre agentul organizator un mesaj coninnd rezultatul execuiei.

In figura 13-5 se prezint secvena de mesaje schimbat ntre doi ageni pe durata unei negocieri de tip client/server.

Sisteme multi-agent

13

ORGANIZATOR COLABORATOR

a) Iniierea unei negocieri de tip Client/Server.

Mesaj cerereexecuie task

ORGANIZATOR COLABORATOR

Mesaj: accept refuz

b) Accept sau refuz al cererii de execuie a unui task.

ORGANIZATOR COLABORATOR

Mesaj ce includerezultatulexecuieitask-ului

c) Trimitere rezultat ctre agentul organizator.

figura 13-5. Negocierea de tip Client/Server

Secvena de mesaje corespunztoare unei negocieri de tip reea contractual este prezentat n figura 13-6.

13.4 Rezolvarea conflictelor

13.4.1 Consideraii generale Intr-un proces de luare a deciziilor conflictele sunt, de cele mai multe ori, inevitabile. Un

mod de a elimina conflictele const n restrngerea analizei, selectnd doar informaia relevant, dezvoltnd numai o alternativ i, n cazul n care aceasta eueaz, schimbnd-o. Aceast strategie mai are i avantajul de a accelera luarea deciziilor. Atunci cnd cantitatea de informaie se reduce, att analiza ct i luarea deciziilor sunt mai rapide.

Problema important care apare const n calitatea alegerii. Situaiile conflictuale conduc la rezultate stimulative n procesul lurii deciziilor. Analiza comparativ a alternativelor multiple i simultane permite evaluarea opiunilor i luarea unei decizii corecte. In plus, mai au i avantajul de a gsi soluii de mijloc: dac o opiune eueaz, se poate comuta rapid la o alt alternativ.

Sisteme multi-agent

14

ORGANIZATOR COLABORATOR 2

Mesaj cerereexecuie task

b) Agenii colaboratori trimit propuneri de execuie a task-ului ctre organizatori.

ORGANIZATOR

Mesaj cererectre

colaboratorulselecionat.

c) Agentul organizator selecioneaz un agent colaborator i trimite cerere deexecuie a task-ului ctre acesta (k n).

COLABORATOR 1

ORGANIZATOR

COLABORATOR n

a) Iniierea unei negocieri de tip Reea contractual.

Mesaj propunereexecuie task

COLABORATOR 2

COLABORATOR 1

COLABORATOR n

COLABORATOR k

figura 5-6a. Negociere de tip Reea contractual

Sisteme multi-agent

15

ORGANIZATOR

Mesaj de acceptsau refuz deexecuie atask-ului.

d) Agentul colaborator informeaz organizatorul despre acceptul sau refuzulcererii de execuie a task-ului.

COLABORATOR k

ORGANIZATOR

Mesaj cerere deexecuie a task-ului

ctre urmtorulagent selecionat.

e) Dac agentul colaborator k refuz execuia task-ului, agentul organizator vatrimite o cerere de execuie a task-ului ctre urmtorul agent selecionat (p n)

COLABORATOR p

ORGANIZATOR

Mesaj curezultatulexecuieitask-ului.

f) Agentul colaborator trimite rezultatul execuiei task-ului ctre agentul organizator.

COLABORATOR k/p

figura 13-6b. Negociere de tip Reea contractual

Cu toate acestea, existena conflictelor prelungete timpul de luare a deciziilor, dei aceasta depinde de forma de rezolvare a conflictelor.

O strategie adecvat va fi dat de obinerea alternativelor multiple i simultane i ncercarea atingerii unui consens calificat pentru rezolvarea conflictelor.

Un consens calificat se poate obine prin intermediul aplicrii urmtoarei metodologii: 1. In primul rnd, analiza i confruntarea diferitelor alternative ce ncearc s ajung la un

consens.

2. Dac consensul nu este posibil, este necesar o alegere ghidat de diferite contribuii ale diferitelor elemente din grup, accentund opiniile elementelor mai credibile.

O alegere trebuie s fie fcut cnd nu este posibil satisfacerea tuturor elementelor din grup. Cnd conflictul este o regul, gsirea consensurilor implic ntrzierea lurii deciziilor. Consensul calificat este rapid deoarece examineaz conflictul ca fiind natural, important i de multe ori inevitabil.

Sisteme multi-agent

16

13.5 Rezolvarea conflictelor n sistemele multi-agent

Cum s-a vzut n consideraiile anterioare, rezolvarea unui conflict oblig la o luare de decizie. Aceast luare de decizie ia n considerare analiza i compararea diferitelor alternative i eventual, o alegere, n cazul n care consensul nu este posibil. Din acest motiv nu este posibil distribuirea acestei luri de decizii ntre diferii ageni ai comunitii multi-agent. Trebuie s se stabileasc numai un singur agent de coordonare a procesului de rezolvare pentru fiecare tip de conflict care poate apare.

Astfel, pentru rezolvarea conflictelor care pot surveni ntre diferite alternative propuse de diveri ageni ntr-o situaie dat, se dovedete necesar s se fac o comparaie ntre diferitele alternative i s se ia o decizie. Dei rezolvarea unui conflict trebuie s fie realizat prin colaborarea diverilor ageni ai comunitii care contribuie la gestionarea alternativelor, conducerea procesului de rezolvare trebuie s fie fcut numai de un agent. Aceast capacitate de a conduce rezolvarea de conflicte trebuie s fie n mod natural atribuit unui agent cunosctor al domeniului.

Aceast centralizare a rezolvrii fiecrui tip de conflict nu este o caracteristic bun a unui sistem distribuit. Intr-o reea de sisteme, oricare serviciu central d natere la ntrzieri n procesul de rezolvare; de asemenea, ar fi posibil ca un eec ntr-un punct s poat cauza eecul ntregului sistem. Totui, exist posibiliti s nu se compromit atingerea obiectivelor sistemelor multi-agent. Un eec n rezolvarea unui conflict poate s fie depit prin executarea unui plan alternativ, care implic rezolvarea acestui conflict i care, n concluzie, poate fi executat cu succes.

Pentru fiecare tip de conflict care poate s apar ntr-un sistem multi-agent, trebuie s existe un agent capabil s rezolve acest tip de conflict. Ca urmare, se poate considera c rezolvarea conflictelor este distribuit ntre diferii ageni ai comunitii.

Considernd conflictele ce pot apare ntr-un SMA n diverse situaii, se poate realiza o clasificare a acestora ca pozitive i negative. Astfel, pe parcursul partajrii task-urilor sau a rezultatelor pot apare urmtoarele tipuri de conflicte [OLIMOU2, 92][JENOLI, 92]:

conflicte pozitive n partajarea task-urilor: apar atunci cnd exist diveri ageni capabili s execute un task cerut de un organizator. Aceast situaie competitiv trebuie s fie tratat printr-un mijloc de negociere;

conflicte negative n partajarea task-urilor: apar cnd nu exist nici un agent capabil s execute (sau nu dorete s execute) un task cerut de un anumit organizator. Acesta trebuie s aleag un plan alternativ pentru depirea acestei situaii;

conflicte pozitive n partajarea rezultatelor: apar n cazurile n care, la un moment dat, exist diveri ageni ce execut un task determinat i produc rezultate diferite, dar coerente (complementare sau identice, dar cu credibilitate diferit);

conflicte negative n partajarea rezultatelor: apar atunci cnd exist ageni ce execut un anumit task i produc rezultate antagonice sau lipsite de consisten.

Se spune c valorile sunt inconsistente dac, atunci cnd sunt intrri ale unui task, trebuie s satisfac o anumit relaie ntre ele, i nu verific aceast relaie.

Se consider ca fiind antagonice rspunsurile alternative diferite, recepionate ca urmare a aceleiai cereri (sau valori diferite pentru aceleai date de intrare ale unui task).

Astfel, unul din cazurile mai importante de conflicte apare la partajarea rezultatelor, cnd diferii ageni care realizeaz acelai task, produc rezultate inconsistente sau antagonice. Este cazul rspunsurilor diferite la aceeai ntrebare (sau pot fi valori diferite de intrare pentru un anumit task al agentului receptor).

Sisteme multi-agent

17

Capacitatea de a se confrunta cu aceste situaii i de a rezolva conflicte depinde n unele cazuri de posibilitatea ca agenii s furnizeze n afar de informaie, o msur a calitii sale i s fie posibil s efectueze comparaii ntre aceste caliti, n timp ce n alte cazuri sunt necesare cunotine dependente de domeniu.

Deoarece este de dorit s nu apar anumite tipuri de conflicte, n special cele negative, trebuie s se utilizeze tehnici pentru a le evita. Cum este aproape imposibil ca ele s nu apar [OLIMOU1, 93], este necesar utilizarea unor tehnici pentru a le detecta i, n continuare, aplicarea unor metodologii care permit rezolvarea lor. Rezolvarea unui conflict depinde n primul rnd de tipul de conflict i, n al doilea rnd, de metoda particular de rezolvare utilizat pentru acest tip de conflict.

Se consider tipul de conflict negativ de obinere a rezultatelor diferite pentru acelai tip de informaie de la ageni diferii (situaie de conflict referit anterior la CCC6), care este mai important. Una din metodologiile posibile pentru rezolvarea sa ar fi, dup detectarea apariiei acestui conflict, iniierea unei negocieri ntre agenii implicai n obinerea rezultatelor diferite pentru acest tip de informaie, cu scopul de a obine un consens [SYCARA, 89]. Aceast metodologie are avantajul de a lua n calcul posibilele contribuii ale agenilor implicai n obinerea primelor rezultate, ageni care, n principiu, trateaz domeniul n care se ncadreaz tipul de informaie analizat. Implementarea sa se dovedete foarte complex, nu numai prin gestiunea procesului de negociere ntre ageni, ci i prin capacitile adiionale pe care agenii trebuie s le posede pentru a le permite corectarea rezultatelor lor, comparativ cu rezultatele obinute de ali ageni, efectuarea de analize, sinteze, nelegerea i tratarea argumentaiei persuasive.

13.5.1.1 Rezolvarea conflictelor n partajarea rezultatelor

Propagarea rezultatelor diferite obinute pentru un anumit tip de informaie ntr-o comunitate multi-agent, conduce la obinerea de rezultate incoerente. Pentru evitarea acestei situaii se consider dou metodologii de rezolvare a acestor conflicte [ADLDAV, 89][LANLES, 90] descrise n continuare.

1. Dup ce agenii au detectat obinerea unor rezultate diferite pentru acelai tip de informaii, ei intr n negociere [ZLOROS, 91] n ideea obinerii unei soluii de compromis (de exemplu pentru relaxarea condiiilor impuse respectivelor rezultate) [FONOLI, 96][SHMOLI, 95]. Aceast soluie oblig la implementarea de protocoale adecvate acestei negocieri i la necesitatea ca agenii s posede capaciti de a corecta rezultatele lor n comparaie cu cele obinute de alt agent. Aceasta implic faptul c ntr-o anumit comunitate multi-agent, dac exist mai mult de un agent care realizeaz un anumit task, trebuie ca fiecare din aceti ageni s posede capacitatea de a-i corecta rezultatele pentru acest task; aceasta are inconvenientul de a conduce la necesitatea multiplicrii capacitilor de a trata aceste situaii de ctre diferii ageni.

Totui, aceast aproximare poate fi indicat pentru un anumit tip de aplicaii, pentru care agenii, la obinerea rezultatelor diferite pentru un anumit tip de informaie, ar putea verifica dac aceste rezultate se ncadreaz n intervalele de acceptare i cad de acord asupra unei anumite soluii intermediare.

2. O alt metodologie const n posibilitatea ca fiecare agent s dispun de mecanisme care s-i permit s detecteze dac exist cel puin un alt agent care realizeaz un anumit task. Dac, la un anumit moment dat, exist mai mult de un agent care execut un task determinat, exist posibilitatea s se ajung la rezultate diferite. Cnd aceast detecie este efectuat, rezultatele sunt trimise, nu numaidect agentului care le-a cerut sau agenilor interesai de aceste rezultate, ci unui agent special, care este agentul nsrcinat cu rezolvarea conflictelor pentru acest tip de informaie. In mod normal, agentul care rezolv conflictele pentru un anumit tip de informaie, este unul dintre agenii care are capacitatea de a executa task-ul ce conduce la acest tip de informaie. In figura 13-7

Sisteme multi-agent

18

este reprezentat metodologia de rezolvare de conflicte, numerele indicnd ordonarea temporal a evenimentelor.

Astfel, pentru fiecare tip de informaie care poate fi obinut de mai mult de un agent al comunitii (rezultatul unui task), trebuie s existe cel puin un agent, Agrc (agent care rezolv conflicte) capabil s analizeze toate rezultatele disponibile. Acest agent specializat n rezolvarea conflictelor este responsabil de trimiterea rezultatului final agentului organizator (agentul care a fcut cererea) i celorlali ageni interesai, dac acetia exist.

In continuare se consider o posibil descriere a protocolului de rezolvare a conflictelor [OLIMOU1, 93][OLIMOU2, 93].

Agenii care lucreaz simultan pentru a rspunde la aceeai cerere (fie pentru c au fost contractai, fie pentru c ofer voluntar ajutorul), trebuie s trimit rezultatele lor ctre agentul Agrc. La primirea unui mesaj, agentul Agrc va consulta automodelul su pentru a activa procedura care trateaz acest tip de conflict i care va fi, n cea mai mare parte din cazuri, bazat pe cunotine dependente de domeniu. Agentul Agrc tie c are numai un anumit timp pentru trimiterea rezultatului final la destinaie.

Agentul Agrc poate s fie sau nu capabil s execute acelai task. In oricare din cazuri, odat ce agentul este nsrcinat cu rezolvarea conflictelor pentru acest task, trebuie s se tie ci i care ageni execut acest task1 (informaie provenind din partea dinamic a modelului agenilor cunoscui - agenda agenilor).

Agentul Agrc va atepta toate mesajele rspuns, n timp ce termenul impus subtask-ului permindu-i s existe pn la atingerea limitei unui nou termen (egal cu termenul impus subtask-ului minus timpul mediu de execuie a task-ului de rezolvare a conflictelor), i apoi s ncerce rezolvarea conflictului. Dac numai un mesaj ajunge n limitele acestui nou termen, acesta va fi cel ce va fi retrimis agentului destinaie. Dac ajung mai multe mesaje n timp oportun, agentul Agrc consult automodelul su pentru a activa procedura care trateaz acest tip de conflict i, dup ce a obinut un rezultat unic, l trimite agentului destinaie.

Procedurile pentru lucrul cu diferite rspunsuri trebuie s includ: calcularea unei noi credibiliti pentru rezultatul final, bazat pe credibilitile diferitelor

rspunsuri; acumularea ntr-un mod determinat, a diferitelor rezultate; alegerea dintre diverse alternative, a celei mai bune.

In unele cazuri, n loc de a considera schimbul de informaie ntre toi agenii interesai (n determinarea datelor sau rezultatelor task-urilor) astfel nct s se permit fiecruia dintre ei recalcularea noilor valori, se prefer a se da capacitatea de a trata rezultate diferite pentru fiecare task numai unui agent specific. Aceast metodologie evit fluxul excesiv de mesaje ntre agenii comunitii, nu oblig la existena unor diferii ageni cu cunotine despre rezolvarea conflictelor pentru un task dat i, n plus, evit proliferarea rezultatelor diferite obinnd numai un rezultat final pentru fiecare task.

1 Cnd iniiaz sau termin execuia unui task, fiecare agent informeaz agenii

interesai de acest task asupra acestui lucru.

Sisteme multi-agent

19

Selecia agentuluictre care se va trimitecererea de execuie a

task-ului

Agent organizator

Rezultate

Detecie necesitate departajare

Exist cel puin unagent care execut

acest task

Execuie task

Agent colaborator

1

2

3

4

5

Selecie ageniinteresai de rezultat

Recepia rezultateloraceluiai task,

executat de mai mulicolaboratori

Agent de rezolvare aconflictelor

Rezolvare conflicte

6

7

8

Rezultat final

figura 13-7. Rezolvarea conflictelor