La pianificazione e la pianificazione automatizzate, a volte indicate semplicemente come Pianificazione IA, sono una branca dell’intelligenza artificiale che riguarda la realizzazione di strategie o sequenze d’azione, tipicamente per l’esecuzione da parte di agenti intelligenti, robot autonomi e veicoli senza equipaggio. A differenza dei classici problemi di controllo e classificazione, le soluzioni sono complesse e devono essere scoperte e ottimizzate nello spazio multidimensionale. La pianificazione è anche legata alla teoria delle decisioni.

In ambienti noti con modelli disponibili, la pianificazione può essere eseguita offline. Le soluzioni possono essere trovate e valutate prima dell’esecuzione. In ambienti dinamicamente sconosciuti, la strategia deve spesso essere rivista online. Modelli e politiche devono essere adattati. Le soluzioni di solito ricorrono a processi di prova ed errore iterativi comunemente visti nell’intelligenza artificiale. Questi includono la programmazione dinamica, l’apprendimento del rinforzo e l’ottimizzazione combinatoria. Le lingue usate per descrivere la pianificazione e la pianificazione sono spesso chiamate linguaggi di azione.

Panoramica
Data una descrizione dei possibili stati iniziali del mondo, una descrizione degli obiettivi desiderati e una descrizione di un insieme di possibili azioni, il problema di pianificazione è sintetizzare un piano che è garantito (se applicato a uno qualsiasi degli stati iniziali) per generare uno stato che contiene gli obiettivi desiderati (tale stato è chiamato stato obiettivo).

La difficoltà di pianificazione dipende dalle ipotesi semplificative utilizzate. Diverse classi di problemi di pianificazione possono essere identificate in base alle proprietà dei problemi in diverse dimensioni.

Le azioni sono deterministiche o non deterministiche? Per le azioni non deterministiche, sono disponibili le probabilità associate?
Le variabili di stato sono discrete o continue? Se sono discreti, hanno solo un numero finito di valori possibili?
Lo stato attuale può essere osservato senza ambiguità? Ci può essere osservabilità totale e osservabilità parziale.
Quanti stati iniziali ci sono, finiti o arbitrariamente molti?
Le azioni hanno una durata?
Possono essere intraprese diverse azioni contemporaneamente o è possibile una sola azione alla volta?
L’obiettivo di un piano è raggiungere uno stato obiettivo designato o massimizzare una funzione di ricompensa?
C’è un solo agente o ci sono diversi agenti? Gli agenti sono cooperativi o egoisti? Tutti gli agenti costruiscono i propri piani separatamente, oppure i piani sono costruiti centralmente per tutti gli agenti?

Il problema di pianificazione più semplice possibile, noto come il problema di pianificazione classica, è determinato da:

uno stato iniziale unico e noto,
azioni senza durata,
azioni deterministiche,
che può essere preso solo uno alla volta,
e un singolo agente.

Poiché lo stato iniziale è noto in modo inequivocabile e tutte le azioni sono deterministiche, lo stato del mondo dopo ogni sequenza di azioni può essere previsto con precisione, e la questione dell’osservabilità è irrilevante per la pianificazione classica.

Inoltre, i piani possono essere definiti come sequenze di azioni, perché è sempre noto in anticipo quali azioni saranno necessarie.

Con azioni non deterministiche o altri eventi al di fuori del controllo dell’agente, le possibili esecuzioni formano un albero e i piani devono determinare le azioni appropriate per ogni nodo dell’albero.

I processi decisionali Markov a tempo discreto (MDP) stanno pianificando problemi con:

azioni senza durata,
azioni non deterministiche con probabilità,
piena osservabilità,
massimizzazione di una funzione di ricompensa,
e un singolo agente.

Quando la osservabilità totale è sostituita da osservabilità parziale, la pianificazione corrisponde al processo decisionale Markov parzialmente osservabile (POMDP).

Se ci sono più di un agente, abbiamo una pianificazione multi-agente, strettamente correlata alla teoria dei giochi.

