Pianificazione automatica

I sistemi di pianificazione automatica del tipo sviluppato nell’ambito dell’Intelligenza detta "classica"^[3] 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.

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.

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^[5][6][7], 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^[3], SIPE^[8], SNLP^[9], PDDL 2.1^[10]) anche perché le forti assunzioni di STRIPS contribuivano a limitare troppo le applicazioni della pianificazione.

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^[11]. 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.

  PRECONDIZIONI: Sopra(b, x) Λ Scoperto(b) Λ Scoperto(y) Λ Blocco(b) Λ Blocco(y) Λ (b ≠ x) Λ (b ≠ y) Λ (x ≠ y)
  AGGIUNTE: Sopra(b, y) Λ Scoperto(x)
  CANCELLAZIONI: Sopra(b, x) Λ Scoperto(y)

  PRECONDIZIONI: Sopra(b, x) Λ Scoperto(b) Λ Scoperto(y) Λ Blocco(b) Λ (b ≠ x)
  AGGIUNTE: Sopra(b, Tavolo) Λ Scoperto(x)
  CANCELLAZIONI: Sopra(b, x)

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

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

• Riduzione al problema della soddisfacibilità proposizionale (es: Satplan^[13]).
• riduzione al problema del Model checking (es: MBP^[14]).

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.

  Lo stesso argomento in dettaglio: Processo decisionale di Markov.

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.

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

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^[16]. L'aumento di complessità impone di ricercare tecniche atte a facilitare la ricerca di piani in tali domini.

Il paradigma della pianificazione probabilista è stato introdotto da Kushmerick negli anni '90^[17]. 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).

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^[18]. 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^[19][20], 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^[21] e 2EXPTIME-completo quando la situazione iniziale è incerta e le azioni hanno effetti nondeterministici^[18].

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^[22][23].

• (EN) Malik Ghallab, Dana Nau e Paolo Traverso, Automated planning : theory and practice, Elsevier/Morgan Kaufmann, 2004, ISBN 9780080490519, OCLC 156908421. URL consultato il 23 luglio 2019.

• Intelligenza artificiale
• STRIPS (pianificatore automatico)
• Teoria del primo ordine

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica