Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals
Authors: Giuseppe De Giacomo, Sasha Rubin
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 2EXPTIMEhardness for strong cyclic plans, which was open. |
| Researcher Affiliation | Academia | Giuseppe De Giacomo Univ. Roma La Sapienza , Italy degiacomo@dis.uniroma1.it Sasha Rubin Univ. Napoli Federico II , Italy sasha.rubin@unina.it |
| Pseudocode | Yes | Algorithm 1: FONDunr for LDLf/LTLf goals Given LTLf/LDLf domain D and goal ϕ 1: Compute DFA corresponding to D (poly) 2: Compute NFA for ϕ (exp) 3: Determinize NFA to DFA (exp) 4: Compute product with DFA of D (poly) 5: Solve DFA game (poly) 6: Return winning strategy if it exists |
| Open Source Code | No | The paper does not provide any statement or link for open-source code related to the described methodology. It mentions experimental feasibility observed in prior work [Camacho et al., 2017b] but not its own code release. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not use dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and discusses algorithmic concepts rather than concrete software implementations, thus no software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or system-level training settings. |