Problemi di scheduling multi-agente
description
Transcript of Problemi di scheduling multi-agente
Problemi di scheduling multi-agente
Alessandro Agnetis, Università di Siena
Gianluca De Pascale, Università di Siena Pitu B. Mirchandani, University of ArizonaDario Pacciarelli, Università di Roma TreAndrea Pacifici, Università di Roma Tor
VergataMarco Pranzo, Università di Siena
Alessandria, 16 marzo 2007
Problemi multi-agente
• Diversi agenti competono per l’utilizzo di un insieme limitato di risorse produttive o logistiche
• Per raggiungere un accordo, gli agenti possono negoziare l’utilizzo della risorsa
• Un eventuale soggetto centrale può avere parte attiva nel problema o essere solo un coordinatore
• Treni in competizione per l’utilizzo di binari [Brewer e Plott 1996]
• Job di diversi ordini che competono per l’uso di slot temporali su una macchina --- agenti autonomi [Kutanoglu e Wu 1999, Wellman et al. 2001]
• AGV in competizione su una rete [Huang e Hallam 1995]
• Tipi diversi di segnali (dati, voce) che competono per le stesse risorse radio [Arbib et al. 2002]
Problemi di scheduling con due agenti
• Due agenti, A e B, possiedono ciascuno un set di job che richiedono determinate risorse di processamento
• Gli agenti possiedono ciascuno una funzione di costo f A() and f B() rispettivamente
• Ogni funzione di costo dipende soltanto dai job del rispettivo agente
Problemi multi-agente: aspetti
• Situazione iniziale• Possibilità e modalità di
scambio delle informazioni tra agenti
• Possibilità di compensazioni/scambi di utilità tra agenti
Situazione iniziale: scenari
• Esiste una allocazione iniziale rispetto alla quale solo un insieme limitato di riallocazioni è possibile (es. orario ferroviario)
• Non esiste alcuna situazione iniziale, tutti gli agenti si presentano contemporaneamente e hanno uguale priorità
Scambi di informazione: scenari
• Tutti gli agenti possono comunicare direttamente tra loro informazioni complete riguardanti i propri job e le proprie utilità
• Esiste un protocollo di comunicazione e offerta (e.g. aste)
• Ciascun agente comunica solo con un sottoinsieme di agenti o con un coordinatore
Trasferimenti di utilità: scenari
• L’utilità degli agenti e i rapporti relativi sono tali da consentire una redistribuzione dell’utilità (e.g. in termini monetari)
• L’utilità degli agenti è espressa in termini che non ne consentono una redistribuzione immediata (e.g. diverse funzioni obiettivo)
Modelli multi-agente
• Giochi cooperativi: sequencing games
• Aste:– Wellman et al. (asta ascendente
parallela)– Kutanoglu-Wu (asta combinatoria)
• Bargaining problems: estensione dei concetti di soluzioni di Nash e Kalai Smorodinski
Sequencing games
• Sono particolari giochi cooperativi ad utilità trasferibile
• Si studiano situazioni di sequenziamento in cui, a partire da uno schedule iniziale 0, i giocatori possono formare coalizioni per rischedulare i loro job in modo proficuo senza danneggiare gli altri giocatori
• In molti casi, il nucleo è non vuoto [Curiel, Pederzoli and Tijs 1989, Slikker 2003]
2. MARKET ORIENTED PROGRAMMING
Aste - Market Oriented Programming
• La situazione è rappresentata da un modello di tipo economico [Wellman, Walsh, Wurman, Mc-Kie Mason 2002]
• Gli agenti si muovono in un mercato i cui beni sono i periodi di utilizzo delle risorse
• La comunicazione è limitata alle offerte che ciascun agente formula per le risorse
Market Oriented Programming - II
• Gli agenti formulano le proprie offerte sulla base di valutazioni individuali
• Le uniche informazioni scambiate sono nel formato di prezzi e avvengono tra agenti e un coordinatore (automatico)
• L’analisi studia le relazioni tra equilibrio e ottimalità
Modello di scheduling
• Un insieme G di n time slot• Un insieme A di agenti compreso
l’agente “venditore” F0
• Un vettore [p1, p2,…, pn] di prezzi per i vari time slot
• Per ogni XG, un valore vj(X) che l’agente j attribuisce a X
• I job sono interrompibili
Modello di scheduling
• Ciascuna risorsa i ha un reserve price qi, che rappresenta il valore della risorsa per il sistema se non viene allocata
• Il valore globale di un’allocazione è
0 1
)()(Fi
m
jjji Fvqfv
Allocazione ottima
• Una allocazione f è ottima se il suo valore globale è massimo
• L’ottimalità di una soluzione dipende soltanto dall’allocazione f e dai valori wj, non dai prezzi a cui le risorse possono essere acquisite
Prezzi e agenti
• Dato un vettore p di prezzi, la quantità Hj(p) misura il massimo guadagno che l’agente j può conseguire
Xiij
GXj pXvpH )(max)(
Equilibrio
• Un’allocazione f è in equilibrio per un vettore p di prezzi se:
1)
(ossia, ogni agente consegue il massimo guadagno)
jFi
ijjj pFvpH )()(
Equilibrio
2) pi qi per ogni slot i allocato
pi = qi per ogni slot i non
allocato
(ossia, anche l’agente “venditore” ha un vantaggio)
Esempio
w1=16d1 =3L1=2
0 1 2 3 4 5 6 7 8
w2=10d2 =4L2=2
w3=6d3 =2L3=1
w4=14,5d4 =8L4=4
€6,25
pi
qi = € 3
€6,25
€6,25
€3,25
€3,25
€3,25
€3,25
€3,25
Esempio
w1=16d1 =3L1=2
0 1 2 3 4 5 6 7 8
w2=10d2 =4L2=2
w3=6d3 =2L3=1
w4=14,5d4 =8L4=4
w1=16d1 =3L1=2
w2=10d2 =4L2=2
w4=14,5d4 =8L4=4
pi €6,25
€6,25
€6,25
€3,25
€3,25
€3,25
€3,25
€3,25
qi = € 3
Equilibrio e ottimalità
Teorema [Bikhchandani e Mamer 1997, Gul e Stacchetti 1999, Wellman et al. 2001]:Se esiste un sistema di prezzi p per cui f è in equilibrio, allora f è ottima
Il viceversa in generale non è vero
Esempio
w1=3d1 =2L1=2
0 1 2
w2=2d2 =2L2=1
qi = € 0
Allocazione ottima
w1=3d1 =2L1=2
0 1 2
w2=2d2 =2L2=1
qi = € 0
w1=3d1 =2L1=2
p1 p2
Equilibrio e ottimalità
• Perché f sia in equilibrio, per l’agente 2 deve essere conveniente non comprare nulla
• Questo si ha solo se p1 2 e p2 2
• Ma allora non può essere in equilibrio per l’agente 1 !
Equilibrio e ottimalità
• Le due condizioni sono equivalenti nel caso più particolare di job unitari
• Anche nel caso multiple-deadline
Analisi dei protocolli di asta
• Come si può raggiungere una soluzione di equilibrio da parte di agenti distribuiti?
• Meccanismi di asta• Esempio: l’asta ascendente
Asta ascendente
• Gli agenti formulano in modo asincrono offerte per ciascuno slot i
• Se l’offerta corrente è i , l’offerta successiva deve essere pari ad almeno
i =i + (ask price)
• Quando non ci sono più offerte, la risorsa è allocata al miglior offerente
Comportamento degli agenti
• Ciascun agente offre il valore i per alcune risorse, in modo da massimizzare il proprio surplus
• L’asta ascendente raggiunge un equilibrio?
Esempio
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
w3= € 2,5d3 =3L3=1
Prezzo corr. 0 0 0
Offerta agente 2
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
Prezzo corr. 0 0 0Prezzo corr. 0 1 1
w2= € 2,5d2 =3L2=1
w2= € 8d2 =3L2=2
Prezzo corr. 0 1 1Prezzo corr. 1 2 1
Offerta agente 1
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
w2= € 2,5d2 =3L2=1
w2= € 8d2 =3L2=2
Prezzo corr. 1 2 1Prezzo corr. 1 2 2
Offerta agente 3
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
w2= € 2,5d2 =3L2=1
w2= € 8d2 =3L2=2
Prezzo corr. 1 2 1Prezzo corr. 1 2 2
Offerta agente 2
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
w2= € 2,5d2 =3L2=1
w2= € 8d2 =3L2=2
Prezzo corr. 2 2 3
• L’agente 3 esce di scena• Perché un sistema di prezzi sia
in equilibrio, dev’essere p3 2
• Ad esempio:
p1= 8 p2 = 8 p3 = 1
Equilibrio
w1= € 20d1 =2L1=2
0 1 2
w2= € 8d2 =3L2=2
qi = € 0, = € 1
3
w2= € 2,5d2 =3L2=1
w2= € 8d2 =3L2=2
Prezzo 8 8 1
Convergenza di un’asta
• L’asta ascendente può non raggiungere un equilibrio, anche se esiste
• Può raggiungere un’allocazione arbitrariamente lontana dall’ottimo
• Nel caso di job unitari, la distanza tra il valore di un’allocazione ottima e quella generata dall’asta è limitata (k+1)
3. KUTANOGLU - WU
Aste – modello di Kutanoglu-Wu
• Il sistema è un job shop• Un insieme di agenti, ognuno dei
quali possiede un job, che richiede l’utilizzo di alcune macchine per alcuni time slot
• I job sono non interrompibili• Un coordinatore centrale gestisce
l’asta combinatoria
Kutanoglu-Wu (II)• A ogni iterazione, ogni slot su ogni
macchina ha un prezzo• In base ai prezzi di ogni slot/macchina
(k,t), e in base alla propria funzione di utilità, ogni agente, risolvendo un problema di ottimizzazione, formula la propria migliore offerta
))((max)(
iBU iiB
Kutanoglu-Wu (III)• Il banditore raccoglie dunque tutte le
offerte, le elabora e annuncia i nuovi prezzi delle risorse
• Lo scopo del banditore è di convergere verso uno schedule ammissibile, per cui i prezzi delle risorse più contese vengono aumentati in misura del livello di conflitto:
N
iiktktD
1
1*
Kutanoglu-Wu (III)
• Ad esempio, l’aggiornamento dei prezzi può realizzarsi attraverso un semplice meccanismo di proporzionalità, ossia
ktr+1 = kt
r + s Dkt
Kutanoglu-Wu (IV)
• Il procedimento va avanti fino a raggiungere un criterio di arresto
• Lo schedule risultante può non essere ammissibile
• Obiettivo globale non monotono• Il comportamento può variare
molto a seconda del pricing scheme e del protocollo usato (regola usata per aggiornare i prezzi)
4. BARGAINING
Bargaining problems
• Due giocatori, A e B, devono scegliere uno di un insieme X di possibili agreements
• I giocatori possono comunicare, ma non possono trasferirsi utilità
• Questi giochi modellano le situazioni di negoziazione
Bargaining problems (II)
• La soluzione di un bargaining problem è un agreement che soddisfa certe proprietà (assiomatiche) che ne fanno un particolare candidato a essere il risultato del processo di negoziazione
Bargaining problems (III)
• A e B sono “razionali”, i.e., hanno funzioni di utilità (o anche value functions) uA(x), uB(x) definite su X che soddisfano gli assiomi di von Neumann-Morgenstern
• D è il disagreement point (dominato da tutti gli altri punti di X)
Bargaining problems (IV)
• La teoria della negoziazione studia in che modo il risultato finale della negoziazione dipende dai parametri del problema e/o dal comportamento dei giocatori
• In particolare, la soluzione di Nash tiene conto dell’utilità dei giocatori e dunque del loro atteggiamento rispetto al rischio
Soluzione di Nash
• La soluzione di Nash può caratterizzarsi in termini delle preferenze dei giocatori sull’insieme delle lotterie aventi come premi gli elementi di X
• La soluzione di Nash x* è un’alternativa rispetto alla quale nessuno dei due giocatori ha abbastanza incentivi a deviare
Soluzione di Nash
• È un agreement x* tale che, se esiste un agreement x e una probabilità p tale che il giocatore A preferisce
L = < p, x; 1-p, d >a x*,allora il giocatore B preferisce
L = < p, x*; 1-p, d >a x
Soluzione di Nash
• Date le funzioni di utilità dei due giocatori, la soluzione di Nash x* è tale cheuA(x*) uB(x*) ≥ uA(x) uB(x)
per ogni xX• La soluzione di Nash è unica
se X è compatto e convesso
Soluzione di Nash
• Se X non è compatto e convesso (e.g. un insieme discreto), il concetto di soluzione di Nash può ancora definirsi come soluzione che massimizza il prodotto delle utilità, ma può non essere unica
d*
Af
Bf (dA,dB) *
arg max ( ) ( )A A B BNash d f d f
*
* *
**
**
*
**
* *
*
**
*
*
*
* *
*
*
*
*
*
*
**
*
**
Non appartiene necessariamente alla frontiera efficiente
S
Soluzione di Nash - dominio discreto
Altri concetti di soluzione• La soluzione di Nash fa riferimento
a una caratterizzazione dei decisori basata sul loro atteggiamento rispetto al rischio (value function)
• Consideriamo il caso di decisori indifferenti al rischio (relativamente al valore dell’indice di costo)
Equità e vantaggio globale
• Un punto di vista diverso confronta la situazione migliore e quella peggiore in assoluto per i due decisori (tipicamente la migliore per A è la peggiore per B e viceversa)
• Siano zA* , zB
* ,zA0, zB
0 , i valori ottimi e quelli peggiori per i due giocatori
Equità e vantaggio globale
• Data una qualsiasi soluzione di valore zA e zB per i due agenti, si può osservare come si situa rispetto agli estremi:
*
*)( 0
AA
AAA
zz
zzr
*
*)( 0
BB
BBB
zz
zzr
Equità e vantaggio globale
• I due valori rA e rB indicano a quanto ciascun giocatore sta rinunciando rispetto alla situazione in cui è da solo
• Dunque, si vuole che rA e rB siano piccoli (qualità globale) ma anche che siano il più possibile vicini (equità)
Equità e vantaggio globale
• Siamo interessati a trovare i due schedule A e B tali che:
)()(
)(min)(
BA
AA
rr
rr
)()(
)(min)(
AB
BB
rr
rr
Equità e vantaggio globale
• La soluzione di Kalai Smorodinski (nel discreto) è definita come quello schedule KS tale che
r(KS) = min {rA (, rB
(}
(dA,dB) *
Af
Bf
1
1
B
Af
Bf (dA,dB) *
*
* *
*
*
*
*
*
**
*
*
*
**
*
*
***
*
** **
*
*
**
*
*
Soluzione di Kalai-Smorodinsky - dominio
discretoA
Non appartiene necessariamente alla frontiera efficiente
Scheduling bargaining problems
• Problemi:– Quanto è grande l’insieme di
tutti gli schedule Pareto-ottimi?– Quanto è complesso trovarne
ognuno?– Quanto è complesso
determinare la soluzione di Nash e quella di KS?
Modello di ottimizzazione vincolato
1 | f B ≤ Q | f A
è il problema di trovare lo schedule * che minimizza f A() tra quelli tali che f B() ≤ Q
Modello bicriterio
• Un altro approccio minimizza una combinazione convessa delle funzioni obiettivo dei due agenti
f A + (1- ) f B
I due approcci
• Il modello vincolato può essere iterativamente utilizzato per trovare tutte le soluzioni Pareto-ottime
• Il modello bicriterio può essere più semplice da risolvere ma consente di trovare solo le soluzioni estreme o efficienti
Soluzioni Pareto-ottime che sonoanche soluzioni del modellobicriterio
f A
f B
1|CiB Q | Tmax
A - Esempio
Agente A
f A= TmaxA
Ji pi di
1 5 42 3 133 4 21
Agente B
f B= iCiB
Q = 43
Ji pi
1 32 43 4
Schedule
iCiB =
8 + 12 + 23 = 43
TmaxA
= 2
0 5 8 12 15 19 23
J1 J2 J3J1 J2 J3
Schedule ’
iCiB =
8 + 12 + 19 = 39
TmaxA
= 2
0 5 8 12 15 19 23
J1 J2 J3J1 J2 J3
Agent A
f A= i wiACi
A
JiA
piA wi
A
1 6 92 5 73 3 44 4 5
Agent B
f B= CmaxB
JiB
piB
1 10
Q = 20
1| CmaxB Q | wi
ACiA - Esempio
Soluzione ottima *
i wiACi
A() = 9*6+5*10+7*25+4*28
CmaxB(*)= 20
0 6 10 20 25 28
J1B J2
A J3AJ4
AJ1A
JiA
piA
wiA
1 6 92 5 73 3 44 4 5
Constr.model Size of P Bicriteria
fmaxA fmax
B O(n2) O(nAnB) O(n4)
wjACj
A CmaxB NP-hard pseudopol. O(n log n)
wjACj
A TmaxB NP-hard pseudopol. NP-hard
CjA fmax
B O(n log n) O(nAnB) O(n3log n)
UjA fmax
B O(n log n) O(nA) O(n2log n)
UjA Uj
B O(n3) O(nA) O(n4)
CjA Uj
B O(nB)
wjACj
A UjB NP-hard O(nB) NP-hard
CjA Cj
B NP-hard pseudopol. O(n log n)
Constr.model Nash/KS Bicriteria
fmaxA fmax
B O(n2) O(nAnB) O(n4)
wjACj
A CmaxB NP-hard O(n log n)
wjACj
A TmaxB NP-hard NP-hard
CjA fmax
B O(n log n) O(n3log n) O(n3log n)
UjA fmax
B O(n log n) O(n2log n) O(n2log n)
UjA Uj
B O(n3) O(n4) O(n4)
CjA Uj
B
wjACj
A UjB NP-hard NP-hard
CjA Cj
B NP-hard NP-hard O(n log n)
Per velocizzare l’intero processo:
1. Generiamo i “triangoli”, ognuno corrispondente ad una coppia di soluzioni estreme.
2. Identifichiamo un “triangolo critico” nel quale cercare la soluzione desiderata.
Af
Bf
Ricerca dei triangoli critici (per WC/WC)
arg max ( ) ( )A A B Bh f d f d
Questa è la soluzione di
Nash
La soluzione di Nashè qui (da qualche parte)
(a), (b) e (c) sono mutuamente esclusive
Triangolo critico di Nash
E’ sufficiente identificare i due schedule(successivi)
’, ’’ tali che:
Af
Bf
’
’’
( ') ( ')
( '') ( '')
A A B B
A B
A A B B
A B
f d f d
f d f d
Triangolo critico di Kalai-Smorodinsky
Ricerca in corso• Algoritmi esatti (branch and bound) per trovare soluzioni Pareto-ottime nei casi difficili• Studio di protocolli di negoziazione per giungere ad allocazioni “buone” senza bisogno di rivelare tutta l’informazione• Connessione con altri modelli di negoziazione, come aste etc