Etapa 4: Realizarea platformei integrate - AIMAS...

SCIPA: Servicii software semantice de Colaborare şi Interoperabilitate pentru

realizarea Proceselor Adaptive de business

Contract nr. 12118/01.10.2008 Autoritatea contractantă: CNMP

Etapa 4: Realizarea platformei integrate

Raportul Stiintific si Tehnic in extenso

Universitatea Politehnica Bucuresti

Universitatea de Vest Timişoara

Academia de Studii Economice Bucureşti

Universitatea din Craiova

Pagina Web: http://aimas.cs.pub.ro/scipa/

SCIPA – Etapa IV 2

CUPRINS

A. Obiective generale ale proiectului

B. Obiectivele etapei de executie

C. Descrierea stiintifica si tehnica


A. Obiective generale ale proiectului In cele ce urmeaza sunt prezentate obiectivele generale ale proiectului modificate pentru a reflecta reducerea de buget efectuata in anii 2008, 2009, 2010 si 2011 fata de bugetul aprobat initial.

Proiectul de fata are ca obiectiv principal studiul, proiectarea si realizarea unei unei solutii software integrate care sa permita:

interoperabilitatea serviciilor software semantice oferite de intreprinderi,

adaptabilitatea proceselor de afaceri

descoperirea si compunerea a noi servicii

un model de colaborare flexibil

Obiectivele specifice sunt:

O1: Dezvoltarea unui model al proceselor de business sustinut de servicii software capabil sa realizeze:

Adaptarea in functie de context si mediul specific

Realizarea colaborarii

Adnotarea semantica a componentelor

O2: Dezvoltarea de agenti inteligenti capabili sa compuna autonom servicii Web generand astfel servicii compuse

O4: Realizarea modelului de colaborare pe baza unei colectivitati de agenti cognitivi

O5: Dezvoltarea solutiei software

O6: Validarea solutiei prin aplicatii particulare ale proceselor de business

B. Obiectivele etapei de executie

O5: Dezvoltarea solutiei software. Rafinarea si dezvoltarea unor module oefrtante de servicii, integrarea componentelor dezvoltate in aceasta etapa si in etapele anteriaore in platforma.

O6: Validarea solutiei prin aplicatii particulare ale proceselor de business.

C. Descrierea stiintifica si tehnica

1. Platforma multi-agent

2. Modulul pentru generarea serviciilor web semantice

3. Proiectarea si implementarea unui server distribuit scalabil bazat pe agenti pentru licitatia engleza

4. Sistemul multi-agent bazat pe incredere, reputatie si norme RESPECT


1. Platforma multi-agent

S-a realizat o platform multi-agent care sa permita oferirea unor servicii informatice diverse in scpopul realizarii serviciilor de business adaptive si dinamice.

Produs informatic care reprezinta o platform bazata pe agenti software pentru implementarea serviciilor de business. Platforma porneste de la o arhitectura slab conectata care poate cuprinde diferite componenet si servicii. Printre componentele si serviciile platformei se pot mentiona: componenta de cooperare intre agenti bazata pe negociere, interactiune si invatare in timpul interactiune; sistemul RESPECT bazat pe incredere si reputatie pentru tranzactionare in medii de comert si servicii de business on-line, serviciul generic de negociere care permite licitatii de diferite tipuri, serviciile de compunere si descompunere semantica a serviciilor web informatice.

Componentele platformei sunt descrise in detaliu in capitolele urmatoare. Arhitectura generala a platformei este prezentata in Figura 1.1 Pe scurt, componentele existente pot fi descrise dupa cum urmeaza.

Sistemul RESPECT contine:

O componenta care implementeaza un model de reputatie pentru administrarea fortei de muncă în cadrul organizatiilor virtuale care poate fi utilizat pentru a simula modul prin care reputatia poate fi utilizată în administrarea unei organizatii virtuale pe baza normelor organizationale. Performantele si competentele unui agent în îndeplinirea unei sarcini sunt traduse în reputatie prin functii de evaluare specifice organizatiei. Nivelul reputatiei determină relatia pe care o are un agent cu organizatia din care face parte: pozitia acestuia în ierarhia organizatiei, includerea sau excluderea lui din organizatie.

O componenta care implementeaza respectarea specificatiilor normative, respectiv un sistem normativ complex care reglementează interactiunile dintre agenti luând în calcul si reputatia acestora. Dându-se un set generic de norme, pentru fiecare context particular acestea pot fi instantiate pe baza unor politici, pentru a fi aplicate. Exista un motor de instantiere procesează normele generice si produce, pe baza politicilor normative, un set de norme specifice, corespunzătoare contextului dat. Mecanismele de reputatie care sunt combinate pentru a asigura acoperirea tuturor tipurilor de interactiune.

Modulul de cooperare intre agenti si componenta de dezvoltare a relatiilor de cooperare.

Acest modul de servicii a fost dezvoltat initial in etapa a III-a si a fost definitivat in aceasta etapa si transformat intr-o componenta a platformei. Modulul de cooperare contine agenti de tip BDI, motivati individual, dotati cu obiective si preferinte pentru aceste obiective. Comportamentul agentilor este motivat in mare parte de castigul pe care il pot obtine din indeplinirea obiectivelor lor preferate si de necesitatea cooperarii cu alti agenti pentru atingerea acestor obiective. In timpul cooperarii cu alti membrii ai societatii de agenti un agent dezvolta profile de cooperare, ce sunt rafinate treptat si folosite pentru controlul propriului comportament in timpul negocierii.

Modulul de generare (compunere/descompunere) a serviciilor web semantice

O componenta care realizeaza abordări automate pentru generarea serviciilor web semantice compuse folosind serviciile web semantice dintr-o bibliotecă. Dat fiind un serviciu software web descris la nivels emantic, acest serviciu este cautat in biblioteca. IN cazul in


care nu a fost gasit, se genereaza descompuneri semntice dupa o metoda originala cercetata, propusa si validata in cadrul proiectului, pana la descompunerea serviciului in servicii individuale (mai simple) care se gasesc in biblioetca de servicii web.

O componenta care realizeaza un sistenm multi-agent pentru generarea de servicii intr-un mediu de comert electronim bazat pe schimburi enmonetare.

Serverul de licitatii

S-a realizat proiectarea si implementarea unui server distribuit bazat pe agenti software pentru licitatia engleza. Ofertele participantilor la licitatie sunt tratate de catre o organizatie ierarhica de agenti ce pot fi distribuiti in mod eficient pe o retea de calculatoare. Aceasta abordare evita punctele de aglomerare in procesarea ofertelor ce pot sa apara in timpul unor perioade de licitare intensa, cum este spre exemplu o situatie de snipping. Se prezinta rezultate experimentale ce arata imbunatatirea semnificativa a raspunsului serverului in comparatie cu arhitectura in care este folosit cate un singur agent manager de licitatii pentru coordonarea participantilor pentru fiecare licitatie activa care a fost creata si inregistrata cu serverul de licitatii. Sistemul a fost implementat utilizand platforma multi-agent JADE si evaluat pe baza unei multimi de scenarii experimentale. Sunt descrise proiectarea si implementarea serverului bazat pe agenti, interfata grafica utilizator bazata pe Web si rezultatele experimentale obtinute.

Service request

Service selection

RESPECT Agents with Trust,

Reputation and Norms

Cooperation Model

Cooperative Agents

Auction Service Agents Server

Semantic Service Composition

Agents Module

Communication and Interaction Layer

Distributed Database Layer

Hardware Abstraction Layer

U

U

U

U U

Figura 1.1 Structura paltformei multi-agent


2. Modulul pentru generarea serviciilor web semantice

2.1 Servicii web semantice

In (Web Services Architecture, 2004), avem următoarea definitie a unui serviciu web:

“Un serviciu web este un sistem software proiectat pentru a suporta interactiuni interoperabile masină-masină intr-o retea. Are o interfată descrisă intr-un format care poate fi procesat de o masină (în general WSDL). Alte sisteme interactionează cu serviciul web intr-un mod prezentat de descrierea sa folosind mesaje SOAP, de obicei folosind HTTP cu o serializare XML impreună cu alte standarde Web”

Web-ul Semantic este un web care poate fi citit şi inteles de către calculator. Conform (Berners-Lee et al., 2001), “Web-ul Semantic nu este un Web separat, ci o extensie a celui actual, în care informaţia are un inteles bine definit, permitand calculatoarelor şi oamenilor să coopereze”.

Serviciile web semantice folosesc aceste două tehnologii: serviciile web şi Web-ul Semantic. Serviciile web semantice sunt servicii web cu o descriere semantică formală (Lécué and Delteil, 2007). Descrierile semantice sunt de obicei reprezentate folosind ontologii şi logici de descriere (Baader and Nutt, 2003); prin utilizarea acestui tip de descrieri semantice mai multe operatii importante referitoare la serviciile web devin automate: descoperirea, selectia, compunerea şi invocarea serviciilor (Lécué and Delteil, 2007).

2.2 Metode de compunere a serviciilor web semantice

Clasificarea contine următoarele clase de metode: compunere semi-automată, planificare AI clasică, planificare AI HTN, planificare AI folosind legături cauzale, agenti şi sisteme multi-agent, limbaje logice (Golog), reguli de productie.

Compunere semi-automata

Compunere automata

Planificare AI

Reguli Agenti şi sisteme multi-agent

Limbaje logice

Planificare AI cu legaturi cauzale

Planificare AI HTN

Planificare AI clasica

Abordare folosita pentru compunerea serviciilor web semantice

Figura 2.1. Arborele de abordări pentru compunerea serviciilor web semantice

Sunt utilizate două abordări principale: compunerea semi-automată şi compunerea automată. Există cateva abordări semi-automate care oferă o compunere eficientă a serviciilor web semantice; principala problemă a acestor abordări este faptul ca este necesară şi interventia umană, calculatorul nefiind capabil sa realizeze de unul singur compunerea.


Majoritatea rezultatelor se refera la compunerea automată a serviciilor web semantice; principalele probleme ale acestor abordări sunt reprezentate de complexitatea computatională ridicată a acestor metode şi de calitatea compunerilor (gradul în care serviciul web semantic compus se potriveste cu specificatia utilizatorului). Rezultatele referitoare la compunerea automată folosesc următoarele tehnici pentru a rezolva problema compunerii: planificarea AI, agentii şi sistemele multi-agent, limbajele logice şi regulile de productie. In Figura 2.1 prezentăm arborele abordărilor folosite pentru compunerea serviciilor web semantice.

In continuare, prezentăm trei comparatii referitoare la abordările pentru compunerea serviciilor web semantice. Tabelul 2.1 prezintă o comparaţie ce are la bază numărul de articole care folosesc fiecare abordare pentru compunere, Tabelul 2.2 arată o comparaţie temporală intre abordările pentru compunere, iar Tabelul 2.3 contine o comparaţie temporală intre abordările pentru reprezentarea semanticii serviciilor web semantice.

Abordare pentru compunerea serviciilor web semantice

Numărul de articole din analiza propusă

Compunere semi-automată 2

Compunere automată 18 Planificare AI 11 Planificare AI clasică 4 Planificare AI HTN 5 Planificare AI cu legături cauzale 2 Agenti şi sisteme multi-agent 4 Limbaje logice 2 Reguli 1

Tabelul 2.1 Comparaţie intre abordările pentru compunerea serviciilor web semantice bazată pe numărul de articole care folosesc fiecare abordare

Tipul de abordare Abordare Old Low Medium High Medium New

Compunere semi-automată

2003 2004 - -

Planificare AI clasică 2003 2004 2007, 2007 - Planificare AI HTN 2003 2004, 2004, 2005 - 2008 Planificare AI cu legături cauzale

- - 2006, 2007 -

Agenti şi sisteme multi-agent

2002 2004 2006 2008

Limbaje logice 2002 - - 2009 Reguli - - 2007 -

Tabelul 0. Comparaţie temporală intre abordările pentru compunerea serviciilor web semantice

Tipul de abordare Abordare pentru semantică SWS Old Low Medium High Medium New

DAML-S (7 rezultate)

2002, 2002, 2003, 2003,

2003

2004 - 2008

OWL-S (11 rezultate)

- 2004, 2004, 2004, 2004, 2005

2006, 2006, 2007, 2007, 2007

2008


WSMO (3 rezultate)

- - 2006, 2006, 2007 -

WSDL-S (0 rezultate)

- - - -

Altele (4 rezultate)

- - 2007, 2007 2008, 2009

Tabelul 2.3. Comparaţie temporală intre abordările pentru reprezentarea semanticii serviciilor web semantice

Ca o concluzie a acestei sectiuni prezentăm următoarele idei: - cea mai importantă metodă generală de compunere a serviciilor web semantice este compunerea automată - cele mai importante abordări automate pentru compunere sunt cele care folosesc planificarea AI - cele mai promitătoare abordări automate pentru compunere sunt: planificarea AI HTN, agentii şi sistemele multi-agent şi limbajele logice - cea mai importantă abordare referitoare la reprezentarea semanticii serviciilor web semantice este OWL-S - o nouă abordare referitoare la reprezentarea semanticii serviciilor web semantice este găsirea unor alternative la abordările existente

2.3 Servicii web semantice matematice

Serviciile web matematice sunt servicii web create pentru a rezolva probleme matematice care pot fi rezolvate automat. De exemplu, un serviciu web matematic poate găsi solutia unei ecuatii (rezolvabile automat) sau poate să calculeze o expresie matematică sau poate să aplice o tehnică de metode numerice pentru o anumită problemă. Pentru a automatiza descoperirea, selectia şi compunerea serviciilor web matematice, este necesar să se adauge acestor servicii descrieri semantice.

Serviciile web semantice matematice sunt foarte utile în practică; cu toate acestea există un numar mic de rezultate de cercetare în acest domeniu. Recent, există o serie de initiative de a dezvolta limbaje pentru descrierea serviciilor web semantice matematice. Interesul pentru dezvoltarea unor astfel de limbaje provine din faptul că serviciile web semantice matematice au anumite particularitati şi se pot dezvolta limbaje mai simple decat limbajele existente pentru serviciile web semantice.

S-au prezintă principalele tehnologii referitoare la serviciile web semantice: serviciile web, Web-ul Semantic şi serviciile web semantic, şi apoi prezintă o analiză a metodelor utilizate pentru compunerea serviciilor web semantice. Principalele concluzii referitoare la aceste metode sunt următoarele: 1) cele mai multe dintre rezultate folosesc abordări automate pentru compunere; 2) cele mai populare abordări automate pentru compunere sunt planificarea AI şi agentii şi sistemele multi-agent; 3) cele mai promitătoare abordări automate pentru compunere sunt planificarea AI, agentii şi sistemele multi-agent şi limbajele logice deoarece au fost folosite pentru cele mai noi rezultate din analiza facută; 4) cea mai populară abordare pentru reprezentarea semantică a serviciilor web semantice este OWL-S.

2.4 Aplicarea serviciilor web semantice la schimburi nemonetare

Această secţiune prezintă două abordări de a adăuga servicii web semantice intr-un sistem multi-agent proiectat pentru a regla comportamentul agentilor intr-un mediu economic


bazat pe schimburi nemonetare. Alegerea partenerilor de schimb se face atat în funcţie de reputatia posibililor parteneri, cat şi în funcţie de valorile increderii pe care le are agentul le are referitor la posibilii parteneri. In cadrul acestui sistem multi-agent propunem o nouă metodă de compunere a serviciilor web semantice.

2.4.1 Structura sistemulului multi-agent

Comunitatea multi-agent constă din două tipuri de agenti: o autoritate centrală (CA) şi agenti producători (sau ‘agenti’). Există un singur CA, care pastrează informatiile legate de toti agentii din sistem, valorile reputatiei agentilor şi capabilitătile de productie ale fiecărui agent. Agentul CA recalculează valorile reputatiei după un anumit număr de tururi. Agentul CA poate să comunice cu agentii şi să răspundă la diferite cereri. Sistemul contine o multime de norme şi CA impune aplicarea normelor prin decrementarea valorii reputatiei pentru agentii pentru care s-au primit plangeri. Valorile reputatiei influentează schimburile modificand ratele de schimb.

Fiecare agent are de constuit un produs; produsul este considerat construit atunci când agentul a adunat toate resursele necesare pentru acel produs. Fiecare agent are acces direct la un număr de tipuri de resurse, numite resurse interne. Niciun agent nu poate să isi construiască produsul folosind doar resurse interne ; fiecare agent trebuie să obtină resursele care ii lipsesc realizand schimburi cu ceilalti agenti. Resursele obtinute prin schimburi vor fi numite resurse externe. Agentii trebuie să colaboreze pentru a isi construi produsele.

Un agent are o anumită reputatie şi apartine clasei de reputatie corespunzătoare. In plus, fiecare agent are asociat o valoare de incredere pentru fiecare din partenerii lui, fosti sau actuali. Un agent poate interactiona cu toti ceilalti agenti şi poate propune schimburi; în acelasi timp poate accepta sau refuza ofertele primite. Agentul CA lucrează ca un registru care pune la dispozitie în orice moment lista cu agentii care oferă un anumit tip de resursă agentilor care cer acest lucru. Un agent poate să ofere la schimb doar resurse interne. Agentii au posibilitatea sa-l informeze pe agentul CA când observă o incălcare de normă.

2.4.2 Modelul schimburilor nemonetare

Mecanismul de sincronizare utilizat de model se bazează pe tururi. Fiecare tur constă din două faze. In timpul primei faze fiecare agent poate face o ofertă unui alt agent sau poate sa-l informeze pe agentul CA de incalcarea unei norme. După primirea tuturor ofertelor, agentul poate sa le accepte sau sa le refuze tinand cont de interesele lui şi de valorile reputatiei agentilor care au facut ofertele. In timpul fazei a doua un agent poate sa raspundă afirmativ unei oferte, acest lucru insemnand că schimbul se face instantaneu, sau poate sa raspundă negativ tuturor ofertelor. Lista agentilor existenti, a capabilitătilor de productie şi valorile reputatiei agentilor sunt accesibile tuturor agentilor din sistem.

2.4.3 Metodă de compunere a SWS pentru schimburi nemonetare

In această subsectiune sunt prezentate două abordări pentru extinderea sistemului multi-agent şi o nouă metodă de compunere a serviciilor web semantice prezentată pentru cele două extinderi ale sistemului.


Goal Product

Internal Resources

Figura 2.2. Sistemul ABE1

Prima abordare pentru extinderea sistemului

Sistemul propus se numeste ABE1. Considerăm că fiecare agent A are un serviciu web semantic responsabil pentru toate resursele lui interne. In această situatie, atunci când un agent B vrea sa obtină o resursă internă a agentului A, agentul B trebuie să invoce acel serviciu web semantic. In Figura 2.2 este prezentată arhitectura sistemului ABE1. Principalul avantaj al acestei abordări este acela ca un serviciu web semantic găsit în bilioteca de servicii web semantice poate fi folosit pentru a obtine mai multe tipuri de resurse.

A doua abordare pentru extinderea sistemului

Sistemul propus se numeste ABE2. Considerăm că pentru fiecare agent A, fiecare tip de resurse interne are un serviciu web semantic asociat. In această situatie, atunci când un agent B vrea sa obtină o anumită resursă internă a agentului A, agentul B trebuie să invoce serviciul web semantic asociat acelei resurse interne. Sistemul ABE2 este prezentat în Figura 2.3. Principalul avantaj al acestei abordări este acela că descrierea semantică a unui serviciu web semantic este foarte simplă.

Semantic web Service

nA

Goal Product

Internal Resources

Semantic web Service

1A

…

CA SWS Search

SWS Search

Semantic Web Service Library

Semantic Web Service Invocations

iA


Goal Product

Figura 2.3 Sistemul ABE2

2.4.4 O discutie referitoare la noua metodă de compunere

Putem observa că strategiile adoptate de un agent A pentru construirea produsului lui reprezintă de fapt o planificare AI HTN în care task-ul dorit este resursa compusă şi resursele necesare task-urile elementare. Conditile care trebuie satisfăcute în cadrul descompunerii sunt reprezentate de normele din sistem (conditii externe) şi de strategiile agentului (conditii interne). De asemenea, se poate observa că ceilalti agenti il pot ajuta pe agentul A să isi termine de construit produsul, prin trimiterea de oferte acestui agent. In acest fel, compunerea de servicii web semantice reprezintă o abordare “de jos în sus” bazată pe sisteme multi-agent. Tinand cont de observatiile de mai sus, compunerea de servicii web semantice este de fapt o abordare mixta “de sus în jos” şi “de jos în sus”, o combinatie interesantă de tehnici de compunere a serviciilor web semantice.

2.4.5 Rezultate experimentale

In această subsectiune sunt prezentate cateva rezultate experimentale referitoare la noua metodă de compunere. Considerăm 11 tipuri de resurse, 8 produse şi 15 agenti. Vom prezenta rezultatele procesului de compunere pentru agentul A2, pentru cele doua sisteme ABE1 şi ABE2. Descrierea serviciului web semantic complex care corespunde produsului pe care agentul A2 il are de construit este prezentată în Tabelul 2.4.

Agent Complex Semantic web service Description A2 R5R5R5R6R6R8R8R8R8

Tabelul 0. Descrierea serviciului web semantic complex pentru agentul A2

In Tabelul 2.4 şi în Tabelul 2.5 sunt prezentate fluxurile de compunere pentru sistemul ABE1 şi respectiv pentru sistemul ABE2 referitor la agentul A2.

Int Res 1

nA

Goal Product

1A

…

CA

Semantic Web Service Library

SWS Search

SWS Search

Semantic Web Service Invocations

SWS 1

…

Int Res k1 SWS k1

Int Res 1

SWS kn Int Res kn

…

SWS 1

iA


A2: S[A13]->R5; S[A2]->R10; S[A9]->; S[A2]->R10; S[A8]->R8; S[A2]->R10; S[A2]->R8; S[A11]->R6; S[A2]->R10; S[A7]->R8; S[A6]->R5; S[A2]->R10; S[A6]->R5; S[A11]->R6R6;

Tabelul 2.5 Fluxul de compunere pentru ABE1 referitor la agentul A2

A2: S[A13,R5]->R5; S[A2,R9]->R10; S[A9,R8]->; S[A2,R2]->R10; S[A8,R8]->R8; S[A2,R4]->R10; S[A2,R9]->R8; S[A11,R6]->R6; S[A2,R9]->R10; S[A7,R8]->R8; S[A6,R5]->R5; S[A2,R9]->R10; S[A6,R5]->R5; S[A11,R6]->R6R6;

Tabelul 2.6 Fluxul de compunere pentru ABE2 referitor al agentul A2

Se observa că, în a doua variantă a sistemului, numele unui serviciu web semantic trebuie sa contină atat numele agentului care detine serviciul cat şi resursa interna care corespunde acelui serviciu. Din acest motiv, fluxurile de compunere pentru ABE2 au o lungime mai mare decat fluxurile de compunere pentru ABE1.

2.5 Generarea serviciilor web semantice folosind descompunerea descrierii semantice

Se prezinta o abordare automata pentru generarea serviciilor web semantice compuse folosind serviciile web semantice dintr-o bibliotecă. Se prezintă o metodă de generare a unui serviciu web folosind descompunerea descrierii lui semantice şi funcţii de complexitate de o variabilă apoi se prezintă două metode de extindere a sistemului prezentat anterior la dictionare multidimensionale.

2.5.1 O metodă de generare a SWSs folosind decompunerea descrierii semantice şi funcţii de complexitate de o variabilă

Dictionar

Considerăm o multime de cuvinte W. De asemenea, considerăm că fiecare cuvânt din W are un singur inteles. Fie s (unde s provine de la semantic) o relaţie binară peste W

cu următoarea definitie:

acelasiauwsiwwwWww s 212121 ,, inteles.

Relatia binară pe W este o relaţie de echivalentă. s

Considerăm familia claselor de echivalentă determinate de pe W.

Această familie are NC clase de echivalentă. Următoarea teoremă oferă o caracterizare a acestei familii.

