Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals

Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals

Giuseppe De Giacomo, Sasha Rubin

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4729-4735. https://doi.org/10.24963/ijcai.2018/657

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.
Keywords:
Knowledge Representation and Reasoning: Action, Change and Causality
Planning and Scheduling: Theoretical Foundations of Planning