Problemi di scheduling
multi-agente
Alessandro Agnetis, Università di Siena
Gianluca De Pascale, Università di Siena
Pitu B. Mirchandani, University of Arizona
Dario Pacciarelli, Università di Roma Tre
Andrea Pacifici, Università di Roma Tor Vergata
Marco 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]
• AGV in competizione su una rete
[Huang e Hallam 1995]
• 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]
• 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(s) and f B(s)
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 s0, 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 XG, 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 è
m
v (f )   qi  v j (Fj )
iF0
j 1
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


H j ( p)  max v j ( X )   pi 
X G
i X


Equilibrio
• Un’allocazione f è in equilibrio per un
vettore p di prezzi se:
1)
H j ( p)  v j (Fj )   pi
iFj
(ossia, ogni agente consegue il
massimo guadagno)
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
pi
€6,25 €6,25 €6,25 €3,25 €3,25 €3,25 €3,25 €3,25
0
1
2
3
4
5
w1=16 w2=10 w3=6
d1 =3 d2 =4 d3 =2
L1=2
L2=2
qi = € 3
L3=1
6
7
8
w4=14,5
d4 =8
L4=4
Esempio
pi
€6,25 €6,25 €6,25 €3,25 €3,25 €3,25 €3,25 €3,25
0
1
2
3
4
5
w1=16 w2=10 w3=6
d1 =3 d2 =4 d3 =2
L1=2
L2=2
qi = € 3
L3=1
6
7
8
w4=14,5
d4 =8
L4=4
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
0
1
w1=3
d1 =2
L1=2
2
w2=2
d2 =2
L2=1
qi = € 0
Allocazione ottima
p2
p1
0
1
w1=3
d1 =2
L1=2
2
w2=2
d2 =2
L2=1
qi = € 0
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 è bi , l’offerta
successiva deve essere pari ad almeno
ai =bi + e (ask price)
• Quando non ci sono più offerte, la risorsa
è allocata al miglior offerente
Comportamento degli agenti
• Ciascun agente offre il valore ai per
alcune risorse, in modo da massimizzare il
proprio surplus
• L’asta ascendente raggiunge un equilibrio?
Esempio
Prezzo corr.
0
w1= € 20
d1 =2
L1=2
0
0
1
0
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w3= € 2,5
d3 =3
L3=1
Offerta agente 2
Prezzo corr.
0
w1= € 20
d1 =2
L1=2
0
0
1
1
0
1
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w2= € 2,5
d2 =3
L2=1
Offerta agente 1
Prezzo corr.
0
w1= € 20
d1 =2
L1=2
0
1
1
2
1
1
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w2= € 2,5
d2 =3
L2=1
Offerta agente 3
Prezzo corr.
0
w1= € 20
d1 =2
L1=2
1
2
1
21
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w2= € 2,5
d2 =3
L2=1
Offerta agente 2
Prezzo
Prezzocorr.
corr.
0
w1= € 20
d1 =2
L1=2
12
22
1
213
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w2= € 2,5
d2 =3
L2=1
• 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
Prezzo
8
0
w1= € 20
d1 =2
L1=2
8
1
1
2
3
w2= € 8
d2 =3
L2=2
qi = € 0, e = € 1
w2= € 2,5
d2 =3
L2=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 (ke+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 U i ( B(i))
B (i )
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
Dkt    ikt * 1
i 1
Kutanoglu-Wu (III)
• Ad esempio, l’aggiornamento dei prezzi può
realizzarsi attraverso un semplice meccanismo di
proporzionalità, ossia
lktr+1 = lktr + 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 >
ax
Soluzione di Nash
• Date le funzioni di utilità dei due
giocatori, la soluzione di Nash x* è tale
che
uA(x*) uB(x*) ≥ uA(x) uB(x)
per ogni xX
• 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
Soluzione di Nash - dominio discreto
S
fB
*
* *
*
d
*
*
* *
*
* *
* *
(dA,dB)
*
*
*
* *
*
*
*
*
*
* *
*
*
*
*
*
*
*
*
f
A
s Nash  arg max  d A  f A (s )  d B  f B (s ) 
s
Non appartiene necessariamente alla frontiera efficiente
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, zB0 , i valori ottimi e
quelli peggiori per i due giocatori
Equità e vantaggio globale
• Data una qualsiasi soluzione s di valore
zA e zB per i due agenti, si può osservare
come si situa rispetto agli estremi:
zA  zA *
r (s )  0
zA  zA *
A
zB  zB *
r (s )  0
zB  zB *
B
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 sA e sB tali che:
r (s A )  min rA (s )
s
rA (s )  rB (s )
r (s B )  min rB (s )
s
rB (s )  rA (s )
Equità e vantaggio globale
• La soluzione di Kalai Smorodinski (nel
discreto) è definita come quello schedule
sKS tale che
r(sKS) = min {rA (s, rB (s}
Soluzione di Kalai-Smorodinsky dominio discreto
A
fB
(dA,dB)
*
1*
*
*
*
*
*
*
* *
*
*
* *
*
*
fB
B
*
*
*
(dA,dB)
*
*
*
*
* *
*
*
*
*
*
f
A
*
*
*1
f
A
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 s*
che minimizza f A(s) tra quelli tali che
f B(s) ≤ Q
Modello bicriterio
• Un altro approccio minimizza una
combinazione convessa delle funzioni
obiettivo dei due agenti
lf
A
+ (1- l) 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
f
A
Soluzioni Pareto-ottime che sono
anche soluzioni del modello
bicriterio
f
B
1|SCiB  Q | TmaxA - Esempio
Agente A
Agente B
f A= TmaxA
f B= Si CiB
Q = 43
Ji
pi
di
Ji
pi
1
2
3
5
3
4
4
13
21
1
2
3
3
4
4
Schedule s
J1
0
J1
5
J2
8
J2
12
J3
15
J3
19
TmaxA = 2
S i C iB =
8 + 12 + 23 = 43
23
Schedule s’
J1
0
J1
5
J2
8
J2
12
J3
15
TmaxA = 2
S i Ci B =
8 + 12 + 19 = 39
J3
19
23
1| CmaxB  Q | S wiACiA - Esempio
Agent A
Agent B
f A=
Si w
f B= CmaxB
JiA
piA
wi A
1
2
3
4
6
5
3
4
9
7
4
5
AC A
i
i
JiB
piB
1
10
Q = 20
Soluzione ottima s*
J1A
0
J4A
6
J2A
J1B
10
20
J3A
25
Si wiACiA(s) = 9*6+5*10+7*25+4*28
JiA
1
2
3
4
piA
6
5
3
4
wiA
9
7
4
5
CmaxB(s*)= 20
28
Constr.model Size of P
fmaxA fmaxB
SwjACjA CmaxB
SwjACjA TmaxB
SCjA fmaxB
SUjA fmaxB
SUjA SUjB
SCjA SUjB
SwjACjA SUjB
SCjA SCjB
O(n2)
NP-hard
NP-hard
O(n log n)
O(n log n)
O(n3)
NP-hard
NP-hard
O(nAnB)
pseudopol.
pseudopol.
O(nAnB)
O(nA)
O(nA)
O(nB)
O(nB)
pseudopol.
Bicriteria
O(n4)
O(n log n)
NP-hard
O(n3log n)
O(n2log n)
O(n4)
NP-hard
O(n log n)
Constr.model Nash/KS
fmaxA fmaxB
SwjACjA CmaxB
SwjACjA TmaxB
SCjA fmaxB
SUjA fmaxB
SUjA SUjB
SCjA SUjB
SwjACjA SUjB
SCjA SCjB
O(n2)
NP-hard
NP-hard
O(n log n)
O(n log n)
O(n3)
NP-hard
NP-hard
O(nAnB)
O(n3log n)
O(n2log n)
O(n4)
NP-hard
Bicriteria
O(n4)
O(n log n)
NP-hard
O(n3log n)
O(n2log n)
O(n4)
NP-hard
O(n log n)
Ricerca dei triangoli critici (per WC/WC)
Per velocizzare l’intero processo:
fB
1. Generiamo i “triangoli”,
ognuno corrispondente ad una
coppia di soluzioni estreme.
2. Identifichiamo un “triangolo
critico” nel quale cercare la
soluzione desiderata.
f
A
Triangolo critico di Nash
s h  arg max  f A (s )  d A  f B (s )  d B 
s
Questa è
la soluzione di Nash
La soluzione di Nash
è qui (da qualche parte)
(a), (b) e (c) sono mutuamente esclusive
Triangolo critico di Kalai-Smorodinsky
E’ sufficiente
identificare i due
schedule(successivi)
s’, s’’ tali che:
fB
s’
s’’
f A (s ')  d A f B (s ')  d B

A

B
f A (s '')  d A f B (s '')  d B

A

B
f
A
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