Ricerc@Sapienza

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.

Planning domains represent what an agent assumes or be- lieves about the environment it acts in. In the presence of non- determinism, additional temporal assumptions, such as fair- ness, are often expressed as extra conditions on the domain. Here we consider environment specifications expressed in ar- bitrary LTL, which generalize many forms of environment specifications, including classical specifications of nondeter- ministic domains, fairness, and other forms of linear-time constraints on the domain itself.