Pianificazione automatica
# Pianificazione automatica

La pianificazione automatica è una branca dell'intelligenza artificiale e, in particolare, rappresenta un'attività di problem solving. L'attività di pianificazione automatica consiste nel concepire in maniera dinamica una certa sequenza di azioni che fanno sì che un obiettivo dato, non inizialmente verificato, venga raggiunto, partendo da una situazione iniziale. Le più comuni applicazioni della pianificazione automatica sono lo scheduling, la robotica e il pilotaggio di veicoli senza equipaggio.

Un agente intelligente con capacità di pianificazione automatica è detto "pianificatore automatico" o planner.

## La pianificazione

I sistemi di pianificazione automatica del tipo sviluppato nell’ambito dell’Intelligenza detta "classica" sono basati sulla conveniente astrazione di “azioni primitive” discrete. I piani consistono in sequenze di azioni primitive e il pianificatore compie una ricerca in un grafo costituito dallo spazio dei piani, definito dalle azioni primitive, o dallo spazio degli stati. Un piano soluzione sarà quindi rappresentato da una serie di azioni che, agendo sul sistema e sul suo comportamento, lo portano ad evolvere da uno stato iniziale a uno stato finale (detto anche goal) nel quale un certo obiettivo sarà raggiunto. Sia il dominio che l’obiettivo da perseguire sono descritti con dei linguaggi formali. Il dominio (definito dagli stati del sistema, dalle configurazioni iniziali e dalle azioni disponibili) è dato in input a un planner che restituisce un piano adatto a risolvere il problema del raggiungimento del goal.

Gli elementi necessari alla pianificazione sono:

* la descrizione dell'obiettivo,
* la descrizione dello stato iniziale del mondo,
* la descrizione di tutte le operazioni possibili che possono essere attuate per modificare lo stato del mondo.

Dati questi elementi, un pianificatore automatico effettua una ricerca nello spazio degli stati al fine di ricavare una sequenza di azioni che, se eseguite, provocano il raggiungimento dell'obiettivo.

Esempio informale di pianificazione.

### Obiettivo

* avere della frutta e della verdura in frigo

### Stato iniziale

* [frigo vuoto, a casa, in pantofole]

### Azioni disponibili (lista non ordinata)

* uscire di casa,
* indossare scarpe,
* prendere chiavi auto,
* raggiungere il negozio in auto,
* raggiungere il negozio a piedi,
* tornare a casa,
* posizionare acquisti nel frigo,
* entrare in negozio,
* prendere frutta,
* prendere verdura,
* pagare.

### Possibile soluzione (lista ordinata)

* [1- indossare scarpe, 2- prendere chiavi auto, 3- uscire di casa, 4- raggiungere il negozio in auto, 5- entrare in negozio, 6- prendere frutta, 7- prendere verdura, 8- pagare, 9- tornare a casa, 10- posizionare acquisti nel frigo]

Altra possibile soluzione (lista ordinata):

* [1- indossare scarpe, 2- uscire di casa, 3- raggiungere il negozio a piedi, 4- entrare in negozio, 5- prendere verdura, 6- prendere frutta, 7- pagare, 8- tornare a casa, 9- posizionare acquisti nel frigo]

### Conclusioni

Dall'esempio si può notare come:

* le soluzioni possono essere molteplici,
* possono essere presenti azioni che devono essere eseguite, per forza di cose, dopo altre (non posso raggiungere il negozio in auto se prima non ho preso le chiavi),
* possono esistere delle azioni che sono invertibili (prendere la frutta e la verdura),
* non è necessario che il piano finale contenga tutte le azioni in caso di più azioni o sequenze di azioni interscambiabili (raggiungere il negozio a piedi o in auto).

## La teoria dietro alla pianificazione

Pianificare consiste nell'effettuare una ricerca nello spazio delle teorie del primo ordine. Ogni stato del mondo rappresenta una teoria ottenuta tramite un insieme di assiomi del primo ordine. Le azioni corrispondono ad operatori in grado di modificare una teoria T1 in una teoria T2.

Un operatore corrisponde ad una terna di componenti:

* precondizioni: assiomi che devono essere in T1 perché l'azione possa essere compiuta,
* aggiunte: assiomi che devono essere aggiunti a T1 per produrre T2,
* cancellazioni: assiomi che devono essere rimossi da T1 per produrre T2.

