Sisteme multiagent. Alocarea task-urilor prin protocolul Contract Net

1

Modelarea şi analiza sistemelor multiagent Laboratorul 5

Alocarea task-urilor prin protocolul Contract Net

1. Aspecte generale .............................................................................................................................. 1

2. FIPA Contract Net Interaction Protocol........................................................................................... 1 2.1. Descrierea protocolului ............................................................................................................. 1 2.2. Excepţii de la execuția normală a protocolului ......................................................................... 3

3. Exemplificare printr-o aplicație ....................................................................................................... 4

4. Aplicaţie ........................................................................................................................................... 7

1. Aspecte generale

Algoritmul Contract Net Protocol stabilește interacțiuni între agenți, în cadrul cărora aceștia pot

juca dinamic două roluri: manager şi contractor. Fiind dată o problemă ce trebuie rezolvată, un

agent determină mai întâi dacă ea poate fi descompusă în subprobleme ce pot fi rezolvate în paralel

(concurent). Se utilizează Contract Net Protocol pentru a anunţa transferul acestor subprobleme

către noduri şi a primi de la aceste noduri informaţii privind modalităţile prin care se pot rezolva

subproblemele. Un nod care primeşte un anunţ relativ la o subproblemă trimite înapoi un răspuns,

indicând cât de bine crede el că va rezolva acea subproblemă. Contractorul colectează aceste

anunţuri şi distribuie subproblemele către cele mai bune noduri. La baza Contract Net Protocol se

află o metodă de coordonare pentru alocarea problemelor care permite agenţilor să liciteze pentru

mai multe subprobleme în acelaşi timp şi asigură un echilibru al încărcării acestora cu subprobleme

(nu este necesar ca agenţii ocupaţi să liciteze).

2. FIPA Contract Net Interaction Protocol

2.1. Descrierea protocolului

FIPA Contract Net Interaction Protocol (IP) este o variantă puţin modificată a versiunii iniţiale a

algoritmului Contract Net, în sensul că adaugă acţiunile de respingere şi confirmare în cadrul

procesului de comunicare. În cadrul Contract Net IP, un agent iniţiator va prelua rolul de manager

care doreşte să delege sarcini către unul sau mai mulţi agenţi participanţi. Inițiatorul doreşte să

optimizeze execuţia sarcinii respective, în sensul de a o efectua cu costuri cât mai scăzute. Acest

aspect este de obicei exprimat ca preţ, timp de finalizare, distribuirea echitabilă a sarcinilor etc.

Pentru o sarcină dată, la solicitarea inițiatorului, orice agent participant poate răspunde cu o

propunere sau poate refuza. Negocierile vor continua cu participanţii care au trimis o propunere.

Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm

2

Fig. 1. Protocolul FIPA Contract Net

În Fig. 1 se prezintă interacțiunea dintre un agent inițiator și un participant. Desigur, în sistem

pot fi mai mulți agenți din ambele categorii, însă între fiecare pereche inițiator-participant

comunicarea se desfașoară, conform diagramei din Fig. 1, astfel:

(a) - Agenții inițiatori trimit participanților mesaje de tip Call for Proposals, unde solicită de la

aceștia soluții de rezolvare a unor probleme.

Initiator Participant

Call for Proposals (CFP)

deadline

refuse

propose

reject-proposal

accept-proposal

failure

inform-done

inform-result

(a)

(b)

(c)

(d)


3

(b) - Agenții participanți pot răspunde cu o propunere sau pot refuza acest lucru (caz în care

comunicarea se încheie). De exemplu, într-un sistem tranzacțional, participanții propun sau refuză

trimiterea de propuneri dupa cum se pot sau nu conforma criteriilor impuse în Call for Proposals

(ex. nu pot furniza anumite bunuri, sau nu le pot vinde sub un anumit preț etc.).

(c) - Inițiatorii evalueaza propunerile primite și decid care din acestea sunt acceptabile. Criteriile

conform cărora propunerile corespund nevoilor inițiatorilor variază de la caz la caz. Inițiatorii trimit

participanților mesaje de acceptare sau respingere a propunerii, după caz.

(d) - Patricipanții cărora le-au fost acceptate propunerile trebuie acum să ducă la îndeplinire

sarcinile aferente. Ei vor răspunde inițiatorilor cu mesaje de confirmare a reușitei sau eșecului

