Progetto per gli esami di Ingegneria del Software e Intelligenza Artificiale



Scaricare 345.5 Kb.
Pagina1/7
23.05.2018
Dimensione del file345.5 Kb.
  1   2   3   4   5   6   7

Università di Bologna

Facoltà di Ingegneria

Progetto per gli esami di




Ingegneria del Software

e

Intelligenza Artificiale







Studenti:
Fabio Adani - N. Matr. 2148-58175

Marco Chiesi - N. Matr. 2148-58143

Introduzione

"CoSa" è un acronimo di "Constraint Satisfaction", cioè soddisfacimento di vincoli, infatti l'obiettivo di questo progetto è realizzare un componente software in grado di risolvere problemi di soddisfacimento di vincoli, in inglese "Constraint Satisfaction Problems" (CSP).


I problemi di soddisfacimento di vincoli, molto brevemente, consistono in un insieme di variabili, ognuna delle quali può assumere valori contenuti in un certo dominio, le quali sono legate tra loro da una serie di vincoli. Una soluzione di un CSP è quindi un'assegnazione di valori alle variabili che sia consistente con tutti i vincoli del problema. In generale una variabile può assumere valori di qualsiasi tipo, e non necessariamente numerici, tuttavia in questo progetto tratteremo esclusivamente domini finiti contenenti valori interi. Per quanto riguarda i vincoli invece, si tratteranno soltanto vincoli puramente matematici, cioè quelli esprimibili tramite espressioni relazionali, mentre non si tratteranno vincoli simbolici. Inoltre non ci sono limitazioni sul numero di variabili coinvolte in un vincolo (mentre alcuni sistemi prevedono soltanto vincoli binari).
Quello che ci si propone di realizzare è una libreria software in grado di poter esprimere, manipolare e risolvere questo tipo di problemi, usando il paradigma di programmazione orientata agli oggetti. Perciò si realizzerà un insieme di classi in grado di rappresentare le varie componenti del problema (vincoli, variabili, domini, ecc), ed inoltre si implementeranno i principali algoritmi usati per la risoluzione di questi problemi.
Un aspetto importante che questo progetto si prefigge è prima di tutto, come si è già detto, quello di realizzare un componente software, e quindi, come tale, dovrà essere progettato per soddisfare requisiti di modularità, riusabilità ed estendibilità.
La parte finale di questo progetto prevede anche la realizzazione di un'applicazione dotata di interfaccia grafica che utilizzi la libreria, al fine di mostrarne le potenzialità.

Analisi e Specifica dei requisiti

Overview sui Constraint Satisfaction Problems

Il soddisfacimento di vincoli è una tematica particolarmente cara a diverse discipline, giacché le sue soluzioni rivestono una notevole importanza in diverse aree applicative (si pensi all’allocazione di risorse, allo scheduling, al planning, ecc.).


Esso è anche un aspetto molto importante dell’Intelligenza Artificiale, il cui tipo di approccio si seguirà in questo progetto.
Formalmente, un Constraint Satisfaction Problem (CSP) è espresso come:


  • Un insieme di variabili (X1, X2, .., Xn).

  • Un dominio (D1, D2, .., Dn) per ognuna di esse.

  • Un insieme di vincoli tra le variabili. Un vincolo tra k variabili individua un sottoinsieme del prodotto cartesiano dei loro domini.

La soluzione di un CSP è un assegnamento di un valore del suo dominio ad ogni variabile, di modo che tutti i vincoli siano soddisfatti.


Il problema si presenta quindi come un tipico problema di ricerca in uno spazio degli stati, e come tale presenta inevitabilmente rischi di esplosione combinatoria e di inefficienza.

Sono quindi necessarie tecniche che consentano di domare questo aspetto: esse si presentano sotto forma di algoritmi di propagazione (e di tecniche di consistenza) e di euristiche di branching (appropriate per ogni problema).


Lo schema base di risoluzione di un CSP è dunque quello di esplorazione di un albero, in cui ogni livello corrisponde ad una variabile ed ogni nodo ad un valore per essa.



Una soluzione corrisponde ad una foglia di questo albero in cui a tutte le variabili sono stati assegnati valori compatibili con tutti i vincoli.
Considerando il costo rilevante che può portare un assegnamento ed un successivo passo di backtracking, si sono inseriti in questo schema delle tecniche per prevenire, almeno in parte, l’assegnamento di valori inconsistenti alle variabili.

