info:eu-repo/semantics/article
Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis
Date
2018-03Registration in:
D'ippolito, Nicolás Roque; Rodriguez, Natalia; Sardina, Sebastian; Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis; AI Access Foundation; Journal of Artificial Intelligence Research; 61; 3-2018; 593-621
1076-9757
CONICET Digital
CONICET
Author
D'ippolito, Nicolás Roque
Rodriguez, Natalia
Sardina, Sebastian
Abstract
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. This complements, and arguably completes, the existing foundational work on non-deterministic planning, which focuses on characterizing (and computing) plans enjoying special “structural” properties, namely loopy but closed policy structures. Second, we provide an encoding suitable for reactive synthesis that avoids the naive exponential state space blowup. To do so, special care has to be taken to specify the fairness assumption on the environment in a succinct manner.