ducerii la bun-sfarșit a propunerii, după caz.

Interacţiunea poate fi identificată în mod unic printr-un parametru conversation-id asignat de

iniţiator. Acest lucru permite fiecărui agent să gestioneze comunicarea: de exemplu, permite unui

agent să identifice conversaţiile cu un anumit agent iniţiator.

2.2. Excepţii de la execuția normală a protocolului

În orice moment al comunicării, receptorul mesajului poate informa expeditorul că nu a înţeles

ce a fost comunicat. Acest lucru este realizat prin returnarea unui mesaj not-understood.

Fig. 2. FIPA Cancel Meta Protocol

Comunicarea faptului că nu s-a înţeles ce s-a recepționat în cadrul unui protocol de interacţiune

poate implica faptul că orice angajamente asumate în timpul interacţiunii nu sunt valabile. Acest

lucru poate duce la rezilierea întregului protocol sau numai a comunicării cu agentul de la care s-a

primit mesajul not-understood.

Initiator Participant

cancel (canceled-communicative-act)

inform-done

failure


4

3. Exemplificare printr-o aplicație

Aplicația AgentProtocol asociată laboratorului implementează interacțiunea dintre un agent

Initiator și unul de tip participant. Desigur, programul poate fi ușor extins prin adaugarea altor

inițiatori / participanți. Comunicarea dintre cei doi agenți urmărește îndeaproape schema din Fig. 1.

Sistemul de luare de decizii al celor doi agenți este implementat în cazul cel mai general.

Fiecare agent se poate conforma cerințelor impuse de protocol cu o anumită probabilitate, stabilită

prin intermediul unor proprietăți din clasele aferente celor două tipuri de agenți. De exemplu,

initiatorAgent are o probabilitate de a accepta o propunere trimisă de participantAgent

specificată prin intermediul proprietății probabilityToAcceptProposal. În cazuri concrete, această

decizie va depinde de diverși factori (de exemplu, prețul propus de participant în cardul unei

tranzacții sau disponibilitatea anumitor produse). participantAgent poate decide în mod similar

cum va răspunde la mesajele de tip Call for Proposals sau accept-proposal are inițiatorului.

JADE dispunde de propriile mecanisme de identificare a tipurilor de mesaje din sistem,

mecanisme care sunt conform cu standardele FIPA (Foundation for Intelligent Physical Agents).

Concret, tipul de mesaj se identifica prin intermediul performativelor (engl: performative).

Acestea sunt implementate prin intermediul unor constante statice întregi definite în clasa

ACLMessage. pentru un obiect de tip ACLMessage, performativa aferentă se poate specifica în

constructor sau utilizând metoda setPerformative(int), și se poate identifica prin metoda

getPerformative().

Inițial, agentul initiatorAgent trimite, în cadrul unui comportament de tip InitiatorSend, un

mesaj de tip Call for Papers, cu performativa ACLMessage.CFP. Metoda action() din cardul

comportamentului arată astfel (codul este practic identic în C# si Java):

public override void action()

{

//send call for proposal to the participant

ACLMessage m = new ACLMessage(ACLMessage.CFP);

string stringToDisplay = "Sending to ";

AID receiverAID = new AID("participantAgent1", AID.ISLOCALNAME);

m.addReceiver(receiverAID);

myAgent.send(m);

stringToDisplay += receiverAID.getLocalName() + " message: [Call for

Proposals]";

GlobalCounter.Increment();

myAgent.windowsForm.AddTextLine(GlobalCounter.Get() + " " +

stringToDisplay);

}

Clasa GlobalCounter servește la numerotarea mesajelor din sistem, pentru ca ordinea în care

sunt trimise să fie mai ușor de urmărit în interfața cu utilizatorul.


5

Agentul participantAgent execută un comportamentul de tip ciclic ParticipantReceive, în

cardul căruia așteaptă mesaje de la initiatorAgent și îi răspunde acestuia. Mesajele nenule primite

sunt prelucrate într-o instrucțiune switch, unde se verifică performativa mesajului m primite de la

initiatorAgent:

switch (m.getPerformative())

{

//...

De exemplu, în cazul în care mesajul primit are performativa ACLMessage.CFP, adică

initiatorul a trimis un mesaj de tip Call for Proposals (Fig. 1(a)), participantAgent decide, în case-ul

corespunzător, daca să trimită sau nu o propunere:

case ACLMessage.CFP: //received call for proposals from initiator

stringToDisplay += "Received from " + senderName + " message: [Call For

Proposals]";