## Pianificazione classica

Il paradigma classico di pianificazione prevede una rappresentazione del mondo basata sugli stati e sulle transizioni tra essi. Generalmente l’intero dominio viene descritto mediante insiemi di proposizioni in un qualche linguaggio formale.

Quest’approccio classico alla pianificazione fa affidamento su alcune assunzioni forti:

* Dominio deterministico: effetti deterministici delle azioni e stato iniziale perfettamente conosciuto.
* L’unica causa del cambiamento dello stato del mondo è l’agente.
* L’agente ha una conoscenza completa dello stato iniziale, delle proprie azioni e dello stato del dominio all’istante finale.
* L’esecuzione delle azioni è istantanea (tempo atomico).
* La raggiungibilità del goal.

l modello STRIPS, sviluppato nei primi anni ’70 a Stanford, rappresenta il capostipite degli attuali sistemi di pianificazione. Esso propone un linguaggio per la rappresentazione di stati e di azioni dalla semplice sintassi. Di fatto, la sintassi di STRIPS viene reputata molto più semplice del Situation Calculus; offre quindi un’efficienza maggiore dovuta alla minore espressività del linguaggio. Sono stati elaborati numerosi algoritmi per la pianificazione che prendono in ingresso un problema descritto nel linguaggio di STRIPS e il successo di questo linguaggio ha portato alla creazione di buon numero di varianti “tipo-STRIPS” (TWEAK, SIPE, SNLP, PDDL 2.1) anche perché le forti assunzioni di STRIPS contribuivano a limitare troppo le applicazioni della pianificazione.

### Il mondo dei blocchi

Si tratta di uno dei più famosi problemi di pianificazione, nato negli anni 1970 quando Terry Winograd era studente al MIT ed elaborava il "mondo a blocchi" per SHRDLU. Il dominio del problema prevede la presenza di un tavolo con sopra dei blocchi di eguale dimensione, ognuno identificato da una lettera dell'alfabeto maiuscola. I blocchi possono essere impilati. Un braccio robotico può prendere un blocco scoperto (che non ha nessun blocco sopra) e spostarlo in un'altra posizione, o sul tavolo (azione: "MuoviSulTavolo") o su un secondo blocco (azione: "Muovi").

L'obiettivo è quello di ottenere una particolare configurazione tra quelle possibili.

Obiettivo:

* Sopra(A, B) Λ Sopra(B, C)

Stato iniziale:

* [Sopra(A, Tavolo) Λ Sopra(B, Tavolo) Λ Sopra(C, A) Λ Blocco(A) Λ Blocco(B) Λ Blocco(C) Λ Scoperto(B) Λ Scoperto(C)]

Azioni disponibili:

* Muovi(b, x, y)
* Muovi_sul_tavolo(b, x)

## Algoritmi per la pianificazione

### Pianificazione classica

* Ricerca forward chaining nello spazio degli stati, eventualmente migliorata con l'uso di euristiche.
* Ricerca backward chaining, eventualmente migliorato dall'uso di vincoli di stato.
* Pianificazione ad ordine parziale

### Riduzione ad altri problemi

La riduzione del problema di pianificazione ad un altro tipo di problema è la tecnica che converte un problema di pianificazione ${\mathcal {P}}$ in un altro problema ${\mathcal {P'}}$ in modo tale che una soluzione per ${\mathcal {P'}}$ possa essere usata per risolvere ${\mathcal {P}}$.

* Riduzione al problema della soddisfacibilità proposizionale (es: Satplan).
* riduzione al problema del Model checking (es: MBP).

### Pianificazione temporale

La pianificazione temporale può essere risolta con metodi simili alla pianificazione classica. La differenza principale è che la definizione di uno stato deve includere informazioni sul tempo assoluto corrente e su quanto è andata avanti l'esecuzione di ogni azione attiva, a causa della possibilità che diverse azioni temporalmente sovrapposte nella durata siano prese simultaneamente. La pianificazione temporale è strettamente legata ai problemi di schedulazione.

La pianificazione temporale può anche essere intesa in termini di automi temporizzati.

### Pianificazione probabilistica

La pianificazione probabilistica può essere risolta con metodi iterativi come value iteration e policy iteration, quando lo spazio di ricerca è sufficientemente piccolo.