Pianificazione indipendente dal dominio
In AI Planning, i pianificatori tipicamente inseriscono un modello di dominio (una descrizione di un insieme di azioni possibili che modellano il dominio) e il problema specifico da risolvere specificato dallo stato iniziale e dall’obiettivo, in contrasto con quelli in cui non c’è dominio di input specificato. Tali pianificatori sono chiamati “Domain Independent” per enfatizzare il fatto che possono risolvere i problemi di pianificazione da una vasta gamma di domini. Esempi tipici di domini sono lo stack stacking, la logistica, la gestione del flusso di lavoro e la pianificazione delle attività del robot. Quindi un pianificatore indipendente a dominio singolo può essere utilizzato per risolvere problemi di pianificazione in tutti questi diversi domini. D’altra parte, un pianificatore di percorsi è tipico di un pianificatore specifico del dominio.

Pianificare le lingue di modellazione del dominio
Le lingue più comunemente utilizzate per rappresentare domini di pianificazione e problemi di pianificazione specifici, come STRIPS e PDDL per la pianificazione classica, sono basate su variabili di stato. Ogni possibile stato del mondo è un’assegnazione di valori alle variabili di stato e le azioni determinano il modo in cui i valori delle variabili di stato cambiano quando viene intrapresa quell’azione. Poiché un insieme di variabili di stato inducono uno spazio di stato che ha una dimensione esponenziale nell’insieme, la pianificazione, analogamente a molti altri problemi computazionali, soffre della maledizione della dimensionalità e dell’esplosione combinatoria.

Un linguaggio alternativo per descrivere i problemi di pianificazione è quello delle reti di compiti gerarchici, in cui viene fornito un insieme di compiti, e ciascuna attività può essere realizzata da un’azione primitiva o decomposta in una serie di altri compiti. Questo non implica necessariamente variabili di stato, sebbene in applicazioni più realistiche le variabili di stato semplificano la descrizione delle reti di compiti.

Algoritmi per la pianificazione
Pianificazione classica
inoltra concatenando la ricerca dello spazio di stato, possibilmente potenziata con l’euristica
ricerca di concatenamento a ritroso, eventualmente potenziata dall’uso di vincoli di stato (vedi STRIPS, graphplan)
pianificazione dell’ordine parziale

Pianificazione classica
La pianificazione tradizionale si basa su due presupposti:

il determinismo delle azioni. Ad esempio, l’azione “metti un cubo sul tavolo” è deterministica. Eseguendolo, passiamo da uno stato all’altro. Al contrario, “tira un dado” non è deterministico perché ci sono valori possibili. L’azione “tira un dado” non rientra nell’ambito della pianificazione tradizionale.
l’osservazione perfetta. L’agente (il robot, il programma, ecc.) Conosce completamente lo stato del mondo.

Per quanto riguarda la pianificazione classica, si tratta di cercare una sequenza di azioni (ad esempio, “prendere una padella”, “mettere acqua”, “mettere la pasta”, “accendere un fuoco”, “raggiungere”, “estrarre il fuoco”). L’algoritmo A * è un tipico esempio di un algoritmo di pianificazione classico, spesso utilizzato nei corsi introduttivi per la sua semplicità. Ecco alcune tecniche algoritmiche utilizzate nei pianificatori classici:

la ricerca diretta in uno spazio di stato: algoritmo di pianificazione euristica della ricerca (HSP), algoritmo Fast-Forward (FF),
la ricerca posteriore in uno spazio di stato,
la ricerca prima in uno spazio di piani, grafico
rilassamento di un problema di pianificazione: calcolo di un problema rilassato per il quale è più facile sapere se esiste un piano che aiuti a risolvere il problema iniziale
la trasformazione in un problema di soddisfacibilità di una formula di logica proposizionale.

Bylander ha dimostrato nel 1994 che la pianificazione convenzionale è completa con PSPACE.

Riduzione ad altri problemi
riduzione al problema di soddisfacibilità proposizionale (satplan).
riduzione al controllo del modello – entrambi sono essenzialmente problemi di attraversamento degli spazi degli stati, e il classico problema di pianificazione corrisponde a una sottoclasse di problemi di controllo del modello.

