Post on 23-Oct-2015
description
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)
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm
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
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm
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.
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm
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]";
GlobalCounter.Increment();
myAgent.windowsForm.AddTextLine(GlobalCounter.Get() + " " +
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);
GlobalCounter.Increment();
myAgent.windowsForm.AddTextLine(GlobalCounter.Get() + " " +
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:
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm
6
case ACLMessage.PROPOSE:
//received a proposal from the participant
GlobalCounter.Increment();
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);
GlobalCounter.Increment();
myAgent.windowsForm.AddTextLine(GlobalCounter.Get() + " " +
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
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm
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ţ.
Modelarea si analiza sistemelor multi-agent - Laboratorhttp://florinleon.byethost24.com/lab_masma.htm