Nei problemi con osservabilità parziale, la pianificazione probabilistica è analogamente risolta con metodi iterativi, ma usando una rappresentazione delle funzioni di valore definite per lo spazio delle credenze piuttosto che degli stati.

### Pianificazione basata sulle preferenze

Nella pianificazione basata sulle preferenze, l'obiettivo non è solo quello di produrre un piano, ma anche di soddisfare le preferenze specificate dall'utente. A differenza della più comune pianificazione basata sulle ricompense, per esempio nei MDP, le preferenze non hanno necessariamente un preciso valore numerico.

## Estensioni del modello classico

Si parla di problemi di pianificazione con azioni deterministiche quando le transizioni da uno stato all’altro sono funzioni biunivoche, ovvero quando ogni stato è collegato a un solo altro stato dall’applicazione di un’azione. Questo è il caso dei problemi di pianificazione classica. Al contrario, in un dominio non deterministico, l’esecuzione di un’azione in uno stato può portare a più di uno stato successivo. Un'altra estensione riguarda la parziale osservabilità, che indica un accesso dell’agente ad un sottoinsieme delle osservazioni possibili sull’ambiente. Ciò permette di simulare, ad esempio, sensori e conoscenza limitata dell'ambiente circostante.

I domini di pianificazione, per avvicinarsi a problematiche reali con applicazioni sfruttabili in tutti i campi della società, si sono notevolmente complessificati; l’evoluzione dalla forma classica di planning ad altre forme, più vicine a problemi che si rispecchiano in applicazioni tangibili, porta ad esacerbare il problema dell’esplosione esponenziale dello spazio di ricerca dei piani. La pianificazione mediante STRIPS – la quale affronta problemi notevolmente più semplici combinatoriamente di quelli affrontati con azioni non-deterministiche e osservabilità parziale, ad esempio –, è PSPACE-completa. L'aumento di complessità impone di ricercare tecniche atte a facilitare la ricerca di piani in tali domini.

### Pianificazione probabilista

Il paradigma della pianificazione probabilista è stato introdotto da Kushmerick negli anni '90. L'effetto delle azioni è descritto con probabilità. Ad esempio, l'azione "il robot prende un blocco" viene così descritta: se la pinza del robot è asciutta, allora il robot tiene il blocco con una probabilità di 0,95; se la pinza è bagnata, allora il robot tiene il blocco solo con una probabilità di 0,5.

Questa impostazione porta al problema della generazione di politiche (o strategie) per un processo decisionale markoviano (MDP) o (nel caso generale) un processo decisionale markoviano parzialmente osservabile (POMDP).

### Pianificazione conformante

Se il modello dell'ambiente non è probabilista, si adottano paradigmi che descrivono l'incertezza considerando un insieme di stati possibili, piuttosto che un solo stato corrente per l'agente. Si parla di pianificazione conformante quando l'agente è incerto sullo stato del sistema e non può fare nessuna osservazione. L'agente poi ha delle credenze sul mondo reale che si riflettono in "stati di credenza". Questi problemi sono risolti con tecniche simili a quelle della pianificazione classica, ma considerando uno spazio degli stati esponenziale nelle dimensioni del problema, a causa dell'incertezza sullo stato corrente. Una soluzione per un problema di conformant planning è una sequenza di azioni.

Il problema della pianificazione contingente è EXPSPACE-completo e 2EXPTIME-completo quando la situazione iniziale è incerta e le azioni hanno effetti nondeterministici.

### Pianificazione contingente

Si parla di pianificazione contingente quando l'ambiente è osservabile tramite sensori, che possono essere difettosi o imprecisi. Per un problema di pianificazione contingente, un piano non è più una sequenza di azioni, bensì un albero decisionale, perché ogni stato del piano è rappresentato da un insieme di stati piuttosto che da un singolo stato perfettamente osservabile, come nel caso della pianificazione classica. Le azioni scelte sono condizionate dallo stato del sistema. Ad esempio, se piove, l'agente sceglie di prendere l'ombrello e, in caso contrario, può decidere di non prenderlo.

Mikael L. Littman ha dimostrato nel 1998 che con le azioni che ramificano sulle osservazioni, il problema di pianificazione diventa EXPTIME-completo.