Pianificazione temporale
La pianificazione temporale può essere risolta con metodi simili alla pianificazione classica. La differenza principale è, a causa della possibilità di diverse azioni temporalmente sovrapposte con una durata concomitante, che la definizione di uno stato deve includere informazioni sul tempo assoluto corrente e fino a che punto è proseguita l’esecuzione di ciascuna azione attiva. Inoltre, nella pianificazione con il tempo razionale o reale, lo spazio dello stato può essere infinito, a differenza della pianificazione classica o della pianificazione con tempo intero. La pianificazione temporale è strettamente correlata ai problemi di programmazione. La pianificazione temporale può anche essere intesa in termini di automi temporizzati.

Pianificazione probabilistica
La pianificazione probabilistica può essere risolta con metodi iterativi come l’iterazione del valore e l’iterazione della politica, quando lo spazio degli stati è sufficientemente piccolo. Con osservabilità parziale, la pianificazione probabilistica viene similmente risolta con metodi iterativi, ma utilizzando una rappresentazione delle funzioni di valore definite per lo spazio delle credenze anziché degli stati.

Pianificazione basata sulla preferenza
Nella pianificazione basata sulle preferenze, l’obiettivo non è solo quello di produrre un piano, ma anche quello di soddisfare le preferenze specificate dall’utente. Una differenza rispetto alla più comune pianificazione basata sulla ricompensa, ad esempio corrispondente a MDP, le preferenze non hanno necessariamente un preciso valore numerico.

Pianificazione condizionale
La pianificazione deterministica è stata introdotta con il sistema di pianificazione STRIPS, che è un pianificatore gerarchico. I nomi delle azioni sono ordinati in una sequenza e questo è un piano per il robot. La pianificazione gerarchica può essere confrontata con un albero di comportamento generato automaticamente. Lo svantaggio è che un normale albero di comportamento non è così espressivo come un programma per computer. Ciò significa che la notazione di un grafico di comportamento contiene comandi di azione, ma nessun loop o if-then-statement. La pianificazione condizionale supera il collo di bottiglia e introduce una notazione elaborata che è simile a un flusso di controllo, noto da altri linguaggi di programmazione come Pascal. È molto simile alla sintesi del programma, cioè un pianificatore genera un codice sorgente che può essere eseguito da un interprete.

Un primo esempio di pianificatore condizionale è “Warplan-C” che è stato introdotto a metà degli anni ’70. Fino ad ora, alla domanda non è stata data risposta quale sia la differenza tra una sequenza normale e un piano complicato, che contiene istruzioni if-then. Ha a che fare con l’incertezza in fase di esecuzione di un piano. L’idea è che un piano possa reagire ai segnali dei sensori che sono sconosciuti per il pianificatore. Il pianificatore genera due scelte in anticipo. Ad esempio, se viene rilevato un oggetto, viene eseguita l’azione A, se manca un oggetto, quindi viene eseguita l’azione B. Uno dei principali vantaggi della pianificazione condizionale è la capacità di gestire piani parziali. Un agente non è costretto a pianificare tutto dall’inizio alla fine, ma può dividere il problema in blocchi. Questo aiuta a ridurre lo spazio degli stati e risolve problemi molto più complessi.

Implementazione di sistemi di pianificazione
Hubble Space Telescope utilizza un sistema a breve termine chiamato SPSS e un sistema di pianificazione a lungo termine chiamato Spike.

Altri tipi di pianificazione
In pratica, controlla solo raramente ipotesi di pianificazione classica. Questo è il motivo per cui sono emerse molte estensioni.

Pianificazione conforme
Parliamo di una pianificazione conforme (programma conforme) in cui il sistema si trova in uno stato incerto, ma non è possibile alcuna osservazione. L’agente ha quindi credenze sul mondo reale. Questi problemi sono risolti con tecniche simili a quelle della pianificazione tradizionale, ma dove lo spazio degli stati è esponenziale nella dimensione del problema, a causa dell’incertezza sullo stato corrente. Una soluzione per un problema di pianificazione conforme è una sequenza di azioni.

Pianificazione di emergenza
Pianificazione di contingenza (pianificazione contingente) in cui l’ambiente è osservabile tramite sensori, che possono essere difettosi. Per un problema di pianificazione contingente, un piano non è più una sequenza di azioni ma un albero decisionale perché ogni fase del piano è rappresentata da un insieme di stati piuttosto che da un singolo stato perfettamente osservabile come nel caso della pianificazione classica.

Rintanen ha dimostrato nel 2004 che se si aggiunge la ramificazione (pianificazione contingente), il problema di pianificazione diventa EXPTIME -completo. Un caso particolare di pianificazione contigua è rappresentato dai problemi FOND – per “pienamente osservabile e non deterministico”. Se l’obiettivo è specificato in LTLf (logica temporale lineare su traccia finita), il problema è sempre EXPTIME-complete 16 e 2EXPTIME-complete per una specifica di scopo in LDLf.

Se, inoltre, si aggiunge incertezza alla pianificazione tradizionale (ad esempio la pianificazione conforme), diventa EXPSPACE -completo. Se aggiungiamo sia la ramificazione che l’incertezza (pianificazione sia conforme che contingente), diventa 2 ESCLUSIVA completa.

Pianificazione probabilistica
Kushmerick et al. ha introdotto la pianificazione probabilistica. Nel loro lavoro, l’effetto delle azioni è descritto con probabilisti. Dà l’esempio dell’azione “il robot prende un blocco” descritto nel modo seguente: se la pinza del robot è asciutta, il robot tiene il blocco con una probabilità di 0,95; se il morsetto è bagnato, il robot mantiene il blocco con una probabilità di 0,5.

Ciò porta al problema della generazione (o della strategia) della politica per un processo decisionale Markov (MDP) o (nel caso generale) un processo decisionale Markov parzialmente osservabile (POMDP).

Pianificazione non lineare
La pianificazione classica risolve i sotto-obiettivi in ​​un dato ordine. Il problema è che a volte porta a distruggere ciò che è già stato costruito. Questo fenomeno è noto come anomalia Sussman.

Supponiamo che un individuo a piedi nudi debba trovarsi nelle stesse condizioni in cui indossa la scarpa destra, la scarpa sinistra, il calzino destro e il calzino sinistro. Se cerca di raggiungere gli obiettivi nell’ordine dell’espressione, fallirà.

Per risolvere questo tipo di problema, è possibile passare a piani parzialmente ordinati in cui l’ordine tra le azioni è fisso solo quando è necessario (impegno al più recente o meno pianificazione dell’impegno).

Nell’esempio precedente, posizionare la scarpa sinistra dopo aver lasciato il calzino a sinistra. Lo stesso per la destra. D’altra parte, l’esecuzione del piano per la sinistra è indipendente dall’esecuzione per la destra. Il piano complessivo è quindi parzialmente ordinato.

I pianificatori in grado di gestire questa categoria di problemi sono considerati come ordini parziali (POP, NOAH, ecc.).

Pianificazione gerarchica
Generalmente, quando si pianifica, si può avere un’informazione gerarchica sulle azioni, vale a dire una descrizione su come le azioni complesse vengono scomposte. Ad esempio, un’azione complessa come “servire un caffè” può essere suddivisa nella sequenza di due azioni complesse “fare un caffè” e quindi “portare il caffè”. Quindi, ci sono progettisti, come ABSTRIPS, che oltre alla descrizione delle azioni, prendono come input la descrizione gerarchica delle azioni. Ad esempio, è possibile iniziare a pianificare a un livello elevato, quindi scendere nei dettagli se necessario (come ad esempio ABSTRIPS). L’obiettivo viene quindi descritto utilizzando una rete gerarchica dei compiti (HTN).

Pianificazione temporale
La pianificazione temporale consente di esprimere tempi di azione, condizioni all’inizio, alla fine e durante l’azione e gli effetti all’inizio e alla fine delle azioni. PDDL 2.1 include pianificazione del tempo. Il metodo TLP-GP 1 costruisce un grafico e quindi risolve i vincoli temporali utilizzando un risolutore SMT. Un backtracke in caso di incoerenza. Rintanen ha dimostrato che la pianificazione temporale simultanea (sono possibili più istanze della stessa azione parallela) è completa con EXPSPACE. D’altra parte, se rilassiamo queste condizioni, possiamo ridurci alla pianificazione convenzionale e quindi la pianificazione temporale con queste restrizioni diventa completa con PSPACE.

Pianificazione generale
La pianificazione generale consiste nel produrre un piano che funzioni per diversi ambienti di partenza.

Pianificazione multi-agente
La pianificazione multi-agente studia il completamento di un’attività da più agenti, ad esempio più robot. La generazione del piano e la sua esecuzione sono quindi spesso distribuiti / decentrati. Un aspetto importante nei piani è la cooperazione tra agenti. Esiste anche un algoritmo di schedulazione centralizzato, che si basa su una generalizzazione di STRIPS per il framework multi-agente, chiamato MA-STRIPS. L’algoritmo è stato quindi distribuito rendering, utilizzando un solver CSP distribuito per gestire il coordinamento tra agenti. Gli autori, Nissim, Brafman e Domshlak, hanno verificato sperimentalmente che il loro algoritmo è migliore della programmazione centralizzata quando gli agenti hanno poca interazione l’uno con l’altro.

Una delle maggiori difficoltà nella pianificazione multi-agente è l’esplosione combinatoria di tutte le azioni, che è esponenziale nel numero di agenti. Nel 2011, Jonsson e Rovatsos offrono una soluzione per contrastare questo problema che si riduce alla classica pianificazione di un singolo agente. C’è anche un rinnovato uso delle tecniche di parallelizzazione per la pianificazione degli algoritmi in scala.

Pianificazione epistemica
Il problema di pianificazione epistemica è di prendere in considerazione la conoscenza degli agenti nella descrizione degli stati e delle azioni. Tipicamente, l’obiettivo è una formula della logica modale epistemica, come “l’agente sa che l’agente b che il blocco C si trova sul blocco A” e le azioni sono rappresentate con modelli di azioni della logica dinamica epistemica. Il problema della pianificazione è indecidibile in tutta la sua generalità.

Obbiettivo :

Sopra (A, B) Λ Sopra (B, C)
Stato iniziale :

[Sopra (A, Tabella) Λ Sopra (B, Tabella) Λ Sopra (C, A) Λ Blocca (A) Λ Blocca (B) Λ Blocca (C) Λ Divulgazione (B) Λ Divulgazione (C)]
Azioni Disponibili:

Sposta (b, x, y)
PRE-CONDIZIONI: Sopra (b, x) Λ Scoperto (b) Λ Scoperto (y) Λ Blocco (b) Λ Blocco (y) Λ (b ≠ x) Λ (b ≠ y) Λ (x ≠ y)
AGGIUNTIVO: Sopra (b, y) Λ Scoperto (x)
CANCELLAZIONI: Sopra (b, x) Λ Scoperto (y)
Move_tool (b, x)
PRECONDIZIONI: Sopra (b, x) Λ Scoperto (b) Λ Scoperto (y) Λ Blocco (b) Λ (b ≠ x)
AGGIUNTIVO: Sopra (b, Tabella) Λ Scoperto (x)
CANCELLAZIONI: Sopra (b, x)

Esempio

Esempio informale di pianificazione.

Bersaglio
prendi un po ‘di frutta e verdura nel frigo

Stato iniziale
[frigo vuoto, a casa, in pantofole]

Azioni disponibili (elenco non ordinato)
vai a casa,
indossare scarpe,
prendere le chiavi della macchina,
raggiungere il negozio in auto,
raggiungere il negozio a piedi,
torna a casa,
posiziona gli acquisti in frigo,
entra nel negozio,
prendi frutta,
prendere le verdure,
pagare.

Possibile soluzione (elenco ordinato)
[1- indossare scarpe, 2- prendere le chiavi della macchina, 3- uscire da casa, 4- arrivare al negozio in auto, 5- entrare nel negozio, 6- prendere frutta, 7- prendere verdure, 8- pagare, 9- torna a casa, 10 posti in frigorifero]

Un’altra possibile soluzione (elenco ordinato):
[1- indossare scarpe, 2- uscire, 3- arrivare al negozio a piedi, 4- entrare nel negozio, 5- prendere verdure, 6- prendere frutta, 7- pagare, 8- andare a casa, acquisti 9 posti nel frigo]

conclusioni
Dall’esempio possiamo vedere come:

le soluzioni possono essere multiple,
possono essere presenti azioni che devono essere eseguite, inevitabilmente, dopo gli altri (non posso raggiungere il negozio in auto se non ho preso le chiavi prima),
possono esistere azioni reversibili (prendere frutta e verdura),
non è necessario che il piano finale contenga tutte le azioni in caso di più azioni o sequenze di azioni intercambiabili (raggiungere il negozio a piedi o in auto).