Tecniche di pianificazione in presenza di conoscenza incompleta

12
dove X,Y,Z ed S sono variabili che, assumendo come valore le costanti che rappresentano
rispettivamente gli oggetti del mondo e la situazione, determinano le varie istanze
dell’azione. Notiamo che X e Z devono essere diversi, cioè non è possibile spostare un
blocco sopra sé stesso. È possibile esprimere lo stesso concetto con una regola generale del
dominio del tipo: ∀ X,S not on(X,X,S) , che afferma che un blocco non può trovarsi
sopra sé stesso. In tal modo un’azione che cerchi di mettere il blocco b sopra il bl cco b
non potrà essere eseguita perché viola un vincolo fisico del dominio. Solitamente, per
evitare di dover controllare questi vincoli ogni volta che viene scelta un’azione, si preferisce
utilizzare la prima notazione, indicando espressamente tutte le proposizioni necessarie al
successo dell’azione.
Un problema molto importante nella descrizione delle azioni è il cosiddetto frame
problem, che consiste nel determinare quali fluents dello stato precedente l’esecuzione non
sono modificati dalla transizione di stato. Se non facciamo assunzioni particolari occorre
indicarli tutti esplicitamente e questo per situazioni complesse e grandi domini è molto
gravoso. Inoltre la logica dei predicati del primo ordine utilizzata nella situation calculus è
molto espressiva e questo permette di descrivere mondi anche molto più complessi di quello
a blocchi. È possibile, ad esempio, rappresentare azioni che coinvolgono una moltitudine di
oggetti grazie a quantificazioni universali sulle variabili o che sfruttano proposizioni in
disgiunzione. Purtroppo questa elevata espressività, come già detto, rende anche difficile
ottenere un algoritmo semplice.
1.2.2  STRIPS language
I primi sistemi di pianificazione implementati accantonano la logica delle situazioni
pur mantenendone molti concetti, in particolare quello di stato del mondo e di transizione
tra gli stati. Fikes e Nilsson [FN71] nei primi anni settanta sviluppano STRIPS : con questo
nome essi si riferiscono sia al pianificatore sia al linguaggio adottato per la rappresentazione
della conoscenza. Questo linguaggio sfrutta un insieme di proposizioni ground per