Fully observable non-deterministic planning as assumption-based reactive synthesis

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-cy...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: D’Ippolito, N., Rodríguez, N., Sardina, S.
Formato: JOUR
Materias:
Electronics engineering
Automated planning
Automatic synthesis
Correct solution
Reactive synthesis
Artificial intelligence
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_10769757_v61_n_p593_DIppolito
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_10769757_v61_n_p593_DIppolito
record_format dspace
spelling todo:paper_10769757_v61_n_p593_DIppolito2023-10-03T16:03:29Z Fully observable non-deterministic planning as assumption-based reactive synthesis D’Ippolito, N. Rodríguez, N. Sardina, S. Electronics engineering Automated planning Automatic synthesis Correct solution Reactive synthesis Artificial intelligence 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. © 2018 AI Access Foundation. All rights reserved. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_10769757_v61_n_p593_DIppolito
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Electronics engineering
Automated planning
Automatic synthesis
Correct solution
Reactive synthesis
Artificial intelligence
spellingShingle Electronics engineering
Automated planning
Automatic synthesis
Correct solution
Reactive synthesis
Artificial intelligence
D’Ippolito, N.
Rodríguez, N.
Sardina, S.
Fully observable non-deterministic planning as assumption-based reactive synthesis
topic_facet Electronics engineering
Automated planning
Automatic synthesis
Correct solution
Reactive synthesis
Artificial intelligence
description 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. © 2018 AI Access Foundation. All rights reserved.
format JOUR
author D’Ippolito, N.
Rodríguez, N.
Sardina, S.
author_facet D’Ippolito, N.
Rodríguez, N.
Sardina, S.
author_sort D’Ippolito, N.
title Fully observable non-deterministic planning as assumption-based reactive synthesis
title_short Fully observable non-deterministic planning as assumption-based reactive synthesis
title_full Fully observable non-deterministic planning as assumption-based reactive synthesis
title_fullStr Fully observable non-deterministic planning as assumption-based reactive synthesis
title_full_unstemmed Fully observable non-deterministic planning as assumption-based reactive synthesis
title_sort fully observable non-deterministic planning as assumption-based reactive synthesis
url http://hdl.handle.net/20.500.12110/paper_10769757_v61_n_p593_DIppolito
work_keys_str_mv AT dippoliton fullyobservablenondeterministicplanningasassumptionbasedreactivesynthesis
AT rodriguezn fullyobservablenondeterministicplanningasassumptionbasedreactivesynthesis
AT sardinas fullyobservablenondeterministicplanningasassumptionbasedreactivesynthesis
_version_ 1807319109003640832

Ejemplares similares