Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals
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.
Cite
Text
De Giacomo and Rubin. "Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/657Markdown
[De Giacomo and Rubin. "Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/giacomo2018ijcai-automata/) doi:10.24963/IJCAI.2018/657BibTeX
@inproceedings{giacomo2018ijcai-automata,
title = {{Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals}},
author = {De Giacomo, Giuseppe and Rubin, Sasha},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {4729-4735},
doi = {10.24963/IJCAI.2018/657},
url = {https://mlanthology.org/ijcai/2018/giacomo2018ijcai-automata/}
}