NCiiC 1)( s

Familia claselor de echivalentă este o partitie a lui W. NCiiC 1)(

Fiind date multimea de cuvinte W şi relatia de echivalentă s pe W, dictionarul D asociat lui

W şi este , unde este familia claselor de echivalentă determinate

de pe W.

s

s

NCiiCD 1)( NCiiC 1)(


O relaţie de ordine intre clasele de echivalentă

2112

2121 ,,

wwsauintelescawdecatgeneralmaiestew

wwWww

s

s

Pentru fiecare clasă de echivalentă }...,,2,1{, NCiCi alegem un cuvânt ii Cw . Acest

cuvânt va fi numit cuvantul reprezentativ al clasei . iC

jiCCDCC jsciji ,,

jsijsciji wwCCDCC ,,

2.5.2 Reprezentarea descrierilor semantice. Dictionarul de descrieri semantice

Considerăm multimea de cuvinte W, relatia de echivalentă pe W şi dictionarul

asociat discutate în subsectiunile anterioare. Considerăm următoarea descriere

semantică a unui serviciu web semantic:

s

NCiiCD 1)(

liii www ...21

, unde Wwwwliii ,...,,

21

Vrem sa exprimăm această descriere semantică ca o funcţie de complexitate.

altfel

Cwincatastfelwwwwifnsd

NCsd

niii l

,0

},...,,{,1)(1

}1,0{}...,,2,1{:1

21

)mod(1)(2},1,0{:2 ** NCnsdnsdNsd

unde definim după cum urmează: dacă *mod ,modmod* NCnNCn 0mod NCn şi

dacă ,NCmod* NCn 0mod NCn .

Descrierea semantică a unui serviciu web semantic este următoarea funcţie:

0)(2),1/(1

1)(2,1)(,: **

nsddacan

nsddacannsdRNsd (6.1.15)

Dictionarul de descrieri semantice (SDD) este multimea descrierilor semantice de incredere din sistem.

2.5.3 O formă simplificată a unei descrieri semantice

Din motive practice, sistemul software va utiliza o formă simplificată a unei descrieri semantice:

Descrierea semantică scurtă asociată unei descrieri semantice este următoarea

funcţie:

ASDsd

*# }...,,2,1{: RNCsd , (6.1.16) }...,,2,1{),()(# NCnnsdnsd

unde NC este numărul claselor de echivalentă din dictionarul NCiiCD 1)( . Notăm cu

multimea descrierilor semantice scurte care corespund descrierilor semantice din ASD.

#ASD


Adăugarea de informatie semantică descrierilor semantice

Adăugam informatie semantică descrierilor semantice din multimea ASD şi prin adăugarea pentru fiecare descriere semantică a urmatoarei informatii: pentru fiecare valoare de intrare n a functiei care reprezintă descrierea semantică, retinem numărul de cuvinte din descrierea semantică initială care apartin clasei de echivalentă .

#ASD

nCliii www ...

21

2.5.4 Structura sistemului ASD

Sistemul propus în această subsectiune se numeste ASD. Structura sistemului folosit pentru generarea unui serviciu web prin descompunerea descrierii lui semantice este descris în Figura 2.4 şi este compus din 8 module: Processing Module, Decomposition Module, Semantic Descriptions Comparing Module, Words Module, Semantic Descriptions Approximation Module, Composition Module, Semantic Web Services Module şi Feedback Module.

Processing Module are o singură componentă: Processing Agent. Acest agent primeste o descriere semantică SD a unui serviciu web care trebuie generat de sistem, rulează algoritmul principal, comunică cu ceilalti agenti pentru a rezolva problema şi ii trimite utilizatorului descrierea completă CD a acelui serviciu.

Decomposition Module are trei componente: Semantic Descriptions Dictionary, Decomposition Agent, şi Semantic Descriptions Generator Agent. Semantic Descriptions Dictionary contine toate descrierile semantice care au fost folosite în trecut de catre sistem, ordonate descrescător în funcţie de coeficientul de incredere. Fiind dată o descriere semantică SD, Semantic Descriptions Generator Agent generează, dacă ii cere Decomposition Agent, descrieri semantice utilizand doar unele cuvinte din descrierea semantică SD.

Semantic Descriptions Comparing Module are o singură componentă: Semantic Descriptions Comparing Agent. Acest agent compară două descrieri semantice utilizand definitiile şi metodele de comparare a descrierilor semantice prezentate deja în acest capitol.

Words Module are cinci componente: Dictionary, Ontology, Words Inequality Comparing Agent, Words Equality Comparing Agent şi Words Searching Agent. Dictionary contine cuvintele permise de sistem, grupate în clase de cuvinte cu acelasi inteles. Ontology descrie relatii de inegalitate intre cuvintele reprezentative asociate claselor de cuvinte din Dictionary. Words Inequality Comparing Agent primeste două cuvinte de la Processing Agent, caută în Ontology şi găseste relatia de inegalitate dintre cele două cuvinte, dacă aceasta există. Words Equality Agent primeste două cuvinte de la Processing Agent, caută în Dictionary şi verifică dacă cele două cuvinte apartin aceleiasi clase din Dictionary (adică dacă cele două cuvinte au acelasi inteles). Words Searching Agent primeste un cuvânt de la Processing Agent, caută în Dictionary şi găseste clasa din care face parte cuvantul respectiv.

Semantic Descriptions Approximation Module are o singură componentă: Semantic Descriptions Approximation Agent. Acest agent primeste de la Processing Agent o descriere semantică, doi indecsi (necesari pentru constructia aproximarii) şi tipul de aproximare dorit şi reintoarce aproximarea acelei descrieri semantice.

Composition Module are o singură componentă: Composition Agent. Acest agent primeste de la Processing Agent o descompunere a descrierii semantice SD şi informaţia necesară pentru a gasi direct (adică fără a căuta) serviciile web semantice (care corespund descrierilor semantice elementare din descompunere) în Semantic Web Services Library, face


compunerea acestor servicii web semantice şi reintoarce descrierea completă CD a serviciului web semantic compus.

Semantic Web Services Module are două componente: Semantic Web Services Library şi Semantic Web Services Searching Agent. Semantic Web Services Library este biblioteca de servicii web semantice disponibile pentru a fi folosite de către sistem. Semantic Web Services Searching Agent primeste o descriere semantică, caută în bibliotecă serviciul web semantic corespunzător, şi dacă serviciul există, reintoarce descrierea completă a acelui serviciu.

Feedback Module are două componente: Feedback Agent şi Semantic Descriptions Dictionary Updating Agent. După ce Processing Agent ii trimite utilizatorului descrierea completă CD, Feedback Agent primeste de la utilizator un mesaj de feedback FB care contine informatii referitoare la ultimul proces de generare a unui serviciu web semantic asociat descrierii semantice SD. Dacă rezulatul a fost acceptat de către utilizator, atunci procesul de generare a serviciului web semantic compus se opreste.

Dacă rezultatul nu este suficient de bun, atunci procesul continuă pentru a rezolva problemele referitoare la unele părti din descrierea semantică SD. Semantic Descriptions Dictionary Updating Agent primeste de la Feedback Agent mesajul FB şi modifică Semantic Descriptions Dictionary.


Semantic Descriptions Generator Agent

Ontology

Processing

Agent

Semantic Descriptions Comparing Agent

Composition Agent

Decomposition Agent

Feedback Agent

Semantic Web Services Library

Words Inequality Comparing Agent

Semantic Descriptions Approximating Agent

Semantic Descriptions Dictionary

Words Searching Agent

Semantic Web Services Searching Agent

Words Equality Comparing Agent

Semantic Descriptions Dictionary Updating Agent

SD

CD

FBFeedback Module

Processing Module

Decomposition Module

Semantic Descriptions Comparing Module

Words Module

Semantic Descriptions Approximation Module

Composition Module

Semantic Web Services Module

Dec

Dictionary

Figura 2.4 Structura sistemului pentru generarea unui servciu web prin descompunerea

descrierii lui semantice


2.5.5 Rezultate experimentale In această subsectiune prezentăm cateva rezultate experimentale. Descrierea semantică

initială este prezentată în 2.7

flight reservation car reservation hotel reservation

Tabelul 2.7 Descrierea semantică initială exprimată în cuvinte

Pentru descrierea semantică initială dată, sistemul lucrează în felul următor:

Initial SD Length: 6 flight reservation car reservation hotel reservation

The solution for the initial semantic description SD 1: 1 743 744 1 -> type: 0 SD 2: 1 743 744 1 -> type: 0 SD 3: 2 123 124 1 743 744 1 -> type: 0 SD 4: 2 24 25 1 152 153 1 -> type: 0

Your response (1: accept / 0: reject) is: SD 1: 0 SD 2: 0 SD 3: 1 SD 4: 0

What is the best SWS for the SD: 2 24 25 1 743 744 1 ? The choices are the following: CarReservation1(1) CarReservation2(2) The best choice is (1-2): 2

The solution for the initial semantic description: SD 1: 2 123 124 1 743 744 1 -> type: 0 SD 2: 2 24 25 1 743 744 1 -> type: 0 SD 3: 2 152 153 1 743 744 1 -> type: 0

Your response (1: accept / 0: reject) is: SD 1: 1 (already validated) SD 2: 1 SD 3: 1

Initial SD Length: 6 flight reservation car reservation hotel reservation

The result of the composition is the following (swsName (type)): (Type: 0 – exact matching, 1 – approx type 1, 2 – approx type 2) FlightReservation1 (0); CarReservation2 (0); HotelReservation1 (0);

Tabelul 2.8 Rezultate experimentale

Acest exemplu se ocupă doar de potrivirea exactă. Sistemul este capabil să folosească şi aproximari ale descrierilor semantice; această caracteristică a sistemului este utilă mai ales atunci când se utilizează nu număr mare de servicii web semantice şi un număr mare de descrieri semantice.


2.6 Metoda pentru compunerea serviciilor web semantice bazată pe potrivire de sabloane

In această secţiune prezentăm o abordare pentru compunerea serviciilor web semantice bazată pe potrivire de sabloane. Fiind dată o descriere semantică, în forma unei liste de descrieri semantice care corespund unor servicii web semantice dintr-o bibliotecă de servicii web semantice, vrem să construim un nou serviciu web semantic compus, care corespunde descrierii semantice initiale, folosind serviciile web semantice din bibliotecă. Acest obiectiv este realizat folosind descompunerea descrierii semantice initiale. Sunt analizate cateva structuri posibile ale descrierii semantice initiale şi sunt prezentate un algoritm de descompunere şi un sistem software pentru rezolvarea problemei. Ideea de bază este să se găsească sabloane similare în descrierea semantică initială şi să se folosească această informatie pentru a obtine o rezolvare eficientă a problemei.

2.6.1 Structura sistemului APM

Sistemul propus în această secţiune se numeste APM. Structura sistemului este prezentată în Figura 2.5. Sistemul este compus din cinci agenti: Main Agent, Decomposition Agent, Pattern Matching Agent, Composition Agent şi Searching Agent şi două biblioteci de servicii web semantice: SWS Library şi Auxiliary SWS Library.

Main Agent

Auxiliary SWS

Library

Decomposition Agent

Composition Agent

Pattern Matching Agent

Searching Agent

SD

CD

SWS Library

Figura 2.5 Structura sistemului pentru scenariul de compunere a SWS bazat pe potrivire de

sabloane

Atunci când biblioteca de servicii web semantice contine multe servicii web semantice căutarea unui serviciu web semantic poate sa reprezinte o problemă dificilă din punct de vedere al resurselor computationale consumate. Principalul avantaj al metodei propuse este acela că minimizează numărul de căutari, prin analizarea structurii descrierii semantice initiale. Metoda este foarte utilă atunci când unele dintre descrierile semantice elementare care compun descrierea semantică initială SD au mai multe aparitii în SD. Cele mai bune performante sunt obtinute atunci când numărul acestor aparitii multiple este ridicat.

2.6.2 Un scenariu de compunere a serviciilor web semantice bazat pe un număr mic de SWS

In această secţiune este prezentat un scenariu de compunere a serviciilor web semantice care utilizează un număr mic de servicii web semantice şi oferă o solutie pentru acest scenariu. Cele mai importante contributii ale acestei sectiuni sunt: prezentarea unui sistem multi-agent care rezolvă problema compunerii pentru acest scenariu, descrierea unei notatii textuale pentru reprezentarea orchestrării serviciilor web semantice folosite pentru


obtinerea serviciului web semantic compus şi prezentarea unor exemple de utilizare a notatiei textuale pentru acest scenariu.

Principalul motiv pentru utilizarea restrictiei referitoare la numărul de servicii web semantice este faptul că notatia textuală propusă este o notatie manuală. De aceea, pentru un număr mare de servicii web semantice, notatia nu este foarte usor de folosit pentru că utilizatorul uman va trebui să reprezinte o orchestratie de dimensiuni mari pentru serviciile web semantice din compunere.

Considerăm că sunt necesare N servicii web semantice pentru obtinerea unui serviciu web semantic compus; din motive practice considerăm că 10N . Fie

descrierile semantice care corespund acestor servicii web semantice. De asemenea considerăm o bibliotecă de servicii web semantice numită SWS Library; fiecare descriere semantică

corespunde cel putin unui serviciu web semantic din bibliotecă. Fiecare

descriere semantică descrie serviciul web semantic care poate rezolva un anumit task. Considerăm că corespunde lui ,

NSDSDSD ...,,, 21

NSDSDSD ...,,, 21

SDi iTask Ni ,1 . Task-urile oferă informatii despre cum

trebuie modifcată starea curentă. Pentru un anumit task Task , i i N,1 , nu toate serviciile

web semantice care corespund acelui task sunt disponibile atunci când sunt invocate, dar cel putin unul dintre servicii poate oferi această informatie.

Fiind date starea intială şi starea finală a mediului, vrem să obtinem, folosind serviciile web semantice din bibliotecă, un serviciu web semantic compus care să transforme starea initială în starea finală. Pentru un anumit task, dintre toate serviciile web semantice din bibliotecă care corespund acestui task, un singur serviciu web semantic trebuie ales pentru starea curentă a mediului. Compunerea este realizată prin utilizarea unei multimi de reguli pentru a stabili serviciile web semantice care trebuie invocate pentru a obtine starea finală.

Structura sistemului ASN

Sistemul propus în această secţiune se numeste ASN. Structura sistemului este prezntată în Figura 2.6. Sistemul este compus din sase agenti: Main Agent, Composition Agent, Rules-Based Agent, Searching Agent, Testing Agent şi SWS Agent, o bază de date pentru reguli, numita Rules Database şi o bibliotecă de servicii web semantice, numita SWS Library.

Composition

Agent

Rules-Based Agent

Testing Agent

Rules Database

Searching Agent

SWS Library

initial state

final state

result SWS Agent

Main Agent

Figura 2.6 Structura sistemului ASN pentru compunerea SWS folosind un număr mic de

servicii web semantice


2.7 O metodă de a genera servicii web semantice matematice folosind descompunerea descrierii semantice

In această secţiune este prezentată o metodă de obtinere a unei aproximări a unui serviciu web semantic matematic, pornind de la descrierea lui semantică, folosind servicii web semantice matematice existente, formule de aproximare şi tehnici ce folosesc metode numerice. Se studiază doar cazul în care serviciul web semantic matematic calculează o expresie matematică. Uneori în loc de serviciu web semantic matematic vom spune MSWS.

Spunem că un MSWS m2 aproximează un MSWS m1, dacă pentru fiecare intrare a lui m1, m2 dă aproape acelasi rezultat ca m1. Diferenta dintre rezultatul dat de m1 şi rezultatul dat de m2 este controlat de o funcţie de eroare. Intelegem prin descriere semantică (SD), informaţia semantică ce permite unui calculator să inteleagă ce face un serviciu web. Intelegem prin descriere completă (CD), intreaga informatie folosită pentru descrierea unui serviciu web, inclusiv descrierea semantică.

Vrem sa rezolvăm urmatoarea problemă: fiind date o descriere semantică a unui MSWS, numit M, o biblioteca de servicii web semantice matematice, o bibliotecă de formule de aproximare şi o bibliotecă de servicii web semantice matematice care folosesc metode numerice pentru calcule, scopul nostru este obtinerea serviciului M sau cel putin a unei aproximari a acestui serviciu.

2.7.1 Algoritmul folosit pentru rezolvarea problemei

In această subsectiune vom descrie algoritmul folosit pentru rezolvarea problemei. Algoritmul primeste o descriere semantică a unui serviciu web semantic matematic şi reintoarce descrierea completă a acelui serviciu web. Daca nu există niciun serviciu web semantic matematic care să corespundă descrierii semantice initiale în biblioteca de servicii web semantice matematice, atunci se descompune descrierea semantică până când se obtine un arbore în care fiecare frunza contine o descriere semantică care corespunde unui serviciu web semantic matematic din biblioteca de servicii web semantice matematice sau descrierea nu poate fi descompusă mai departe.

Pentru fiecare frunză din arbore pentru care nu există un serviciu web semantic matematic în bibliotecă, incercăm să găsim o formulă de aproximare. Dacă o formula este gasită, atunci cautăm în bibliotecă de servicii web semantice matematice mai multe servicii web care, compuse corespund descrierii semantice reprezentate de partea dreapta a formulei de aproximare. Dacă, pentru o anumită frunză fără serviciu web semantic matematic asociat nu găsim nicio formulă de aproximare, atunci incercăm să găsim un serviciu web semantic matematic ce foloseste metode numerice pentru acea frunză; dacă există mai mule servicii web semantice matematice ce folosesc metode numerice, potrivite pentru descrierea semantica din acea frunză, atunci se compara, folosind un agent de comparare, complexitatile algoritmilor folositi şi se alege unul din serviciile de complexitate minima. Ultimul pas al algoritmului este acela de a construi fluxul de compunere folosind serviciile web semantice matematice asociate frunzelor arborelui de descompunere şi de a reintoarce descrierea completă pentru serviciul dorit.

2.7.2 Structura sistemului AME

Sistemul propus în aceasta secţiune se numeste AME. Structura sistemului este prezentată în Figura 2.7.


Processing

Agent

Decomposition Module

Composition Module

Searching Agent

MSWS Matching Module

Approximation Formula Matching Module

MSWS Library

Approximation Formula Library

SD

CD

Comparing Agent

Numerical Methods MSWS Matching Module

Numerical Methods MSWS Library

Figura 2.7 Structura sistemului pentru generarea unui MSWS prin descompunerea descrierii

semantice

2.7.3 Rezultate experimentale

Considerăm următoarea formulă matematică initială:

))*2exp()3,((*7 xxpowsqrt

Fluxul de compunere reintors de sistem este prezentat în Tabelul 3.2.1.

mult1(7,sqrt1(plus1(pow1(x,3),exp1(mult1(2,x)))))

Tabelul 2.9 Fluxul de compunere

Bibliografie Berardi, D., Calvanese D., Giacomo G. D., Lenzerini M. and Mecella M. (2003). Automatic

composition of e-services that export their behavior, in Proceedings of the 1st International Conference on Service Oriented Computing, 2003, vol. 2910, pages 43–58

Berners-Lee T., Hendler J. and Lassila O. (2001). The Semantic Web, Scientific American, May 2001

BPEL4WS (2003). Business Process Execution Language for Web Services 1.1, see http://www.ibm.com/developerworks/library/specification/ws-bpel/, last accessed March 2011

http://www.ibm.com/developerworks/library/specification/ws-bpel/


BravoAirServiceB (2004). Bravo Air Service Example, OWL-S 1.1 Beta Release, see http://www.daml.org/services/owl-s/1.1B/BravoAirService.owl, last accessed March 2011

Bryson J. J., Martin D., McIlraith S. A. Stein L. A. (2002). Semantic Web Services as Behavior-Oriented Agents, 2002, see http://www.cs.bath.ac.uk/~jjb/ftp/ieee-daml.pdf, last accessed August 2010

Cardoso J. (2006). Approaches to Developing Semantic Web Services, International Journal of Computer Science, vol. 1, no. 1, 2006, pp. 8-21

Carman M., Serafini L. and Traverso P. (2003). Web Service Composition as Planning, in Proceedings of ICAPS’03 Workshop on Planning for Web Services, Trento, Italy, June 2003

Charif Y. and Sabouret N. (2006). An Overview of Semantic Web Services Composition Approaches, in Electronic Notes in Theoretical Computer Science (ENTCS), vol. 146, iss. 1, 2006, pages 33-41

Dewar M., Smirnova E. and Watt S. M. (2005). XML in Mathematical Web Services, in Proc. XML 2005 Conference -- Syntax to Semantics, (XML 2005), November 14-18 2005, Atlanta USA. See http://www.csd.uwo.ca/~watt/pub/reprints/2005-xml-mathwebservices.pdf

Ermolayev V., Keberle N., Kononenko O., Plaksin S. and Terziyan V. (2004). Towards a framework for agent-enabled semantic web service composition, in International Journal of Web Services Research, 1(3), 2004, pages 63-87

Fensel D., Bussler C., Ding Y., Kartseva V., Klein M., Korotkiy M., Omelayenko B. and Siebes R. (2002). Semantic Web Application Areas, in Proceedings of the 7th International Workshop on Applications of Natural Language to Information Systems, Stockholm - Sweden, June 27-28, 2002

Gómez-Pérez A., González-Cabero R. and Lama M. (2004). A Framework for Design and Composition of Semantic Web Services, in Proceedings of the First International Semantic Web Services Symposium, AAAI 2004, Spring Symposium Series, 22-24 March 2004, California, USA

Hendler J. (2001). Agents and the Semantic Web, IEEE Intelligent Systems, March/April 2001, pp. 30-37

Hoffmann J., Bertoli P. and Pistore M. (2007). Web Service Composition as Planning, Revisited: In Between Background Theories and Initial State Uncertainty, in Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), 22-26 July 2007, Vancouver, British Columbia, Canada, vol. 2, pages 1013-1018

Kapitsaki G., Kateros D. A., Foukarakis I. E., Prezerakos G. N., Kaklamani D. I. and Venieris I. S. (2007). Service Composition: State of the art and future challenges, in Mobile and Wireless Communications Summit, 16th IST, 1-5 July 2007, Budapest, Hungary, pages 1-5

Klusch M. Gerber A. and Schmidt M. (2005a). Semantic Web Service Composition Planning with OWLS-Xplan, in Proceedings 1stIntl. AAAI Fall Symposium on Agents and the Semantic Web, 2005, Arlington VA, USA

Klusch, M., Fries B., Khalid M. and Sycara K. (2005b). Owls-mx: Hybrid owl-s service matchmaking, in AAAI Fall Symposium Series, 2005

Kumar S. and Mishra R. B. (2008). Multi-Agent Based Semantic Web Service Composition Models, in Journal of Computer Science, Infocomp, vol. 7, iss. 3, pages 42-51

Lécué F. and Léger A. (2006). A formal model for semantic Web service composition, in Proceedings of the 5th International Semantic Web Conference (ISWC 2006), November 2006, Athens, GA, USA, pages 385-398

Lin N., Kuter U. and Sirin E. (2008). Web Service Composition with User Preferences, in Proceedings of the 5th European Semantic Web Conference (ESWC 2008), Tenerife, Canary Islands, Spain, 1-5 June 2008, pages 629-643

Liu Z., Ranganathan A. and Riabov A. (2007). A Planning Approach for Message-Oriented Semantic Web Service Composition, in Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), 22-26 July 2007, Vancouver, British Columbia, Canada, vol. 2, pages 1389-1394

http://www.daml.org/services/owl-s/1.1B/BravoAirService.owl

http://www.cs.bath.ac.uk/%7Ejjb/ftp/ieee-daml.pdf


MathML (2003). See http://www.w3.org/TR/MathML/, last accessed March-June 2010

Mathematical Web Services (2003). See http://www.w3.org/Math/Documents/Notes/services.xml, last accessed March 2010

McIlraith S. and Son T. C. (2002). Adapting Golog for Composition of Semantic Web Services, in Proceedings of the 8th International Conference on Knowledge Representation and Reasoning (KR 2002), 22-25 April 2002, Toulouse, France, pages 482-493

Meditskos G. and Bassiliades N. (2007). A Semantic Web Service Discovery and Composition Prototype Framework Using Production Rules, in Proceedings of OWL-S: Experiences and Directions Workshop in conjunction with the 4th European Semantic Web Conference (ESWC 2007), 3-7 June 2007, Innsbruck, Austria

Mogos Andrei-Horia (2007). g(n) - Comparable Complexity Functions, Proceedings of CSCS 16, the 16th International Conference on Control Systems and Computer Science, 22-25 May 2007, Bucharest, Romania, vol. 2, pages 246-251

Mogos Andrei-Horia and Florea Adina Magda (2008a). Solving the Countdown Problem Using Automatic Composition of Semantic Web Services, in IEEE Proceedings of SYNASC'08, the 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, ACSys'08 Workshop on Agents for Complex Systems, 26-29 September 2008, Timisoara, Romania, pages 310-315 (ISI Proc)

Mogos Andrei-Horia and Florea Adina Magda (2008b). Approximating Mathematical Semantic Web Services Using Semantic Description Decomposition and Approximation Formulas, Economy Informatics, vol. 8, no. 1-4, 2008, ASE, Bucharest, Romania, pages 16-18 (B+ Journal)

Mogos Andrei-Horia and Florea Adina Magda (2009a). Composing Semantic Web Services for the Blocks World, Proceedings of the Ninth International Conference on Informatics in Economy, 7-8 May 2009, Bucharest, Romania, pages 741-746

Mogos Andrei-Horia and Florea Adina Magda (2009b). Comparing Two Complexity Functions Using g(n) - Comparable Complexity Functions, Proceedings of CSCS 17, the 17th International Conference on Control Systems and Computer Science, 26-29 May 2009, Bucharest, Romania, vol. 1, pages 155-160

Mogos Andrei-Horia and Andreica Mugurel Ionut (2009). Approximating Mathematical Semantic Web Services Using Approximation Formulas and Numerical Methods, Proceedings of CSCS 17, the 17th International Conference on Control Systems and Computer Science, 26-29 May 2009, Bucharest, Romania: MASTS 2009, the International Workshop on Multi-Agent Systems Technology and Semantics in conjunction with CSCS 17, vol. 2, pages 533-538

Mogos Andrei-Horia and Florea Adina Magda (2009c). A Method To Compare Two Multivariable Complexity Functions, Proceedings of the 4th International Conference on Knowledge Management: Projects, Systems and Technologies, 6-7 November 2009, Bucharest, Romania, pages 61-65

Mogos Andrei-Horia and Urzica Andreea (2009). TN4PM: A Textual Notation for Process Modelling, in Springer Studies in Computational Intelligence, Proceedings of IDC 2009, the 3rd International Symposium on Intelligent Distributed Computing, 13-14 October 2009, Ayia Napa, Cyprus, pages 263-268 (ISI Proc)

Mogos Andrei-Horia and Florea Adina Magda (2009d). Complexity Classes for Multi-Variable Complexity Functions, Annals of DAAAM for 2009 & Proceedings of the 20th International DAAAM Symposium, B.Katalinic (Editor), Published By DAAAM International, Vienna, Austria, 2009, pages 1813-1814 (ISI Proc)

Mogos Andrei-Horia and Florea Adina Magda (2009e). Comparing Two Multivariable Complexity Functions Using One-variable Complexity Classes, Informatica Economica, vol. 13, no. 4 / 2009, December 2009, pages 116-128 (B+ Journal)


Mogos Andrei-Horia and Florea Adina Magda (2010a). A Method to Compare Two Complexity Functions Using Complexity Classes, UPB Scientific Bulletin, Series A: Applied Mathematics and Physics, vol. 72, iss. 2, 2010, pages 69-84 (ISI indexed Journal)

Mogos Andrei-Horia and Florea Adina Magda (2010b). A Method for Semantic Web Service Composition Based on Pattern Matching, in Proceedings of the 5th International Conference on Knowledge Management: Projects, Systems and Technologies, 12-13 November 2010, Bucharest, Romania, pages 179-184

Narayanan, S. and McIlraith S. (2002): Simulation, verification and automated composition of web services, in Proceedings of the Eleventh International World Wide Web Conference, 2002, pages 7–10

OpenMath (2004). See http://www.openmath.org/, last accessed March-June 2010

OWL (2004). OWL Web Ontology Language, http://www.w3.org/TR/2004/REC-owl-features-20040210/, last accessed September 2010

OWL-S (2004). OWL-S: Semantic Markup for Web Services, see http://www.w3.org/Submission/OWL-S/, last accessed September 2010

OWL-S / DAML-S (2010). See http://www.ai.sri.com/daml/services/owl-s/, last accessed February 2011

OWL-S Editor (2006). See http://owlseditor.semwebcentral.org/download.shtml, last accessed March 2010

Paolucci, M., Sycara K. P. and Kawamura T. (2003). Delivering semantic web services, in Proceedings of the Twelfth International World Wide Web Conference (Alternate Paper Tracks), 2003, pages 829–837

RDF (2004). Resource Description Framework (RDF), see http://www.w3.org/RDF/, last accessed March 2011

RDF Schema (2004). RDF Schema, see http://www.w3.org/TR/rdf-schema/, last accessed March 2011

Russell S. J. and Norvig P. (1995). Artificial Intelligence: A Modern Approach, Prentice-Hall, Upper Saddle River, New Jersey, USA, 1995

Sirin E., Parsia B., Wu D., Hendler J. and Nau D. (2004a). HTN Planning for Web Service Composition Using SHOP2, in Journal of Web Semantic, vol. 1, 2004, pages 377-396

Sirin, E., Parsia B. and Hendler J. A. (2004b). Filtering and selecting semantic web services with interactive composition techniques, in IEEE Intelligent Systems 19(4), 2004, pages 42–49

SOAP (2007). SOAP 1.2, see http://www.w3.org/TR/soap12-part1/, last accessed March 2011

Sohrabi S., Prokoshyna N. and McIlraith S. A. (2009). Web Service Composition via the Customization of Golog Programs with User Preferences, in Conceptual Modeling: Foundations and Applications: Essays in Honor of John Mylopoulos, A. T. Borgida, V. K. Chaudhri, P. Giorgini and E. S. Yu (eds.), Springer-Verlag, 2009, pages 319-334

Srivastava B. and Koehler J. (2003). Web Service Composition - Current Solutions and Open Problems, in Proceedings of ICAPS 2003 Workshop on Planning for Web Services, 10 June 2003, Trento, Italy, pages 28-35

Studer, R., Grimm S. and Abecker A. (eds.) (2007). Semantic Web Services. Concepts, Technologies, and Applications, Springer, 2007

Traverso P. and Pistore M. (2004). Automated Composition of Semantic Web Services into Executable Processes, in Proceedings of Semantic Web Services Workshop at 3rd International Semantic Web Conference (ISWC 2004), 7-11 November 2004, Hiroshima, Japan, pages 380-394

UDDI (2004). UDDI 3.0.2, see http://www.oasis-open.org/committees/uddi-spec/doc/spec/v3/uddi-v3.0.2-20041019.htm, last accessed March 2011

http://www.w3.org/TR/2004/REC-owl-features-20040210/

http://www.w3.org/TR/2004/REC-owl-features-20040210/

http://www.w3.org/Submission/OWL-S/

http://www.ai.sri.com/daml/services/owl-s/

http://owlseditor.semwebcentral.org/download.shtml

http://www.w3.org/RDF/

http://www.w3.org/TR/rdf-schema/

http://www.w3.org/TR/soap12-part1/

http://www.oasis-open.org/committees/uddi-spec/doc/spec/v3/uddi-v3.0.2-20041019.htm

http://www.oasis-open.org/committees/uddi-spec/doc/spec/v3/uddi-v3.0.2-20041019.htm


Urzica Andreea, Mogos Andrei-Horia and Florea Adina Magda (2010). An Economy Model Based on Barter Exchanges between Software Agents, in Springer Studies in Computational Intelligence, Proceedings of the 4th International Symposium on Intelligent Distributed Computing – IDC 2010, MASTS 2010 Workshop, 16-18 September 2010, Tangier, Morocco, pages 295-304 (ISI Proc)

Urzica Andreea, Mogos Andrei-Horia and Florea Adina Magda (2011). A Reputation Based Negotiation Model for Barter Transactions between Software Agents, accepted paper to the International Journal on Artificial Intelligence Tools, (ISI indexed Journal, Impact Factor: 0.667 (2008))

Web Services Architecture (2004). W3C Working Group: “Web Services Architecture”, February 2004, http://www.w3.org/TR/ws-arch/

Wooldridge M. (2002). An Introduction to MultiAgent Systems, John Wiley & Sons, 2002, pages 71-75

WSDL (2001). Web Services Description Language (WSDL) 1.1, see http://www.w3.org/TR/wsdl, last accessed March 2011

WSDL2 (2007). Web Services Description Language (WSDL) 2.0, see http://www.w3.org/TR/wsdl20/, last accessed March 2011

WSDL-S (2005). Web Service Semantics - WSDL-S, see http://www.w3.org/Submission/WSDL-S/, last accessed September 2010

WSMO (2005). Web Service Modeling Ontology (WSMO), see http://www.w3.org/Submission/WSMO/, last accessed September 2010

http://www.w3.org/TR/ws-arch/

http://www.w3.org/TR/wsdl

http://www.w3.org/TR/wsdl20/

http://www.w3.org/Submission/WSDL-S/

http://www.w3.org/Submission/WSMO/


3. Proiectarea si implementarea unui server distribuit scalabil bazat pe agenti pentru

licitatia engleza 3.1 Introducere

Interesul in automatizarea comertului electronic s-a concentrat pe dezvoltarea de modii globale bazate pe agenti care permit realizarea unor tranzactii dinamice intre partenerii de afaceri. In acest context, cercetarile de comert electronic au depus efort considerabil in vederea analizei, proiectarii si implementarii unui suport bazat pe agenti pentru automatizarea activitatilor de comert electronic (Badica et al., 2007a).

In particular negocierea este o activitate necesara si importanta ce permita angajarea partenerilor de afaceri (indivizi sau organizatii) in relatii netriviale de afaceri. In mod traditional, negocierile sunt definite si studiate ca procese controlate de agenti umani ce sunt derulate pentru rezolvarea conflictelor in comunicarea in afaceri. Negocierile electronice, incluzand licitatiile, s-au raspandit odata cu dezvoltarea Internet-ului si Web-ului. In acest context, s-a evidentiat un interes semnificativ in domeniul tehnologiei informatiei si comunicatiilor pentru analiza, proiectarea si implementarea negocierilor automate in mediile bazate pe agenti.

Licitatiile sunt mecanisme de negociere pentru alocarea unor resurse (de obicei discrete) agentilor interesati dintr-o multime de agenti. O licitatie furnizeaza un protocol ce (i) permite fiecarui agent participant sa-si manifeste interesul pentru una sau mai multe resurse si (ii) determina pe baza acestor indicatii atat alocarea resurselor agentilor cat si platile ce trebuie realizate de agenti. O licitatie este o negociere unu-multi in care sunt implicate rolurile: (i) initiatorul licitatiei ce este responsabil cu crearea si initializarea licitatiei, putand avea si functia de coordonare a participantilor la negociere; (ii) participant ce reprezinta agentii participanti care depun oferte in cadrul licitatiei. Exista numeroase tipuri de licitatii incluzand: licitatii cu produs unic, licitatii cu unitati multiple, licitatii inverse, licitatii combinatoriale si licitatii duble. Licitatiile au diverse aplicatii practice in implementarea tranzactiile economice (Ockenfels et al., 2006):

- Licitatii pentru spectrul de telecomuncatie. Sunt utilizate de guverne pentru a vinde drepturile de a transmite semnale electromagnetice intr-o anumita gama de frecvente.

- Licitatii pentru electricitate. Sunt acele licitatii in care furnizorii si consumatorii majori de energie oferteaza contracte de energie electrica.

- Licitatii pentru drepturile de poluare a mediului. Sunt licitatii prin care guvernele vand dreptul de poluare a mediului prin emisii de poluant. Cantitatea de permise disponibile este limitata, asa ca firmele care au nevoie de permise mai multe trebuie sa le achizitioneze de la firmele care au nevoie de permise mai putine folosind licitatii.

- Licitatii pentru companiile aeriene prin care acestea oferteaza pentru a cumpara dreptul de folosire a spatiului si a perioadei de aterizare, respectiv decolare in aeroporturi.


- Licitatii pentru drepturile de exploatare a solului, subsolului sau apelor terioriale, de exemplu pentru obtinerea de drepturi de foraj minier sau petrolier.

- Licitatii pentru cumpararea unor diverse tipuri de produse sau marfuri: produse second-hand, produse rare, bijuterii, produse perisabile (de exemplu: flori, peste, etc.), materii prime, etc.

Licitatiile sunt cu siguranta exemplul cel mai popular de negocieri ale pretului de vanzare

in sectorul de comert electronic Customer-to-Customer, cu eBay.com reprezentand probabil una dintre cele mai cunoscute aplicatii de comert electronic din mediul online. Licitatiile s-au raspandit si in sectorul Business-to-Business (B2B) (de exemplu Dovebid.com or Liquidation.com). Licitatiile sunt de asemenea folosite de comerciantii cu amanuntul pentru lichidarea stocurilor in exces (de exemplu CompUSA.com) la sfarsit de sezon.

Odata cu raspandirea licitatiilor electronice in mediul Web a crescut si numarul furnizorilor de licitatii electronice. In acest fel, poate fi foarte dificil pentru comparatorii sau vanzatorii umani de a gasi cea mai potrivita licitatie care sa corespunda cerintelor lor. De obicei, aceasta activitate necesita folosirea unui navigator de Web si a unui motor de cautare de uz general pentru a gasi produsul dorit sau licitatia potrivita in functie de o multime data de cerinte, incluzand diverse caracteristici ale produsului si/sau licitatiei respective (tipul licitatiei, data de inceput / terminare, optiunile disponibile). De exemplu, disponibilitatea optiunii Buy it now pentru o licitatie enegleza permite cumparatorului sa castige imediat si sa cumpere produsul fara a mai parcurge procedura standard de licitatie.

Un progres important fata de aceasta abordare manuala o reprezinta o clasa particulara de aplicatii Web numite directoare de licitatii. Un director de licitatii este o aplicatie Web care furnizeaza o lista actualizata a celor mai populare aplicatii Web pentru licitatii. Cateva exemple sunt: auction-lynx.com or reallyfirst.com. Licitatiile listate intr-un director de licitatii sunt de obicei organizate fie in ordine alfabetica, fie in functie de categoria de produse vandute sau de valoarea popularitatii lor – o facilitate cunoscuta ca top de licitatii. Aceste caracteristici permit unui utilizator uman sa navigheze mai usor intr-un director de licitatii pentru a gasi o licitatie corespunzatoare care sa corespunda nevoilor sale. In plus, directoarele de licitatii mai avansate (de exemplu internetauctionlist.com) furnizeaza o facilitate de cautare a licitatiilor, luand in calcul diverse caracteristici cum ar fi numele licitatiei (sau a unui cuvant cheie prezent in numele licitatiei), categoria produsului licitat, locatia (tara, regiunea si/sau orasul), data de inceput a licitatiei, etc. Directoarele mai avansate de licitatii permit interogarea si monitorizarea in timp real a licitatiilor active (de exemplu auctionlotwatch.co.uk).

O facilitate avansata care este mai potrivita pentru automatizare folosind agenti software o reprezinta meta-licitatiile (Bornhövd et al., 2000; Cilia and Buchmann, 2002). O meta-licitatie propune integrarea mai multor aplicatii pentru licitatii electronice prin intermediul unei scheme globale. Aceasta facilitate permite potentialilor cumparatori pentru automatizarea cautarii intr-o multime de aplicatii pentru licitatii in functie de produsele de interes. Totusi, meta-licitatiile sufera de problema cunoscuta a integrarii schemei si protocolului de acces, astfel ca ele necesita atat un efort suplimentar de dezvoltare, cat si o complexitate ridicata asociata middleware-ului necesar pentru integrare.

Recent, efortul de cercetare s-a concentrat pentru dezvoltarea of de aplicatii specializate pentru licitatii folosind tehnologii Web pentru furnizarea de solutii generice, mai flexibile si cu un grad ridicat de reutilizabilitate avand un potential ridicat pentru sectorul Business-to-Business (Blake, 2001). In acest context, orientarea pe agenti si servicii a propus o abordare


noua care preia idea de serviciu de licitatii din lumea Web-ului destinata consumatorilor umani si o adapteaza lumii agentilor software. Aceasta solutie furnizeaza un nivel imbunatatit de flexibilitate si reutilizabilitate in dezvoltarea de negocieri automate generice (Benyoucef and Rinderle, 2006; Dobriceanu et al., 2009; Resinas et al., 2006) cu un grad ridicat de autonomie.

Privind abordarea orientate pe servicii, s-au realizat progrese recente in domeniul negocierii acordurilor la nivel de servicii. Totusi, dezvoltarea unor sisteme software avansate care sa fie capabile a se angaja in mod dinamic in licitatii automate in medii deschise cum sunt Internet-ul sau Web-ul este inca intr-o faza incipienta (Resinas et al., 2006).

Activitatea noastra recenta in acest domeniu a urmarit sa imbunatateasca aceasta stare de lucruri prin focalizarea pe analiza, proiectarea si implementarea unei infrastructuri deschise si flexibile pentru negocieri automate bazate pe servicii in sistemele de agenti. Aceasta solutie inovativa combina cele mai bune caracteristici ale:

- Cadrului software generic pentru negociere automata prezentat in (Bartolini et al., 2005; Badica et al., 2007b)

- Arhitecturii de piata electronica pentru licitatii propusa de (Rolli et al., 2005) - Reprezentarii declarative bazate pe reguli a mecansimelor de licitatie prezentata in

(Badica et al., 2007c)

Principalul avantaj al abordarii noastre este conceptualizarea unei licitatii ca serviciu separat, in loc de a fi incorporata in intregime in infrastructura unui e-magazin ca in (Badica et al., 2007a). Serviciul poate fi, spre exemplu, inchiriat si configurat de catre un magazin care doreste sa-si vanda produsele printr-o licitatie in vederea lichidarii stocurilor la inchiderea unui sezon.

Aceasta abordare poate fi aplicata la alte scenarii de comert electronic, nu doar pentru situatia in care un magazin isi vinde produsele catre clientii sai, cum este spre exemplu modelul propus de (Badica et al., 2007a). In particular, aceasta abordare este aplicabila si la comertul electronic Business-to-Business (Blake, 2001). Spre exemplu, sa consideram un scenariu de achizitii care trebuie derulat conform legislatiei din Romania pentru alocarea contractelor de achizitii publice, conform Deciziei Guvernamentale no.925/2006. Acest proces este controlat de o procedura complexa ce, intr-o anumita etapa, apeleaza la o licitatie inverse inchisa. In acest scenariu, institutia publica contractoare poate folosi un serviciu de licitatii configurat pentru o licitatie inverse inchisa in vederea realizarii acestei sarcini. Acest lucru chiar se intampla in realitate cand contractorul apeleaza la serviciul Web e-licitatie.ro, dar procesul este derulat manual. O imbunatatire semnificativa ar fi automatizarea acestui proces prin intermediul agentilor software, folosind abordarea noastra.

Avantajele solutiei noastre pot fi rezumate astfel: - Orientare pe serviciu – abordarea furnizeaza o solutie ce permite integrarea usoara a

licitatiilor bazate pe agenti in procesele de business orientate pe servicii - Deschidere – comunicarea cu serviciul de licitatii se bazeaza pe un protocol generic ce

este independent de mecanismul de licitatie - Flexibilitate – mecanismul de licitatie poate fi configurat folosind o multime de reguli

declarative; mai mult, regulile pot fi publicate astfel incat, cel putin in principiu, agentii participanti pot invata mecansimul de licitatie la momentul executiei si isi pot configura si ajusta in mod corespunzator strategiile de negociere

- Generalitate – aceasta abordare poate fi aplicata si altor mecanisme de negociere, nu doar licitatiei engleze.


Primele rezultate au fost raportate in lucrarea (Dobriceanu et al., 2009). In continuare, am

fost preocupati de imbunatatirea raspunsului serverului prin folosirea unei organizatii ierarhice de agenti care poate fi distribuita pe o retea locala de calculatoare. Baza solutiei a constat in rezultatele initiale din (Dobriceanu et al., 2009) unde am introdus proiectarea si implementarea unei infratsructuri deschise si flexibile pentru negocierei automate orientate pe serviciu folosind sisteme multi-agent. Noua abordare urmeaza idea introdusa in (Hillston and Kloul, 2001) pentru imbunatatirea performantei sistemelor de licitatii online utilizand noduri de calcul speciale disponibile in retele active. Aceste noduri sunt implementate ca agenti proxy in cadrul serverului nostru.

Ne-am orientat catre licitatia engleza, una dintre cele mai raspandite forme de licitatie folosita in mediul online. In acest caz, coordonatorul licitatiei anunta un pret initial pentru produsul licitat (presupunand ca ne aflam in cadrul unei aplicatii de comert electronic) si participantii la licitatie oferteaza preturi crescatoare de cumparare pe durata unei perioade predefinite de timp, cu un increment minim de pret stabilit de coordonator. Agentul cu cea mai mare oferta la finalul perioadei de licitare este declarat catsigator al licitatiei engleze si el devine cumparatorul produsului la pretul cu care a castigat licitatia.

Licitatia fiind modelata cu ajutorul unui sistem multi-agent, interactiunile dintre agenti sunt realizate prin schimburi de mesaje ce permit transmiterea ofertelor si informarea participantilor privind actualizarea pretului. In cadrul abordarii noastre initiale (Dobriceanu et al., 2009), agentul central responsabil cu managementul licitatiei era responsabil cu coordonarea comunicatiei cu si intre participantii la licitatie. Astfel ca, daca un numar mare de participanti se inscriu la o licitatie, acest agent ar deveni foarte solicitat. In al doilea rand, cu toate ca abordarea prezentata in (Dobriceanu et al., 2009) a fost descrisa ca distribuita, acest lucru insemnand de fapt ca agentii pot fi localizati in mod arbitrar pe calculatoare interconectate in retea, arhitectura avea totusi o tenta de centralizare deoarece agentul central reprezenta un punct de strangulare a procesarii mesajelor, impiedicand astfel scalabilitatea.

In acest raport prezentam o solutie ce urmareste sa imbunatateasca architectura serverului de licitatii bazat pe agenti prin relaxarea solicitarii agentului central cauzata de incarcarea sa excesiva cu mesaje (Sandu et al., 2011). Bazandu-ne pe idea propusa initial de (Hillston and Kloul, 2001) pentru imbunatatirea performantei sistemelor de licitatii online utilizand noduri de calcul speciale disponibile in retele active, am imbunatatit sistemul initial prin introducerea unui nou tip de agenti numiti agenti proxy. Fiecare agent proxy este responsabil cu gestionarea unei parti a comunicatiei agentului centrul cu participantii la licitatie.

Astfel ca, in timp ce in abordarea noastra initiala coordonatorul unei licitatii receptiona toate ofertele de la participanti, in noua abordare participantii sunt divizati in grupe disjuncte, si fiecare grup este gestionat de un singur agent proxy. Participantii comunica intens cu agentii proxy asignati, in timp ce agentii proxy transfera catre agentul coordonator al licitatiei numai ofertele relevante, in timp ce celelalte oferte sunt filtrate si procesate local, reducandu-se astfel cantitatea de mesaje care trebuie tratate de coordonatorul licitatiei.

Totodata, se observa ca interactiunea dintre doi agenti decurge mai rapid daca ei sunt localizati pe aceeasi masinadecat in cazul cand agentii sunt localizati pe masini separate. Pornind de la aceasta observatie, atunci cand serverul de licitatii trebuie distribuit pe mai multe calculatoare, anumiti agenti vor trebui sa schimbe mesaje in retea, astfel rezultand cresterea timpului de comunicatie, fapt ce va conduce la cresterea timpului de raspuns al


serverului. Astfel ca, in cazul solutiei propuse am urmarit si imbunatatirea timpului de comunicatie intre agenti, atunci cand serverul este distribuit pe mai multe calculatoare, prin pastrarea, ori de cate ori acest lucru este posibil, a agentilor proxy pe aceeasi masina cu agentii participanti. 3.2 Tipuri de agenti Prin negociere automata intelegem un proces prin care un grup de agenti software comunica in vederea obtinerii unei intelegeri acceptabila de toti asupra unui anumit subiect (Lomuscio et al., 2002). Licitatiile reprezinta o forma particulara de negociere in care alocarea resurselor si platile se determina prin oferte schimbate de participanti conform unui set prestabilit de reguli (McAfee and McMillan, 1987). In negocierea automata (incluzand licitatiile), este important sa distingem intre protocolul de negociere (numit si mecansim) si strategia de negociere. Protocolul cuprinde ‘regulile publice de intalnire encounter’ ce trebuie respectate de participantii la negociere prin specificarea cerintelor ce permit acestora sa interactioneze si sa negocieze. Strategia defineste comportamentul privat al fiecarui participant, prin care acesta urmareste sa-si maximizeze sansele de obtinere a rezultatului dorit in urma negocierii. Acest comportament trebuie sa fie consistent cu regulile protocolului de negociere si este ales astfel incat sa imbunatateasca functia de maximizare a bunastarii participantului (Wooldridge, 2002). Principala inovatie a solutiei noastre este propunerea uneui concept nou de serviciu generic de negociere bazat pe agenti. Urmand propunerea lui (Rolli et al., 2005), consideram ca un mediu de comert electronic trebuie sa fie capabil sa furnizeze unul sau mai multe tipuri de Servicii de Licitatie (SL). Fiecare astfel de serviciu permite realizarea unui anumit tip de licitatie. Partenerii de afaceri, de obicei reprezentati prin agenti cumparatori si/sau vanzatori ce ‘traiesc’ in acest mediu sunt capabili sa descopere dinamic un SL corespunzator ce se identifica cu cerintele lor particulare si sa-l foloseasca in scopul atingerii propriilor obiective de vanzare si/sau cumparare prin tranzactii de comert electronic.

Figura 3.1. Servicii de licitatie Un SL (vezi Figura 3.11) implementeaza un tip specific de licitatie si are doua functii importante:

- managementul licitatiilor active, incluzand activitati cum sunt crearea si terminarea unei licitatii


- coordonarea participantilor la o licitatie, incluzand activitati ca trimiterea unei oferte sau contra-oferte, determinarea unei intelegeri, informarea participantilor si castigatorilor.

In mod normal, un mediu de comert electronic poate dispune de un registru de servicii de licitatie (Auction Service Directory), iar un serviciu de licitatie este realizat prin intermediul unui server ce implementeaza un anumit tip de licitatie, de exemplu licitatie engleza, licitatie olandeza, licitatie Vickrey, licitatie combinatoriala, etc. Un SL include o multime de agenti ce colaboreaza pentru a sprijini SL sa-si realizeze functiile. Agentii de baza dintr-un SL sunt urmatorii:

- GSL (Auction Service Host numit si Auction Service) ce reprezinta agentul gazda al serverului pentru servicii de licitatie. El reprezinta punctul de intrare in SL, adica locul unde un agent participant se conecteaza initial pentru a beneficia de o anumita licitatie (nou sau existent).

- GL (Auction Host numit si Auction Manager) ce reprezinta agentul ce gazduieste o anumita licitatie. Un SL poate gestiona la un moment dat mai multe licitatii active, numite si instante.

- RL (Auction Directory) ce reprezinta registrul licitatiilor active. - P (Auction Participant) ce reprezinta un agent participant la o licitatie gazduita de SL. - IP (Auction Initiator Participant) ce reprezinta un agent capabil de a initia o noua

licitatie. Spre exemplu, in cazul unei licitatii englez, IP are rolul de vanzator. In cadrul abordarii noastre am conceptualizat o licitatie activa folosind modelul initial introdus in literatura de (Bartolini et al., 2005) si dezvoltat ulterior de (Badica et al., 2007b). Conform acestui model, fiecare licitatie activa gazduita de un SL este gestionata de un agent special GL. Fiecare licitatie activa din SL este reprezentat printr-o intrare in registrul RL. In mod normal o astfel de intrare va contine o referinta la GL corespunzator si o descriere corespunzatoare a licitatieii respective, ce poate include atribute ca produsul scos la licitatie, cotatia curenta, data de inchidere, initiatorul licitatiei, etc. In general aceste atribute depind de tipul de licitatie corespunzator SL.

Figura 3.2. Tipuri de agenti ai serverului si interactiunile dintre ei


Pe langa acesti agenti de baza, un astfel de server pentru servicii de licitatie va trebui sa includa si alti agenti, cu rolurile urmatoare:

- agenti pentru gestionarea resurselor serverului si eficientizarea procesarii ofertelor - agenti pentru interfatarea serverului cu lumea exterioara

In vederea imbunatatirii performantei, un server de licitatii poate rula pe o multime de calculatoare interconectate intr-o retea locala. Agentii pentru gestionarea resurselor de calcul si eficientizare a procesarii ofertelor includ:

- Proxy, un agent care trateaza ofertele transmise de o multime de participanti. Rolul sau este de a degreva agentul GL de tratarea unui numar prea mare de mesaje.

- MC (Computer Manager), un agent responsabil cu gestionarea agentilor participant P si Proxy ce au fost creati pe unul dintre calculatoarele pe care ruleaza serverul.

- RM (Resource Manager), un agent responsabil cu gestiunea tuturor agentilor MC din cadrul serverului.

Pentru interfatarea serverului cu lumea exterioara, fiecare utilizator este reprezentat in sistem prin intermediul unui agent personal PA (Personal Agent). Tipurile de agenti din cadrul serverului impreuna cu interactiunile dintre ei sunt ilustrate in Figura 3.2. 3.3 Interactiuni intre agenti

Interactiunea cu serverul pentru servicii de licitatie se realizeaza printr-o multime de protocoale de interactiune. Un utilizator poate interactiona cu serverul prin intermediul agentului sau personal PA. PA va utiliza protocoalele de interactiune pentru:

- Crearea si initierea unei noi licitatii - Cautarea unei licitatii existente - Inscrierea la o licitatie existenta - Participarea prin depunere de oferte la o licitatie existenta.

Figura 3.3. Crearea si initierea unei licitatii


Protocoalele de interactiune permit totodata instiintarea participantilor privind acceptarea sau rejectarea unei oferte, modificarea starii licitatiei (de exemplu in urma acceptarii unei noi oferte), anuntul castigatorului si terminarea licitatiei. Protocolul de interactiune pentru crearea si initierea unei licitatii este ilustrat in Figura 3.

GSL reprezinta agentul care gestioneaza toate licitatiile active de pe server. In mod normal el implementeaza un tip specific de licitatie – licitatia engleza spre exemplu, dar poate fi in principiu reconfigurat pentru a implementa orice alt tip arbitrar de licitatie. El primeste o cerere de la un PA pentru crearea unei noi licitatii. Efectul este crearea unui nou agent GL care va gestiona noua licitatie, cat si a unui agent participant initiator IP. Aceasta licitatie este inscrisa in registrul licitatiilor active RL. Partcipantul nou creat va fi inscris de catre GSL la PA, ce are astfel rolul de a dirija toate participarile uitlizatorului la licitatii, prin intermediul a cate unui participant separat pentru fiecare licitatie in parte. Protocoalele de interactiune prin care un PA poate cauta o licitatie si se poate inscrie ca participant la o licitatie sunt ilustrate in Figura 3.4.

Figura 3.4. Cautarea unei licitatii si inscrierea la o licitatie

Protocolul de interactiune pentru participarea la o licitatie si trimiterea de oferte este prezentat in Figura 3.5.


Figura 3.5. Participarea la licitatie si trimiterea de oferte

3.4 Gestiunea resurselor

Interactiunea dintre utilizator si server are loc prin intermediul agentilor PA, P si Proxy. Pentru fiecare licitatie la care este inscris utilizatorul la un moment dat exista cate un singur agent participant P conectat la PA. Fiecare agent P reprezinta participarea unui utilizator la o licitatie activa, gestionata prin intermediul unui agent GL. Cu toate acestea, pentru folosirea eficienta a resurselor si evitarea strangularii agentului GL cu prea multe mesaje in momentele de licitatie intensa, intre agentii P si GL se interpune un nivel intermediar de agenti Proxy. Fiecare agent Proxy raspunde de o multime de agenti P, iar fiecare agent P este conectat la un singur agent Proxy. In acest fel participantii nu interactioneaza in mod direct cu agentul GL, ci prin intermediul agentilor Proxy.

Controlul crearii si terminarii agentilor Proxy este realizat de agentul GL. In momentul in care un nou utilizator se inscrie la o licitatie, pe langa crearea agentului P (conform Figurii 4), GL decide sa conecteze agentul P la un Proxy existent sau la un nou Proxy. Ofertele transmise de un agent P ajung intai la agentul Proxy corespunzator, care poate decide sa rejecteze imediat oferta pe baza informatiei sale locale, sau sa o inainteze agentului GL. Similar, in momentul in care GL accepta o noua oferta cu un pret mai bun decat pretul curent (presupunem ca ne aflam intr-o licitatie engleza), el anunta imediat agentii Proxy, care la randul lor inainteaza anuntul agentilor P, fiecare dintre acestia informand utilizatorii prin intermediul agentilor PA.


Agentul GL este responsabil cu decizia de creare a agentilor Proxy si participant. Cu toate acestea, crearea propriuzisa este realizata de combinatia dintre agentul manager de resurse MR si un agent manager de calculator MC. Astfel, GL cere agentului RM crearea unui agent P si eventual a unui nou Proxy (sau refolosirea unui existent). La randul sau RM gestioneaza disponibilitatea si incarcarea curenta a tututor calculatoarelor din retea disponibile serverului, si decide carui agent MC sa i se adreseze pentru crearea participantului. Exista cate un agent MC responsabil cu fiecare calculator din reteaua serverului.

Sa presupunem ca in medie un agent Proxy gestioneaza k agenti participanti P si ca numarul total de agenti Proxy este p. Acest lucru inseamna ca numarul total de participanti este n = p k. Conform modelului pentru coordonarea participantilor intr-o licitatie engleza (Bartolini et al., 2005; Badica et al., 2007b), ori de cate ori GL accepta a noua oferta transmisa de catre unul din participanti, toti ceilalti participanti trebuie instiintati in mod corespunzator (conform unui model push), iar acest proces va necesita in mod evident un timp O(n). Totusi, cu noua abordare bazata pe organoizatia ierarhica a agentilor participanti si Proxy, timpul va fi redus la O(max(p,k)). Aceasta valoare poate fi optimizata la O(n1/2) pentru n agenti participanti daca vom introduce urmatoarea constrangere de echilibrare a ierarhiei de agenti Proxy si participanti, si anume ca numarul de participanti gestionati de fiecare agent Proxy sa nu depaseasca niciodata numarul total de agenti Proxy conectati la agentul coordonator GL.

Controlul crearii de noi agenti Proxy va fi realizat de agentul GL. Astfel, daca in urma crearii unui nou participant avem n2 > p unde n este numarul total de participanti (incluzandu-l si pe cel nou creat) si p este numarul de agenti Proxy atunci se va crea un agent Proxy nou, altfel participantul se va conecta la un agent Proxy existent. Schimbul de mesaje necesar pentru crearea unui nou agent Proxy este ilustrat in Figura 3.6.

Figura 3.6. Crearea unui nou agent Proxy

In momentul in care un agent participant paraseste o licitatie, daca (n-1)2 p atunci se

va sterge agentul Proxy avand cel mai mic numar de agenti participanti conectati, restul acestor agenti fiind distribuiti in mod echitabil la ceilalti agenti Proxy.

Avand in vedere interactiunea intensa intre agentul Proxy si agentii participant conectati la el, alocarea se face astfel incat toti participantii sa fie creati pe acelasi calculator cu agentul Proxy la care ei sunt conectati. 3.5 Interfata utilizator

Am dezvoltat o interfata grafica utilizator bazata pe Web prin intermediul careia un utilizator poate crea licitatii, se poate inscrie la o licitatie existenta, respectiv poate sa liciteze. In acest scop serverul de licitatii bazat pe agenti a fost interfatat pe partea de server cu o aplicatie Web bazata pe tehnologia miniserverilor, aceasta aplicatie reprezentand liantul dintre interfata grafica pentru utilizatorii Web si agentul personal PA al fiecarui utilizator.


Arhitectura intregului ansamblu format din interfata grafica utilizator bazata pe Web, miniserveri, agentii personali si serverul distribuit de licitatii este prezentata in Figura 7.

Personal Agents AgentServlet

Log-in

MyAuctions

AddAuction

MyProducts

Register

UserInfo

BD

ChangePass

Disconect

Search

Distributed auction

server

Figura 3.7. Interfatarea serverului de licitatii cu o aplicatie Web

Functionalitatea interfetei grafice este realizata prin intermediul unei multimi de miniserveri prezentati in Figura 3.7. Dintre acestia, miniserverul AgentServlet este responsabil cu realizarea legaturii cu partea de agenti. Miniserverul AgentServlet se interfateaza cu ceilalti minserveri folosind tehnologia AJAX (Mahemoff, 2006). Totodata miniserverul AgentServlet este responsabil cu crearea si interfatarea cu agentii personali PA. Astfel ca legatura dintre aplicatia Web si serverul distribuit bazat pe agenti este practic realizata de ansamblul format din miniserverul AgentServlet si agentii personali PA.

Procesul generic de interactiune dintre un utilizator si serverul distribuit de licitatii prin intermediul interfetei grafice bazata pe Web decurge astfel:

- Utilizatorul acceseaza minserverul corespunzator actiunii sale curente (de exemplu miniserverul Login daca doreste sa se autentifice, miniserverul CreateAuction daca utilizatorul are rol de vanzator si doreste sa creeze o licitatie, miniserverul MyProducts pentru examinarea licitatiilor pe care le deruleaza in mod curent in calitate de vanzator, respectiv miniserverul MyAuctions pentru examinarea licitatiilor pe care le deruleaza in calitate de cumparator, etc.).

- Fiecare dintre miniserverii corespunzatori actiunilor utilizatorului are capabilitatea de a transmite o comanda minserverului AgentServlet, care este repsonsabil cu interfatarea cu partea bazata pe agenti.

- Miniserverul AgentServlet poate crea si comunica cu un nou agent personal PA, respectiv el poate comunica cu un agent personal PA existent prin schimb de obiecte Java, de la miniserver catre agentul personal si invers, de la agentul personal catre miniserver.

Pentru exemplificare, se prezinta in Figura 8 interactiunile dintre miniserveri si agentul personal al unui utilizator pentru o activitate de licitare si de vizualizare a starii curente a licitatiilor curente la care acesta este inscris.


Figura 3.8. Activitatile de licitare si de vizualizare a starii licitatiilor

Astfel, prin intermediul miniserverului MyAuctions, un utilizator U poate vizualiza

starea tuturor licitatiilor la care este inscris si poate licita in oricare dintre acestea, cu conditia ca acea licitatie sa fie activa. O oferta licitata de utilizatorul U va fi transmisa de catre miniserverul MyAuctions catre miniserverul AgentServlet, acesta o va transmite la randul sau agentului personal PA, si in final PA o va licita in numele utilizatorului U (interactiunile 1 si 1.1 in Figura 3.8). In situatia in care PA este informat de catre serverul de licitatii ca cea mai buna oferta curenta pentru una dintre licitatiile active la care este inscris U a fost actualizata, el va transmite aceasta informatie miniserverului AgentServlet (interactiunea 2 in Figura 3.8). Pentru a putea fi afisata, miniserverul MyAuctions va interoga in mod regulat (la intervale de timp de cateva secunde) miniserverul AgentServlet privind eventualele actualizari ale celor mai bune oferte de interes pentru U (interactiunile 3 si 4 in Figura 3.8). 3.6 Rezultate experimentale

Am dezvoltat o implementare prototip a acestei arhitecturi folosind platforma JADE (Bellifemine et al., 2007) urmarind sa realizam evaluarea experimentala si compararea sa cu arhitectura initiala propusa in (Dobriceanu et al., 2009), care nu a folosit agentii Proxy si structura ierarhica de agenti. Experimentele au fost realizate pe o retea Myrinet la 2Gb/s formata din 3 calculatoare cu procesoare dual core la 2.5 GHz si 1GB de memorie RAM.

In cadrul acestui experiment participantii au fost configurati sa liciteze in mod automat, asa ca au fost echipati cu o strategie simpla de licitare ce sa le indice daca, cand si cat sa liciteze. Licitarea a urmarit un secnariu de snipping, adica imediat ce un participant receptioneaza o instiintare ca un alt participant a licitat mai mult, el liciteaza imediat o valoare mai mare cu un increment predefinit decat cea mai buna oferta curenta. In timpul derularii scenariului de snipping, serverul de licitatii este puternic incarcat cu prelucrarea ofertelor primite. Unele dintre aceste oferte vor fi rejectate imediat de agentii Proxy, altele vor ajunge sa fie procesate de catre agentul coordonator GL.

Pretul de pornire al unei licitatii a fost setat la valoarea 0. Durata unei licitatii a fost setata la 1.5 minute pentru toate experimentele. Valoarea incrementului din strategia participantilor a fost setata la 10. Agentilor li s-a permis sa liciteze pana la o valoare de rezerva foarte mare (setata la 100000). Licitatia a fost terminata la expirarea duratei de timp alocata initial. Prin setarea pretului de rezerva la o valoare foarte mare, licitatiile s-au terminat inainte ca agentii participanti sa ajunga cu licitarea pana la pretul de rezerva.


Ori de cate ori un agent participant liciteaza conform strategiei sale, el va trebui sa

primeasca un raspuns ce sa confirme acceptarea sau nu a ofertei de catre server. Acest aspect este foarte important, deoarece plasandu-ne intr-un mediu distribuit in care mai multi agenti sunt in competitie si liciteaza concurent, se poate intampla ca in ciuda faptului ca un agent alege o valoare corecta pe care sa o oferteze, el poate fi supralicitat de un alt agent care isi trimite oferta catre server aproape simultan cu el (serverul va considera prima dintre ofertele primite si va actualiza valoarea ofertei maxime in mod corespunzator, oferta primita mai tarziu fiind astfel declarata incorecta si in consecinta fiind refuzata). In cadrul experimentelor am evaluat urmatoarele masuri de performanta:

- Latenta definita ca durata medie de timp in care serverul raspunde afirmativ sau negativ la primirea unei oferte de la un participant

- Capacitatea definita ca numarul de oferte tratate pe unitatea de timp; aceasta valoare este calculata prin impartirea numarului total de oferte la care s-a transmis un raspuns la durata de timp a unei licitatii

Pentru initializarea experimentului am definit unui script ce realizeaza pornirea platformei

JADE, crearea automata a infrastructurii minimale a serverului ce include agentii GSL si RL, si apoi crearea agentilor personali PA pentru toti utilizatorii care vor participa la licitatie. Unul dintre agentii personali este cel care creaza licitatia, proces ce are ca rezultat si crearea agentului GL. Acest PA a fost configurat sa controleze inceputul procesului de licitare. In acest scop, el este anuntat de catre agentul GL cand un numar prefixat de participanti s-au inscris la licitatie.

Am considerat un sir crescator de valori ale numarului de agenti PA (fiecare reprezentand un utilizator participant la licitatie) si am calculat valorile masurilor de performanta pentru fiecare experiment realizat prin rularea serverului pe 1, 2 si respectiv 3 calculatoare. Totodata, in idea de a compara solutia cu varianta fara agenti Proxy, am realizat si un experiment fara agentii Proxy, in acest fel agentul GL fiind responsabil cu gestionarea tuturor ofertelor primite de la participanti. In cadrul acestui experiment am considerat o singura licitatie. Acest lucru inseamna ca pentru fiecare agent PA se va crea automat pe server cate un singur agent participant P. Procesul de licitare a fost oprit dupa 1.5 minute. S-a observat ca in cazul rularii serverului fara agenti Proxy, dintre cei 2000 de agenti participanti la licitatie numai 1273 de agenti au putut sa liciteze macar o data. Rezultatele experimentelor sunt prezentate in Figura 3.9 si in Figura 3.10.

Nr.agenti

Nr.Proxy

1 calc 2 calc 3 calc

500 5087.53 2172.14

148.55

104.39

1000 20038.9 8114.66

266.85

217.01

1500 39752.5 8781.39

426.50

277.88

2000 66852.3 11691.2

575.06

452.73

Figura 3.9. Latenta [ms]


Agenti y c lc lc Nr.Prox 1 Cal 2 Ca 3 Ca500 1 5 7 1 0.14 1.11 1.52 1.801000 5 9 4 4 0.06 0.94 1.71 1.741500 5 1 3 6 0.03 0.85 1.4 1.82000 5 9 2 2 0.02 0.77 1.50 1.67

Figura 3.10. Capacitatea [nr.oferte / ms] 3.7 Concluzii

In acest raport am prezentat un server distribuit bazat pe agenti pentru licitatii. Serverul dispune de o arhitectura ierarhica de agenti pentru a se imbunatati modul de gestionare a ofertelor primite de la agentii participanti. Experimentele initiale arata ca noua arhitectura propusa este scalabila, raspunsul imbunatatindu-se daca serverul este distribuit pe mai multe calculatoare. In plus raspunsul serverului este imbunatatit fata de arhitectura care nu foloseste structura ierarhica de agenti bazata pe agenti Proxy. Serverul a fost integrat intr-o aplicatie Web pentru aplicatii online folosind tehnologia miniserverilor. REFERINTE Bartolini, C., Preist, C. and Jennings, N.R., 2005: A software framework for automated negotiation, Lecture Notes in Computer Science, Springer, Vol. 3390, pp.213–235. Badica, C., Ganzha, M. and Paprzycki, M., 2007a: Developing a model agentbased e-commerce system, Studies in Computational Intelligence, Springer, Vol. 37, pp.555–578. Badica, C., Ganzha, M. and Paprzycki, M., 2007b: Implementing rule-based automated price negotiation in an agent system, Journal of Universal Computer Science, Vol. 13, No. 2, pp.244–266. Badica, C., Giurca, A. and Wagner, G., 2007c: Using rules and R2ML for modeling negotiation mechanisms in e-commerce agent systems, Lecture Notes in Computer Science, Springer, Vol. 4473, pp.84–99. Bellifemine, F. L., Caire, G., and Greenwood, D., 2007): Developing Multi-Agent Systems with JADE, John Wiley & Sons. Benyoucef, M. and Rinderle, S., 2006: Modeling e-negotiation processes for a service oriented architecture, Group Decision and Negotiation, Vol. 15, No. 3, pp.449–467. Blake, M.B., 2001: Agent-oriented approaches to b2b interoperability, Knowledge Engineering Review, Vol. 16, No. 4, pp.383–388. Bornhövd, C., Cilia, M., Liebig, C. and Buchmann, A., 2000: An infrastructure for meta-auctions, Proceedings of the Second International Workshop on Advance Issues of E-Commerce and Web-Based Information Systems (WECWIS 2000), IEEE Computer Society, pp.21. Cilia, M. and Buchmann, A.P., 2002: An active functionality service for e-business applications, SIGMOD Record, Vol. 31, No. 1, pp.24–30.


Dobriceanu, A., Biscu, L., Badica, A., Badica, C., 2009: The design and implementation of an agent-based auction service, International Journal of Agent-Oriented Software Engineering (IJAOSE) Vol.3, No.(2/3), pp.116-134, Inderscience Publishers. Hillston, J. and Kloul, L., 2001: Performance investigation of an on-line auction system, Concurrency and Computation: Practice and Experience, Vol. 13, No.1, pp.23-41, John Wiley & Sons. Lomuscio, A.R., Wooldridge, M. and Jennings, N.R., 2001: A classification scheme for negotiation in electronic commerce, Lecture Notes in Computer Science, Springer, Vol. 1991, pp.19–33. Mahemoff, M., (2006): Ajax Design Patterns. O'Reilly. McAfee, R.P. and McMillan, J., 1987: Auctions and bidding, Journal of Economic Literature, Vol. 25, No. 2, pp.699–738. Ockenfels, A., Reiley, D., and Sadrieh, A., 2006: Online Auctions. In: T. Hendershott (ed.): Economics and Information Systems, Elsevier, pp.571-628. Resinas, M., Fernandez, P. and Corchuelo, R., 2006: A conceptual framework for automated negotiation systems, Lecture Notes in Computer Science, Springer, Vol. 4224, pp.1250–1258. Rolli, D., Luckner, S., Gimpel, H. and Weinhardt, C., 2005: A descriptive auction language, Electronic Markets – The International Journal, Vol. 16, No. 1, pp.51–62. Sandu, L., Sbora, R., Ilie, S. and Badica, C.: Scalable Distributed Agent Based English Auction Server, Proceedings of the 15th International Conference on System Theory, Control and Computing, ISSN 2068-0465, ISBN 987-973-621-322-9, pp 496-501. Wooldridge, M., 2002: An Introduction to MultiAgent Systems, John Wiley & Sons. LUCRARI PUBLICATE 1. Sorin Ilie and Costin Badica: JADE-based Distributed Ant Colony Optimization on a Computer Cluster, Proceedings of 6th International Symposium on Applied Computational Intelligence and Informatics, SACI’2011, pp. 247- 252, 2011, DOI: http://dx.doi.org/10.1109/SACI.2011.5873008 2. Liviu Sandu, Raluca Sbora, Sorin Ilie and Costin Badica: Scalable Distributed Agent Based English Auction Server, Proceedings of the 15th International Conference on System Theory, Control and Computing, ISSN 2068-0465, ISBN 987-973-621-322-9, pp 496-501. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6085676&isnumber=6085648 3. George Sacerdotianu, Sorin Ilie and Costin Badica: ”Distributed AI Framework for Agent-based Games and Simulations”, 8th Workshop on Agents for Complex Systems, 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2011. 4. Alex Muscar, Costin Badica: A Functional Approach to Agent Development: Research Agenda, IEEE 35th Annual Computer Software and Applications Conference Workshops (COMPSACW), 380- 385, 2011, DOI: http://dx.doi.org/10.1109/COMPSACW.2011.70 5. Alex Muscar: Towards a Pragmatic Approach to Agent Development, Proceedings of the 6th Annual South-East European Doctoral Student Conference, SEERC, pp 320-326, 2011. 6. Costin Badica and Mihnea Scafes: Experimental Evaluation of Service Negotiation Protocols in Agent Systems, Proceedings of the 15th International Conference on System Theory, Control and

http://dx.doi.org/10.1109/SACI.2011.5873008

http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6085676&isnumber=6085648

http://dx.doi.org/10.1109/COMPSACW.2011.70


Computing, Sinaia, ISSN 2068-0465, ISBN 987-973-621-322-9, pp 63-68, 2011. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6085667&isnumber=6085648 7. Amelia Badica, Costin Badica: Formal Verification of Business Processes Represented as Role Activity Diagrams. International Workshop on Advances in Business ICT, Proceedings of the Federated Conference on Computer Science and Information Systems - FedCSIS 2011, 277-280, 2011, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6078243&isnumber=6078170 8. Alex Muscar, Costin Badica: A Functional Take on Multi-Agent Systems - Position Paper, International Conference on Numerical Analysis and Applied Mathematics, ICNAAM’2011, AIP Conference Proceedings, vol.1389, pp 865- 868, 2011, DOI: http://dx.doi.org/10.1063/1.3636870 9. Alex Muscar: Agent Oriented Programming: From Revolution to Evolution (Position Paper), In: Andrew V. Jones (Ed.): Proc. Imperial College Computing Student Workshop, ICCSW’2011, pp.52-58, Imperial College London, 2011.



http://dx.doi.org/10.1063/1.3636870


4. Sistemul multi-agent bazat pe incredere,

reputatie si norme RESPECT

4.1 Procesul de decizie în privinta încrederii si metodologia de extragere a reputatiei

Propunem o procedură complexă de decizie în privinta încrederii şi de extragere a valorii reputaţiei în cadrul sistemelor multi-agent. Analizam, de asemenea, care sunt sursele de informaţii care ar putea ajuta un agent pentru a decide dacă să se încreadă sau nu într-un alt agent în cazul unei tranzactii sau colaborări. După ce interacţiunea a avut loc, un agent este capabil să emită o opinie cu privire la desfăşurarea si rezultatele interactiunii, precum şi despre partenerul său. Prin adunarea opiniilor mai multor agenţi referitor la situaţii similare, se pot trage anumite concluzii, ce reflectă comportamentul actorilor implicati în aceste situaţii. Evaluarea rezultată din agregarea mai multor opinii este, adesea numită reputatia agentului evaluat. Reputaţia cuiva constituie o informatie utilă atunci când ne aflăm în faţa deciziei de ne încrede în el sau nu. Secţiunea de fată arată cum, prin optimizarea aceastei influenţe circulare între încredere şi reputaţie din cadrul unui sistem multiagent, putem îmbunătăţi funcţionalitatea sistemului spre beneficiul agentului. Mecanismul reputaţie descris în acest capitol extinde rezultatele obtinute în (Urzica, Neata, & A. Florea, 2011) şi (Urzica, 2010).

4.1.1. Prezentarea generală a modelului Figura 4.1 explică viziunea propusă asupra modului în care este construită încrederea şi modul în care ar trebui utilizate opiniile. Se subliniază distincţia dintre evaluarea subiectivă a gradului de încredere a unui potenţial partener de interacţiune, şi opinia emisă de către acelaşi agent referitoare la colaboratorul său după interacţiune, în cazul în care interacţiunea a avut loc.

Modulul de calcul al încrederii

Factori în evaluarea încrederii

Această secţiune enumeră şi descrie în detaliu cele mai relevante elementele pe care se bazează încrederea: o valoare de bază a încrederii specifice evaluatorului, experienţa anterioară, informaţii despre rolurile din sistem, competenţa percepută de către evaluator, contextul, informaţiile provenite din terţe surse, certificatele de încredere / certificatele de competenţă, importanţa situaţiei, riscul perceput, normele care reglementează interacţiunea, precum şi aşteptările.


Functii de agregare

În urma achizitiei de informaţii, un agent poate utiliza o funcţie de agregare pentru a combina factorii ce intră în evaluarea încrederii, în funcţie de relevanţa lor pentru a obţine o valoare a gradului de încredere. În literatura de specialitate a modelelor de încredere sunt propuse diverse formule şi metode în acest scop. Această secţiune trece în revistă funcţiile de mediere cele mai potrivite pentru proiectul nostru, şi discută apoi un exemplu pentru această strategie.

Figura 4.1 - Viziune asupra interdependenţei dintre încredere si reputaţiei

Corectituninea factorilor ce construiesc încrederea

Pentru a putea utiliza o informaţie în construirea încrederii, un agent trebuie să îi atribuie acesteia o măsură care să arate cat de mult se poate avea încredere în sursă de informaţii. Măsura de fiabilitate, la fel ca şi încrederea în sine, este o măsură dinamică. Ea evoluează în timp odată cu confirmarea sau infirmarea corectitudinii informaţiilor furnizate de-a lungul mai multor sesiuni. În timp, agenţii ar trebui să înveţe să îsi adapteze în mod dinamic importanta pe care o acordă fiecăre surse de informatii.

4.1.2 Opiniile: feedback al deciziei de a avea încredere O opinie este un tuplu ce contine identitatea agentului, un alt tuplu ce descrie situaţia în care a fost emisă opinia şi valoarea de satisfacţie atribuită de către agent rezultatului interacţii. Am ales numele de „opinie”, pentru această evaluare deoarece este o măsură subiectivă, ce depinde de evaluator, care reflectă perspectiva proprie referitoare la situaţia descrisă.

Anonimitatea în schimbul de opinii

Există două abordări în ceea ce priveşte identitatea emitentului unei opinii, ambele puternic susţinute în literatura de specialitate. Una este dezvăluirea informaţiilor despre emitentul opiniei, în timp ce altele insistă în apărarea anonimatul. Solutia pe care o propunem pentru păstrarea anonimatului constă în folosirea unei asocieri între emitentii de opinii si un set de


identificatori dintr-o schemă de adresare separată. În acest fel, agentii care prelucrează seturile de opinii pot manifesta preferinte în privinta autorilor, si le pot folosi în calculul reputatiei.

Depozite de opinii

Depozitele definite în acest model conţin date omogene, multi-dimensionale şi non-volatile. Unul din rolurile principale ale depozitelor de opinii este acela de a atenua opiniile extreme. Se presupune că un astfel de depozit poate stoca mult mai multe înregistrări decât ar putea memoria locală a unui agent. Prin stocarea datelor brute, depozitele permit agentilor să utilizeze orice functie de interograre si de agregare care le serveste mai bine intereselor lor. Astfel, agentii pot selecta doar datele care le sunt de folos si interpreta-le în mod independent de ceilalti agenti, aplicând propriile lor functii de agregare.

4.2 Extragerea Reputatiei În modelul pe care îl propunem, valoarea reputaţiei întoarsă de Modulul de Agregare a Reputaţiei reprezintă o reputatie contextuală, care exprimă opinia globală a comunităţii în ceea ce priveşte performanţele unui agent tintă într-o situaţie dată, răspunzând astfel cel mai bine la întrebările specifice ale agentului.

Sabloane situationale

O caracteristică importantă pe care dorim să o subliniem este aspectul situaţional al evaluărilor folosite în modelul propus. În general, reputaţia este calculată şi folosită drept o valoare absolută, o măsură universală, folosind un singur model de agregare, ales de designer, care este aplicat asupra tuturor datelor corespunzătoare agentului ţintă. Noi propunem o soluţie mai precisă şi mai personalizată: precisă, pentru că datele colectionate sunt legate de contextul corespunzător, şi personalizată, pentru că interogările sunt configurabile, întorcând răspunsuri cu adevărat utile.

Modulul de Agregare a Reputatiei

Agenţii din acest model sunt dotati cu module pentru extragerea informaţiilor despre reputaţie prin agregarea în mod independent a opiniilor altor membri ai comunităţii cu privire la situaţii similare celei cu care se confruntă în acest moment. Sistemul pune la dispozitia agentilor unul sau mai multe depozite de date, ce conţin date brute, omogene, multidimensionale. Modulele agentilor se conectează la orice depozit de date şi selectează datele corespunzătoare unui subset de situaţii. Subsetul de date returnat în urma interogării este apoi utilizat pentru a calcula valoarea ce reflectă cel mai bine părerea comunităţii asupra situaţiei date.

4.3 Validarea modelului printr-un studiu de caz: Piata imobiliară

Acest proiect studiază modul în care entităţile din cadrul comunităţilor virtuale sunt capabile să identifice şi să utilizeze nivelul de reputaţie al altora, aplicând un model reputaţie. Modelul de reputatie ales pentru această implementare modelul de extracţie al reputaţiei prezentat în secţiunile anterioare. Descrierea problemei este una des întâlnită: corespondenta dintre cerere si ofertă într-o piaţă liberă. Problema dată poate fi aplicată în mai multe domenii: tranzacţii comerciale, bursa locurilor de muncă, matrimoniale, etc. Cazul ales pentru a fi studiat în cadrul acestui proiect este acela al pieţei imobiliare. Mai exact, proiectul tratează piata închirierilor de locuinte.


Există două roluri care pot fi adoptate de către agenţii din cadrul sistemului multi-agent: Chirias şi Proprietar. Chiriasii sunt în căutarea unei case, iar proprietarii vor sa inchirieze casele pe care le deţin. Sistemul include două tipuri de medii de comunicare pentru agenţii: agenţia imobiliară şi forumul. Agentia imobiliară intermediază interacţiunile dintre chiriasi şi proprietari, dar nu face mai mult decât să selecteze si să furnizeze chiriaşilor toate ofertele corespunzătoare cererilor lor. Figura 4.2 oferă o privire de ansamblu asupra sistemului si a căilor pentru schimburile de mesaje

Figura 4.2 - Interacţiunile dintre agenţi în cadrul sistemului

Ciclul de viată asteptări – opinii

Prin prelucrarea opiniilor emise de ceilalti, un agent îsi construieste un set de asteptări referitoare la fiecare dintre optiunile care îi sunt puse la dispozitie, asteptări care îi permit să ia o decizie informată. În proiectarea sistemului pentru testarea calitătii modelului de reputatiei s-a făcut următoarea conventie: fiecare proprietate imobiliară are asociată o valoare „absolută”, cunoscută doar de către proiectantul simulării, numită în continuare realitate.

În urma alegerii uneia dintre optiunile posibile, agentul ia contact cu această realitate, dar perceptia sa este supusă unor deformări (ce tin, spre exemplu, de preferintele agentului). Asadar, perceptia sa va fi egală cu valoarea realitătii, la care se adaugă un factor de alterare (pozitiv sau negativ), mai mare sau ma mic, în functie de profilul agentului, reprezentând gradul lui de obiectivitate.

Figura 4.3 - Ciclul de viată Asteptări – Opinii

În sistemul propus se presupune că agentii sunt sinceri, asa că vor publica percerptia lor, ca opinie, pe forumul de opinii. Pe baza acestor opinii, acelasi agent, sau altii, îsi pot crea asteptări cu privire la entitătile tintă. Procesul prezentat aici este ilustrat în Figura 4.3.

Raţionamente despre reputaţie

Proiectul implementează patru metode diferite de decizie folosind diverse funcţii de agregare pentru mecanismul descentralizat de reputaţie.


1) „Opinia expertului”: Un agent care foloseste această metodă va lua decizii pe baza opiniei unui singur autor de pe forum, considerat de către agent ca fiind cel mai potrivit pentru situaţia dată.

2) „Veriga cea mai slabă”: Prin utilizarea acestei metode de decizie, agenţii îsi aleg o locuintă considerând că cea mai relevantă notă primită de o casă este cea mai mică dintre toate notele primite.

3) „Încredere adaptabilă”: Această metodă de decizie agregă metodă toate opiniile despre o locuintă ale tuturor utilizatorilor găsite pe forum. În plus, această metodă utilizează un factor de încredere ajustat dinamic asociat fiecărui autor ca furnizor de informatii despre reputaţie.

4) „Experienţa personală”: Aceasta metodă balansează opinia comunităţii cu opiniile personale ale agentului în funcţie de cantitatea de experienţa personală pe care acesta o are.

Implementare si rezultate experimentale

Proiectul descris în această secţiune implementează modelul propus de extragere a reputaţiei şi oferă un cadru de testare pentru diferite funcţii de agregare şi metode de decizie. O observaţie cu privire la teste este aceea că valorile reputaţiei sunt influenţate si de ofertele disponibile pe piaţă şi de modul în care agentii îsi formulează cererile.

(a) Reputatia furnizorilor de servicii

Graficul din Figura 4 confirmă eficacitatea modelului de reputaţie, evidentiind corelaţia dintre calitatea serviciilor oferite şi reputaţia furnizorilor. Modelul de reputaţie propus functioneză ca ghid în alegerea celui mai bun furnizor de servicii dintr-o multime de opţiuni date.

Figura 4.4 - Reputatia si calitatea serviciilor


(b) Reputatia furnizorilor de informatii

Pentru a evalua calitatea opiniilor postate pe forum, au fost studiate două aspecte: obiectivitatea autorilor în descrierea realitatătii, pe de o parte şi, pe de altă parte, în ce măsură se stabileşte o relaţie de afinitate între autori şi public în funcţie de gradul în care opiniile distorsionează realitatea.

(c) Compartie între metodele de decizie propuse

Cele patru metode de extragere a reputaţiei propuse în acest capitol au fost testate comparativ, în scopul de a stabili care dintre ele aduce cea mai mare utilitate agentilor. Pentru acest studiu, am masurat gradul de satisfactie pentru fiecare agent şi am alfat ce categorie de agenti (clasificati după metoda de decizie pe care o folosesc) estimează cel mai corect reputatia furnizorilor de servicii.

4.4 Model de negociere pe baza reputatiei

Acest capitol discută cazurile în care agenţii trebuie să coopereze pentru a-şi îndeplini propriile obiective. Cooperarea în scenariul este reprezentată prin schimbul de bunuri. Schimbul are loc în urma unei negocieri, iar factorul cheie pentru negociere în modelul propus este reputaţia participantilor.

4.4.1 Folosirea reputatiei ca factor de negociere

Folosind reputaţia ca mijloc de controlul social, secţiunea de faţă propune un model de negociere în care reputatia funtionează ca o pârghie în apărarea intereselor unui individ. În acest capitol este prezentat un scenariu în care agenţii pot face schimb de bunuri numai prin troc şi se propune un mecanism prin care se evidenţiază strategiile pe care agenţii le pot utiliza pentru a-si maximiza profitul. Modelul poate fi cu uşurintă adaptat şi aplicat si în alte aplicatii de comert electronic ce facilitează, spre exemplu, schimburile între colectionari. Am selectat câteva dintre cele mai relevante modele de reputaţie şi norme pentru a fi discutate în această secţiune: (V. da Silva, R Hermoso, & R Centeno, 2009), (Muller & Laurent Vercouter, 2008), (Castelfranchi, 2000), (Vázquez-Salceda & Dignum, 2003), (Esteva, Rodriguez-Aguilar, C. Sierra, Garcia, & Arcos, 2001) si (Karl Aberer & Zoran Despotovic, 2001).

4.4.2. Structura sistemului de agenti

Această subsecţiune descrie principalele componente ale scenariul propus pentru analiză. Sunt prezentate mai întâi tipurile de agenti şi caracteristicile specifice ale acestora, după care, sunt discutate conceptele cu care operează agentii. Comunitatea multiagent contine două tipuri de agenti: o autoritate centrală (denumită în continuare CA) şi agenţi producători (sau pur şi simplu "agenţi" după cum îî vom numi în continuare). Există m tipuri de resurse, ce pot fi grupate în două categorii: interne şi externe. Există r tipuri de produse, fiecărui agent care intră în sistem fiindu-i asociat un produs pe care acesta să îl dezvolte. Un produs este pe deplin dezvoltat atunci când agentul a adunat resursele care compun produsul, în cantităţile prescrise.

4.4.3 Modelul de reputatie

Dinamica sistemului

În această subsecţiune este descris mecanismul de sincronizare utilizat în modelul propus. Mecanismul de sincronizare foloseste ture, iar fiecare tură are doi pasi. În primul pas un agent

Model de negociere pe baza reputatiei 48

poate fie să trimită o ofertă altui agent, fie să depună o plângere referitoare la o contraventie. După primirea tuturor ofertelor, un agent poate să le accepte sau să le refuze pe baza intereselor sale precum si a informatiilor despre reputatie. În cea de-a doua fază, un agent poate răspunde unei cereri de schimb fie în mod afirmativ, făcându-se automat si transferul produselor, fie printr-un refuz.În evaluarea unei oferte, agentul verifică dacă are în stoc resursele necesare pentru schimb. Dacă da, atunci poate accepta schimbul după negocierea unei rate convenabile, altfel, poate refuza oferta, poate încerca o negociere pentru a se încadra în cantitatea pe care o are sau poate încălca norma acceptând tranzactia desi stie ca nu o poate onora.

Reputatia

După un număr fix de ture (numit în continuare perioada de evolutie), autoritatea centrală re-calculează valorile de reputaţie aplicând următorul set de reguli. Dacă(tranzactii(A) > 0) dacă (NrContraventiiReportate(A) = 0) reputatia(A) = min(RpBound, reputatia(A) + 1) altfel reputatia(A) = max(-RpBound, reputatia(A) – 1) altfel reputatia(A) = reputatia(A) În funcţie de valorile reputaţiei, agenţii sunt distribuiti în mod dinamic în trei clase de reputaţie: demn de incredere, neutru sau nedemn de încredere, asa cum e reprezentat în Figura . Axa R reprezintă nivelul reputaţiei.

Încrederea

În aceast model încrederea este considerată a fi opinia subiectivă a unui agent asupra

comportamentului partenerilor săi de schimb, bazat pe interactiuni directe.

Figura 4.5 - Grila de reputatie

Dacă (nrInteractiuni(A1, A2) > 0) dacă (NrContraventii(A2, A1) = 0) încredere(A1, A2) = min(RpBound, încredere(A1, A2) + 1) altfel încredere(A1, A2) = max(-RpBound, încredere(A1, A2)- 1) altfel încredere(A1, A2) = încredere(A1, A2)

Normele

Pentru a oferi un scenariu simplu şi ilustrativ am ales o singură regulă generală. Norma generală după care se guvernează întregul sistem este următoarea. „Agenţi trebuie să respecte ratele de schimb din Figura , în funcţie de clasa de reputaţie din care fac parte. Rata de schimb între un agent care aparţine clasei „demn de încredere” şi un agent din clasa „nedemn de încredere”, este 1:3 (pentru fiecare unitate pe care o dă agentul

Model de negociere pe baza reputatiei 49

din clasa superioară, primeste în schimb 3 unităti), 1:2 pentru agenţii aparţinând unor clase adiacente şi 1:1 între agenţii din aceeaşi clasă. „

Strategii

Depunerea unei plângeri

Un agent poate decide să informeze sau nu autoritatea centrală cu privire la încălcarea unei norme. Acţiunea rezultată în urma acestui proces de decizie poate varia în funcţie de gradul de completare al produsului tintă. Întrucât aceste decizii sunt gestionate intern de către fiecare individ, nu putem decât sugera o funcţie ce descrie probabilitatea ca un agent să depună o plângere (x% este procentul de unităţi obtinute din numărul total necesar):

, .

Încălcarea normelor

Un agent va alege să încalce o normă mai degrabă atunci când este aproape de realizarea produsului scop decât în stadiile incipiente de dezvoltare. Astfel, această strategie este, cumva opusă strategiei de depunere a plângerilor.

4.5 Modelul de negociere 4.5.1 Rolul reputatiei în procesul de negociere

Fiind publicate într-un mediu partajat si puse la dispozitia oricui, nivelurile de reputatie ale agentilor devin un punct oficial de referintă, putând fi invocate în justificarea unei rate de schimb mai avantajoase. După cum s-a discutat anterior, agentii îsi aleg partenerii de interactiune nu numai după valoarea reputaţiei, dar si în funcţie de valoarea încrederii lor personale, stocate la nivel local. Pot exista cazuri în care cele două valori sunt diferite. Valoarea publică a reputaţiei poate fi, astfel, folosită în cadrul negocierii, fiind interesul ambelor părţi să ajungă la un acord, plasându-si oponentul cât mai precis posibil pe grila de reputatie.

4.5.2 Protocolul de negociere

Ideea pe care dorim să o subliniem în această subsecţiune este aceea că, indiferent de abilităţile de negociere ale unui agent, (spre exemplu, protocolul folosit), puterea de negociere dată de o bună reputaţie duce la aplicarea normelor în sistem, menţinând astfel ordinea socială. Protocolul de negociere constă în trei faze de comunicatie, ilustrate prin diagrama de interactiune din Figura . Fie Alice un agent care decide să initieze o tranzactie cu agentul Bob. Prin procesul de negociere se încearcă pozitionarea reputatiei agentului Bob în grila de reputatie astfel încât valoarea sa fie agreată de către cei doi agenti. În prima etapă, Alice îi comunică lui Bob nivelul său de încredere în privinta lui Bob. Nivelul încrederii este exprimat ca apartinând uneia dintre cele trei clase: de încredere, neutru sau nu e de încredere. Dacă valoarea încrederii, calculată local este mai mare decât valoarea reputatiei, Alice îi va comunica lui Bob clasa corespunzatoare reputatiei lui, întrucât agentii sunt interesati în primul rând de propriul lor profit.

Figura 4.6 - Protocolul de negociere

Model de reputatie pentru gestiunea fortei de muncă în cadrul organizatiilor virtuale 50

Răspunsul lui Bob, este reprezentat în Figura pentru a arăta că si el este constient de valoarea reputatiei sale, si că o poate folosi, atunci cand este cazul ca mijloc de justificare a atitudinii sale referitoare la rata de schimb propusă de partenerul de negociere. În a doua etapă, Alice îi trimite lui Bob propunerea sa. Bob poate fie să o accepte, fie să o refuze, refuzul său ducând la o a treia etapă în care Alice poate să îsi revizuiască sau nu oferta.

4.5.3 Găsirea unui acord

În evaluarea ofertelor primite sau atunci când inspectează lista agenţilor care oferă un anumit tip de resursă, un agent, A1, calculează clasa de reputaţie pentru fiecare dintre agentii vizati, utilizând următoarele două reguli: (a) În cazul în care nu există nici o colaborare anterioră între cei doi agenţi, agentul evaluator, A1, consideră încrederea sa fată de A2 ca fiind egală cu reputaţia lui A2, furnizată de către autoritatea centrală. (b) În cazul în care agentul de evaluator, A1, are deja un însemnare cu privire la agentul evaluat, A2, (adică au mai colaborat), atunci clasa de reputaţia atribuită lui A2 rezultă din media dintre reputaţia publică a lui A2 şi încrederea pe care o are agentul A1 în A2. Pentru a determina într-un mod cât mai realist nivelul pe care un agent ar trebui îsi plaseze partenerul pe grila de reputaţie, propunem folosirea mediei ponderată dintre impresiile rezultate în urma experienţelor anterioare si valoarea publică a reputatiei:

. Unde, si dacă se consideră că experienta personală este cea care contează mai mult, si dacă se consideră că experienta personală nu este relevantă în cazul respectiv.

4.5.4 Rezultatele implementării

Pe baza diversilor parametri alesi pentru evaluarea realizărilor fiecărui agent în timpul simulării, este calculat periodic un clasament al agentilor. Modelul abordează problema sanctiunilor prin plasarea agenţilor în clase diferite de reputatie, un alt statut implicând costuri diferite pentru aceleaşi bunuri. Mecanismul de negociere oferă agenţilor şansa de a se justifica si de a ajunge la un acord cu partener de interactiune. Rezultatele prezentate în acest capitol au fost publicate în (Urzica et al., 2010) and (Urzica, Mogos, & A. M. Florea, 2011).

4.6 Model de reputatie pentru gestiunea fortei de muncă în cadrul organizatiilor virtuale

În cadrul unei organizaţii, atât reale, cât şi virtuale, o serie de decizii privind fluxul personalului sunt luate pe baza de încredere şi de reputaţia individului. Acest capitol propune un model de reputatie pentru agenţii din cadrul organizaţiilor virtuale, care poate fi folosit pentru a decide începutul, continuarea, sau oprirea colaborării cu un agent. Reputaţia unui agent se construieste pe baza încrederii pe care organizaţia o are în agentul respectiv. O parte dintre rezultatele prezentate în acest capitol au fost publicate în (Neata, Urzica, & A. M. Florea, 2011). Acest capitol oferă descrierea noii abordări propuse. Aceasta constă într-un instrument vizual pentru proiectarea unei organizaţii virtuale ce permite definirea specificaţiilor structurale, funcţionale şi deontice ale unei organizatii, un motor de implementare a organizaţiei virtuale, un sistem organizational normativ şi un model de reputaţie pentru managementul organizaţiei.

4.6.1 Motivatie

Reputaţia unei organizaţii depinde de performanţa angajaţilor săi în executarea activitătilor. Prin urmare, monitorizarea, evaluarea şi selectia angajaţilor în conformitate cu standardele de


calitate ale companiei sunt esenţiale în construirea unei bune reputaţii. Încrederea pe care organizaţia investeşte în fiecare agent este principalul factor din spatele deciziilor de selectie.

4.6.2 Cercetări similare

Mecanismul de reputaţie prezentat în acest capitol pleacă de la următoarele modele ca punct de inspiratie şi le îmbunătăteste prin multiple contribuţii originale.

Modele de încredere si reputatie

Din studiul modelelor teoretice putem extrage urmatoarea concluzie: modelul Marsh răspunde la întrebarea "cum putem calcula cantitatea de încredere investită?", modelul propus de Carter et al. raspunde la intrebarea: "Care este relaţia dintre rolurile sociale şi aşteptări în cadrul unui sistem care utilizează mecanisme de încredere şi reputaţie?" iar modelul REGRET răspunde la întrebarea "care sunt datele de intrare ale unei funcţii de evaluare a încrederii?". Modelul propus foloseste conceptele de specificatii structurale şi specificatii funcţionale definite în MOISE (Jomi F. Hubner, Sichman, & Olivier Boissier, 2007). Spre deosebire de MOISE însă, modelul prezentat aici permite o asociere directă între roluri şi activităţi, care să permită ca două sau mai multe activităţi asociate unui rol, să fie executate, după instanţiere de către agenţi diferiţi, cu roluri compatibile. Planificarea si distribuirea activităţilor nu sunt acoperite în implementarea ORA4MAS (J. F. Hubner, Kitio, & O. Boissier, 2009). Rezultatul nesatisfăcător a unei activităti executate de către un agent în organizaţie nu atrage după sine reluarea întregului sistem, la fel ca în MOISE, ci, activitatea nesatisfăcător îndeplinită poate fi reprogramată la momentul rulării programului şi executată din nou, de către acelaşi agent sau de un altul.

4.6.3 Componentele sistemului

În Figura 4.7 sunt reprezentate principalele module ale sistemului propus pentru mangementul fortei de muncă în cadrul unei organizatii, pe baza unui mecanism de evaluare a încrederii. Specificatiile structurale definesc ierarhia de roluri ce vor fi create iar specificatiile functionale descriu modul în care obiectivul global al organizatiei se împarte în obiective mai simple până la nivelul activitătilor atomice. Specificatiile de performantă includ specificatiile normative ale organizatiei precum si diversi parametri de acceptabilitate folositi de modelul de reputatie.

Figura 4.7 - Componentele sistemului


Modulul de implementare contine instrumentele folosite în construirea organizatiei virtuale pe baza proiectării făcute cu ajutorul modulului de specificare. Modulul de implementare este, de asemenea, folosit pentru executia organizatiei si testarea corectitudinii mecanismului de evaluare a încrederii, precum si pentru a observa modul în care specificatiile referitoare la performantă influentează comportamentul sistemului. La momentul rulării, modulul de implementare recrutează agentii de care este nevoie pentru ca organizatia să fie bine-formată, îi evaluează în mod permanent si ia decizii pe baza specificatiilor de performantă. Deciziile privesc atât continuarea sau întreruprea colaborării cu un agent, precum si atribuirea agentului unui rol care să maximizeze utilitatea organizatiei.

4.7 Obtinerea unei reputatii în cadrul organizatiilor virtuale Modelul propus permite monitorizarea activitătii agenţilor şi evaluarea performanţei lor în cadrul unei organizaţii virtuale. Modelul calculează valoarea încrederii pe baza calitătii muncii unui agent în îndeplinirea activitătii sale. Cu cât un agent îsi îndeplineste mai bine angajamentele, cu atât organizatia are mai multă încredere în el, prin urmare, cu atât mai mult va putea rămâne în cadrul organizatiei si ajunge mai sus în ierarhie. Crescând pe scara ierarhică, reputatia agentului creste şi el poate obtine dreptul de a da ordine şi de a îi monitoriza pe agenţii subordonati. Din acest motiv, fluxul de personal depinde în mare măsură de mecanismele de evaluare încredere folosite de organizaţie. Această sectiune explică modul prin care agentii sunt selectionati si evaluati pe baza normelor organizationale pentru a le putea fi atribuite cele mai potrivite obiective de îndeplinit. Procedura de recrutare propusă se bazează pe recomandările unor terţe părţi şi pe rezultatul unei probe initiale impuse agentilor. Agregarea acestor doi termeni reprezintă valoarea de iniţializare a încrederii pe care organizatia o are în fiecare agent. În scopul interactiunii cu agentii raţionali, organizaţia foloseste următoarele mecanisme prin care le aduce la cunostintă care este comportamentul dorit în cadrul organizatiei: mecanisme de recompensare şi mecanisme de sanctionare. Există trei metode de bază pe care organizatia le poate utiliza pentru recompensarea unei bune conduite ale angajaţilor săi: bonusul, mărirea de salariu şi promovarea.

4.7.1 Implementare si rezultate experimentale Optimizare în simulare: predictabilitate si aleatoriu

Pentru a putea evalua corect comportamentul unui agent, astfel încât valoarea reputaţie atribuite să fie relevantă în luarea unei decizii cu privire la agentul evaluat, comportamentul acestuia trebuie să aibă un profil coerent. Am ales să definim profilul unui agent printr-un set de parametri, specifici fiecărui individ, care influenţează calitatea rezultatului. Astfel, rezultatele obtinute de agenti diferiti, pentru aceeaşi problemă, pot fi diferite. Prin modelarea capacitătii unui agent de a rezolva o problemă folosind algoritmi genetici acoperim toate cerinţele enumerate în faza de proiectare. Calitatea soluţiei depinde atât de calitatea codul scris în corpul agentului cât şi de parametrii săi specifici. Profilul agentului este constrâns de parametrii constanti, dar împrumută din nedeterminismul algoritmilor genetici.

Instrumente de vizualizare

Implementarea modelului propus, ce constă într-un instrument de proiectare a organizatiilor virtuale dotate cu module normative şi de reputaţie, oferă si metode pentru înregistrarea evolutiei organizaţiilor construite. Aplicatia permite observarea evolutiei încrederii în fiecare agent, tendinta performanţelor sale în indeplinirea obiectivelor şi profilul fiecărui agent în urma interviului.

SCIPA – Etapa IV

Interpretarea rezultatelor

Experimentele efectuate cu ajutorul aplicatiei au demonstrat corectitudinea modelul propus în evaluarea încrederii astfel încât aceasta să reflecte cât mai precis performanţele agenţilor.

Figura 4.9

Figura 4.8

tr-adevăr, modelul de încredere propus este capabil să urmărească evolutia

4.7.2 Discutie

Modelul organizational raportat în acest capitol are drept scop îmbunătătirea modelelor

lterioare este de a aplica modelul propus si în cadrul

4.8 RESPECT – Un model de reputatie pentru respectarea

Exista să explice acordul oamenilor de a renunta la libertatea

Încomportamentului agentului (asa cum se poate vedea în Figura ) şi să ajusteze nivelul încrederii atribuite, în conformitate cu aşteptările organizaţiei (Figura ).

existente, introducând o dimensiune calitativă în evaluarea obiectivelor îndeplinite de către membrii organizaţiei. Modelul propus permite gestionarea agenţilor în cadrul unei organizaţii virtuale prin utilizarea unui mecanism de evaluare a încrederii. Performanţele agenţilor sunt cuantificate, si influenţează relatia agentilor cu organizaţia: un agent poate fi promovat, retrogradat sau exclus din organizaţie. O posibilă direcţie pentru dezvoltări ualtor structuri organizatorice. Un exemplu de structură organizatorică în care este necesară coordonarea agenţilor în vederea atingerii unui obiectiv global şi se folosesc abordări evolutive în îndeplinirea obiectivelor individuale este sistemul descris în (Huruiala, Urzica, & Gheorghe, 2010). Modelul reputaţie prezentate în acest capitol ar putea fi aplicat, de asemenea, si pe o structură ierarhică precum lanţul de comandă din organizaţiile militare, precum cele descrise în (Tanase & Urzica, 2009).

specificatiilor normative

numeroase teorii care incearcăindividuală nelimitată în favoarea adoptării unui guvern sau a unei alte forme de autoritate, pentru a instaura sau menţine ordinea socială prin suprematia legii. Întrucât actiunile unui individ erau initial limitate doar de puterea şi de conştiinţa personală, trebuie că există beneficii importante politice şi economice care determină un individ interesat de propriile sale avantaje să aleagă respectarea limitărilor impuse de un contract social. Acest capitol

SCIPA – Etapa IV

investighează impactul pe care îl are un contract social distribuit asupra comportării generale a unui sistem multi-agent. În acest capitol vom prezenta RESPECT (REputation model for normative SPECificaTions

4.8.1 Folosirea reputatiei în impunerea normelor si a normelor în

În RES ate ca o descriere a comportamentului dorit prevazute

Recunoast a termenilor de interacţiune, precum şi accesul la servicii

O compone iv. Rolul modulului

compliance), un model de reputatie ce foloseşte mai multe tehnici pentru construirea, propagarea si utilizarea informaţiilor despre reputaţie, în funcţie de contextul la care se referă. Modelul de reputaţie este folosit pentru impunerea normelor în sisteme multi-agent deschise, descentralizate si eterogene. Sistemul normativ propus de RESPECT foloseste politici sensibile la context pentru instantierea si aplicarea normelor pentru fiecare situatie particulară. Premisele care stau la baza modelului RESPECT constau în strânsa legătura care trebuie să existe între orice tip de evaluare, fie la nivel interpersonal, fie la nivelul comunitătii, şi un set clar definit de norme. Orice declaraţie de încredere sau de neîncredere ar trebui să fie determinată de îndeplinirea sau de încălcarea unor aşteptări. Pentru a-i face pe membrii unui grup conştienti de aşteptările celorlalti, este stabilit si comunicat în sistem un set de norme. Obiectul modelul propus este de a stabili relaţia dintre evaluarea socială şi specificaţiile normative într-o comunitate, cu scopul de a face posibil controlul social.

construirea reputatiei PECT normele sunt formul

pentru membrii sistemului, fiecare normă de identificând în mod clar agentii prin rolurile acestora. Interacţiunile dintre agenţii în cadrul sistemului sunt modelate ca servicii prin care sunt proiectate pentru a fi oferite de unii si accesate de altii, în funcţie de rolurile lor. Fiecare tip de serviciu are asociat un set de norme, corespunzător domeniului său aplicaţie. Câteva exemple de interacţiuni reprezentatate ca astfel de servicii includ: vânzarea de bunuri, împrumutul de bunuri, furnizarea de informaţii, transferul de cunoştinţe, etc.

Proiectarea modelului

erea setului de norme şi se face prin intermediul unui contract, care trebuie semnat de ambele părţi. Desfăşurarea interacţiunii între cele două părţi generează un set de fapte. Distanţa dintre termenii asupra cărora s-a convenit în contract şi situaţia de fapt conduce la ajustarea reputaţiei. Reputaţia unui individ are o influentă importantă asupra terminilor contractelor viitoare. Modul în care reputatia influentează contractele viitoare in RESPECT este conceput în aşa fel încât să încurajeaze respectarea normelor şi să pedepsească încălcarea lor. Această influenţă reciprocă dintre reputaţia si norme este reprezentată în Figura , unde setul generic de norme reprezintă un "şablon de contract" iar setul de norme îmbogăţit cu termeni specifici reprezintă contractul care este oferit unui agent pentru a-l semna.

Figura 4.10 - Interdependenta dintre reputatie si norme

ntă cheie a modelului RESPECT este Modulul Normatnormativ este descris pe scurt în Figura.

SCIPA – Etapa IV

Normele definite în acest model sunt generice si exprimă comportamentul dorit, stabilt prin

omponentele modelului mpus din trei module principale: modulul normativ, modulul de

Modulul de credibilitate ges onderile

4.8.2 Modelarea interactiunilor ca servicii în RESPECT Pentru estora, modelul

Această se bularul folosit în modelul RESPECT, pornind de la cele mai

consens la nivelul întregului sistem. Setul de norme generice poate fi particularizat pentru fiecare interactiune în parte prin folosirea politicilor. Politicile sunt specifice fiecărei entităti si exprimă propriile sale reguli de business. Pentru a genera normele specifice ce vor reglementa noua interactiune, modulul normativ aplică politicile corespunzătoare contextului dat peste setul de norme generice.

Figura 4.11 - Rolul modulului normativ

CModelul RESPECT este coreputatie si modulul de credibilitate. Modulul normativ este mecanimsul care transformă un set de norme generice în norme specifice, conform setului de politici si a contextului dat, si generează contracte. Modulul de reputatie se ocupă cu atribuirea, ajustarea si propagarea informatiilor despre reputatia membrilor comunitătii. Principalele componente ale modelului RESPECT sunt prezentate în Figura 4.12.

Figura 5 - Principalele module ale modelului RESPECT

tionează reteaua de conexiuni dintre entităti precum si pasociate fiecărei legături. Entitătile care sunt capabile să facă schimb de informatii sunt conectate prin legaturi de comunicatie ce au asociate ponderi.

a permite interactiunea agentilor si monitorizarea interactiunilor acRESPECT descrie câteva formalisme si proceduri.

Sistemul de agenti

ctiune stabileste vocasimple elemente, precum conceptul de agent si sistem multi-agent. Definitia 6.1. Un agent, în modelul RESPECT, este definit astfel:

Unde:

SCIPA – Etapa IV

Modelul RESPECT este proiectat pentru a ajuta la stabilirea unei ordini sociale în cadrul comunitătilor de agenti. Modelul RESPECT este aplicabil în sisteme mult-agent deschise si descentralizate.

Definitia 6.2. Un sistem multi-agent este definit, în modelul RESPECT, ca o pereche ordonată de multimi , unde:

Orice doi agenti din cadrul unui sistem multi-agent pot partaja o conexiune de comunicatie pentru a face schimb de informatii despre ei însisi, despre mediu sau despre alti agenti. Definition 6.3. O conexiune între doi agenti din sistem este definită astfel:

Unde:

Un exemplu pentru multimea tipurilor de conexiuni poate fi:

Observatie: Fiind dată conexiunea si , poate fi diferită fată de , asa cum si poate fi diferită de

Definitia 6.4. În modelul RESPECT, multimea cunoscutilor unui agent este definită astfel:

1.1.2 Profilurile agentilor

Orice tip de interactiune dintre agenti este modelată in RESPECT printr-un serviciu. Pentru a putea identifica serviciul de care un agent este interesat, criteriile sale selectie precum si diversi alti parametri ai colaborării, fiecare agent are asociată o listă de preferinte cu privire la orice serviciu pe care ar dori să îl acceseze. Definitia 6.5: Un serviciu în RESPECT este definit după cum urmează:

SCIPA – Etapa IV

Unde,

;

Definitia 6.6. O preferintă a unui agent cu privire la caracteristicile unui serviciu este definită astfel:

Unde:

Această noţiune este utilă în definirea cererii adresate de către un agent potenţialului său partener interacţiune. În acest fel, caracteristicile serviciului sunt instantiate şi comunicate de către solicitant. Spre exemplu: locatia, data sau culoarea unui bun ce urmează a fi cumpărat sau închiriat, etc. Dacă alegem ca exemplu un serviciu de închiriere de maşini, preferinţele unui agent în accesarea acestui serviciu pot include: coordonatele destinatie, clasa masinii, numărul de kilometri estimat, datele de plecare şi de sosire, etc. Definitia 6.7. Lista preferintelor unui agent asupra caracteristicilor serviciului pe care îl caută este definită astfel:

Definitia 6.8. Lista constângerilor referitoare la caracteristicile unui serviciu oferit de un agent este definită astfel:

Unde:

Noţiunea de listă constrângeri este utilă în definirea ofertelor propuse de un agent potenţialului său partener de interacţiune. În acest fel, caracteristicile serviciului sunt instantiate şi comunicate de către furnizor. Ca exemple, putem enumera: preţul serviciului, perioada de garanţie, etc În scenariul dat ca exemplu mai sus, constrângerile privind serviciul

SCIPA – Etapa IV

de închiriere auto includ: preţul care trebuie plătit pentru perioada de inchiriere, pretul pentru fiecare kilometru suplimentar, preţul pentru fiecare litru de combustibil lipsă, suma de bani care urmează să fie plătită în avans, etc.

4.8.3 Primitive de comunicare în RESPECT Formatul mesajelor schimbate de către agenţii şi primitivele folosite în tratarea mesajelor sunt discutate în această secţiune. Definitia 6.9. Principalele două primitive folosite de către agenti în RESPECT pentru a comunica unii cu altii sunt: send si receive, definite după cum urmează:

Unde:

o

o

;

Informaţiile referitoare la reputaţia negativă sunt reprezentate în modelul RESPECT fie ca "puncte de penalizare", fie ca asocierea la o listă neagră, în timp ce informaţiile referitoare la reputaţia pozitivă provin din recomandarea unui alt agent. Exemplul 6.1. Atunci când agentul A vrea să trimită informatii cu privire la reputatia negativă a agenului C către agentul B, mesajul său are forma:

La primirea unui astfel de mesaj, în functie de credibilitatea lui A în fata lui B, agentul B va ajusta reputatia agentului C cu un procent din valoarea primită în mesaj, procent corespunzator credibilitătii lui A. Exemplul 6.2. Atunci când agentul A vrea să trimită informatii cu privire la reputatia pozitivă a agenului C către agentul B, mesajul este:

Un astfel de mesaj poartă următoarea semnificatie pentru agentul B: agentul A îl recomandă pe agentul C ca fiind cel mai bun partener cunoscut de A pentru serviciul si preferintele mentionate în solicitare.

SCIPA – Etapa IV

4.8.4 Modelul normativ Modelul utilizat de societăţile umane în ghidarea comportamentului membrilor lor către cel dezirabil functionează pe baza acordării unor drepturi cu conditia unui set de constrângeri. Constrângerile pot fi respectate sau cel care le încalcă suportă sancţiunile anunţate a priori ca fiind asociate încălcării lor.

Normele

Modelul RESPECT consideră asociat fiecărui serviciu un set de norme generice, recunoscute de către toţi membrii sistemului şi grupate în multimi, denumite în continuare şabloane de contract. Discuţia asupra legiuitorului, şi anume entitatea înzestrată cu dreptul de emitere a normelor generice, nu face obiectul acestui model. Definitia 6.9. (sablon de contract, normă): Un sablon de contract este definit astfel:

Unde: ●

● ●

●

●

Condiţia de pertinenţă a unei norme este un predicat prin care se decide dacă norma este sau nu aplicabilă în contextul actual al sistemului. Spre deosebire de o condiţie de activare, pertinenţa controlează si dezactivarea normei. În cazul în care norma este aplicabilă, rezultatul aşteptat este reprezentat prin conţinutul său, peste care se aplică operatorul deontic. Conţinutul normei este tot un predicat, care testează acţiunile entitătii ţintă. Agentul cu rolul de evaluator este cel care are dreptul de a verifica, indeplinirea conţinutului normei şi de a aplica, în cazul nerespectării ei, sancţiuni agenului ţintă. Astfel, în modelul actual, evaluatorii reprezintă atât a sistemului judiciar cât si puterea executivă. Normele atribuie actorilor din sistem responsabilitatea respectării regulilor de business. Definitia BNF a unei norme în modelul RESPECT este prezentată mai jos. <Norm> ::= <deonticOp>, <Target>, <Evaluator>, <PertinenceCondition>, <Content>; <deonticOp> ::= 'I' | 'O' | 'P' ; <Target> ::= <RoleName> ; <Evaluator> ::= <RoleName> ; <PertinenceCondition> ::= <B_R_IntegrityConstraint> | <B_R_Condition> |

SCIPA – Etapa IV

| <B_R_Authorization> | <B_R_Timer>; <Content> ::= <Fact>;

Politicile

Instantierea sablonului de contract într-un contract propriu-zis, care ia în calcul si contextul, si reputatia, se face pe baza politicilor. Politicile sunt dictate de regulile de business ale fiecare entităti si sunt folosite în interpretarea contextului si atribuirea unor valori fixe variabilelor specificate în contract. Definitia 6.10. O politică referitoare la un sablon de contract reprezintă setul de asocieri care, dându-se valoarea reputatiei si variabilele cunoscute, întoarce valorile posibile pentru toate variabilele:

