LIPIcs.TIME.2023.22.pdf
- Filesize: 493 kB
- 3 pages
Document
Qualitative past Timeline-Based Games (Extended Abstract)
Authors
Luca Geatti 
,
Nicola Gigante ,
Angelo Montanari
-
Part of:
Volume:
30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Temporal Representation and Reasoning (TIME) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-09-18
File
Document Identifiers
Author Details
Cite As Get BibTex
Renato Acampora, Luca Geatti, Nicola Gigante, and Angelo Montanari. Qualitative past Timeline-Based Games (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 22:1-22:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.TIME.2023.22
Abstract
This extended abstract discusses timeline-based planning, a modeling approach that offers a unique way to model complex systems. Recently, the timeline-based planning framework has been extended to handle general nondeterminism in a game-theoretic setting, resulting in timeline-based games. In this context, the problem of establishing whether a timeline-based game admits a winning strategy and synthesizing such a strategy have been addressed. We propose exploring simpler yet expressive fragments of timeline-based games by leveraging results about the role of past operators in synthesis from temporal logic specifications. The qualitative fragment of timeline-based planning is a good starting point for this exploration. We suggest introducing syntactic restrictions on synchronization rules so that they only constrain the behavior of the system before the current time point, which is expected to lower the complexity of synthesizing timeline-based games to EXPTIME.
Subject Classification
ACM Subject Classification
- Computing methodologies → Planning for deterministic actions
Keywords
- Automata
- Planning
- Temporal Reasoning
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Renato Acampora, Luca Geatti, Nicola Gigante, Angelo Montanari, and Valentino Picotti. Controller synthesis for timeline-based games. In Pierre Ganty and Dario Della Monica, editors, Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2022, Madrid, Spain, September 21-23, 2022, volume 370 of EPTCS, pages 131-146, 2022. URL: https://doi.org/10.4204/EPTCS.370.9.
- Alessandro Artale, Luca Geatti, Nicola Gigante, Andrea Mazzullo, and Angelo Montanari. Complexity of safety and cosafety fragments of linear temporal logic. In Proceedings of the AAAI Conference on Artificial Intelligence 37(5), pages 6236-6244, 2023. URL: https://doi.org/10.1609/aaai.v37i5.25768.
-
Jerry R Burch, Edmund M Clarke, Kenneth L McMillan, David L Dill, and Lain-Jinn Hwang. Symbolic model checking: 1020 states and beyond. Information and computation, 98(2):142-170, 1992.
- Dario Della Monica, Nicola Gigante, Angelo Montanari, Pietro Sala, and Guido Sciavicco. Bounded timed propositional temporal logic with past captures timeline-based planning with bounded constraints. In Carles Sierra, editor, Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 1008-1014, 2017. URL: https://doi.org/10.24963/ijcai.2017/140.
- Richard E. Fikes and Nils J. Nilsson. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3):189-208, 1971. URL: https://doi.org/10.1016/0004-3702(71)90010-5.
- Giuseppe De Giacomo, Antonio Di Stasio, Francesco Fuggitti, and Sasha Rubin. Pure-past linear temporal and dynamic logic on finite traces. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4959-4965. ijcai.org, 2020. URL: https://doi.org/10.24963/ijcai.2020/690.
- Nicola Gigante, Angelo Montanari, Andrea Orlandini, Marta Cialdea Mayer, and Mark Reynolds. On timeline-based games and their complexity. Theoretical Computer Science, 815:247-269, May 2020. URL: https://doi.org/10.1016/j.tcs.2020.02.011.
-
Swen Jacobs, Roderick Bloem, Romain Brenguier, Rüdiger Ehlers, Timotheus Hell, Robert Könighofer, Guillermo A Pérez, Jean-François Raskin, Leonid Ryzhyk, Ocan Sankur, et al. The first reactive synthesis competition (syntcomp 2014). International journal on software tools for technology transfer, 19:367-390, 2017.
- Marta Cialdea Mayer, Andrea Orlandini, and Alessandro Umbrico. Planning and execution with flexible timelines: a formal account. Acta Informatica, 53(6-8):649-680, 2016. URL: https://doi.org/10.1007/s00236-015-0252-z.
- Dario Della Monica, Nicola Gigante, Salvatore La Torre, and Angelo Montanari. Complexity of qualitative timeline-based planning. In 27th International Symposium on Temporal Representation and Reasoning, TIME 2020, September 23-25, 2020, Bozen-Bolzano, Italy, volume 178 of LIPIcs, pages 16:1-16:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.TIME.2020.16.
- Nicola Muscettola. HSTS: Integrating Planning and Scheduling. In Monte Zweben and Mark S. Fox, editors, Intelligent Scheduling, chapter 6, pages 169-212. Morgan Kaufmann, 1994. URL: https://apps.dtic.mil/sti/pdfs/ADA266991.pdf.
- Nicola Muscettola, Stephen F. Smith, Amedeo Cesta, and Daniela D'Aloisi. Coordinating space telescope operations in an integrated planning and scheduling architecture. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Sacramento, CA, USA, 9-11 April 1991, pages 1369-1376. IEEE Computer Society, 1991. URL: https://doi.org/10.1109/ROBOT.1991.131803.