ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis
Autor/es:
SEBASTIÁN SARDIÑA; NATALIA RODRIGUEZ; NICOLAS D'IPPOLITO
Revista:
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, THE
Editorial:
AI ACCESS FOUNDATION
Referencias:
Año: 2018 vol. 61
ISSN:
1076-9757
Resumen:
We contribute to recent efforts in relating two approaches to automatic synthesis, namely, automatedplanning and discrete reactive synthesis. First, we develop a declarative characterizationof the standard ?fairness? assumption on environments in non-deterministic planning, and showthat strong-cyclic plans are correct solution concepts for fair environments. This complements, andarguably completes, the existing foundational work on non-deterministic planning, which focuseson characterizing (and computing) plans enjoying special ?structural? properties, namely loopy butclosed policy structures. Second, we provide an encoding suitable for reactive synthesis that avoidsthe naive exponential state space blowup. To do so, special care has to be taken to specify thefairness assumption on the environment in a succinct manner