>   Dipartimento di Informatica   >   Toni Mancini
[login|nuovo account]      [Italiano|English]

Laurea in Informatica, Corso di

Intelligenza Artificiale

Edizione dell'a.a. 2017/2018

Alcune idee di progetto

In questa pagina vengono indicate alcune idee di progetto (si vedano le modalità d'esame). Si tratta per ora di idee molto generali che andranno raffinate mediante discussioni con il docente.

Ricerca A* con gestione efficiente della memoria e del parallelismo
Esistono numerose varianti dell'algoritmo A* per gestire memoria limitata e presenza di processori o core multipli.
Il progetto richiede di: studiare la letteratura esistente, isolare le proposte più interessanti, implementarle (da zero, oppure usando framework opportuni), ed effettuare esperimenti comparativi con alcuni problemi di esempio.
Ricerca locale: altri algoritmi
Esistono molti algoritmi di ricerca locale non puramente greedy.
Il progetto richiede di: studiare la letteratura esistente, isolare alcune tra le proposte più interessanti, implementarle (da zero, oppure usando framework opportuni), ed effettuare esperimenti comparativi con alcuni problemi di esempio.
Ricerca locale: il sistema Comet
Comet è un sistema che permette la modellazione dichiarativo di problemi a vincoli e di ottimizzazione combinatoria e la loro risoluzione con tecniche di ricerca locale (e non solo).
Il progetto richiede di: studiare il sistema Comet, modellare alcuni problemi a vincoli e di ottimizzazione, ed effettuare esperimenti che confrontino le performance di diverse modellazioni dello stesso problema e diverse strategie di ricerca.
Ricerca evolutiva: altri algoritmi
Esistono molti algoritmi di ricerca evolutiva.
Il progetto richiede di: studiare la letteratura esistente, isolare alcune tra le proposte più interessanti, implementarle (da zero, oppure usando framework opportuni), ed effettuare esperimenti comparativi con alcuni problemi di esempio.
Ricerca in presenza di avversari
Il progetto richiede di: studiare la letteratura recente sugli algoritmi di ricerca con avversari e le tecniche di risoluzione più comunemente impiegate, implementare risolutori per alcuni problemi ed effettuare esperimenti.
Risoluzione di problemi a vincoli: il linguaggio OPL
OPL è un linguaggio di modellazione dichiarativo di problemi a vincoli e di ottimizzazione combinatoria. L'applicazione IBM Optimization studio fornisce un ambiente di sviluppo e di esecuzione con algoritmi allo stato dell'arte.

Il seguente è un esempio di specifica in OPL del problema N-queens:
	// La dimensione della scacchiera, definisce l'istanza del problema
	int+ N = ...;

	// Il resto della specifica e' parametrica rispetto ad N
	
	// Definizione di intervalli
	range Row 1..N;
	range Col 1..N;

	// Definizione delle variabili di decisione: Queen[1]..Queen[N], tutte con dominio Col (ovvero 1..N)
	var Col Queen[Row];

	// Vincoli
	solve {
	   forall (r1, r2 in Row : r1 < r2) { // Per ogni coppia di righe r1 < r2
	      Queen[r1] <> Queen[r2]; // Le regine alle righe r1 e r2 sono su colonne diverse...
	      Queen[r1] - Queen[r2] <> abs(r1 - r2); //	e non sulla stessa diagonale
	}};
Il primo vincolo può essere riscritto usando il vincolo globale alldifferent().
Il progetto richiede di: studiare il linguaggio OPL, modellare alcuni problemi a vincoli e di ottimizzazione, ed effettuare esperimenti che confrontino le performance di diverse modellazioni dello stesso problema e diverse strategie di ricerca.
Risoluzione di problemi a vincoli: simmetrie
Molti CSP contengono simmetrie. Ad esempio, nel problema di colorazione di una mappa con tre colori (R, G, B), per ogni soluzione (colorazione di tutti gli stati che soddisfa i vincoli) è possibile individuarne immediatamente altre scambiando in modo uniforme l'uso dei colori (ad es. colorando in G tutti gli stati colorati in R e viceversa).
La presenza di simmetrie può rendere la ricerca molto più dispendiosa del necessario, soprattutto quando il problema è insoddisfacibile oppure quando si cercano tutte le soluzioni. Ad esempio, dopo aver scoperto che una certa colorazione viola i vincoli, non ha senso verificare anche le sue simmetriche: anche queste violeranno i vincoli.
Esistono diverse tecniche per ridurre l'impatto negativo delle simmetrie sulla ricerca. Queste tecniche vanno sotto il nome di "symmetry breaking": ad es. è possibile aggiungere ulteriori vincoli al problema di modo da ridurre (se non eliminare del tutto) la presenza di simmetrie, oppure è possibile sviluppare algoritmi che tengano conto delle simmetrie durante la ricerca, evitando di esplorare porzioni dell'albero simmetriche rispetto a porzioni già esplorate (ad es. la tecnica "symmetry breaking via dominance detection (SBDD)").
Il progetto richiede di: studiare alcuni articoli della letteratura su CSP che presentano tecniche per riconoscere e gestire simmetrie e presentare i diversi approcci esistenti, con i loro vantaggi e svantaggi, facendo uso di esempi ed effettuando esperimenti.
Risoluzione di problemi a vincoli: vincoli globali
Sono stati definiti molti vincoli globali utili in diverse aree di applicazione del paradigma CSP, oltre il ben noto alldifferent() (si veda ad es. il Global Constraint Catalog). I risolutori stato dell'arte equipaggiano questi vincoli con algoritmi di propagazione specifici che consentono una propagazione maggiore rispetto a quella ottenibile rimpiazzando tali vincoli globali con vincoli ordinari.
Il progetto richiede di: studiare il ruolo dei vincoli globali nei risolutori per CSP allo stato dell'arte e presentare gli algoritmi di propagazione per alcuni di essi, facendo uso di esempi ed effettuando esperimenti.
Risoluzione di problemi a vincoli: il risolutore GeCode
GeCode è un risolutore open-source per CSP.
Il progetto richiede di: studiare GeCode, modellare alcuni problemi a vincoli e di ottimizzazione, ed effettuare esperimenti che confrontino le performance di diverse modellazioni dello stesso problema e diverse strategie di ricerca.
Risoluzione di problemi combinatori con la logica: il paradigma dell'Answer Set Programming
L'Answer Set Programming (ASP) è un paradigma di modellazione dichiarativo di problemi a vincoli e di ottimizzazione combinatoria.
Il progetto richiede di: studiare il paradigma ASP ed uno o più risolutori ASP stato dell'arte, modellare alcuni problemi a vincoli e di ottimizzazione, ed effettuare esperimenti che confrontino le performance di diverse modellazioni dello stesso problema e diverse tecniche di risoluzione (backtracking, traduzione in SAT, etc.).
Risolutori SAT di ultima generazione
Molti dei risolutori SAT di ultima generazione, sebbene basati sull'algoritmo DPLL, utilizzano molte altre tecniche per raggiungere prestazioni elevate.
Il progetto richiede di: studiare la letteratura recente sui risolutori SAT stato dell'arte e le tecniche più comunemente impiegate, ed effettuare esperimenti che confrontino le performance dei diversi risolutori su alcuni benchmark.
Paradigma Satisfiability Modulo Theories (SMT)
Una generalizzazione del paradigma SAT.
Il progetto richiede di: studiare la letteratura recente sul paradigma SMT e le tecniche di risoluzione più comunemente impiegate, modellare alcuni problemi combinatori ed effettuare esperimenti che confrontino le performance dei diversi risolutori.
Paradigma Pseudo Boolean Optimization (PBO)
Una generalizzazione del paradigma SAT.
Il progetto richiede di: studiare la letteratura recente sul paradigma PBO e le tecniche di risoluzione più comunemente impiegate, modellare alcuni problemi combinatori ed effettuare esperimenti che confrontino le performance dei diversi risolutori.
Apprendimento di reti bayesiane a partire da campioni

Il progetto richiede di: studiare la letteratura recente sulle tecniche di apprendimento della struttura e delle tabelle di probabilità condizionate di una rete bayesiana a partire da un insieme di campioni rappresentanti osservazioni, in particolare su approcci completi (basati sulla ricerca, mediante ad es., backtracking, nello spazio delle possibili reti) e incompleti (basati, ad es., su algoritmi di ricerca locale o evolutiva).


[This web site could never be realised without the sophisticated features of a pure text editor and the extreme power of 220V]