Tecniche di pianificazione in presenza di conoscenza incompleta

2deterministicamente quale sarà l’evoluzione dell’ambiente nel corso del piano, in qualunque
fase del piano stesso. Questa capacità deriva dall’assunzione di correttezza e completezza
della descrizione della situazione iniziale in cui verrà eseguito il piano, dall’assunzione di
determinismo degli effetti delle azioni, e dall’assunzione di unicità dell’agente nel suo
ambiente, in base alla quale nessun evento imprevisto può modificare la programmata
evoluzione del mondo.
Per realizzare un algoritmo che sia in grado di risolvere problemi di pianificazione in
campi d’applicazione reali, occorre superare in qualche modo queste assunzioni. Un
ambiente complesso, dinamico e, soprattutto, di vaste dimensioni, è difficilmente
descrivibile in maniera completa. Inoltre, il comportamento degli agenti reali spesso non è
perfettamente deterministico, a causa del fatto che alcune sue azioni hanno effetti
impredicibili. Questo, a sua volta, può essere dovuto alla stessa natura delle azioni, oppure
al fatto che esse hanno effetti diversi in situazioni diverse. In quest’ultimo caso, se non è
possibile conoscere a priori le condizioni in cui esse vengono eseguite, perché la descrizione
del mondo è incompleta, non è possibile conoscere nemmeno i loro effetti. Nella realtà,
quindi, la determinazione dello stato dell’ambiente in un certo istante, nel corso
dell’esecuzione di un piano, presenta delle incertezze, relative sia all’identificazione degli
oggetti contenuti nel mondo sia alla descrizione delle loro caratteristiche.
Nel corso dell’evoluzione delle tecniche di pianificazione, sono stati sviluppati
diversi sistemi in grado di trattare queste incertezze e risolverle in maniera opportuna.
Questi sistemi si basano sulla considerazione che, per poter operare adeguatamente in una
situazione incerta, è necessario che l’agente sia in grado di osservare il proprio ambiente e
acquisire nuove informazioni o, almeno, che sia in grado di prevedere le possibili situazioni,
basandosi su assunzioni che derivano da osservazioni precedenti. Il processo di acquisizione
della conoscenza è, perciò, una parte fondamentale della pianificazione in condizioni incerte.
Alcuni algoritmi di pianificazione progettano il piano senza sapere a priori quale saranno i
risultati di questo processo, supponendo che esso venga effettuato durante l’esecuzione del
3piano. Le informazioni recuperate permetteranno all’agente di scegliere le azioni corrette tra
un certo numero di possibili alternative, ognuna delle quali già analizzata dal pianificatore.
In questo caso, si può dire che l’acquisizione è effettuata off-line, cioè dopo che la
costruzione del piano è stata completata. In altri casi, il processo di acquisizione è
effettuato, su richiesta del pianificatore, durante la fase di pianificazione, per permettere
all’algoritmo di inserire nel piano solamente le azioni corrette, evitando così di dover
analizzare tutte le possibili azioni alternative, a fronte di un’incertezza. In questo caso, si
può parlare di acquisizione on-line. Si noti che, in ogni caso, l’acquisizione di informazioni
fa parte del piano stesso e, perciò, deve essere espressamente trattata da parte
dell’algoritmo. Questo crea alcuni problemi, il più importante dei quali è un incremento
della complessità, che riguarda sia il piano generato sia la struttura dell’algoritmo stesso.
In questa tesi viene presentato un modello di pianificazione alternativo, in grado di
risolvere i problemi di incertezza che derivano, in particolare, dall’incompletezza della
conoscenza iniziale del mondo. Questo modello sfrutta l’integrazione, nel pianificatore, di
una particolare tecnica di Risoluzione di Vincoli (Constraint Solving, CS), detta Risoluzione
di Vincoli Interattivi (Interactive Constraint Solving), per rendere la fase di acquisizione
dati trasparente al pianificatore. Il termine Constraint Solving si riferisce ai metodi di
risoluzione dei Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem,
CSP). Un CSP è costituito da un insieme di variabili, ad ognuna delle quali è associato un
insieme di valori possibili, e da un insieme di vincoli ad esse imposti. La soluzione del CSP
consiste nel determinare l’assegnazione ad ogni variabile di un valore che soddisfi l’insieme
di vincoli imposti.
Le tecniche di Constraint Solving sono state ampiamente sfruttate, in passato, per
modellare e risolvere efficientemente problemi di pianificazione. Nel corso dell’evoluzione
degli algoritmi di pianificazione si è rivelata vincente una strategia detta leas -commitment.
Questa strategia impone di ritardare il più possibile le scelte che legano il piano alla sua
forma definitiva. Queste scelte possono riguardare l’inserimento delle azioni in un ordine
4totale, l’identificazione degli oggetti coinvolti nelle azioni, cioè l’istanziazione delle variabili
del piano, o le operazioni di modifica del piano per risolvere i conflitti tra le azioni. Per
rendere ancora più efficace questa strategia, in molti sistemi è stata sfruttata la possibilità di
imporre vincoli sul piano e sulla sua costruzione, in modo che quando le scelte posticipate
vengono realmente effettuate, i vincoli imposti permettono di verificarne la correttezza. A
questo punto, è possibile creare una corrispondenza tra un problema di pianificazione ed un
CSP, le cui variabili possono rappresentare le variabili stesse del piano o, in generale, le
scelte posticipate. L’applicazione delle tecniche di Constraint Solving diventa molto
vantaggiosa, dato che esse permettono di sfruttare i vincoli attivamente, per ridurre a priori
lo spazio di ricerca della soluzione, eliminando dai domini delle variabili i valori che non
possono certamente far parte della soluzione finale.
Tuttavia, le tecniche di Constraint Solving classiche richiedono che, nel CSP da
risolvere, gli insiemi di valori possibili, per ciascuna variabile, siano tutti noti a priori, cioè
che la conoscenza iniziale del problema sia completa. Di conseguenza, i pianificatori che
adottano queste tecniche sono tutti basati sull’assunzione di completezza e correttezza della
conoscenza descritta in precedenza. Il Constraint Solving Interattivo è invece applicabile
anche a situazioni di conoscenza incompleta. Con questo metodo, sono gli stessi vincoli che
compongono il problema da risolvere a richiedere, durante la loro propagazione, le
eventuali procedure di acquisizione dati necessarie, in modo trasparente al sistema di alto
livello che risolve il CSP. Questo significa che, rappresentando il problema di pianificazione
come un CSP Interattivo, nel quale i vincoli rappresentano le condizioni di applicabilità
(precondizioni) delle azioni e le variabili rappresentano gli oggetti coinvolti nelle azioni, non
è più necessario definire ed inserire nel piano esplicite azioni di osservazione dell’ambiente.
In questo modo si risolvono i problemi di complessità tipici dei pianificatori che operano in
condizioni di incertezza. La struttura dell’algoritmo diventa analoga a quella di un
pianificatore che opera con conoscenza completa e il dominio di azioni a disposizione del
sistema si riduce alle sole azioni causali di modifica dell’ambiente. Inoltre, dato che
5l’acquisizione determinata dai vincoli interattivi preleva solo dati consistenti con il vincolo in
esame, la conoscenza risulta meglio focalizzata sulla porzione del mondo reale
effettivamente trasformata dal piano.
Nel primo capitolo di questa tesi sono descritti alcuni algoritmi di pianificazione noti
nella letteratura, distinguendoli tra pianificatori lineari e pianificatori non lineari. Questi
ultimi, in particolare, seguono una strategia least-commitment sull’ordinamento delle azioni,
rinviando ad una fase finale, detta di completamento del piano, il loro inserimento in una
sequenza lineare completamente ordinata. L’ultima parte del capitolo presenta una
panoramica dei vari sistemi che hanno utilizzato le tecniche classiche di Constraint Solving,
per migliorare l’efficienza del processo di costruzione del piano.
Nel secondo capitolo è analizzato il problema dell’incertezza nella pianificazione,
descrivendo le sue possibili cause e gli approcci maggiormente seguiti per la sua risoluzione.
Questi ultimi comprendono: l’approccio condizionale, secondo il quale il pianificatore deve
analizzare ogni possibile contingenza che derivi da una specifica fonte di incertezza;
l’approccio probabilistico, con il quale la costruzione del piano ottimale viene effettuata
sfruttando previsioni dello stato dell’ambiente, basate su analisi probabilistiche; l’approccio
reattivo, in base al quale il piano diventa una sequenza di reazioni opportunamente
predefinite, in risposta alla specifica situazione osservata; l’approccio che prevede
l’alternarsi di fasi di pianificazione e di fasi di esecuzione, in modo da effettuare in
quest’ultima i processi conoscitivi necessari alla prima per decidere le corrette azioni da
inserire nel seguito del piano.
Nel terzo capitolo viene dapprima presentata la descrizione generica di un CSP
Interattivo. In seguito viene descritto come un problema di pianificazione possa essere
rappresentato come un CSP Interattivo e viene presentato un algoritmo non lineare, analogo
a quelli descritti nel primo capitolo, in grado di ottenere, grazie al Constraint Solving
Interattivo, un piano corretto anche in condizioni di conoscenza incompleta. In particolare,
6è descritto un semplice esempio di applicazione nel campo delle reti di computer, un
ambiente tipicamente molto complesso e fortemente dinamico.
Nel quarto capitolo viene presentata l’implementazione dei vincoli che compongono
il CSP Interattivo integrato nel problema di pianificazione, con riferimento al campo di
applicazione delle reti di computer. I vincoli interattivi sono definiti come predicati binari, in
un linguaggio di Programmazione Logica a Vincoli. Questi predicati corrispondono alle
relazioni tra le risorse della rete e alle loro singole caratteristiche. Esempi di queste relazioni
sono quelle tra un file e il disco sul quale è memorizzato, tra un file e la propria dimensione
e così via. La propagazione dei vincoli interattivi permette di eliminare dai domini delle
variabili coinvolte gli oggetti noti che rappresentano risorse non compatibili con le
caratteristiche richieste e di osservare direttamente l’ambiente reale per determinare gli
oggetti ancora sconosciuti che, invece, sono compatibili, acquisendo nuove informazioni su
di essi.
7CAPITOLO 1
La pianificazione automatica
1.1  La pianificazione generativa
Uno dei problemi maggiormente studiati nell’Intelligenza Artificiale è quello della
pianificazione automatica o planning. Questo termine si riferisce al processo di sintesi di
una procedura che permetta ad un sistema agente all’interno di un determinato ambiente di
ottenere un risultato prefissato. Un sistema con capacità di pianificazione è in grado di
analizzare la situazione in cui si trova l’agente e sviluppare una strategia per raggiungere la
meta che tale agente si prefigge, cioè generare una sequenza di azioni, un pi no, valutando
a priori gli effetti delle azioni contenute in questo piano.
Il comportamento di questo sistema si contrappone a quello di un Sistema Reattivo, il
quale utilizza la situazione osservabile come uno stimolo per una reazione immediata,
scegliendo la migliore azione eseguibile in quella situazione senza valutarne le conseguenze.
Nello stesso modo agirà in seguito per far fronte alle modifiche dell’ambiente conseguenti al
suo operato. Determinare quale tra questi due tipi di comportamento sia maggiormente
efficace dipende fortemente dal mondo in cui agiscono questi sistemi e dagli scopi per i
quali sono progettati. È evidente che la pianificazione risulta più appropriata quando, per
ottenere l’obiettivo, è necessario eseguire numerose azioni i cui effetti interagiscono in
maniera complessa. Un comportamento reattivo è invece più idoneo per far fronte a un
mondo in rapida evoluzione, nel quale è più importante agire velocemente che fermarsi a
“riflettere”, oppure quando l’azione migliore, cioè quella che raggiunge direttamente lo
scopo, è sempre eseguibile in ogni situazione. Ad esempio, considerando problemi di
robotica, per la navigazione di un robot mobile in un ambiente pieno di ostacoli occorre che
8esso sia in grado di effettuare rapidi cambi di direzione. Quindi, in questo caso, un
comportamento reattivo è certamente efficace. Se invece vogliamo che un robot dotato di
un braccio meccanico disponga alcuni oggetti in una determinata configurazione, è
necessario che il sistema elabori la corretta successione delle azioni di raccolta e
posizionamento degli oggetti. Si rende quindi necessario, in casi come questo, un algoritmo
che sia in grado di generare come output una sequenza di azioni, un piano, che, una volta
eseguito a partire dalle condizioni iniziali, conduca il sistema alla meta, riconoscendo e
risolvendo in anticipo le interazioni tra gli effetti di queste azioni. Questo algoritmo è
definito pianificatore o planner.
L’ingresso del pianificatore, vale a dire il problema di pianificazione, deve
rappresentare opportunamente il mondo in cui opera l’agente, cioè il dominio di
applicazione, e l’obiettivo da raggiungere, quindi deve essere composto da:
(1) una descrizione formale dello stato iniziale del mondo,
(2) una descrizione formale del goal o stato finale del mondo,
(3) una descrizione delle possibili azioni che l’agente può eseguire nel mondo e delle regole
generali che vincolano il comportamento dell’agente, cioè una teoria del dominio.
I punti (1) e (3) costituiscono la conoscenza del sistema.
La descrizione di un dominio reale in una forma facilmente rappresentabile in un
calcolatore non è un problema banale. Nella realtà, infatti, i sistemi automatici devono far
fronte a una serie di problemi che li rendono difficilmente modellabili e complicano
l’elaborazione di una strategia per il loro comportamento. Ad esempio, l’esecuzione di
un’azione potrebbe non avere gli effetti desiderati a causa delle interferenze da parte di altri
agenti, oppure per via di lacune nelle informazioni sul mondo reale a disposizione del
sistema. Pensiamo al caso del robot con braccio meccanico: se gli si chiede di mettere alcuni
pacchi uno sopra l’altro senza informarlo del loro contenuto, questo potrebbe mettere un
peso eccessivo in cima alla pila con il risultato di farla crollare. Inoltre l’azione potrebbe
essere per sua stessa natura di esito incerto, si pensi alla compattazione di un file sulla
9memoria di massa di un computer: a priori non è possibile sapere di quanto questo possa
essere compattato e quindi la dimensione finale del file è impredicibile.
Un buon pianificatore deve essere corr tto e completo, dove per correttezza si intende
la proprietà di fornire come soluzione solo piani corretti, cioè che una volta eseguiti
ottengono effettivamente il risultato finale, e per completezza la capacità di trovare il piano
corretto, se questo esiste. Purtroppo i problemi visti in precedenza rendono molto difficile
implementare un algoritmo con queste proprietà. I primi studi sulla formalizzazione della
conoscenza di un dominio per un pianificatore eliminano questi problemi introducendo
semplificazioni notevoli della realtà, che, se da un lato limitano le possibili applicazioni
dell’algoritmo, dall’altro ne agevolano l’implementazione.
Le più importanti di queste assunzioni sono:
n Atomicità del tempo (Atomic time), cioè che l’esecuzione di un azione non sia
scomponibile e interrompibile e che porti ad una trasformazione atomica del mondo da
uno stato ad un altro.
n Effetti deterministici (Deterministic effects) cioè che l’effetto di un’azione sia una
funzione deterministica dell’azione stessa e dello stato del mondo al momento
dell’esecuzione.
n Onniscienza (Omniscience) cioè che l’agente abbia una conoscenza completa e corretta
dello stato iniziale del mondo e della natura delle sue azioni.
n Unicità della causa di cambiamenti (Sole cause of change) cioè che il solo motivo di
cambiamenti nel mondo sia l’esecuzione dei piani di azioni da parte dell’agente; il sistema
è unico nel suo ambiente.
 
1.2  La rappresentazione della conoscenza
La scelta del linguaggio per la rappresentazione del mondo e della sua evoluzione
influenza anch’essa la complessità del pianificatore. Un linguaggio molto espressivo risulta
molto difficile da trattare per un algoritmo. Di conseguenza il pianificatore, in grado di
10
comprendere e di sfruttare la conoscenza che esso descrive per risolvere il problema,
risulterà molto articolato. Viceversa, un linguaggio poco espressivo facilita la stesura
dell’algoritmo ma limita la possibilità di rappresentare domini complessi.
1.2.1  Situation Calculus
McCarthy ed Hayes [McCH69] alla fine degli anni sessanta sviluppano una
formalizzazione che chiamano situation calculus (logica delle situazioni), basata sulla logica
dei predicati del primo ordine, per rappresentare lo stato del mondo in funzione del tempo.
Il linguaggio della logica del primo ordine permette di esprimere proposizioni, cioè frasi, e
relazioni tra proposizioni grazie a un alfabeto composto di cinque insiemi di elementi:
n l’insieme dei simboli di costante, C.
n l’insieme dei simboli di variabile, V.
n l’insieme dei simboli di funzione, F.
n l’insieme dei simboli di predicato (o relazione), P.
n i connettivi logici (negazione, congiunzione, disgiunzione, implicazione, equivalenza) ed i
quantificatori universale ed esistenziale.
Le costanti rappresentano le singole entità, gli oggetti del dominio. Le variabili
possono rappresentare diversi oggetti del dominio, lasciando indefinite le entità che
compongono una frase. Una funzione, ad n argomenti, individua univocamente un oggetto
del dominio mediante una relazione tra altri n oggetti. Un predicato n-ario rappresenta una
relazione fra n oggetti del dominio, che può essere vera o falsa. Infine una formula o
espressione è una sequenza di simboli appartenenti all’alfabeto. Una formula che non
contiene variabili è detta ground.
Nel situation calculus le espressioni vengono usate per descrivere una situazione,
cioè lo stato del mondo in un determinato momento. Occorre definire una serie di predicati
che esprimono le relazioni tra gli oggetti e le loro caratteristiche, il cui valore di verità può
cambiare nel tempo. Queste proposizioni vengono dette fluents. Considerando una
11
situazione s come argomento di un fluent possiamo affermare i fatti che caratterizzano
questa situazione. Vediamo in figura 1.1 come è possibile rappresentare una situazione del
Mondo a Blocchi, un dominio molto usato nella letteratura del planning, nel quale il sistema
agente è un robot dotato di un braccio in grado di afferrare dei blocchi e spostarli da una
posizione ad un’altra, sopra il ripiano di lavoro o sopra un altro blocco.
Il predicato n indica che un oggetto è sopra a una certa locazione, clear che
l’oggetto è libero quindi può essere afferrato dal braccio.
Nel situation calculus le transizioni fra stati del mondo avvengono solo al verificarsi
di specificati eventi, in mancanza dei quali il mondo permane indefinitamente in uno stato.
L’evoluzione temporale del mondo è quindi descritta da una successione di eventi, che, nel
caso della pianificazione, sono determinati dall’esecuzione delle azioni. Ad esempio a fronte
dell’esecuzione dell’azione di trasferimento del blocco a dalla locazione table  alla
locazione b, indicata con il predicato move(a,table,b) , nello stato s0, avremo la
trasformazione di s0 in uno stato che sarà il risultato dell’applicazione della funzione
do(move(a,table,b),s0) . Formalizzare le regole per determinare questo risultato
significa descrivere il modello delle azioni. Per ogni azione a disposizione dell’agente
occorre indicare quali fatti devono essere veri in una situazione perché possa essere
eseguita, quali vengono modificati e in che modo. Ad esempio per l’azione mov  la regola
generale sarà:
clear(X,S) and clear(Z,S) and on(X,Y,S) and different(X,Z) ⇒
clear(X,do(move(X,Y,Z),S)) and clear(Y,do(move(X,Y,Z),S)) and
on(X,Z,do(move(X,Y,Z),S)),
A
B
C
D
E
on(a,table,s0).
on(b,c,s0).
on(c,table,s0).
on(d,e,s0).
on(e,table,s0).
clear(a,s0).
clear(b,s0).
clear(d,s0).
Figura 1.1.
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
13
descrivere il mondo e le relazioni tra gli oggetti che lo compongono, ma, per la descrizione
delle azioni, considera la possibilità di sostituire, in queste proposizioni, le costanti con delle
variabili per mantenere la generalità di tale descrizione. Tuttavia, semplificando la
formalizzazione del situation calculus, non permette di riferire le variabili con quantificatori
né di considerare proposizioni in disgiunzione.
Le azioni sono modellate da uno schema, detto operator schemata, composto di tre
parti: una lista di precondizioni, cioè le proposizioni che devono essere verificate in uno
stato del mondo per poter eseguire l’azione e due liste dette add-list e delete-list che
rappresentano gli effetti dell’esecuzione. L’applicazione di tale operatore ad un certo stato
aggiunge alle proposizioni che lo descrivono quelle contenute nella add-list ed elimina quelle
contenute nella delete-list ottenendo così la descrizione dello stato successivo. Il frame
problem è risolto con un’assunzione che, nella letteratura, è riferita proprio con il termine
STRIPS assumption, che afferma che tutto ciò che non è espressamente modificato dalle
liste add e delete si presume permanga valido nello stato risultante dall’esecuzione
dell’azione. Vediamo in figura 1.2 come è possibile esprimere un problema di pianificazione
del Mondo a Blocchi.
Notiamo che, poiché l’assunzione vista nel primo paragrafo richiede che la descrizione
B
A C D
A
C
D
B
INIZIO:
on(b,a).
ontable(a).
ontable(d).
ontable(c).
handempty.
clear(c).
clear(b).
clear(d).
GOAL:
on(c,a).
ontable(a).
on(b,d).
ontable(d).
clear(c).
clear(b).
handempty.
Figura 1.2