Towards Fully Observable Non-Deterministic Planning as Assumption-based Automatic Synthesis
Authors: Sebastian Sardina, Nicolas D'Ippolito
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we revisit what planning under nondeterministic actions is with the aim of framing it as a special case of controller synthesis [Pnueli and Rosner, 1989]. The study of both novel controller synthesis and planning techniques could lead to interesting developments in the planning community by taking advantages of the expressiveness and guarantees provided by the controller synthesis approaches. Moreover, whereas control synthesis was deemed computationally impossible in the past, recent approaches (e.g., [Bloem et al., 2012; D Ippolito et al., 2011]) have shown that for some quite expressive specifications, the task is amenable for computation. In turn, planning problem specifications can inform meaningful specifications for goals and assumptions to the reactive synthesis field. It turns out that to make such link evident, one needs to formalize the assumptions on the environments in which strong cyclic plans are guaranteed to eventually achieve their goals. Surprisingly, this aspect has merely been discussed at an informal level, by calling for fair environments, that is, those in which all actions outcomes will ensue infinitely often, if tried infinitely often. To settle that formally, we provide a logical characterization of the environment which complements that of good plans found in [Pistore and Traverso, 2001]. We show, with an example, that a naive interpretation of the fairness assumption does not yield the expected results, and provide a characterization that accounts for failure independence. We prove that strong cyclic plans are indeed sound and complete solution concepts under such characterization. Finally, we argue that, by using the characterization developed, reactive synthesis [Pnueli and Rosner, 1989] can be directly used to solve FOND planning tasks, and show that, for the special case in which actions have intended effects, existing effective synthesis techniques can be exploited. |
| Researcher Affiliation | Academia | Sebastian Sardina School of Computer Science and IT RMIT University Melbourne, Australia sebastian.sardina@rmit.edu.au Nicolas D Ippolito Departamento de Computaci on, FCEN Universidad de Buenos Aires Buenos Aires, Argentina ndippolito@dc.uba.ar |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., specific repository link, explicit statement of code release, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on formalizing planning problems and relating them to synthesis. It does not conduct experiments on datasets or provide access to any training data. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving validation datasets or splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers for its own contributions. It mentions existing tools (PRP, NDP, FIP, MBP, GRENDEL) but not as dependencies for its own work or with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no experimental setup details like hyperparameters or training settings are provided. |