Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria – Sede di Modena
Corso di Laurea in Ingegneria Informatica – Nuovo Ordinamento
Protocolli di negoziazione
per agenti intelligenti
Relatore:
Prof. Sonia Bergamaschi
Anno Accademico 2002-2003
Candidato:
Serena Sorrentino
Agenti
Definizione : entità computazionali capaci di agire in modo
autonomo, prelevando informazioni dall’ambiente in cui si
trovano, ed agendo secondo la propria base di conoscenze allo
scopo di scambiare informazioni con altri agenti e di
raggiungere determinati obbiettivi.
Caratteristiche :
-Autonomia
-Abilita’ sociale
-Reattività
-Proattività
Un agente intelligente
in particolare è dotato
di autonomia di
capacità di
collaborazione e di
apprendimento.
Multi-Agent System (MAS): è un sistema in cui gli agenti
intelligenti interagiscono fra di loro allo scopo di soddisfare un
certo insieme di compiti.
Negoziazione e Protocolli
Negoziazione
La negoziazione è l'insieme di attività ed operazioni (processo) che
permettono a due o più soggetti (negoziatori), ognuno con un
interesse economico privato da perseguire (funzione di utilità), di
scambiarsi opinioni (offerte e contro-offerte) nel rispetto un insieme
di regole condivise (protocollo di negoziazione) con lo scopo di
arrivare ad un accordo finale
Protocollo di negoziazione
Il protocollo di negoziazione ha il compito di coordinare gli agenti e
di controllare il rispetto delle regole di negoziazione. In particolare
rappresenta l’insieme delle regole che governano l’interazione.
Contract Net Protocol (CNP)
Introdotto da Smith nel 1980, specifica le interazioni fra gli
agenti per realizzare una negoziazione automatizzata attraverso
l’uso di contratti per l’allocazione dei task. Si basa su una rete di
nodi indipendenti.
Caratteristiche :
- il processo di negoziazione è locale
- non vi è un’unità centrale di controllo
- esistono due direzioni di scambio per le informazioni
- ogni nodo (agente) valuta le informazioni in modo soggettivo
dalla propria prospettiva
- l’accordo è ragiunto attraverso una mutua selezione.
Due negoziatori:
Manager
Contractor
CNP Come funziona
Annuncio
Offerta
Manager
Contractor
Assegnazione
FIPA Contract Net Interaction
Protocol
FIPA: organizzazione senza scopo di lucro con l’obbiettivo di definire
uno standard riguardante le tecnologie legate agli agenti.
Ha definito una specifica per il Contract Net Interaction Protocol
(CNIP) che rappresenta la più fedele estensione del CNP.
Quattro fasi principali:
1-L’iniziatore (manager) invia una call for proposal (CFP) ai
partecipanti
2-Ogni potenziale partecipante analizza la CFP e, se vuole, fa una
proposta
3-L’iniziatore analizza le proposte e sceglie la più vantaggiosa
4-L’iniziatore si preoccupa di rifiutare le altre offerte
Esempio
Un agente iniziatore
-ha il compito di produrre 100 unità del prodotto A
-è disposto a pagare al massimo 5,00 euro per ogni
unità di A
-il tempo di consegna è per le ore 14,00
Quattro partecipanti : P1, P2, P3, P4
Esempio
CFP
P1
Initiatore
P2
P3
P4
Esempio
Rifiuta
Initiatore
P1
P2
Propone
3.50/unità
P3
Propose 4.00/unità
P4
Esempio
Initiatore
P1
Rifiuto Proposta
Accetta
Proposta
P2
P4
Esempio
P1
Initiatore
Inform
Done
P2
P3
P4
Protocolli di negoziazione estesi (1)
Gli agenti sono entità self-interested (SI): agiscono perseguendo
i propri interessi
-negoziazione competitiva
-problema di allocazione dei task globale e locale
Calcolo dei costi marginali nella gestione dei task
Commitment: accordo stipulato fra due agenti che li vincola ad un
potenziale contratto
-commitment multi livello
-decommitment
Gli agenti sono entità limitate razionalmente
-ambiente aperto
-costo risorse computazionali
Protocolli di negoziazione estesi (2)
Gli agenti possono contro proporre
Contratti multi agente cioè tra più di due
Problema della congestione
Protocolli di negoziazione task-swap
Raggruppamento di task in unità atomiche per la negoziazione
Contratto individualmente razionale (IR)
Nuovi meccanismi
multi-linked
-Negoziazione fra più agenti riguardo a più elementi in relazione
tra loro.
-Algoritmi per l’allocazione ottima dei task e l’assegnamento ottimo
per ciascun attributo
multi-leveled
-la negoziazione si sviluppa su su due livelli, molto utile in caso
di negoziazione multi-task
-primo livello: informazioni di alto livello, definizione “grezza” dei
commitment, determinazione costi di decommitment.
-secondo livello: analisi dettagliata dei task candidati
“raffinamento” dei commitement
multi-step
-serie di cicli di proposte e contro proposte fra gli agenti
-scopo: raggiungere soluzioni sempre migliori
Conclusioni
Ogni tipologia di protocollo presenta vantaggi e svantaggi e
svantaggi a seconda delle condizioni di allocazione dei task
Una possibile soluzione sta nella scelta dinamica del protocollo da
adottare
Bilanciamento fra i costi e i guadagni di una negoziazione
Sviluppi futuri:
-maggiore standardizzazione
- interdipendenza fra le tecniche studiate
possibile integrazione