Esse si possono dividere in due : algoritmi di propagazione (che effettuano la propagazione durante la ricerca, cioè su un problema ottenuto dall’originale in seguito ad una serie di assegnamenti) e tecniche di consistenza (che trasformano il problema originale in un problema più semplice, ma ad esso equivalente)

Tuttavia, analizzando i vincoli e i domini, il loro obiettivo comune è rimuovere a priori combinazioni di valori che porteranno sicuramente ad un fallimento.
Alla luce di questo possiamo classificare le tecniche di risoluzione in due categorie:


  • Quelle che effettuano un assegnamento a priori (e quindi considerano i vincoli solo a posteriori) :

  • Generate & Test

  • Standard Backtracking




  • Quelle che effettuano un assegnamento a posteriori (e quindi analizzano i vincoli a priori per limitare lo spazio di ricerca) :

    • Forward Checking

    • Partial e Full Look Ahead

    • Arc-Consistency (che è anche una tecnica di consistenza)

Il Generate & Test effettua un assegnamento a tutte le variabili (cioè in pratica raggiunge una foglia) e solo alla fine controlla che i vincoli siano soddisfatti. E’ evidentemente la soluzione meno efficiente.


Lo Standard Backtracking controlla il soddisfacimento dei vincoli, ed in caso negativo provoca un backtracking, dopo ogni istanziazione. Si limita però a valutare solo il valore di tale istanziazione rispetto alle variabili istanziate precedentemente.
Il Forward Checking controlla tutti i vincoli che contengono l’ultima variabile istanziata eliminando dai domini delle variabili non istanziate tutti i valori non compatibili con il valore appena assegnato.
Il Partial ed il Full Look Ahead effettuano innanzitutto un forward checking. Sul problema ridotto poi effettuano una propagazione anche su vincoli che contengono variabili non ancora istanziate. Però, mentre il Partial Look Ahead controlla ogni variabile solo con quelle successive, il Full Look Ahead la controlla anche con quelle precedenti.
La Node Consistency e l’Arc-Consistency sono proprietà di un constraint graph (e quindi di un CSP).
In particolare la Node Consistency (o consistenza di grado 1) è soddisfatta se ogni vincolo unario è soddisfatto da tutti i valori del dominio della variabile su cui opera. L’algoritmo che realizza la node-consistency, è quindi semplicissimo: basta togliere dal dominio di ogni variabile i valori incompatibili con i vincoli unari su di essa.
L’Arc-Consistency (o consistenza di grado 2, generalizzata per vincoli non necessariamente binari) invece è soddisfatta se il problema è node-consistent e se ogni vincolo è consistente. Un vincolo tra le variabili X1, .., Xn è consistente se per ogni valore Vi  Di esiste una n-1 pla di valori (V1, .., Vi-1, Vi+1, .., Vn)  D1x..xDi-1xDi+1xDn, tale che il vincolo sia soddisfatto.

L’algoritmo che realizza l’arc-consistency è tipicamente iterativo ed opera assegnando ad ogni vincolo uno stato (addormentato o attivo) e facendo transitare i vincoli da uno stato all’altro, in seguito alla modifica di una variabile coinvolta in esso (addormentato -> attivo) o in seguito alla verifica di consistenza (attivo -> addormentato), finché non si raggiunge la quiescenza (cioè tutti i vincoli sono addormentati).

Le euristiche costituiscono uno strumento molto potente in quanto consentono in genere di abbreviare la ricerca scegliendo per la variabile e per il valore da assegnare quelli che appaiono più promettenti.
Le euristiche per la selezione delle variabili più comuni sono la First Fail (che sceglie la variabile col dominio più piccolo), le Least e Most Constraining (che scelgono rispettivamente la variabile coinvolta nel minore e nel maggiore numero di vincoli).
Le euristiche per la selezione dei valori più comuni sono la Growing Order e la Decreasing Order (che selezionano gli elementi del dominio rispettivamente in ordine crescente e decrescente).
Queste euristiche, aspirando ad essere utilizzate con ogni CSP, sono necessariamente generiche, nel senso che fanno le loro scelte in base a considerazioni che non hanno nulla a che fare con il problema specifico.




Condividi con i tuoi amici:
  1   2   3   4   5   6   7


©astratto.info 2019
invia messaggio

    Pagina principale