We study planning for LTLf and LDLf temporally extended goals in nondeterministic fully observable domains (FOND). We consider both strong and strong cyclic plans, and develop foundational automata-based techniques to deal with both cases. Using these techniques we provide the computational characterization of both problems, separating the complexity in the size of the domain specification from that in the size of the formula. Specifically we establish them to be EXPTIME-complete and 2EXPTIME-complete, respectively, for both problems. In doing so, we also show 2EXPTIME-hardness for strong cyclic plans, which was open.
Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals / DE GIACOMO, Giuseppe; Rubin, Sasha. - (2018), pp. 4729-4735. (Intervento presentato al convegno 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 tenutosi a Stockholm; Sweden).
Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals
Giuseppe De Giacomo
;RUBIN, SASHA
2018
Abstract
We study planning for LTLf and LDLf temporally extended goals in nondeterministic fully observable domains (FOND). We consider both strong and strong cyclic plans, and develop foundational automata-based techniques to deal with both cases. Using these techniques we provide the computational characterization of both problems, separating the complexity in the size of the domain specification from that in the size of the formula. Specifically we establish them to be EXPTIME-complete and 2EXPTIME-complete, respectively, for both problems. In doing so, we also show 2EXPTIME-hardness for strong cyclic plans, which was open.File | Dimensione | Formato | |
---|---|---|---|
DeGiacomo_Automata-Theoretic_2018.pdf
solo gestori archivio
Note: https://www.ijcai.org/proceedings/2018/
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
201.27 kB
Formato
Adobe PDF
|
201.27 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.