Suggerimenti per l'implementazione in Prolog

Le azioni possono essere specificate dando le precondizioni, effetti delete ed effetti add con tre predicati:

precond(pickup(X),[ontable(X),clear(X),handempty]).
delEffects(pickup(X),[ontable(X),clear(X),handempty]).
addEffects(pickup(X),[holding(X)]).

Le azioni no-op, una per ogni proposizione P, possono essere descritte come:

precond(persists(P),[P]).
delEffects(persists(P),[]).
addEffects(persists(P),[P]).

Azioni e proposizioni devono essere completamente istanziate quando vengono usate dall'algoritmo di planning. Per questo può essere utile specificare quali sono gli oggetti, le azioni e le proposizioni:

isblock(a).
isblock(b).
......
proposition(handempty).
proposition(holding(X)):- isblock(X).
proposition(on(X,Y)):- isblock(X), isblock(Y), X \== Y.
............
action(pickup(X)):- isblock(X).
action(stack(X,Y)):- isblock(X), isblock(Y), X \== Y.
...........

Esempio:  dominio rocket

Dato che l'algoritmo usa pesantemente gli insiemi, di azioni o di proposizioni, si consiglia di usare la libreria ordered sets che fornisce le operazioni sugli insiemi (unione, intersezione, sottoinsieme, ..). Gli insiemi sono liste di elementi senza duplicazioni ed ordinate secondo la relazione @<. Per passare da una generica lista ad un insieme si può usare il predicato list_to_ord_set.

Una possibile soluzione implementativa è quella di rappresentare esplicitamente solo i nodi del grafo e le relazioni di mutua esclusione fra di essi, mentre gli archi potranno essere ricavati quando occorre usando i predicati del dominio: precond, delEffects e addEffects. In questo caso un planning graph con n livelli può essere rappresentato come una lista di 2n+1 elementi, ciascuno corrispondente alternativamente a un livello di proposizioni o a un livello di azioni:

[LivProp0, LivAz1, LivProp1, ..., LivAzn, LivPropn]

Ogni elemento della lista dovrà contenere la rappresentazione di un livello del grafo, ossia un insieme di proposizioni o di azioni e le relative relazioni di mutua esclusione. Una possibile rappresentazione di un livello è come una coppia [InsElem, InsMutex], dove InsElem è un insieme di azioni o di proposizioni, e InsMutex è un insieme di termini mutex(X,Y), dove X e Y sono elementi di InsElem che sono mutamente esclusivi:

[[e1,e2,e3,e4,e5], [mutex(e1,e3), mutex(e2,e4)]]

Il livello 0 sarà [[p1,p2,p3,...] []] dove p1, p2,p3, .. sono le proposizioni valide nello stato iniziale (se lo stato è dato correttamente, non ci sono proposizioni mutuamente esclusive).

I componenti principali del programma saranno i seguenti predicati:

• extend(PropLevel, NewActionLevel, NewPropLevel) che crea un nuovo livello di un planning graph, costituito dal livello di azioni NewActionLevel e dal livello di proposizioni NewPropLeveel, partendo dall'ultimo livello di proposizioni PropLevel.
• solve(Goal, PlanningGraph, Plan) che restituisce il piano Plan eseguendo una ricerca all'indietro guidata dal Goal su PlanningGraph.
• un predicato che realizza l'iterative deepening chiamando extend e solve ad ogni ciclo fino a quando non trova la soluzione.

 
Ad esempio, extend può essere implementata come segue:

extend(PropLevel,[ActionSet,MutexActions],[Nprop,MutexProp]):-

applicableActions(PropLevel,ActionSet),
makeMutexActions(ActionSet,PropLevel,MutexActions),
effects(ActionSet,Nprop),
makeMutexProps(Nprop,ActionSet,MutexActions,MutexProp).

dove le prime due righe costruiscono il nuovo livello di azioni e le altre due il nuovo livello di proposizioni.

Il predicato applicableActions costruisce l'insieme ActionSet delle azioni applicabili al livello proposizionale PropLevel, e può essere definito facilmente usando setof:

applicableActions(PropLevel,ActionSet):-

setof(A,applicable(A,PropLevel),ActionSet).

Il predicato applicable restituisce nondeterministicamente una azione A applicabile a PropLevel, verificando che le precondizioni siano presenti in PropLevel e che non siano incompatibili fra di loro:

applicable(A,[PropSet,MutexProp]):-

action(A),
precond(A,Prec),
list_to_ord_set(Prec,PrecSet),
ord_subset(PrecSet,PropSet),
\+ mutexPropSet(PrecSet,MutexProp).

La lista di precondizioni restituita da precond potrebbe non essere un insieme ordinato. Prima di verificare se è un sottoinsieme di PropSet occorre trasformarla in insieme ordinato con list_to_ord_set.

Il predicato mutexPropSet verifica se c'è una coppia di precondizioni mutuamente esclusive:

mutexPropSet(PropSet,MutexSet):-

member(P1,PropSet),
member(P2,PropSet),
member(mutex(P1,P2),MutexSet).

Dato che l'implementazione usa gli insiemi, l'uso dei predicati built-in setof o findall può rendere più compatta la scrittura del programma. Ad esempio il seguente predicato restituisce in ASet l'insieme di tutte le azioni contenute in ActionSet che hanno la proposizione Prop come effetto add.

supports(Prop,ActionSet,ASet):-

setof(A,AddList^(member(A,ActionSet),addEffects(A,AddList),
member(Prop,AddList)),ASet).

Perché occorre usare AddList^? Cosa succede se non lo mettiamo?