Pianificazione automatica

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

La pianificazione automatica è una branca dell'intelligenza artificiale e, in particolare, rappresenta un'attività di problem solving[1]. 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[2].

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

La pianificazione[modifica | modifica wikitesto]

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.

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[4][modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

Il mondo dei blocchi[1][modifica | modifica wikitesto]

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.

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)
  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)
  • Muovi_sul_tavolo(b, x)
  PRECONDIZIONI: Sopra(b, x) Λ Scoperto(b) Λ Scoperto(y) Λ Blocco(b) Λ (b ≠ x)
  AGGIUNTE: Sopra(b, Tavolo) Λ Scoperto(x)
  CANCELLAZIONI: Sopra(b, x)

Algoritmi per la pianificazione[modifica | modifica wikitesto]

Pianificazione classica[modifica | modifica wikitesto]

Riduzione ad altri problemi[modifica | modifica wikitesto]

La riduzione del problema di pianificazione ad un altro tipo di problema è la tecnica che converte un problema di pianificazione in un altro problema in modo tale che una soluzione per possa essere usata per risolvere .

Pianificazione temporale[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

Pianificazione basata sulle preferenze[modifica | modifica wikitesto]

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.

Estensioni del modello classico[modifica | modifica wikitesto]

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.

Pianificazione probabilista[modifica | modifica wikitesto]

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).

Pianificazione conformante[modifica | modifica wikitesto]

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].

Pianificazione contingente[modifica | modifica wikitesto]

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].

Note[modifica | modifica wikitesto]

  1. ^ a b Stuart J. Russel e Peter Norving, Artificial Intelligence, Pearson, 2017, ISBN 978-93-325-4351-5.
  2. ^ Susan Reichley, 2001 News Releases - Artificial Intelligence: It's More Than a Movie, su jpl.nasa.gov. URL consultato il 12 settembre 2017 (archiviato dall'url originale il 7 giugno 2019).
  3. ^ a b (EN) Chapman, Planning for conjunctive goals, in Artificial Intelligence, vol. 32, n. 3, 1º luglio 1987, pp. 333–377, DOI:10.1016/0004-3702(87)90092-0. URL consultato il 27 luglio 2018.
  4. ^ Aldo Franco Dragoni, IA22.1. Pianificazione: ricerca in uno spazio di teorie logiche, 6 dicembre 2016. URL consultato il 18 settembre 2017.
  5. ^ Russel e Norvig, cap. 11-4.
  6. ^ Nilsson, N., Principles of Artificial Intelligence, Tioga, 1980.
  7. ^ (EN) Fikes, R. e Nilsson, N., STRIPS: A new approach to the application of theorem proving to problem solving, in Artificial Intelligence, vol. 1, 1971, pp. 27–120.
  8. ^ (EN) Wilkins, D., Practical Planning: Extending the classical AI paradigm, Morgan Kaufmann, 1988.
  9. ^ (EN) McAllester, David e Rosenblatt, David, Systematic Nonlinear Planning, Artificial Intelligence Lab Publications, MIT, 1º dicembre 1991. URL consultato il 27 luglio 2018.
  10. ^ (EN) M. Fox e D. Long, PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains, in Journal of Artificial Intelligence Research, vol. 20, 1º dicembre 2003, pp. 61–124, DOI:10.1613/jair.1129. URL consultato il 27 luglio 2018.
  11. ^ (EN) Winograd T., Understanding Natural Language, New York, USA, Academic Press, 1972.
  12. ^ (EN) Blai Bonet e Héctor Geffner, Planning as heuristic search, in Artificial Intelligence, vol. 129.1-2, 2001, pp. 5-33.
  13. ^ (EN) Henry Kautz, Bart Selman e Joerg Hoffmann, SatPlan: Planning as satisfiability, in 5th international planning competition, vol. 20, n. 49, 2006.
  14. ^ Bertoli, P., Cimatti, A., Pistore, M., Roveri, M. e Traverso, P., MBP: a model based planner, in Proc. of the IJCAI’01 Workshop on Planning under Uncertainty and Incomplete Information, 2001.
  15. ^ (EN) M. Bienvenu e S. McIlraith, Specifying and Generating Preferred Plans, in Working Notes of the Seventh International Symposium on Logical Formalizations of Commonsense Reasoning, maggio 2005.
  16. ^ (EN) Bylander, Complexity Results for Extended Planning, in Artificial Intelligence Planning Systems, 1º gennaio 1992, pp. 20–27, DOI:10.1016/B978-0-08-049944-4.50008-2. URL consultato il 27 luglio 2018.
  17. ^ (EN) Nicholas Kushmerick, Steve Hanks e Daniel S. Weld, An algorithm for probabilistic planning, in Artificial Intelligence, vol. 76, n. 1-2, 1995-7, pp. 239–286, DOI:10.1016/0004-3702(94)00087-H. URL consultato il 23 luglio 2019.
  18. ^ a b (EN) Jussi Rintanen, Complexity of Planning with Partial Observability (PDF), in AAAI, 2004, p. 1. URL consultato il 23 luglio 2019 (archiviato dall'url originale il 31 ottobre 2020).
  19. ^ (EN) Hector Palacios e Hector Geffner, Compiling uncertainty away in conformant planning problems with bounded width, in Journal of Artificial Intelligence Research, vol. 35, 2009, pp. 623-675.
  20. ^ (EN) Alexandre Albore, Miquel Ramírez e Hector Geffner, Effective heuristics and belief tracking for planning with incomplete information, International Conference on Automated Planning and Scheduling (ICAPS), 2011.
  21. ^ (EN) Haslum e Jonsson, Some Results on the Complexity of Planning with Incomplete Information, in Biundo, Susanne e Fox, Maria (a cura di), Recent advances in AI planning, 5th European Conference on Planning, ECP'99, 8-10 settembre 1999, Durham, UK, Springer, 2000, ISBN 9783540446576, OCLC 321345753. URL consultato il 23 luglio 2019.
  22. ^ (EN) Michael L. Littman, Probabilistic Propositional Planning: Representations and Complexity, Fourteenth National Conference on Artificial Intelligence, MIT Press, 1997, pp. 748–754. URL consultato il 10 febbraio 2019.
  23. ^ (EN) Jussi Rintanen, AAAI, Complexity of Planning with Partial Observability (PDF), Int. Conf. Automated Planning and Scheduling, 2004. URL consultato il 23 luglio 2019 (archiviato dall'url originale il 31 ottobre 2020).

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]