Tecniche di pianificazione in presenza di conoscenza incompleta

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