We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies mu that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that mu terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable nondeterministic planning.
Generalized planning: Non-deterministic abstractions and trajectory constraints / Bonet, Blai; De Giacomo, Giuseppe; Geffner, HECTOR ALBERTO; Rubin, Sasha. - STAMPA. - (2017), pp. 873-879. (Intervento presentato al convegno 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 tenutosi a Melbourne; Australia nel 2017) [10.24963/ijcai.2017/121].
Generalized planning: Non-deterministic abstractions and trajectory constraints
De Giacomo, Giuseppe
;GEFFNER, HECTOR ALBERTO
;RUBIN, SASHA
2017
Abstract
We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies mu that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that mu terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable nondeterministic planning.File | Dimensione | Formato | |
---|---|---|---|
Bonet_Postprint_Generalized-Planning_2017.pdf
accesso aperto
Note: https://www.ijcai.org/proceedings/2017/121
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
242.11 kB
Formato
Adobe PDF
|
242.11 kB | Adobe PDF | |
Bonet_Generalized-Planning_2017.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
160.36 kB
Formato
Adobe PDF
|
160.36 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.