Progetti Prolog
1. Strategie di ricerca
Il file Strategie di ricerca
contiene l'implementazione di base della ricerca in profondità e
in ampiezza, come descritte nel libro di Console et al.
Si richiede di modificare queste implementazioni come segue:
- Modificare la ricerca in profondità in modo da realizzare
la strategia di iterative deepening
- Estendere l'iterative deepening in modo da tener conto anche
della stima (si esegue la
ricerca in profondità finché il valore g(n) + h(n) di un
nodo n è minore dellla soglia fissata per una certa iterazione)
- (opzionale) Modificare la ricerca in ampiezza in modo da non
espandere un nodo più di una volta (i nodi già visitati
devono essere mantenuti in una struttura globale invece di essere
associati ad ogni singolo nodo come nella implementazione data)
Le varie tecniche dovranno essere applicate agli esempi dei cammini e dei blocchi
(o a esempi analoghi) per verificarne l'efficacia.
Visto che l'utilizzo della stima è difficile per il problema del
blocchi, si suggerisce un'ulteriore semplice variazione dell'iterative
deepening:
4. Modificare l'iterative deepening in modo da ricordarsi
la lista delle operazioni fatte a partire dallo stato iniziale. Questa
lista può essere usata per evitare di eseguire operazioni
ridondanti in base a considerazioni dipendenti dal problema. Ad esempio
nel modo dei blocchi può essere inutile eseguire più di
una volta l'azione di mettere un certo blocco sul tavolo o di impilare
gli stessi due blocchi.
2. CSPplan: un pianificatore
basato su vincoli
Si richiede di implementare un pianificatore in Prolog con vincoli. La
struttura del pianificatore è descritta in CSPplan,
mentre il file spare-tire contiene
l'implementazione di un esempio.
Possibili domini su cui sperimentare il planner sono:
Blocchi
Mondo dei blocchi con le azioni pickup, putdown, stack e unstack. In
questo dominio però non c’è la possibilità di
sfruttare il planner per generare piani parzialmente ordinati. Potrebbe
essere interessante estendere il dominio in modo da aver più di
un braccio per muovere i blocchi.
Rocket (logistica)
Gli oggetti sono:
- un insieme di posizioni
- un insieme di carichi
- un insieme di rocket per spostare i carichi da una posizione all'altra
Le proposizioni sono
- at(O,P) dove O può essere o un rocket o un carico e P è
una posizione
- in(C,R) il carico C è nel rocket R
Le azioni sono:
- load(R,P,C) carica C nel rocket R alla posizione P
- unload(R,P,C) scarica C dal rocket R alla posizione P
- move(R,From,To) sposta il rocket R dalla posizione From alla
posizione To
Una descrizione in Prolog di questo dominio è data in rocket.
Suggerimenti per l’implementazione
Anche se le variabili hanno domini booleani, si consiglia di usare il
modulo di SICSTUS per i vincoli su domini finiti clpfd, perché questi
sembrano essere più efficienti di quelli sui booleani.
La componente principale del programma dovrebbe essere una procedura
extend(LivProp_k, LivAz_k+1,
LivProp_k+1)
che estende il planner di un livello, creando tutti i vincoli relativi
alle nuove variabili. LivProp_k è la lista delle variabili
proposizionali del livello k, che si suppone già esistente,
mentre LivAz_k+1 e LivProp_k+1 sono le liste delle nuove variabili,
azione e proposizionali, del livello k+1. Si noti che i nuovi vincoli
da aggiungere dipendono, oltre che dalle nuove variabili azione e
proposizionali del livello k+1, solo dalle variabili proposizionali del
livello k, e quindi non è necessario passare a extend come
parametri altre variabili dei livelli precedenti.
Occorrerà poi definire una procedura, molto semplice, che
realizzi l’iterative deepening
chiamando extend ripetutamente
fino a quando non trova la soluzione.
L’implementazione del planner dovrebbe essere parametrica rispetto al
dominio, in modo da poterla utilizzare facilmente su domini diversi.
Per fare questo occorre definire una interfaccia che consenta di
associare i nomi delle azioni e delle proposizioni (che sono termini
ground nella descrizione del dominio) alle variabili create dai vari
passi della procedura. Questa interfaccia può essere separata
dalle procedure indicate sopra, oppure inserita al loro interno. Ad
esempio, la procedura extend potrebbe
essere fatta nel seguente modo:
%
Estende il grafo di un passo, creando tutti i vicoli
% PS è l'ultimo livello
proposizionale
% ASN e PSN sono il nuovo
livello di azioni e proposizioni
extend(PS,ASN,PSN):-
setof(A,action(A),ActionSet),
same_length(ActionSet,ASN),
domain(ASN,0,1),
setof(P,proposition(P),PropSet),
same_length(PropSet,PSN),
domain(PSN,0,1),
% inserisci
i vincoli
.....................
..........................
La prima linea crea in ActionSet una
lista di tutte le azioni. La seconda crea una lista di variabili ASN della stessa lunghezza di ActionSet, e la terza linea
stabilisce che il dominio di queste variabili è 0..1. Ogni
variabile in ASN corrisponde
all’azione che si trova nella stessa posizione in ActionSet. Ad esempio, nth(N, ActionSet, pickup(a))
assegna ad N la posizione
dell’azione pickup(a) in ActionSet, e nth(N, ASN, V) assegnerà a V l’N-esima variabile in ASN. Quindi V è la variabile in ASN che corrisponde all’azione pickup(a).
Analogamente per le proposizioni.