Definitia BNF a unei politici în RESPECT este următoarea: <Policy> ::= <Match>, <Action>; <Match> ::= <Condtion>+; <Condition> ::= <FormalParam>, <Relation>, <Literal>; <FormalParam> :: = <BusinessTerm> | <Type> ; <Relation> ::= '<'| '='| '>'| "<=" | ">=" ; <Action> ::= <ActualParamList>; <ActualParamList> ::= <Literal>+ ; <Request> ::= <Preference>+; <Preference> ::= <Literal> | "N/A"; <Context> ::= <Request>, <ClientData>, <Reputation>, <Situation> ; <Situation> ::= <Literal>+ ; //descrie starea curentă a furnizorului de servicii si contextul general <ClientData> ::= <Literal>+ ; // informatii complementare despre agent (ex: vârsta, nationalitatea, data de expirare a cardului de credit, tipul documentului de identificare, data obtinerii permisului de conducere, etc.) <Reputation> ::= <RepValue>; //reputatia agentului care solicită serviciul <RepValue> ::= <Literal>; Lista literalilor din cadrul unei cereri trebuie formată conform specificatiilor serviciului. Ordinea si semantica literalilor dintr-o cerere sunt definite în descrierea serviciului.

Algoritmul de instantiere a normelor

Algoritmul de instantiere a normelor descrie modul în care se aplică politicile asupra normelor generice pentru a genera norme specifice, dependente de context.

1) Lista ActualParamList este initializată cu un sir de valori implicite, reprezentând parametrii de initializare, corespunzători politicii implicitie.

2) Șirul de literali, reprezentând solicitarea unui agent, este completată cu alti (tot literali) ce descriu: date despre agent (ex. vârsta, nationalitatea, etc.), reputatia agentului, precum si o serie de literali specifici furnizorului de servicii în contextul dat (spre exemplu, pentru

SCIPA – Etapa IV

cazul unei firme de închirieri auto: câte masini sunt disponibile în acea zi, conditiile meteorologice, etc).

3) Sirul rezultat este denumit „context”.

4) Din sirul denumit „context”, si pe baza specificatiilor de implementare a serviciului, se identifică diferenta dintre cele două momente de timp mentionate în cerere. Perioada de timp rezultată se împarte la unitatea de timp cea mai mare pentru care se taxează serviciul (spre exemplu, o zi).

5) Pentru fiecare unitate de taxare (ex: pe zi), se crează o replică a contextului.

6) Pentru fiecare replică a contextului, se selectează, una câte una, politicile din lista de politici, în ordinea în care au fost specificate, si pentru fiecare politică se verifică dacă literalii validează sau nu conditiile

7) Dacă, înlocuind toate variabilele din partea de matching a politicii cu literalii dati, nu rezultă nici o contradictie, politica poate fi aplicată.

8) Se înlocuiesc parametrii formali ai normelor din sablonul de contract cu toti literalii din partea de action a politicii.

9) În anumite cazuri, este necesară o prelucrare suplimentară pentru derivarea termenilor. În astfel de situatii, se aplică regulile de derivare (ex: pretul pentru o perioadă de mai multe zile se calculează însumând preturile pentru fiecare dintre zile).

10) Regulile de derivare sunt formule matematice pentru calculul parametrilor specifici regulilor de business.

4.8.5 Modelul de reputatie Modelul RESPECT foloseşte un mecanism de reputaţie ce permite aplicarea unor sancţiuni eficiente pentru impunerea normele. Această secţiune discută principalele caracteristici ale proiectării modelului de reputaţie din două perspective: reputaţia agentilor ca furnizori de servicii şi reputaţia agentilor care ajuta la propagarea informaţiior referitoare la calitatea serviciilor furnizate de alti agenti. Se poate spune că modelul RESPECT utilizează două mecanisme separate de reputaţie, ce rulează în paralel pentru acelaşi sistem multi-agent.

Reputatia unui furnizor de servicii

Furnizarea unui serviciu implică existenta unei asocieri între cel putin doi termeni. Este vorba despre relatia dintre furnizorul de servicii si beneficiarul serviciului, asa cum este prezentată în Figura 4.13

Figura 4.13 - Relatia dintre cele două roluri

(a) Reputatia furnizorului

Reputatia unui furnizor de servicii se construieste, în modelul RESPECT, pe baza a trei componente: recomandările altor colaboratori, reclamatiile altor colaboratori, si o a treia componentă ce reflectă aprecierea în ansamblu a partenerului în urma experientelor precedente, dacă au existat. Evaluarea unei potentiale colaborări cu furnizorul de servicii se realizează, in RESPECT, prin calculul valorii încrederii, numită în continuare măsura avantajului.

SCIPA – Etapa IV

Definitia 6.11. Avantajul oferit de colaborarea cu un furnizor de servicii este calculat, a priori, folosind următoarea formulă:

În urma calculelor este ales furnizorul cu valoarea cea mai mare a acestei măsuri.

(i) Experienta personală

Măsura care reflectă impresia de ansamblu a unui individ cu privire la calitatea serviciilor oferite către un furnizor de servicii este numită în RESPECT experientă. Valoarea Experientei se bazează pe multimea interactiunilor anterioare, fiecare dintre ele fiind evaluate, la momentul respectiv, în funcţie de diferenţele dintre aşteptări şi percepţii.

Definitia 6.12. Valoarea de satisfactie se calculează printr-o medie ponderată, folosind urmatoarea formulă:

Unde:

reflectă importanta pe care o acordă agentul unei fatete considerată a fi esentială pentru serviciul respectiv

reflectă importanta pe care o acordă agentul fatetelor pe care le consideră a fi ne-esentiale pentru acel serviciu

, reprezintă multimea de caracteristici ale serviciului S, selectate de către agentul ag si clasificate de către acesta ca fiind esentiale pentru serviciul în cauză.

, reprezintă multimea de caracteristici ale serviciului S, selectate de către agentul ag si clasificate de către acesta ca fiind ne-esentiale pentru serviciul în cauză.

Notele prin care agentii evaluează calitatea serviciului, pentru fiecare caracteristică în parte, sunt reprezentate prin numere întregi apartinând intervalului [1, 10], cu următoarea semnificatie: cu cât este mai mare nota, cu atât mai mult a fost apreciat serviciul.

După fiecare interactiune, beneficiarul serviciului actualizează valoarea Experientei, la valoarea , înglobând valoarea nou obtinută a gradului de satisfactie, :

Formula folosită pentru unificarea setului de experiente posedă trei caracteristici care o fac adecvată pentru a exprima nivelului actual al încrederii. În primul rând, acordă o mai mare importantă experientelor recente fată de cele mai îndepărtate în trecut. Ponderea �, factorul de iertare, este cea care stabileste influenta pe care ar trebui să o aibă trecutul asupra impresiei de ansamblu. În al doilea rând, curba de scădere a încrederii pentru o valoare mică a gradului curent de satisfactie este mult mai abruptă decât curba de crestere, care are nevoie de mai multe valori înalte pentru ca încrederea să atingă nivelul la care se afla înaintea unei deceptii. În al treilea rând, această functie descurajează un comportament oscilant mai mult decât alte o fac alte functii de agregare.

(ii) Reputatia negativă

SCIPA – Etapa IV

O componentă importantă pentru imaginea unui furnizor este rezultatul agregării reclamatiilor colaboratorilor săi. Un agent îsi poate exprima nemultumirea trimitând tuturor cunoscutilor săi mesaje ce sanctionează nivelul reputatiei furnizorului. Mesajele ce raportează încălcarea normelor, contin un anumit număr de puncte de penalizare. Definitia 6.13. Factorul de reputatie negativă corespunzător unui furnizor de servicii este măsurat în RESPECT de către agentul evaluator prin următoarea formulă:

Credibilitatea celui care face recomandarea este o măsură subiectivă, proprie fiecărui agent către fiecare dintre cunoscutii săi. Credibilitatea este dată de o functie de învătare care identifică sursele de informatie cele mai de încredere, conform descrierii din Sectiunea 0.

(i) Recomandările

O caracteristică însemnată a modelului RESPECT constă în folosirea recomandărilor în construirea reputatiei agentilor. Când un agent are nevoie de ghidare în alegerea unui furnizor de servicii, îi va întreba pe toti agentii la care este direct conectat, cerându-le recomandări pentru serviciul dat. Considerăm a nu fi eficientă cererea de recomandări de la agentii care nu sunt direct conectati, întrucât informatia ar putea să fie alterată de către orice nod de legătură prin retea. Un agent căruia îi este solicitată o recomandare răspunde cu numele si coordonatele furnizorului de servicii pe care el îl consideră a fi cel mai bun pentru acel serviciu. Definitia 6.14. Factorul de recomandare corespunzător unui furnizor de servicii în RESPECT se calculează, de către evaluator folosind următoarea formulă:

Unde: A este agentul evaluator agent, B este furniorul de servicii,

este multimea preferintelor pe care A le are referitor la serviciul S, asa cum sunt definite în Sectiunea 1.1.2. este numărul de instante în care agentul A a emis o solicitare continând cerintele iar este numărul instantelor în care furnizorul B a fost recomandat pentru multimea de cerinte .

(b) Reputatia beneficiarului

Furnizarea de servicii poate fi privită drept o relatie de colaborare. Agentul care accesează serviciul trebuie să se supună si el unui set de norme si poate fi, de asemenea, tras la răspundere pentru încălcarea angajamentelor. Reputatia beneficiarului are rolul de a-i proteja contra fraudelor pe furnizorii de servicii. Modelul RESPECT rezolvă problema ajustării reputatiei beneficiarilor prin două mecanisme: unul pentru propagarea bunei reputatii, iar altul pentru propagarea reputatiei negative. Buna reputaţie care pot fi câstigată de către un agent prin îndeplinirea obligaţiilor si angajamentelor sale cu privire la un contract este înregistrată pe un card de membru. Cardul de membru este eliberat de către furnizorul de servicii şi este recunoscut de către toţi membrii grupului de furnizori din care acesta face parte. Cardul de membru acumulează puncte de loialitate ce reflectă conformitatea proprietarululi cu normele pe durata colaborărilor anterioare. În acest fel, dovada unui comportament adecvat rămâne la agent, putându-i fi prezentată oricui, în orice moment. Furnizorii de servicii nu trebuie să se preocupe de propagarea informaţiilor despre buna reputaţie, economisindu-se astfel resurse de timp, de lăţime de bandă şi de stocare. Proasta reputaţie a unui agent în rândul furnizorii de servicii se propagă prin utilizarea de liste negre. Modelul RESPECT foloseste un set de liste negre, numit BlackListCategories. Un set generic de liste negre, folosit ca exemplu, poate fi următorul: "Rău", "Mai rău" şi "Cel mai rău". În functie de domeniul de aplicare, titlurile listelor negre pot fi modificate. Adăugarea

SCIPA – Etapa IV

unui agent pe o listă neagră se face de către prestatorul de servicii care observă încălcarea unei norme în timpul colaborării. Decizia este difuzată în grupul de parteneri ai furnizorului de servicii. După ce a fost adăugat pe o listă neagră, un agent va fi perceput de către toţi furnizorii de servicii din cadrul grupului, ca fiind un partener de colaborare riscant şi, drept consecinţă, politicile aplicate la şablonul contractelor viitoare, vor genera norme mai stricte, cu condiţii mai puţin avantajoase, în funcţie de gravitatea proastei reputatii.

Reputatia unui furnizor de informatii – Credibilitatea

Modelul RESPECT permite agentilor să filtreze informaţiile provenite de la cunoscuţii lor în funcţie de gradul de utilitate. Relatia de furnizare de informatii între agenti este reprezentată în Figura .

Pentru actualizarea valorii credibilitătii se foloseste o funcţie de învăţare. Funcţia de învăţare compară nivelul aşteptărilor construite pe baza informaţiilor primite de la un agent cu rezultatul interacţiunii cu furnizorul recomandat.

Figura 4.14 - Relatia ce defineste furnizarea de informatii

(c) Explorare vs. exploatare

Când un agent trebuie să se decidă în privinta colaborării cu un furnizor de servicii, el se va ghida fie după o strategie de exploatare a cunisstintelor pe care le-a acumulat deja, fie după o strategie de lărgire a orizonturilor prin explorarea noilor optiuni găsite în recomandările pe care le-a primit. Alegerea strategiei se face cu ajutorul unui set de conditii si valori de prag. Spre exemplu, dacă multimea recomandărilor primite de către agentul Alice contine si identificatori ai unor furnizori cu care Alice nu a mai colaborat, agentul va aplica următorul algoritm: dacă (k(Alice) < MinThreshold) sau (k(Alice) > MinThreshold si k(Alice) < MaxThreshold si ExploringFactor > ExploringProbability) atunci colaborează(Alice, partenerNou); altfel colaborează(Alice, partenerCunoscut);

Unde, este un agent în sistem iar este numărul de furnizori diferiti cu care Alice a colaborat în trecut.

(d) Integrarea noilor membri

Având în vedere că modelul actual este proiectat pentru sisteme deschise, noi agenţi poate adera sau părăsi sistemul în orice moment. Această secţiune discută statutul noilor veniti, consecinţele schimbării identitătii prin re-intrare, şi modul în care agenţii noi cu strategii mai bune pot fi recunoscuti de către vecinii lor, în ciuda lipsei unor interactiuni anterioare.

(i) Optimizarea feeback-ului

Ori de câte ori este evaluată o recomandare (spre exemplu când un furnizor de servicii recomandat este ales şi interacţiunea are loc), toate contactele pe care l-au recomandat ca furnizor de servicii primesc un bonus de credibilitate, dacă experienţa a fost una de succes sau, o sancţiune în termeni de credibilitate, dacă interactiunea nu a fost satisfăcătoare. Bonusul de credibilitate este egal pentru toţi cei care au emis recomandarea.

(ii) Îmbunătătirea selectiei

Abordarea noastră propune evitarea folosirii doar a recomandărilor venite din partea agentului cel mai sus plasat în

SCIPA – Etapa IV

clasamentul de credibilitate, deoarece, în acest fel, alte soluţii, poate chiar mai bune, s-ar putea pierde. Pe baza unui clasament preliminar care identifică agentii cu cele mai apreciate recomandări, cei care ocupă primele locuri N (N este determinat ca o valoare de prag) sunt sunt adăugati într-o multime neordonată. Agentul a cărui recomandare va fi folosită pentru următorul contract este ales aleatoriu din această multime. Procesul descris mai sus este simbolizat în Figura . Tehnica propusă este similară metodei de selectie Roulette Wheel, (“Roulette Wheel Selection,” 2011) folosită în algoritmi genetici.

(iii)Costurile unei schimbări de identitate

Consecinta pe care o implică un nivel scăzut al credibilitătii pentru un agent constă în faptul că recomandărilor făcute de acesta li se atribuie o pondere foarte mică, ajungând chiar la 0, ceea ce înseamnă că nu prea sunt luate în calcul de către beneficiar. Unul dintre scopurile acestui model este gruparea agentilor pe baza similaritătilor cu privire la criteriile de evaluare sau nivelurile de acceptabilitate fată de furnizorii de servicii. Din acest motiv, un agent nu va avea nici o motivatie să re-intre în sistem pentru a-si îmbunătăti credibilitatea în fata cunoscutilor săi. Dacă totusi alege să îsi schimbe identitatea, i se va atribui o valoare minimă a credibilitătii. Costul re-intrării în sistem constă în timpul necesar acumulării punctelor de credibilitate.

Figura 4.15 - Tehnica de selectie pe bază de

elitism

Algoritmul de decizie în modelul RESPECT

for each Customer in Agents for each Service in reqServ(Customer) for each Friend in AcqList(Customer) 1. send(Customer, Friend, Request(Service), t); 2. receive(Friend, RepInfo, t); endfor 3. choose(Provider, ServiceProviders); 4. send(Customer, Provider, Request(Service), t); 5. receive(Provider, Reply); 6. if (Reply.Answer == "Reject") then got to 3. else commit(Answer.Offer); 7. sign(Contract, Customer, Provider); 8. uses(Customer, service(Provider)); 9. if violation(Contract, Customer) then provider.addToBlacklist(Customer, Category); else provider.addPoints(MembershipCard(Customer)), Amount); 10. if violation(Contract, Provider) then customer.broadcast(AcqList(Customer),PenaltyPoints(Provider)); 11. customer.update(Customer, personalExperience(Provider)); customer.update(Customer, credibility(recommender(Provider))); endfor endfor

Discutie si cercetări similare

REGRET, “A reputation model for gregarious societies”, prezentat în (J. Sabater & C. Sierra, 2001) oferă un model pentru evaluarea mai multor tipuri de reputatie si propune fuzionare a unor aspecte legate de reputatie, cu ajutorul ontologiilor. După cum se mentionează în REGRET, este necesară extinderea experimentelor de valifare a modelelor de reputatie prin

SCIPA – Etapa IV

scenarii care implică grupuri de agenti, „unde indivizii folosesc experienta grupului pentru a-si completa propria lor experientă” (J. Sabater & C. Sierra, 2001) si unde agentii pot apartine mai multor grupuri în acelasi timp. Modelul de reputatie RESPECT îndeplineste aceste cerinte de extindere a gamei experimentelor. Unele entităti din RESPECT sunt organizate în mod explicit în grupuri, iar informatiile despre reputatie sunt propagate doar în interiorul grupului. În plus, multimea de agenti formată dintr-un agent si toti agentii direct conectati la acesta se comportă, de asemenea, ca un grup, partajând informatii despre reputatie (atât pozitivă cât si negativă). Aceasta înseamnă că, asa cum se arată în figura 4.16, orice agent apartine unui număr de grupuri egal cu numărul de agenti la care este direct conectat.

Figura 4.16 - Apartenenta multi-grup în RESPECT O lucrare ce abordează problema impunerii normelor în sisteme deschise si descentralizate este si modelul L.I.A.R. (“Liar Identification for Agent Reputation”), (Muller & Laurent Vercouter, 2008). Acesta este un model de implementare a controlului social asupra interactiunilor dintre agenti în sisteme deschise si descentralizate. O diferentă semnificativă între modelul RESPECT si modelul L.I.A.R. constă în faptul că, în RESPECT, continutul normei face referire la parametri formali. Parametrii formali sunt inlocuiti cu parametri actuali prin folosirea politicilor. Fiecare agent poate avea, în RESPECT, un set diferit de parametri actuali pentru acelasi set de norme. Lucrarea publicată de Hermoso et al., (Ramón Hermoso et al., 2010), introduce conceptul de acord pe baza reputatiei, ca fiind consensul atins, în spatiul opiniilor despre reputatie, de către o multime de agenti, cu privire la o situatie particulară. În modelul RESPECT se ajunge, de asemenea, la un acord, dar mai degrabă printr-o selectie naturală decât printr-o agregare a opiniilor participantilor. În RESPECT, fiecare agent se decide asupra unui singur colaborator pe care să îl recomande altora, aflati în situatii similare, ca fiind cel mai bun pentru serviciul dat. În acest fel, acordul este atins în mod natural între agentii care împărtăsesc interese similare, si se manifestă ca fiind rezultatul unei competitii.

4.9 Validarea modelului RESPECT

În acest capitol se prezintă câteva studii de caz ilustrative pentru sisteme deschise şi descentralizate şi se utilizează modelul RESPECT, descris în capitolul 0, pentru a garanta respectarea normelor folosind mecanisme de reputaţie.

4.9.1 Impunerea normelor folosind reputatia Scenariul propus reprezintă descrierea unei familii de problemele specifice comunităţilor virtuale, probleme care pot fi abordate numai prin intermediul unor mecanisme de coordonare.

Motivatie

Considerăm că nici încrederea, nici reputatia, nici conformitatea cu un set de norme poate fi evaluată în absenţa posibilitătii de trăda. Multe scenarii, mai ales cele care descriu interacţiunile de comert electronic , prezintă situaţii în care clientul este fie multumit, fie nemultumit de produsul sau de serviciul primit, cât timp este încă în contact cu vânzatorul.


Prin urmare, nu există nici o normă care să fie încălcată: fie clientul acceptă marfa, fie acesta este dezamăgit şi renuntă. Pentru a analiza evolutia comportamentului agenţilor lăsându-le, în acelaşi timp, suficientă libertate şi oportunităţi pentru a încălca regulile, propunem următorul scenariu: după semnarea unei tranzacţii, un agent are timp suficient pentru a încălca acordul înainte de a fi evaluat. Din moment ce vorbim despre încălcarea normelor, scenariul va defini un sistem normativ pentru reglementarea interacţiunilor. Sistemul normativ foloseşte sancţiuni care afectează reputaţia participanţilor, reducând-le astfel şansele unor interacţiunile viitoare. Serviciile de inchirieri auto devin din ce în ce mai populare în societăţile umane, fiind concepute metode ingenioase care il fac simplu de utilizat. Spre exemplu, modelul de afaceri self-service pay-as-you-go pentru inchirieri auto (vezi (“Streetcar,” 2011)), oferă acces la maşinile deţinute de firma de inchirieri direct către clienţi, pe baza unui card de membru, fără o intermediere din partea unui angajat al firmei. Masina este rezervată on-line de către client şi luată de la locaţia cea mai apropiată din vecinătatea sa. Autovehiculul se află într-o parcare normală, independent de locatia biroului de închiriere. Clientul deschide masina cu ajutorul cardului său de fidelitate, o foloseşte şi o aduce înapoi la locul convenit în rezervare. În contextul unui astfel de serviciu simplu de folosit de către client, sunt necesare mecanisme puternice de încredere care să susţină sistemul. O componentă majoră care stă la baza încrederii este reputatia. Acesta este motivul pentru care susţinem că lucrarea de faţă aduce o contribuţie importantă la evoluţia actuală a serviciilor publice, prin crearea unui model de reputaţie şi alegerea acest scenariu pentru a testa eficienţa modelului.

4.9.2 Descriere generală: firma de inchirieri auto Scenariul pe care îl propunem simulează dinamica agentilor care inchiriază masini de la companii de inchirieri auto. Componenta sistemului multi-agent se împarte în două mari tipuri de agenţi: agenţii care au nevoie de masini, care vor fi denumiti în continuare clienti si companiile de închirieri, pe care le vom numi în continuare firme. Comunitatea clientilor este descrisă printr-un un graf, reprezentând reţeaua de cunoştinţe. Fiecare agent este reprezentat ca un nod în graf şi este conectat prin muchii la toţi agenţii din lista sa de cunoscuti (spre exemplu, lista de cunoscuti din telefon). Ne vom referi în continuare, prin cuvântul „cunoscuti” la toti agentii cu care un agent este conectat print-o singura muchie în graful comunitătii. Firmele sunt interesate să pe de o parte să participe în cât mai multe tranzacţii iar pe de alta, să evite fraudele. Ele vor încerca să împiedice situatiile în care masinile ar fi deteriorate de cătreclienti prin analizarea certificatelor de identitate si de competenţă şi prin impunerea unui set de condiţii de eligibilitate. Un indicator util în această evaluare este reputaţia clientului. Pe baza rezultatelor evaluării, o firmă va aplica politica normativă corespunzătoare de adaptare a contractului pentru a se potrivi situaţiei.

Distribuirea informatiei

Modelul RESPECT foloseste o strategie de tip „solicitare” pentru propagarea reputaţiei pozitive, în timp ce reputaţia negativă este transmis prin „inundare”. Acest lucru se întâmplă atât pe partea clientilor cât şi în partea firmelor, chiar dacă mecanismele de propagare utilizate sunt alese în mod diferit. Prin „inundare” sunt transmise, între clienţi, avertizările cu privire la proasta reputaţie a firmelor iar între firme, informaţii despre normele încălcate de către clienţi.

Reputatia clientilor evaluată de către cόmpanii

Această secţiune explică modul în care clienţii sunt perceputi de către cόmpanii, cum se construieste încrederea şi modul prin care se propagă reputaţia pozitivă sau negativă în cadrul grupurilor de firme. Mecanismul de reputatie prin care firmele îsi evaluează clienttii trebuia să întrunească o serie de conditii pentru a putea oferi suficient realism si utilitate acestui proiect. În primul rând, considerăm a fi ineficient din punct de vedere al stocări datelor ca baza de date cu clienti să


