DISTRIBUTED CONSTRAINT SATISFACTION
PROBLEM E ARC-CONSISTENZA
Applicazioni di Intelligenza Artificiale LS
Reti di Calcolatori LS
Francesca Nocerino
Matricola 171107
Constraint Satisfaction Problem
Un problema di soddisfacimento di vincoli è definito da:
• un insieme di n variabili (X1,X2…Xn);
• un dominio discreto per ogni variabile (D1,D2…Dn);
• un insieme di vincoli su queste variabili.
La soluzione di un problema di soddisfacimento di vincoli è un
assegnamento di valori alle variabili consistente con i vincoli.
Senza perdita di generalità si può supporre che tutti i vincoli siano
binari.
Un problema di soddisfacimento di vincoli si può rappresentare con
un grafo detto constraintgraph, in cui alle variabili corrispondono i
nodi e ai vincoli gli (iper)-archi.
CSP - Esempio
[1..10]
=
[1..10] X1
[1,2,5..33]
>
X2
=
X4
>
[1..5,9,10]
<
>
>
≥
[1..10,50] X5
X3
[1,5]
<
X6
X7
[1..5,10..15]
≠
[1..5]
X8
≤
≥
X9
≥
X10
[1..5]
[1..5]
Variables
x1::[1..10]
x2::[1..10]
x3::[1,5]
x4::[1,2,5..33]
x5::[1..10,50]
x6::[1..5,9,10]
x7::[1..5,10..15]
x8::[1..5]
x9::[1..5]
x10::[1..5]
Constraints
x1=x2
x1>x3
x2>x3
x2>x4
x3<x8
x4<x5
x4=x6
x5>=x7
x6>x7
x7!=x9
x8<=x9
x8>=x10
x9>=x10
CSP - Esempio
alfabeto:={natural, string, =, !=, >, <, >=, <=, ::, [, ], ,, .. , Variables,
Constraint, External Constraint}
natural rappresenta un numero naturale.
[1..10]
[1,2,5..33]
[1..5,9,10]
string è una stringa
alfanumerica che inizia con un carattere.
>
=
X2 essere definiti mediante un’altra
X4semplice X6
natural e string possono
=
grammatica.
[1..10] Constraints,
> External Constraints sono parole
< chiave.
>
Variables,
X1
>
≥
Variables
[1..10,50] X5
X7
<variableList>
[1,5]
[1..5,10..15]
Constraints
<
≠
[1..5]
<constraintList>
≤
<variableList>::= <variable> | <variable>
<X9
variableList >
X8
[1..5]
<variable>::= <varName> :: <domain>
≥
<varName>::=string
≥
<domain>::= [<domContent>]
X10
<domContent>::= <domElem>| <domElem>,<domContent>
[1..5]
<domElem>::= natural|natural..natural
< constraintList > ::= <constraint> | <constraint> < constraintList >
<constraint>::=<varName><op>< varName >
<op>::= =|!=| >| <| >=| <=
<constraintProblem>::=
X3
Variables
x1::[1..10]
x2::[1..10]
x3::[1,5]
x4::[1,2,5..33]
x5::[1..10,50]
x6::[1..5,9,10]
x7::[1..5,10..15]
x8::[1..5]
x9::[1..5]
x10::[1..5]
Constraints
x1=x2
x1>x3
x2>x3
x2>x4
x3<x8
x4<x5
x4=x6
x5>=x7
x6>x7
x7!=x9
x8<=x9
x8>=x10
x9>=x10
Arc-consistency
Un arco A(i,j) è consistente se per ogni valore a appartenente a Di
esiste almeno un valore b appartenente a Dj tale che il vincolo tra i e j
sia soddisfatto. Un constraintgraph è arc-consistente se ogni suo arco
è consistente.
[1..10] [3..10]
=
[1..10] X1
[3..10]
[2,5,9] [1,2,5..33]
>
X2
<
>
X3
[1,5]
[1] <
=
X4
>
[1..5,9,10]
[2,5,9]
>
≥
[1..10,50] X5
[2..10,50]
X7
[1..5]
[1..5,10..15]
[2..5]
[1..5]
X8
X6
≠
≤
≥
X9
≥
X10
[1..5]
[1..5]
[2..5]
Distributed CSP (1)
Un CSP può essere partizionato su k agenti.
X2
X4
X6
X2
X4
X6
X3
X5
X7
X1
X1
X3
X5
X8
X7
X8
X9
X9
X10
X10
k=1
k=n
X2
X4
X6
X3
X5
X7
X1
X8
X9
X10
1≤k≤ n
Distributed CSP (2)
• Ogni variabile è associata a uno e un solo agente e tale agente è detto
responsabile di quella variabile.
• I vincoli riguardanti due variabili appartenenti allo stesso agente sono
associati unicamente a tale agente e sono chiamati internal constraint.
• Un vincolo che coinvolge due variabili legate a due agenti diversi è
associato ad entrambi gli agenti e viene definito external constraint.
• Se due agenti A1 e A2 condividono un vincolo esterno si dice che A1
è vicino (o neighbour) di A2 e viceversa.
• Il neighbourhood di un agente è quindi definito come l’insieme di
tutti i suoi vicini.
• Ad ogni agente è associato un CSP costituito dalle variabili di cui è
responsabile e dai vincoli interni.
• Ogni agente deve essere in grado di rendere il grafo di vincoli
corrispondente a tale CSP arc-consistente.
DCSP – Esempio (1)
=
A1
>
X2
>
X1
=
X4
<
>
>
X3
≥
X5
<
≠
X8
A3
≤
≥
X9
≥
X10
X6
X7
A2
Agente 1
Variables
x1::[1..10]
x2::[1..10]
x3::[1,5]
Constraints
x1=x2
x1>x3
x2>x3
External Constraints
x2>x4
x3<x8
DCSP – Esempio (1)
=
A1
>
X2
X4
>
X1
=
X6
<
>
X3
X5
<distributedConstraintProblem>::=
A3
≤
≥
X9
≥
X10
≥
X7
<constraintProblem>
External Constraints
≠
< constraintList
>
<
X8
>
A2
Agente 1
Variables
x1::[1..10]
x2::[1..10]
x3::[1,5]
Constraints
x1=x2
x1>x3
x2>x3
External Constraints
x2>x4
x3<x8
DCSP – Esempio (2)
=
A1
>
X2
>
X1
=
X4
<
>
>
X3
≥
X5
<
≠
X8
A3
≤
≥
X9
≥
X10
X6
X7
A2
Agente 2
Variables
x4::[1,2,5..33]
x5::[1..10,50]
x6::[1..5,9,10]
x7::[1..5,10..15]
Constraints
x4<x5
x4=x6
x5>=x7
x6>x7
External Constraints
x4<x2
x7!=x9
DCSP – Esempio (3)
=
A1
>
X2
>
X1
=
X4
<
>
>
X3
≥
X5
<
≠
X8
A3
≤
≥
X9
≥
X10
X6
X7
A2
Agente 3
Variables
x8::[1..5]
x9::[1..5]
x10::[1..5]
Constraints
x8<=x9
x8>=x10
x9>=x10
External Constraints
x8>x3
x9!=x7
Distributed CSP (3)
Sulla struttura della rete costituita dagli agenti non vengono posti
vincoli di nessun tipo:
• non c’è un ordinamento tra gli agenti;
• si possono presentare dei cicli;
• la rete di agenti può non essere completamente connessa.
Ogni agente deve conoscere tutti i suoi vicini e, per ognuno di essi,
sapere quali sono le variabili di cui questo è responsabile e che sono
coinvolte in un vincolo esterno con una delle sua variabili locali.
Gli agenti comunicano attraverso lo scambio di messaggi.
Si è scelto di usare TCP\IP per avere la garanzia che i messaggi
arrivino al più una volta e nell’ordine in cui sono stati inviati.
A1
A2
A3
A1
A2
A3
A4
Messaggi
Esistono nove tipi di messaggi che gli agenti possono scambiarsi:
• arc-information X1 Dom1 X2 Dom2 ...
• arc-no-solution
• arc-first-marker num-mess-ricevuti numero-iniziativa
• arc-first-waiting my-id numero-iniziativa
• arc-waiting init-id numero-iniziativa
• arc-not-waiting init-id numero-iniziativa
• arc-message-travelling init-id numero-iniziativa
• arc-marker num-mess-ricevuti init-id numero-iniziativa
• arc-consistency
Inizializzazione (1)
Inizialmente ogni agente effettua la propagazione localmente.
[2..10]
[2..10]
[1..10] X1
[1..10]
[2,5,9,10]
[1,2,5..33]
X2
X4
=
>
[2,5,9,10]
[1..5,9,10]
[1..5]
X6
X8
>
≥
=
<
>
X3
X5
[1,5]
[1..10,50]
≤
X7
[1..5]
[1..5,10..15]
[1..5]
A2
X9
≥
X10
≥
[3..10,50]
A1
[1..5]
A3
Inizializzazione (2)
In seguito invia a ciascun vicino un messaggio
arc-information X1 Dom1 X2 Dom2 ...
contenente le informazioni su tutte le variabili locali coinvolte in un
vincolo esterno con tale vicino.
arc-information x2 [2..10]
A2
A1
arc-information x3 [1,5]
A3
Inizializzazione (2)
In seguito invia a ciascun vicino un messaggio
arc-information X1 Dom1 X2 Dom2 ...
contenente le informazioni su tutte le variabili locali coinvolte in un
vincolo esterno con tale vicino.
arc-information x4 [2,5,9,10]
A2
A1
arc-information x7 [1..5]
A3
Inizializzazione (2)
In seguito invia a ciascun vicino un messaggio
arc-information X1 Dom1 X2 Dom2 ...
contenente le informazioni su tutte le variabili locali coinvolte in un
vincolo esterno con tale vicino.
A2
A1
arc-information x9 [1..5]
arc-information x8 [1..5]
A3
Propagazione (1)
Alla ricezione dei messaggi arc-information ogni agente propaga di
nuovo localmente, ma tenendo conto dei vincoli esterni relativi alle
variabili di cui ha ricevuto informazioni.
[1..10]
X2
=
[1..10] X1
Es.: A1 riceve
arc-information
>
>
<
X3
[1,5]
[1]
A1
X8
[1..5]
x8
come primo messaggio.
[1..5]
Propagazione (2)
In seguito a ogni propagazione ciascun agente può aver modificato il
dominio di alcune delle sue variabili locali. Ad ogni vicino coinvolto
in almeno un vincolo esterno la cui variabile locale è stata modificata
viene mandato un nuovo messaggio arc-information.
A2
A1
arc-information x3 [1]
A3
Stati degli agenti (1)
Ogni agente ha uno stato, i possibili stati in cui può trovarsi un agente
sono:
• waiting: l’agente non sta effettuando localmente alcuna
propagazione ed è in attesa che gli arrivino dei messaggi arcinformation dai vicini;
• not waiting: l’agente sta propagando localmente o inviando ai vicini
dei messaggi arc-information;
• consistent: in questo stato l’agente sa che è stata raggiunta la
consistenza;
• impossible: in questo stato l’agente sa che il problema non ammette
soluzione.
Stati degli agenti (2)
NW not-waiting
W waiting
IMP impossible
C consistent
C
ricezione
arc-consistency
ricezione arc-information
NW
W
propagazione locale senza
modifiche rilevanti per i vicini
ricezione
arc-no-solution
IM
P
ricezione
arc-no-solution
ricezione arc-no-solution
o fallimento locale
Terminazione
Gli agenti possono terminare per due ragioni:
• il problema non ammette alcuna soluzione, cioè almeno un agente si
accorge che il dominio di almeno una delle variabili di cui è
responsabile è vuoto;
• l’arc-consistenza è stata raggiunta, cioè non è più possibile, per
nessun agente, eliminare dei valori dal dominio di nessuna variabile.
Problema impossibile
Se durante la propagazione locale un agente si accorge che non c’è
soluzione invia a tutti i suoi vicini il messaggio arc-no-solution
dopo aver aggiornato il suo stato, che diventa impossible, e prima di
terminare.
Alla ricezione di un messaggio arc-no-solution ogni agente, se il
suo stato non è già impossible, cambia il suo stato, avvisa i vicini e
termina a sua volta.
Alle ricezione di un arc-no-solution è necessario che un agente
verifichi il proprio stato, per evitare di mandare messaggi inutili,
infatti:
• la conclusione che il problema è impossibile può essere raggiunta da
più agenti autonomamente;
• non essendo stati imposti vincoli strutturali alla rete, un stesso agente
può essere avvisato da più di un vicino.
Arc-consistenza (1)
Dire che l’arc-consistenza è stata raggiunta significa dire che tutti gli
agenti si trovano in stato di waiting.
Per rilevare questo stato globale si usa un algoritmo di global state
detection del tipo proposto da Chandy e Lamport e si introduce un
nuovo agente, detto Monitor .
Il Monitor memorizza lo stato di tutti gli agenti e, appena si accorge
che essi si trovano tutti contemporaneamente nello stato di waiting, li
avvisa che è stata raggiunta la consistenza col messaggio arcconsistency, alla ricezione del quale ogni agente sa che può
terminare.
Arc-consistenza (2)
Quando un agente, in seguito alla propagazione locale, non deve
mandare arc-information a nessuno esegue le seguenti operazioni:
• prende l’iniziativa di registrare il suo stato, che è waiting;
• invia ai suoi vicini il messaggio
arc-first-marker num-mess-ricevuti numero-iniziativa
per informarli che per lui potrebbe essere stata raggiunta la
consistenza;
• invia al Monitor il messaggio
arc-first-waiting my-id numero-iniziativa
Arc-consistenza (3)
Alla ricezione di un arc-first-marker un agente esegue le seguenti
operazioni:
• se i messaggi che ha inviato sono stati tutti ricevuti ed è anche lui in
stato di waiting invia al Monitor un messaggio
arc-waiting init-id numero-iniziativa
• se i messaggi che ha inviato sono stati tutti ricevuti, ma lui non è in
stato di waiting invia al Monitor un messaggio
arc-not-waiting init-id numero-iniziativa
• se i messaggi che ha inviato non sono stati tutti ricevuti invia al
Monitor il messaggio
arc-message-travelling init-id numero-iniziativa
• invia a ogni suo vicino un messaggio
arc-marker num-mess-ricevuti init-id numero-iniziativa
Arc-consistenza (4)
Alla ricezione di un arc-marker ogni agente si comporta come alla
ricezione di un arc-first-marker, rispettando la seguentea regola:
• memorizzare i marker inviati e non inviare mai due volte un marker
con gli stessi init-id e numero-iniziativa; ciò serve per evitare un
loop infinito in cui gli agenti continuano a far girare marker nella rete,
in quanto, non essendo stati posti vincoli di nessun tipo sulla struttura
della rete, un agente potrebbe ricevere due volte lo stesso marker da
due vicini diversi.
Arc-consistenza (5)
A2
arc-first-marker 3 3
A1
arc-first-waiting A1 3
A1 A2 A3
W NW W
A1
...
W
arc-first-marker 2 3
Monitor
A3
Arc-consistenza (5)
A2
arc-waiting A1 3
arc-marker 2 A1 3
A1 A2 A3
W NW W
A1
A1
...
W
W
arc-marker 1 A1 3
Monitor
A3
Arc-consistenza (5)
A2
A1 A2 A3
W NW W
arc-marker 2 A1 3
A1
A1
...
W
W
W
Monitor
arc-marker 1 A1 3
arc-first-waiting A1 3
A3
Arc-consistenza (5)
A2
arc-consistency
A1 A2 A3
W NW W
arc-consistency
A1
A1
...
W W W
arc-consistency
Monitor
A3
Conclusioni
Rendere un constraintgraph arc-consistente…
[2,5,9]
[3..10]
=
>
X2
X4
>
[3..10] X1
=
X6
<
>
>
X3
X5
[1]
[2..10,50]
<
A1
[2,5,9]
[2..5]
X8
[2..5]
≤
≥
X9
≥
X10
[1..5]
A3
≥
X7
[1..5]
≠
A2
Conclusioni
… non vuol dire risolvere il problema corrispondente.
10
=
10
5
>
X2
X4
>
X1
X3
A1
=
X6
<
>
>
1
5
X5
<
≥
X7
10
3
X8
4
≤
≥
X9
≥
X10
2
A3
2
≠
A2