10. Ragionamento con vincoli PT.1

Gli agenti lavorano in termini di stati, in genere questi vengono descritti in termini di caratteristiche, descrivendo le funzionalità attraverso le variabili. Le caratteristiche non indipendenti e ci possono essere vincoli rigidi che specificano combinazioni legali di assegnazioni di valori a variabili. Nella pianificazione e programmazione un agente assegna un tempo per ogni azione. Questi incarichi devono soddisfare vincoli sull'ordine in cui le azioni possono essere eseguite e vincoli che specificano che le azioni raggiungono un obiettivo. Le preferenze rispetto alle assegnazioni sono specificate in termini di vincoli flessibili.

Nel descrivere i problemi di soddisfazione dei vincoli si utilizzano variabili e mondi possibili. Un mondo possibile è un modo possibile in cui il mondo potrebbe essere. La loro descrizione avviene tramite variabili algebriche, ovvero dei simboli usati per denotare caratteristiche di mondi possibili. Vengono scritte in maiuscolo e ognuna ha un dominio associato. Vi sono diversi tipi di variabili:

• variabili discrete, le quali hanno un dominio finito o numerabili finito
• variabili binarie, che sono un caso particolare di variabili discrete e hanno solo due valori nel proprio dominio
• variabili booleane, le quali possono assumere solo i valori di "vero" o "falso"
• variabile continua, i cui valore sono all'interno di un insieme reale

E' importante definire la funzione di assegnazione sull'insieme di variabili e diciamo che questa assegnazione è totale quando questa assegna tutte le variabili. Quindi un mondo possibile è definito come un incarico totale, ovvero come una funzione che assegna da variabili in valori ad ogni variabile.

Il numero di mondi è il prodotto del numero di valori nei domini delle variabili. Quindi se ci sono N variabili e ciascuna con una dimensione del dominio pari a D, allora ci sono $D^N$ mondi possibili.

In molti domini, non tutte le possibili assegnazioni di variabili sono consentite per via dell'esistenza di vincoli, detti anche vincoli rigidi. Questi vincoli specificano le combinazioni legali di assegnazione di valori alle variabili. Definiamo un ambito come un insieme di variabili e una relazione al suo interno è costituita da una funzione che agisce su un ambito S restituisce un valore vero o falso.

Un vincolo C è un ambito S e una relazione su S. Si dice che un vincolo coinvolge ciascuna delle variabili nel suo ambito. Un mondo soddisfa un insieme di vincoli se per ogni vincolo, i valori assegnati in w alle variabili soddisfano il vincolo. Definiamo il problema di soddisfazione del vincolo o CSP.

Definizione del problema di soddisfazione del vincolo

Un problema di soddisfazione del vincolo (CSP) è costituito da

• un insieme di variabili,
• un dominio per ogni variabile
• un insieme di vincoli.

Un CSP finito ha un insieme finito di variabili e un dominio finito per ogni variabile. Alcuni dei metodi considerati in questo capitolo funzionano solo per CSP finiti, sebbene alcuni siano progettati per domini infiniti, anche continui. Quando ci si ritrova a dover risolvere un CSP, è utile svolgere una serie di attività:

• Determinare se esiste o meno un modello
• Trovare un modello
• Contare il numero di modelli.
• Enumerare tutti i modelli
• Trovare un modello migliore, data una misura di quanto sono buoni i modelli
• Determinare se qualche affermazione vale in tutti i modelli

L'aspetto multidimensionale dei CSP, in cui ogni variabile è una dimensione separata, rende questi compiti difficili da risolvere, ma fornisce anche una struttura che può essere sfruttata. Alcuni dei metodi possono anche determinare se non esiste un modello e possono essere adattati per trovare tutti i modelli. Ciò che può essere più sorprendente è che alcuni dei metodi possono trovare un modello se ne esiste uno, ma non possono determinare che non esiste un modello se non esiste.

Algoritmi di generazione e test

Un CSP finito potrebbe essere risolto da un esaustivo algoritmo di generazione e test. Lo spazio di assegnazione D è l'insieme delle assegnazioni totali. L'algoritmo restituisce un modello o tutti i modelli. L' algoritmo di generazione e verifica per trovare un modello è il seguente: controllare a turno ogni assegnazione totale; se viene trovato un incarico che soddisfa tutti i vincoli, restituire tale assegnazione. Un algoritmo di generazione e verifica per trovare tutti i modelli è lo stesso tranne che, invece di restituire il primo modello trovato, salva tutti i modelli trovati.

Se ciascuna delle N variabili di dominio ha una dimensione pari a d, allora D ha una dimensione pari a $D^N$ elementi. Inoltre la presenza di è vincoli, comporta che il totale dei vincoli testati è $O(ed^n)$. Al crescere di n il problema diventa intrattabile e si deve pensare a diversi metodi risolutivi.