fie replicată în fiecare firmă a unui grup. Aceasta ar fi condus la comportarea întregului grup ca o singură entitate, ce are mai multe puncte de interactiune. Din acest motiv s-a luat decizia de a transmite doar informatiile critice cu privire la un client, tuturor membrilor grupului de furnizori. Lucrarea de fată tratează, în special, reputatia negativă a clientilor, pe care o consideră a fi o informatie critică privitoare la acestia. Reputatia negativă despre clienti este distribuită prin intermediul listelor negre gestionate de membri grupului, iar reputatia pozitivă prin caduri de fidelitate, responsabilitatea utilizării lor fiind atribuită clientilor.

Reputatia cόmpaniilor în rândul clientilor

Această secţiune explică procesul de evaluare din cadrul comunităţii clientilor privind calitatea serviciilor oferite de companii, conform modelului propus la punctul 0 Când un client are nevoie de o recomandare pentru un serviciu, îsi întreabă toti cunoscutii, acestia răspunzându-i, fiecare, cu datele de contact ale unei singure companii. �ansa de a fi recomandată si, posibil, evaluată de către un client îi este acordată unei firme numai dacă a ajuns în varful clasamentului de preferinte al unui cunoscut.

Reputatia cunoscutilor în rândul clientilor

Disocierea dintre furnizorii şi consumatori de servicii subliniată prin modelul RESPECT permite o mai bună distinctiei si analiză a relaţiilor dintre agenţii: relaţia dintre un agent si consilierul său care îi furnizează informatii cu privire la reputaţia celorlalti şi relaţia dintre un agent si partenerii săi de afaceri. Toate relatiile din reteaua de cunoscuti au asociate, fiecare, în mod asimetric, câte un nivel de încredere. Fiecare client evaluează relatia de încredere pe care o are fată de un cunoscut de-al lui pe baza calitătii recomandărilor pe care acesta i le face. Dacă un client nu poate lua legătura cu o firmă recomandată de alt agent, încrederea clientului fată de agentul care a făcut recomandarea va scădea. Acelasi lucru se întâmplă si dacă un client a ales să contacteze o firmă si a fost nemultumit de calitatea serviciilor oferite de firma recomandată.

Sistemul normativ

Această secţiunea începe prin a arata modul în care sistemul normativ propus de RESPECT poate fi aplicat în scenariul dat, enumeră o submultime a normelor utilizate în cadrul acestui scenariu şi explică modul în care se folosesc contracte cadru şi politicile de instantiere pentru a lega mecanismul de reputaţie de setul de norme specificat. Setul de norme propus ca exemplu în această sectiune este preluat (si adus în forma prescrisă de RESPECT) dintr-un contract cadru pentru servicii de închirieri de masini găsit într-un studiu al European Consumer Centres Network (Network, 2005).

Artefacte

Pentru a creste realismul simulării, aplicatia implementează accesul agenţilor la obiectul contractului. Întrucât sistemul multiagent descris în această sectiune este implementat folosind limbajul de programare Jason (Bordini, J.F. Hubner, & Wooldridge, 2007), folosirea tehnologiei Cartago framework (Ricci, Piunti, Viroli, & Omicini, 2009), (Ricci, 2010), pentru implementarea obiectelor schimbate între agenţii devine subânteleasă.

Discutie

Credem că modelul RESPECT ar putea fi, de asemenea, uşor de implementat pentru orice alt caz de interacţiuni reglementate prin contracte. Un prim pas în extragerea automată a normelor de interacţiune dintre agenţi din seturile de reguli de business ar fi utilizarea de instrumentului de transformare a notatiei BPMN în limbajul AUML, prezentat în (Urzica & Tanase, 2010) şi (Urzica & Tanase, 2009). În plus, procesele de business pot fi modelate folosind notaţia textuală descrisă în (Mogos & Urzica, 2009).


4.9.3 Distribuirea de continut în mod directionat, pe baza reputatiei Renumele reprezintă, încă din timpuri istorice, un puternic mecanism folosit de către societăţile umane în ghidare comportamentul membrilor lor. Tradus în lumea computatională, acelaşi mecanism de feedback păstrează, ba chiar lărgeşte acest impact. Secţiunea aceasta prezintă o perspectivă interesantă privitoare la utilizarea sistemelor de reputaţie: reputaţia este dobândită prin respectarea normelor şi normele sunt modificate de către agenţii renumiti. Scopul modelului propus în această secţiune este de a optimiza distribuirea de conţinut într-un sistem multiagent. Mecanismul propus îsi atinge obiectivul prin prioritizarea preferinţelor agentilor cu cea mai mare reputatie.

Motivatie

Un factor important în luarea deciziilor atunci ne confruntăm cu o alegerea între mai multi prestatori de servicii este reputaţia acestora. Întrucât reputaţia poate fi privită ca fiind unificarea tuturor opiniilor referitoare la o entitate evaluată, ea ar trebui să reflecte caracteristica medie a comportamentului celui evaluat.

Clasificarea continutului pentru replicare

Modelul propus vizează creşterea vitezei de reactie a serviciilor de furnizare de conţinut multimedia oferite clientilor mobil. Fie o multime agenti care rulează pe dispozitive mobile, aflati în căutarea de continut audio. Continutul audio este oferit de către alţi agenţi, numiti în continuare depozite. Depozitele au o capacitate de stocare limitată şi pot deţine doar un anumit număr de fişiere. Depozitele pot distribui conţinutul în mod simultan doar pentru un anumit număr, limitat, de clienţi. Scopul modelului propus aici este de a reduce timpul de aşteptare în obtinerea fisierelor populare într-un sistem precum cel descris mai sus. Prin utilizarea mecanismului de reputaţie propus, conţinutul solicitat mai des va avea o prioritate mare pentru agentii depozit, acestia încercând să îl procure si să îl pună cât mai curând la dispozitia agentilor mobili, reducând astfel, atât timpul de aşteptare precum şi numărul de redirecţionări.

Motorul de reputatie

Fiecare client poate avea propriul său sistemul de clasificare, dar toti folosesc acelaşi mod de căutare al conţinutului multimedia. Sistemul se adaptează usor la schimbările preferinţelelor clienţilor, asigurând aprovizionarea cu cel mai popular conţinut. Un client păstrează în memoria sa, pentru fiecare tip de conţinut de care este interesat, doar numele depozitului pe care îl consideră a fi cel mai bun furnizor şi, dacă este cazul, numele unui alt agent, care i-a recomandat acel depozit. Un client stochează, de asemenea, lista cunoscutilor săi, ordonati după precizia lor de a recomanda depozite, pentru fiecare tip de conţinut în parte. Fiecare depozit menţine un tabel cu clienţii şi cererile lor. Un depozit îsi va

adapta oferta pentru a se conforma cu

Figura 4.17 - Corelatia dintre reputatie si timpul de asteptare

cerintele clientului care l-a recomandat cel mai mult altor clienţi. Pe măsură ce un depozit devine foarte recomandat, timpul său de reacţie va creste, prin urmare va creste şi numărul clintilor redirecţionati, adică nemultumiti. În acest timp, un alt depozit va câştiga popularitate pentru conţinut si timp de reactie ducând la echilibrarea


sarcinii în cadrul sistemului. Corelatia dintre timpul de aşteptare si reputaţie este ilustrată în figura 4.17

Clientii mobili si reteaua de furnizori

Fiecare client mobil retine în memorie: o multime de tipuri preferate de continut ("genuri", spre exemplu, genuri de muzică), lista de noduri la care este conectat direct la ("prieteni"), lista de prieteni sortată, pe genuri, pe baza credibilitătii lor pentru fiecare gen în parte, datele de contact ale unui depozit şi nivelul de încredere în el, un prag de încredere şi de o politică de explorare pentru fiecare gen. Politica de explorare a unui client mobil poate fi una "radicală" sau "conservatoare". O politică radicală de explorare presupune o rata mare de penalizare a încrederii în agentii depozit, în sensul că agentul vrea să fie întotdeauna la curent locurile în care poate găsi un anumit continut, în timp ce o politică conservatoare de explorare reflectă loialitatea unui client fată de furnizorul său. Aceasta înseamnă că, dacă furnizorul nu răspunde la primul apel, clientul va scădea, cu putin, încrederea şi va face o a doua încercare după un anumit timp, dar de vreme ce rata de penalizare a încrederii este cu mult mai mică decât în cazul unei politici radicale, acesta va ajunge să facă mai multe încercări către acelaşi furnizor înainte ca nivelul său de încredere să ajungă sub pragul ce determină schimbarea furnizorului. Algoritmul folosit de mecanismul propus în această secţiune este sintetizat în figura 4.18 Ca platformă de implementare a acestui sistem am ales Jason (Bordini et al., 2007) deoarece este un limbaj de programare robust pentru sisteme multiagent ce folosesc arhitectura BDI (Bratman, Pollack, & DJ, 1988). Atât clienţii, cât şi depozitele sunt modelate ca agenţi, desi depozitele ar fi putut fi implementate, de asemenea, ca artefacte Cartago (Ricci & Viroli, n d). Reprezentând depozitele prin artefacte, ele ar putea pune la dispozitia agentilor operaţii (spre exemplu, plasarea unei cereri, citirea timpului de aşteptare) şi proprietăţi observabile (spre exemplu, link-ul către un alt depozit care furnizează conţinutul dorit), care ar face comunicarea mai simplă, dar s-ar pierde caracteristica de autonomie.

Identificarea tendintelor prin analiza solicitărilor

Principalul rezultat obtinut prin folosirea modelului propus este o convergenţă rapidă nu a reputaţiilor (ale magazinelor sau clientilor), ci a tendinţelor. Identificarea rapidă a tendinţelor conţinutului dorit de comunitatea clientilor reprezintă o caracteristică utilă în optimizarea utilizării resurselor.

Reputatia si influenta – cel mai renumit stabileste norma

Mecanismul de identificare a conţinutului celui mai popular este următorul. Odată cu cererea, clientul trimite primului furnizor contactat si numele clientului care i l-a recomandat. În acest fel, fiecare furnizor poate face o clasificare a clienţilor săi în funcţie de cât de mult acestia îl promovează. Clientul cel mai fervent în promovarea unui furnizor va deveni clientul pe baza preferintelor căruia furnizorul va selecta ce conţinut va a pune la dispoziţia publicului. Acest model arată modul în care unui utilizator cu un prestigiu mai mare îi sunt acordate privilegii superioare. Cu alte cuvinte, utilizatorul cu cea mai bună reputaţie este cel care stabileste norma.

Personalizare, varietate si disponibilitate

Un aspect important tratat de modelul propus este eficientizarea procesului de distribuire a resurselor. Punerea la dispozitia clienţilor o mare varietate de tipuri de conţinut prin utilizarea unor furnizori foarte specializati, care urmăresc în mod dinamic schimbările din preferintele clientilor este principala calitate a modelului prezentat.

Discutie

Un avantaj semnificativ al scenariul propus este posibilitatea de a analiza cazurile în care competenţa prestatorului de servicii se modifică rapid si într-un mod imprevizibil. În


scenariile clasice, furnizorii de servicii tind să îsi menţină nivelul reputaţiei destul de constant, iar mecanismele de reputaţie nu au de a face cu schimbări atât de rapide.

Figura 4.18- Algoritmul corespunzător aplicării modelului RESPECT pe dispozitive

mobile

Bibliografie

Abdul-Rahman, A., & Hailes, S. (2000). Supporting trust in virtual communities. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences (pp. 9 - 19). IEEE Computer Society.

Abdul-Rahman, Alfarez, & Hailes, Stephen. (1997). A distributed trust model. Proceedings of the 1997 workshop on New security paradigms - NSPW ’97, 48-60. New York, New York, USA: ACM Press. doi:10.1145/283699.283739

Aberer, K, & Despotovic, Z. (2001). Managing trust in a peer-2-peer information system. Proceedings of the tenth international conference on Information and knowledge management (p. 317). ACM. Retrieved from http://portal.acm.org/citation.cfm?id=502638

Aberer, Karl, & Despotovic, Zoran. (2001). Managing Trust in a Peer-2-Peer Information System. Proceedings of the tenth international conference on Information and knowledge management (Vol. Proceeding, pp. 317 - 125).


Bordini, R. H., Hubner, J.F., & Wooldridge, M. J. (2007). Programming multi-agent systems in Agent-Speak using Jason. (John Wiley & Sons, Ed.) (Wiley Seri.). Wiley-Interscience.

Bratman, M., Pollack, M., & DJ, I. (1988). Plans and resource-bounded practical reasoning. Computational Intelligence, 4, 349−355.

Castelfranchi, C. (2000). Engineering social order. In A. Ominici, R. Tolksdorf, & F. Zambonelli (Eds.), Proceedings of Engineering Societies in the Agents World (ESAW’00) (pp. 1–18). Berlin, Germany: Springer- Verlag.

Castelfranchi, C., & Falcone, R. (2002). Social trust: A cognitive approach. Trust and deception in virtual societies, 55--90. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.6870&rep=rep1&type=pdf

EMSE. (2010). http://www.emse.fr/en/.

Esteva, M., Rodriguez-Aguilar, J. A., Sierra, C., Garcia, P., & Arcos, J. (2001). On the formal specification of electronic institutions. Agent mediated electronic commerce, 126–147. Springer.

Fullam, K. K., Klos, T. B., Muller, G., Sabater-Mir, J., Topol, Z., Barber, K. S., Rosenschein, J., et al. (2005). The agent reputation and trust (ART) testbed architecture. Proceeding of the 2005 conference on Artificial Intelligence Research and Development (pp. 389–396). IOS Press.

Grandison, T., & Sloman, M. (2002). Specifying and analysing trust for internet applications. Proceedings of the 2nd IFIP Conference on e-Commerce, e-Business, e-Government (pp. 1-13). Lisbon, Portugal. Retrieved from http://books.google.com/books?hl=en&lr=&id=bGBRqaQOkh0C&oi=fnd&pg=PA145&dq=Specifying+and+Analysing+Trust+for+Internet+Applications&ots=195YGZT2V1&sig=AnCnnmzLFVZeWCtl1J1HNbbm_TM

Hermoso, Ramón, Centeno, Roberto, & da Silva, T. V. (2010). Reputation-based Agreement for Agent Organisations. Principles of Practice in Multi-Agent Systems, 02, 624—631.

Herzig, A., Lorini, E., Hubner, J. F., & Vercouter, L. (2009). A logic of trust and reputation. Logic Journal of IGPL, 18(1), 214-244. doi:10.1093/jigpal/jzp077

Hubner, J. F., Kitio, R., & Boissier, O. (2009). Instrumenting Multi-Agent Organisations with Organisational Artifacts and Agents “ Giving the organisational power back to the agents .” Autonomous Agents and Multi-Agent Systems, 1--32.

Hubner, Jomi Fred, Lorini, Emiliano, Vercouter, Laurent, & Herzig, Andreas. (2009). From cognitive trust theories to computational trust. Proc. of the Twelfth Workshop” Trust in Agent Societies” at AAMAS (p. 55--67).

Hubner, Jomi F., Sichman, J. S., & Boissier, Olivier. (2007). Developing Organised Multi-Agent Systems Using the Moise + Model�: Programming Issues at the System and Agent Levels. International Journal of Agent-Oriented Software Engineering, 1(3/4), 1-27.

Huruiala, P.-C., Urzica, A., & Gheorghe, L. (2010). Hierarchical routing protocol based on evolutionary algorithms for Wireless Sensor Networks. Proceedings of the 9th Roedunet International Conference (RoEduNet) (p. 387--392).


Huynh, D. T., Jennings, N. R., & Shadbolt, N. R. (2004). Fire: An integrated trust and reputation model for open multi-agent systems. ECAI 2004: 16th European Conference on Artificial Intelligence (pp. 18 - 23). Valencia, Spain: Ios Pr Inc.

Huynh, T. (2006). Trust and reputation in open multi-agent systems. Methodology. UNIVERSITY OF SOUTHAMPTON.

Jansson, L. R. A. S. (1996). Simulated Social control for Secure Internet Commerce. Proceedings of the New Security Paradigms Workshop. Lake Arrowhead.

Jones, A. (2002). On the concept of trust. Decision Support Systems, 33(3), 225-232. doi:10.1016/S0167-9236(02)00013-1

Koster, A., Sabater-Mir, J, & Schorlemmer, M. (2009). An interaction-oriented model of trust alignment. Proc. of the 13th Conference of the Spanish Association for Artificial Intelligence, CAEPIA, 655--664. Retrieved from http://www.iiia.csic.es/files/pdfs/eumas.pdf

Krupa, Y., Vercouter, Laurent, Hubner, J., & Herzig, Andreas. (2009). Trust Based Evaluation of Wikipedia ’ s Contributors. Proceedings of the 10th International Workshop on Engineering Societies in the Agents World X (p. 148--161). Springer-Verlag.

LSTI. (2010). http://www.emse.fr/spip/-LSTI-.html.

Marsh, S. (1994). Formalising trust as a computational concept. Computing Science and Mathematics. University of Stirling. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.6243&rep=rep1&type=pdf

Marsh, Stephen. (1992). Trust and reliance in multi-agent systems: A preliminary report. Proceedings of the European Workshop on Modelling Autonomous Agents in a Multi-Agent World (pp. 94–112). Citeseer.

Marsh, Stephen. (1994). Optimism and pessimism in trust. Proceedings of the Ibero-American Conference on, 1-12. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.8948&rep=rep1&type=pdf

Mogos, A.-H., & Urzica, A. (2009). TN4PM - A Textual Notation for Process Modelling. In G. A. Papadopuolous & C. Badica (Eds.), Springer Studies in Computational Intelligence, Proceedings of the 3rd International Symposium on Intelligent Distributed Computing – IDC 2009 (p. 263--241). Springer Berlin / Heidelberg.

Mui, L. (2002). Computational Models of Trust and Reputation�: Agents , Evolutionary Games , and Social Networks Computational Models of Trust and Reputation�: Agents , Evolutionary Games , and Social Networks. Social Networks. Massachusetts Institute of Technology.

Muller, G., & Vercouter, Laurent. (2008). L . I . A . R .: Achieving Social Control in Open and Decentralised Multi-Agent Systems. Journal of Autonomous Agents and Multi-Agent Systems, 1-46.

Neata, S., Urzica, A., & Florea, A. M. (2011). Trust Model for Virtual Organizations. 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.


Network, E. C. C. (2005). Car Rental Contracts. Retrieved from http://ec.europa.eu/consumers/redress/ecc_network/car_rental_report2005.pdf

Pinyol, I., Sabater-Mir, Jordi, & Cuní, G. (2007). How to talk about reputation using a common ontology: From definition to implementation. Proceedings of the Ninth Workshop on Trust in Agent Societies. (p. 90--101). Hawaii, USA. Retrieved from http://www2.iiia.csic.es/~jsabater/Publications/2007-TrustWS.pdf

Rapoport, A. (1989). Prisoner’s dilemma. J. Eatwell, M. Milgate, and P. Newman (eds.): The New Palgrave: Game Theory, 199--204.

Rasmusson, L. And Janson, S. And Boman, M. (1996). Socially Controlled Global Agent Systems.

Rehák, M., & Pvechouček, M. (2007). Trust modeling with context representation and generalized identities. Cooperative Information Agents XI, 298–312. Springer. Retrieved from http://www.springerlink.com/index/3744J788N006Q1J5.pdf

Ricci, A. (2010). CArtAgO By Example version: 2.0. DEIS, Universita di Bologna, Italy (pp. 0-45).

Ricci, A., & Viroli, M. (n.d.). CArtAgO: An infrastructure for engineering computational environments in MAS. Weyns et al.[31]. To appear. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.1163&rep=rep1&type=pdf

Ricci, A., Piunti, M., Viroli, M., & Omicini, A. (2009). Environment Programming in CArtAgO. (Rafael H Bordini, M. Dastani, J. Dix, & A. El Fallah Seghrouchni, Eds.)Communication, 1-31. Springer. doi:10.1007/978-0-387-89299-3

Sabater, J., & Sierra, C. (2001). REGRET: A reputation model for gregarious societies. Proceedings of the fifth international conference on Autonomous agents (pp. 475-482).

Sabater, Jordi, & Sierra, Carles. (2005). Review on Computational Trust and Reputation Models. Artificial Intelligence Review, 24(1), 33-60. doi:10.1007/s10462-004-0041-5

Schillo, M. And Funk, P. And Rovatsos, M. (2000). Using Trust for Detecting Deceitful Agents in Artificial Societites. Applied Artificial Intelligence, 14(8), 825--848.

Sen, S. (2002). Believing others: Pros and cons. Artificial Intelligence, 142(2), 179-203. Published by the IEEE Computer Society. doi:10.1016/S0004-3702(02)00289-8

Silva, V. da, Hermoso, R, & Centeno, R. (2009). A hybrid reputation model based on the use of organizations. Coordination, Organizations, Institutions and Norms in Agent Systems IV, 02, 111--125.

da Silva, V., Hermoso, Ramón, & Centeno, Roberto. (2010). A hybrid reputation model based on the use of organizations. Coordination, Organizations, Institutions and Norms in Agent Systems IV, 02, 111–125. Springer. Retrieved from http://www.springerlink.com/index/F7T8T37565703767.pdf

Streetcar. (2011). . Retrieved from http://www.streetcar.co.uk/

Tanase, C., & Urzica, A. (2009). Global Military Conflict Simulator. In G. A. Papadopuolous & C. Badica (Eds.), Springer Studies in Computational Intelligence, Proceedings of the 3rd


International Symposium on Intelligent Distributed Computing – IDC 2009 (Vol. 237/2009, pp. 313 - 318). Springer Berlin / Heidelberg.

Teacy, L., Patel, J., Jennings, N., & Luck, M. (2005). Coping with inaccurate reputation sources: Experimental analysis of a probabilistic trust model. Proceedings of the 4th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS) (pp. 997–1004). ACMPress. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.4441&rep=rep1&type=pdf

Urbano, J., Rocha, A. P., & Oliveira, E. (2009). A Trust Aggregation Engine that Uses Contextual Information. Proc. of EUMAS.

Urzica, A. (2010). Distributed Reputation Extraction in Multi-Agent Systems. In T. Balke & R. Yaich (Eds.), Proceedings of the 12th European Agent Systems Summer School Student Session, EASSS 2010 (pp. 6-12). ISSN 1864-9300.

Urzica, A., & Tanase, C. (2009). Mapping BPMN to AUML: Towards and Automatic Process. Proceedings of the 17th International Conference of Control Systems and Computer Science, MASTS 2009 Workshop (p. 539--547).

Urzica, A., & Tanase, C. (2010). Bridging the Gap Between Business Experts and Software Agents:BPMN to AUML Transformation. U.P.B. Scientific Bulletin, 72(4).

Urzica, A., Mogos, A.-H., & Florea, A. M. (2010). An Economy Model Based on Barter Exchanges between Software Agents. Springer Studies in Computational Intelligence, Proceedings of the 4th International Symposium on Intelligent Distributed Computing – IDC 2010, MASTS 2010 Workshop, 16-18 September 2010 (p. 295--304). Tangier, Morocco: Springer.

Urzica, A., Mogos, A.-H., & Florea, A. M. (2011). A Reputation based Negotiation Model for Barter Transactions between Software Agents. International Journal on Artificial Intelligence Tools (IJAIT).

Urzica, A., Neata, S., & Florea, A. (2011). Contextual Reputation Extraction for Trust Decision in MAS. Proceedings of the 18th International Conference of Control Systems and Computer Science (p. 729 -- 735). Politehnica Press.

Vázquez-Salceda, J., & Dignum, F. (2003). Modelling electronic organizations. Multi-Agent Systems and Applications III, 1070–1080. Springer.

Yu, B., & Singh, M. P. (2001). Towards a Probabilistic Model of Distributed Reputation Management. Proceedings of the Fourth Workshop on Deception, Fraud and Trust in Agent Societies (p. 125--137).

Yu, B., & Singh, M. P. (2002). An Evidential Model of Distributed Reputation Management. Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-02) (p. 294--301). Bologna, Italy.

Yu, Bin, & Singh, Munindar P. (2002). Distributed Reputation Management for Electronic Commerce. Computational Intelligence, 535–549.

Etapa 4: Realizarea platformei integrate - AIMAS...

Documents

Transcript of Etapa 4: Realizarea platformei integrate - AIMAS...