stringToDisplay);

stringToDisplay = "Replying to " + senderName + " with message: ";

// decide whether or not to send a proposal to the initiator

if (Probability.Validate(myAgent.probabilityToSubmitProposal) == true)

{

reply = new ACLMessage(ACLMessage.PROPOSE);

stringToDisplay += "[PROPOSE]";

}

else

{

reply = new ACLMessage(ACLMessage.REFUSE);

stringToDisplay += "[REFUSE]";

}

reply.addReceiver(senderAID);

myAgent.send(reply);



stringToDisplay);

break;

În mod similar se tratează și celelalte cazuri, când mesajul primit este de tip

ACLMessage.ACCEPT_PROPOSAL sau ACLMessage.REJECT_PROPOSAL.

La rândul său, agentul initiatorAgent răspunde mesajelor trimise de participant în cardului

propriului comportament ciclic InitiatorReceive. Mesajele primite se identifică în același mod (un

switch care primește ca parametru performativa mesajului primit). De exemplu, la trimiterea de

către initiator a mesajului Call for Proposals, participantul îi poate răspunde cu un mesaj

ACLMessage.PROPOSE. În acest caz, inițiatorul decide dacă propunerea îi convine sau nu și

trimite răspunsul corespunzător deciziei luate:


6

case ACLMessage.PROPOSE:

//received a proposal from the participant


stringToDisplay += GlobalCounter.Get() + " " + "Received from " +

senderName + " message: [PROPOSE]";

myAgent.windowsForm.AddTextLine(stringToDisplay);

stringToDisplay = "Replying to " + senderName + " with message: ";

ACLMessage reply = null;

//decide if to accept the proposal

if (Probability.Validate(myAgent.probabilityToAcceptProposal) == true)

{

reply = new ACLMessage(ACLMessage.ACCEPT_PROPOSAL);

stringToDisplay += "[ACCEPT_PROPOSAL]";

}

else

{

reply = new ACLMessage(ACLMessage.REJECT_PROPOSAL);

stringToDisplay += "[REJECT_PROPOSAL]";

}

reply.addReceiver(senderAID);

myAgent.send(reply);



stringToDisplay);

break;

În Fig. 3 se prezintă un exemplu de execuție a aplicației. Cazul prezentat este cel în care

participantul răspunde inițiatorului cu o propunere pe care acesta o acceptă. Ulterior, participantul

soluționează cu succes propunerea.

Fig. 3. Unul din posibilele rezultate ale execuției aplicației AgentProtocol


7

4. Aplicaţie

4.1. Să se creeze un market virtual alcătuit dintr-un număr de agenţi cumpărători şi un număr de

agenţi vânzători. Să se implementeze protocolul FIPA Contract Net Interaction prezentat mai sus.

vânzătorii vor avea o listă de produse cu anumite cantităţi şi preţuri (se vor înregistra în

“Pagini Aurii”). Vor avea un preţ maximal şi unul minimal şi un algoritm de discounturi

(de exemplu pentru mai mult de 5 produse de tip A o reducere de 2%, dar nu mai puţin

de preţul minim). După vânzare stocurile aferente respectivului produs vor scădea.

vânzătorii vor accepta cererea doar dacă pot să o satisfacă (de exemplu au cantitatea

respectivă în stoc sau cu o anumită probabilitate), altfel o vor refuza.

cumpăratorii vor putea face anunţul despre produs/cantitate dorită, căutând vânzătorii în

“Pagini Aurii”.

cumpărătorii vor avea o listă de produse din care vor alege aleator un produs-cantitate pe

care doresc să o achiziţioneze, şi vor face periodic câte un anunţ de achiziţie. Un nou

anunţ se va putea face doar după ce achiziţia în curs s-a finalizat (primesc notificare de

la câştigătorul licitaţiei că marfa a fost livrată inform-done sau task-ul a eşuat failure).

Criteriul de stabilire a câştigătorului licitaţiei va fi cel mai mic preţ.


Sisteme multiagent. Alocarea task-urilor prin protocolul Contract Net

Documents

Transcript of Sisteme multiagent. Alocarea task-urilor prin protocolul Contract Net