I problemi CSP possono essere risolti attraverso algoritmi di ricerca. Gli algoritmi di generazione e test assegnano valori alle variabili prima di controllare i vincoli. Poiché i singoli vincoli coinvolgono solo un sottoinsieme delle variabili, alcuni vincoli possono essere verificati prima che a tutte le variabili vengano assegnati valori. Se un'assegnazione parziale non è coerente con un vincolo, anche qualsiasi assegnazione totale che estende l'assegnazione parziale sarà incoerente.

L'algoritmo di ricerca che viene utilizzato nella risoluzione dei problemi CSP utilizza un grafo da cercare è definito mediante:

• I nodi sono costituiti da assegnazioni di valori di sottoinsiemi di variabili
• I neighbors di un nodo n sono ottenuti selezionando una variabile Y che non è assegnata a un nodo n
• n ha un neighboor per ogni assegnamento i un valore a Y che non viola il vincolo
• Il nodo iniziale è un'assegnazione vuota che non assegna nessun valore a nessuna variabile
• Un nodo obiettivo è un nodo che assegna un valore a ogni variabile.

Supponiamo che n sia l'assegnazione {$X_1=v_1, \dots. X_k=v_k$}. Per trovare i neighbors di n, si seleziona una variabile Y che non nell'insieme {$X_1,\dots,X_k$}. Per ogni valore $y_i \in dom(Y)$, nella quale $X_1 = v_1, \dots, X_k = v_k, Y = y_i$ è consistente per ogni vincolo, il nodo {$X_1 = v_1, \dots, X_k = v_k, Y = y_i$} è un neighbor di n.

La ricerca in un albero attraverso un algoritmo di ricerca in profondità viene chiamato tipicamente backtracking ed è più efficiente di un algoritmo di generazione e test. L'algoritmo di generazione e test è equivalente a non controllare i vincoli sui nodi foglia prima di effettuare delle operazioni. Il controllo dei vincoli più in alto nell'albero può eliminare i sottoalberi di grandi dimensioni che non devono essere cercati.

Algoritmi di consistenza

La ricerca in profondità all'interno dello spazio dei vincoli presenta ancora alcuni punti di miglioramento. In questo caso vengono in aiuto gli algoritmi di consistenza, i quali operano molto bene su una rete di vincoli dei problemi CSP. Infatti in questi algoritmi:

• Esiste un nodo in ogni variabile
• Esiste un nodo per ogni vincolo
• Ogni variabile X viene associata a un insieme di possibili valori $D_X$ che prende il nome di dominio della variabile
• Per ogni vincolo c e per ogni variabile X nel suo ambito esiste un arco < X, c>

Questa rete prende il nome di rete di vincoli. Se un vincolo ha solo una variabile nello scopo, l'arco è consistente nel dominio per ogni valore che la variabile soddisfa nel vincolo. Mentre se esiste un vincolo c ha nel proprio scopo { $X, Y_1, \dots, Y_k$ }, un arco < X, c > è un arco consistente se, per ogni valore di $x \in D_X$, esistono valori $y_1, \dots, y_k$ dove ogni $y_i \in D_{Y_i}$, tale che il vincolo $c = ( X =x, Y_1=y_1, \dots, Y_k = y_k$ è soddisfatto. Una rete di archi è consistente se tutti gli archi sono consistenti.

Se un arco <X, c> non è un arco consistente, ci sono alcuni valori di X per i quali non ci sono valori per $Y_1, \dots. Y_k$ per i quali vale il vincolo. In questo caso, tutti i valori di X in $D_X$ per i quali non vi sono valori corrispondenti per altre variabili possono essere cancellate da $D_X$ per rendere l'arco consistente. Quando un valore è rimosso dal dominio, gli archi che precedentemente erano consistenti, non lo saranno più.

L'algoritmo della consistenza generalizzata dell'arco (GAC)

Questo tipo di algoritmo rende un insieme di archi consistenti considerando un insieme di archi potenzialmente inconsistenti. L'insieme to_do inizialmente consiste di tutti gli archi del grafo. Fino a quando l'insieme non rimane vuoto, un arco < X, c > è rimosso dall'insieme e considerato. Se l'arco non è consistente, viene reso consistente sfoltendo il dominio della variabile X.

Dopo aver eliminato la variabile X, tutti gli archi precedentemente consistenti potrebbero non esserlo più e vengono inseriti nell'insieme to_do. Questi archi < Z, c' >, dove c' è una consistenza differente da c in X, e Z è la variabile coinvolta in c'.

Indipendentemente dall'ordine in cui vengono considerati gli archi, l'algoritmo terminerà con lo stesso risultato, vale a dire una rete consistente con gli archi e lo stesso insieme di domini ridotti. Sono possibili tre casi, a seconda dello stato della rete al momento della terminazione:

• Nel primo caso, un dominio diventa vuoto, indicando che non esiste alcuna soluzione per il CSP;
• Nel secondo caso, ogni dominio ha un valore singleton, che indica che esiste un'unica soluzione per il CSP;
• Nel terzo caso, ogni dominio non è vuoto e almeno uno contiene più valori. In questo caso, non sappiamo se esiste una soluzione o come sono le soluzioni.