Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor

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. © 2018 AI Access Foundation. All rights reserved.

Registro:

Documento: Artículo
Título:Fully observable non-deterministic planning as assumption-based reactive synthesis
Autor:D’Ippolito, N.; Rodríguez, N.; Sardina, S.
Filiación:Instituto de Ciencias de la Computación CONICET, Argentina
Departamento de Computación, FCEN, Universidad de Buenos, Aires, Argentina
School of Science (Computer Science), RMIT University, Australia
Palabras clave:Electronics engineering; Automated planning; Automatic synthesis; Correct solution; Reactive synthesis; Artificial intelligence
Año:2018
Volumen:61
Página de inicio:593
Página de fin:621
Título revista:Journal of Artificial Intelligence Research
Título revista abreviado:J Artif Intell Res
ISSN:10769757
CODEN:JAIRF
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10769757_v61_n_p593_DIppolito

Referencias:

  • Abadi, M., Lamport, L., Wolper, P., Realizable and unrealizable specifications of reactive systems (1989) Proceedings of The International Colloquium on Automata, Languages and Programming (ICALP), pp. 1-17
  • Baier, C., Katoen, J., (2008) Principles of Model Checking, , The MIT Press
  • Bloem, R., Jobstmann, B., Piterman, N., Pnueli, A., Sa’ar, Y., Synthesis of reactive(1) designs (2012) Journal of Computer and System Sciences, 78 (3), pp. 911-938
  • Bryce, D., Buffet, O., The 6th international planning competition: Uncertainty track (2008) Proceedings of International Planning Competition (IPC)
  • Buchi, J., Landweber, L., Solving sequential conditions by finite-state strategies (1969) Transactions of The American Mathematical Society, pp. 295-311
  • Bylander, T., The computational complexity of propositional strips planning (1994) Artificial Intelligence, 69, pp. 165-204
  • Camacho, A., McIlraith, S.A., Strong-cyclic planning when fairness is not a valid assumption (2016) Proceedings of The Workshop on Knowledge-Based Techniques for Problem Solving and Reasoning, , http://ktiml.mff.cuni.cz/bartak/KnowProS2016
  • Camacho, A., Triantafillou, E., Muise, C.J., Baier, J.A., McIlraith, S.A., Non-deterministic planning with temporally extended goals: Completing the story for finite and infinite LTL (2016) Proceedings of The Workshop on Knowledge-Based Techniques for Problem Solving and Reasoning, , http://ktiml.mff.cuni.cz/bartak/KnowProS2016
  • Chatterjee, K., Jurdzinski, M., Henzinger, T.A., Quantitative stochastic parity games (2004) Proceedings of The Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 121-130
  • Church, A., Logic, arithmetic, and automata (1963) Proceedings of The International Congress of Mathematicians, pp. 23-35
  • Cimatti, A., Pistore, M., Roveri, M., Traverso, P., Weak, strong, and strong cyclic planning via symbolic model checking (2003) Artificial Intelligence, 147 (1-2), pp. 35-84
  • Ciolek, D., Braberman, V.A., D’Ippolito, N., Uchitel, S., Directed controller synthesis of discrete event systems: Taming composition with heuristics (2016) Proeedings of The IEEE Conference on Decision and Control (CDC), pp. 4764-4769
  • Clarke, E., Emerson, E., Design and synthesis of synchronization skeletons using branching time temporal logic (1982) Logics of Programs, 131, pp. 52-71. , D. Kozen Ed, Springer
  • Clarke, E., Grumberg, O., Peled, D., (1999) Model Checking, , Springer
  • Daniele, M., Traverso, P., Vardi, M., Strong cyclic planning revisited (2000) Recent Advances in AI Planning, pp. 35-48
  • De Giacomo, G., Patrizi, F., Felli, P., Sardina, S., Two-player game structures for generalized planning and agent composition (2010) Proceedings of The National Conference on Artificial Intelligence (AAAI), pp. 297-302
  • De Giacomo, G., Patrizi, F., Sardina, S., Generalized planning with loops under strong fairness constraints (2010) Proceedings of The International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 351-361
  • De Giacomo, G., Vardi, M.Y., Synthesis for LTL and LDL on finite traces (2015) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 1558-1564
  • D’Ippolito, N., Braberman, V.A., Piterman, N., Uchitel, S., Synthesis of live behaviour models for fallible domains (2011) Proceedings of The International Conference on Software Engineering (ICSE), pp. 211-220
  • D’Ippolito, N., Braberman, V.A., Piterman, N., Uchitel, S., Synthesizing non-anomalous event-based controllers for liveness goals (2013) ACM Transactions on Software Engineering and Methodology (TOSEM), 22 (1), pp. 9:1–9:36
  • Domshlak, C., Fault tolerant planning: Complexity and compilation (2013) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 64-72
  • Emerson, E.A., Temporal and modal logic (1990) Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, B, pp. 995-1072. , The MIT Press
  • Emerson, E.A., Halpern, J.Y., Sometimes” and “not never” revisited: On branching versus linear time temporal logic (1986) Journal of The ACM, 33 (1), pp. 151-178
  • Forejt, V., Kwiatkowska, M.Z., Norman, G., Parker, D., Automated verification techniques for probabilistic systems (2011) Proceedings of The International School on Formal Methods for The Design of Computer (SFM), pp. 53-113
  • Fu, J., Ng, V., Bastani, F., Yen, I.-L., Simple and fast strong cyclic planning for fully-observable non-deterministic planning problems (2011) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 1949-1954
  • Geffner, H., Bonet, B., (2013) A Concise Introduction to Models and Methods for Automated Planning, , Morgan & Claypool Publishers
  • Gerevini, A., Bonet, B., Givan, B., (2006) Booklet of 4th International Planning Competition, , http://www.ldc.usb.ve/bonet/ipc5/, Eds
  • Ghallab, M., Nau, D.S., Traverso, P., (2004) Automated Planning: Theory and Practice, , Morgan Kaufmann Publishers Inc
  • Green, C., Application of theorem-proving to problem solving (1969) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 219-239
  • Kerjean, S., Kabanza, F., St.-Denis, R., Thiébaux, S., Analyzing LTL model checking techniques for plan synthesis and controller synthesis (work in progress) (2006) Electronic Notes in Theoretical Computer Science (ENTCS), 149 (2), pp. 91-104
  • Kesten, Y., Piterman, N., Pnueli, A., Bridging the gap between fair simulation and trace inclusion (2005) Journal Information and Computation, 200, pp. 35-61. , July
  • Kissmann, P., Edelkamp, S., Solving fully-observable non-deterministic planning problems via translation into a general game (2009) Proceedings of The Annual German Conference on AI, pp. 1-8
  • Kupferman, O., Piterman, N., Vardi, M.Y., Safraless compositional synthesis (2006) Proceedings of The International Conference on Computer Aided Verification (CAV), pp. 31-44
  • Kuter, U., Nau, S., Reisner, E., Goldman, P., Using classical planners to solve nondeterministic planning problems (2008) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 190-197
  • Maler, O., Pnueli, A., Sifakis, J., On the synthesis of discrete controllers for timed systems (1995) Stacs, 95, pp. 229-242
  • Manna, Z., Waldinger, R., How to clear a block: A theory of plans (1987) Journal of Automed Reasoning, 4 (3), pp. 343-377
  • Martin, D., Borel determinacy (1975) Annals of Mathematics, pp. 363-371
  • Muise, C., Belle, V., McIlraith, S.A., Computing contingent plans via fully observable non-deterministic planning (2014) Proceedings of The National Conference on Artificial Intelligence (AAAI), pp. 2322-2329
  • Muise, C., McIlraith, S.A., Beck, J.C., Improved non-deterministic planning by exploiting state relevance (2012) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 172-180
  • Muise, C., McIlraith, S.A., Belle, V., Non-deterministic planning with conditional effects (2014) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 370-374
  • Ortlieb, M., Mattmüller, R., Pattern-database heuristics for partially observable nondeterministic planning (2013) Proceedings of The Annual German Conference on AI, pp. 140-151
  • Patrizi, F., Lipovetzky, N., De Giacomo, G., Geffner, H., Computing infinite plans for LTL goals using a classical planner (2011) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 2003-2008
  • Patrizi, F., Lipovetzky, N., Geffner, H., Fair LTL synthesis for non-deterministic systems using strong cyclic planners (2013) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI)
  • Pistore, M., Traverso, P., Planning as model checking for extended goals in nondeterministic domains (2001) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 479-486
  • Pistore, M., Vardi, M.Y., The planning spectrum - One, two, three, infinity (2007) Journal of Artificial Intelligence Research (JAIR), 30, pp. 101-132
  • Piterman, N., Pnueli, A., Sa’ar, Y., Synthesis of reactive(1) designs (2006) Proceedings of The International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI), pp. 364-380
  • Pnueli, A., The temporal logic of programs (1977) Proceedings of The Annual Symposium on Foundations of Computer Science (SFCS), pp. 46-57
  • Pnueli, A., Rosner, R., On the synthesis of an asynchronous reactive module (1989) Proceedings of The International Colloquium on Automata, Languages and Programming (ICALP), pp. 652-671
  • Pnueli, A., Rosner, R., On the synthesis of a reactive module (1989) Proceedings of The ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 179-190
  • Ramirez, M., Sardina, S., Directed fixed-point regression-based planning for nondeterministic domains (2014) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 235-243
  • Rintanen, J., Constructing conditional plans by a theorem-prover (1999) Journal of Artificial Intelligence Research (JAIR), 10, pp. 323-352
  • Rintanen, J., Expressive equivalence of formalisms for planning with sensing (2003) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 185-194
  • Rintanen, J., Complexity of planning with partial observability (2004) Proceedings of The International Conference on Automated Planning and Scheduling (ICAPS), pp. 345-354
  • Rintanen, J., Regression for classical and nondeterministic planning (2008) Proceedings of The European Conference in Artificial Intelligence (ECAI), pp. 568-572
  • Rosner, R., (1992) Modular Synthesis of Reactive Systems, , Unpublished doctoral dissertation). Weizmann Institute of Science
  • Sardina, S., D’Ippolito, N., Towards fully observable non-deterministic planning as assumption-based reactive synthesis (2015) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 3200-3206
  • Torres, J., Baier, J.A., Polynomial-time reformulations of LTL temporally extended goals into final-state goals (2015) Proceedings of The International Joint Conference on Artificial Intelligence (IJCAI), pp. 1696-1703
  • Vardi, M.Y., An automata-theoretic approach to fair realizability and synthesis (1995) Proceedings of The International Conference on Computer Aided Verification (CAV), pp. 267-278
  • Vardi, M.Y., An automata-theoretic approach to linear temporal logic (1996) Logics for Concurrency: Structure Versus Automata, 1043, pp. 238-266. , Springer
  • Von Neumann, J., Morgenstern, O., Kuhn, H., Rubinstein, A., (1944) Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition), , Princeton University Press

Citas:

---------- APA ----------
D’Ippolito, N., Rodríguez, N. & Sardina, S. (2018) . Fully observable non-deterministic planning as assumption-based reactive synthesis. Journal of Artificial Intelligence Research, 61, 593-621.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10769757_v61_n_p593_DIppolito [ ]
---------- CHICAGO ----------
D’Ippolito, N., Rodríguez, N., Sardina, S. "Fully observable non-deterministic planning as assumption-based reactive synthesis" . Journal of Artificial Intelligence Research 61 (2018) : 593-621.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10769757_v61_n_p593_DIppolito [ ]
---------- MLA ----------
D’Ippolito, N., Rodríguez, N., Sardina, S. "Fully observable non-deterministic planning as assumption-based reactive synthesis" . Journal of Artificial Intelligence Research, vol. 61, 2018, pp. 593-621.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10769757_v61_n_p593_DIppolito [ ]
---------- VANCOUVER ----------
D’Ippolito, N., Rodríguez, N., Sardina, S. Fully observable non-deterministic planning as assumption-based reactive synthesis. J Artif Intell Res. 2018;61:593-621.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10769757_v61_n_p593_DIppolito [ ]