Questo progetto è stato realizzato per l'esame di Intelligenza Artificiale e Laboratorio del corso di Laurea Magistrale all'Università di Torino.
- Installare SWI-Prolog.
- Installare VSCode e l'apposita estensione VSC-Prolog.
- Clonare il progetto.
Un sistema intelligente è collocato in uno spazio di n righe ed m colonne, in cui sono posti degli ostacoli. Il sistema si trova in una delle celle del labirinto e, muovendosi all’interno dello stesso, deve raggiungere una casella di uscita.
Il sistema può muoversi nelle quattro direzioni (nord, sud, est, ovest) e non in diagonale e, ovviamente, non può raggiungere una cella contenente un ostacolo.
Il sistema conosce la configurazione del labirinto (dimensioni, posizione degli ostacoli, uscite).
labyrinths
contiene tutte le basi di conoscenza rappresentanti le mappe di labirinti.actions.pl
descrive tutte le azioni possibili effettuabili dal sistema, a prescindere dall'algoritmo utilizzato.- il predicato
acceptable(S)
controlla se la posizioneS
esiste all'interno del labirinto. applicable(action, S)
dev'essere usata prima di ognimove/3
per verificare che lo spostamento sia corretto.move(action, S, S1)
restituisce la nuova posizioneS1
effettuando lo spostamento derivato daaction
a partire dalla posizione di partenzaS
.
- il predicato
utils.pl
specifica ulteriori predicati.heuristic(S, S1, Distance)
calcola il valore di euristicaDistance
mediante la distanza di Manhattan tra le posizioniS
edS1
load_maze.pl
effettua la load della mappa selezionata.
a_star.pl
implementa l'algoritmo di ricerca A*. La struttura dati principale è la lista[[Actions], pos(X, Y), f(n)]
che contiene per ogni tassello esplorato del labirinto le azioni necessarie, la sua posizione e la sua funzione di costo. L'algoritmo è implementato da 4 predicati:a_star
dà inizio all'algoritmo, controllando i parametri forniti (come la posizione di inizio e fine) e stampa la soluzione.a_star_search/3
è il predicato che implementa la ricerca A*; ha 3 parametri, il primo è la lista dei nodi di frontiera, il secondo è la lista di nodi già visitati, mentre il terzo è la lista di azioni che rappresenta la soluzione.expand/3
genera i figli di un nodo, controllando tutte le azioni permesse in quel nodo.add/3
concatena in modo ordinato (in base alla funzione di costo) i nodi generati daexpand/3
a quelli già presenti, creando la nuova frontiera.
ida_star.pl
implementa l'algoritmo di ricerca IDA*. Per la gestione del limite asserisce nuovi fatti dinamicamente. Si basa su 3 predicati:ida_star
dà inizio all'algoritmo, controllando i parametri forniti (come la posizione di inizio e fine).ida_main/3
utilizzaida_search/5
per la ricerca del percorso e permette di incrementare il limite di volta in volta, nel caso una soluzione non sia stata ancora trovata.ida_search/5
è il predicato che implementa la ricerca IDA*.
iterative_deepening.pl
implementa l'algoritmo di ricerca Iterative Deepening. È costituito da 3 predicati:iterative_deepening
dà inizio all'algoritmo, controllando i parametri forniti (come la posizione di inizio e fine) e setta il limite massimo di profondità aRows
xColumns
.iterative_deepening_search/5
incrementa il limite di volta in volta, nel caso una soluzione non sia stata ancora trovata.depth_search/4
effettua la DFS attenendosi al limite di profondità attuale.
Il testing dei vari algoritmi di ricerca è stato effettuato su varie mappe qui sotto riportate:
A* | IDA* | Iterative Deepening | |
---|---|---|---|
maze7 | 0 sec | 0 sec | 0 sec |
maze10 | 0 sec | 0.6 sec | 2.81 sec |
maze10_1 | 0 sec | 72.21 sec | 172.78 sec |
maze10_2 | 0 sec | 0 sec | 0 sec |
maze10_3 | 0 sec | 3.22 sec | 31.89 sec |
maze14 | 0 sec | 0 sec | > 600 sec |
Come previsto, i risultati ottenuti mostrano la supremazia dell'algoritmo A*, a prescindere dalla disposizione degli ostacoli e dalla dimensione della mappa.
Al secondo posto troviamo IDA*, che a seconda della complessità della mappa varia il proprio tempo di esecuzione in maniera pressochè accettabile.
Infine come ci aspettiamo Iterative Deepening, che per sua natura, essendo un algoritmo blind, ha tempi di esecuzione nettamente maggiori. Inoltre degrada le sue prestazioni in maniera importante all'aumentare delle dimensioni della mappa.