Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis
Authors: Nicolás D'Ippolito, Natalia Rodrı́guez, Sebastian Sardina
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We contribute to recent efforts in relating two approaches to automatic synthesis, namely, automated planning and discrete reactive synthesis. First, we develop a declarative characterization of the standard fairness assumption on environments in non-deterministic planning, and show that strong-cyclic plans are correct solution concepts for fair environments. ... Second, we provide an encoding suitable for reactive synthesis that avoids the naive exponential state space blowup. ... The above two theorems say that state-strong fair is a complete characterization of the type of environment for which strong-cyclic plans are successful. ... Theorem 4 (Complexity). Let P = P, O, s I, φgoal be a FOND planning problem and GP its associated B uchi Control Problem as per Definition 8. Deciding whether GP is winning and computing a winning strategy for 2 can be done in O((4 |2P | |O|)2). |
| Researcher Affiliation | Academia | Nicolas D Ippolito EMAIL Instituto de Ciencias de la Computacion CONICET, Argentina Natalia Rodr ıguez EMAIL Departamento de Computacion, FCEN Universidad de Buenos Aires, Argentina Sebastian Sardina EMAIL School of Science (Computer Science) RMIT University, Australia |
| Pseudocode | No | The paper describes methods and transformations using mathematical definitions, theorems, and proofs. It includes diagrams of game reductions (Figure 1 and 2) but does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code, nor does it provide links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical contributions to non-deterministic planning and reactive synthesis, using abstract problem definitions and a coin-flipping example (Example 1) for illustration. It does not use or refer to any publicly available empirical datasets. |
| Dataset Splits | No | The paper does not utilize empirical datasets, therefore, there is no information regarding dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is a theoretical work focusing on formalizing planning problems and their complexity. It does not describe any experiments that would require specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical formalizations and complexity analysis. It does not describe an implementation or require specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | As a theoretical paper, it does not describe any empirical experiments, and therefore no experimental setup details, such as hyperparameters or training configurations, are provided. |