Realizzazione di un pianificatore mediante CLP

Il planner ha una struttura analoga a Graphplan, ed è costituito da una sequenza di livelli, alternativamente di proposizioni ed azioni. Ogni livello è costituito da un insieme di proposizioni o azioni, mentre gli archi del planning graph sono rappresentati con vincoli. Le azioni sono le stesse di Graphplan, comprese le azioni no-op.

La struttura dati che descrive lo spazio di ricerca (planning graph) è costituita da una lista di livelli

[LivProp_0, LivAz_1, LivProp_1, ......., LivAz_i, LivProp_i]

Ogni livello proposizionale è costituto da un insieme (lista) di variabili, una per ogni proposizione del dominio. Analogamente ogni livello di azioni è costituto da un insieme (lista) di variabili, una per ogni azione del dominio. Quindi, se il dominio contiene np proposizioni e naz azioni, e il grafo ha i livelli, ci saranno (np X (i + 1) + naz X i) variabili.

Tutte queste variabili hanno dominio 0-1. Se una variabile di un livello proposizione k ha valore 1 (oppure 0), la proposizione corrispondente sarà vera (oppure falsa) a livello k. Analogamente se una variabile di un livello di azioni k ha valore 1 (oppure 0), l'azione corrispondente farà parte (oppure non farà parte) del livello k del piano.

Le relazioni fra queste variabili sono espresse con insiemi di vincoli. Ad esempio si consideri una azione az che ha come effetto add una proposizione p. Siano Vaz_i e Vp_i le variabili che corrispondono all'azione az e alla proposizione p al livello i. Per ogni livello i occorre creare un vincolo che dice che, se Vaz_i è vera (cioè se az viene eseguita al livello i) allora Vp_i dovrà essere vera, ovvero che Vaz_i implica Vp_i. In clpfd questo vincolo può essere formulato come:

Vaz_i #=> Vp_i

Analogamente, se p è un effetto delete, il vincolo dovrà specificare che, se Vaz_i è vera, allora Vp_i è falsa.

Dovranno essere creati vincoli dei seguenti tipi:

Effetti add: legano azioni a livello i con proposizioni a livello i

Effetti delete: legano azioni a livello i con proposizioni a livello i

Precondizioni: legano azioni a livello i con proposizioni a livello i-1

Azioni mutuamente esclusive: occorre mettere un vincolo che dice che due azioni dello stesso livello non possono essere eseguite simultaneamente, se una cancella una precondizione dell'altra

Ogni proposizione a livello i>0 deve essere causata da una azione allo stesso livello: ovvero se una variabile Vp_i è vera, allora ci deve essere almeno una variabile Vaz_i vera, dove az ha p come effetto add.

Si noti che la mutua esclusione fra azioni e fra proposizioni viene ottenuta automaticamente attraverso gli altri vincoli, salvo il caso indicato sopra che va trattato esplicitamente.

L'algoritmo di planning procede iterativamente aggiungendo un livello per volta al grafo fino a quando si trova una soluzione. La ricerca della soluzione in un grafo di livello i avviene come segue. Al livello proposizionale 0 si dà valore 1 a tutte le variabili che rappresentano proposizioni che valgono nello stato iniziale, e valore 0 a tutte le altre variabili. Al livello proposizionale i si dà valore 1 a tutte le variabili che rappresentano proposizioni che devono valere nello stato finale. Si cerca una assegnazione delle variabili che soddisfi i vincoli. Questo può essere fatto semplicemente usando la primitiva labeling del modulo clpfd.

 

Suggerimenti per l'implementazione

Come per Graphplan in Prolog, si suggerisce di definire una funzione

extend(LivProp_i-1, LivAz_i, LivProp_i)

che estende il grafo di un livello, creando tutti i vincoli relativi alle nuove variabili.

 

Una implementazione ben fatta dovrebbe essere parametrica rispetto al dominio, come nel caso di Graphplan in Prolog. Tuttavia, per semplicità, è possibile realizzare l'algoritmo per un preciso dominio (es. mondo dei blocchi con 3 blocchi, dominio dei rocket con 1 rocket, 2 oggetti e 2 posizioni, ...). In questo modo i vincoli possono essere inseriti ad hoc nel codice della extend.

Vedere l'esempio allegato.