Document Open Access Logo

A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty

Authors Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, Andrea Orlandini, Mark Reynolds

PDF
Thumbnail PDF

File

LIPIcs.TIME.2018.13.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Nicola Gigante
  • University of Udine, Udine, Italy
Angelo Montanari
  • University of Udine, Udine, Italy
Marta Cialdea Mayer
  • University of Roma Tre, Rome, Italy
Andrea Orlandini
  • National Research Council, Rome, Italy
Mark Reynolds
  • The University of Western Australia, Perth, Australia

Funding

  • Gigante, Nicola: N. Gigante and A. Montanari’s work was mainly done while on leave at The University of Western Australia. The work was supported by the GNCS project Formal methods for verification and synthesis of discrete and hybrid systems (N. Gigante, A. Montanari, M. Cialdea Mayer) and the PRID project ENCASE - Efforts in the uNderstanding of Complex interActing SystEms (N. Gigante, A. Montanari).
  • Reynolds, Mark: Mark Reynolds acknowledges the support of Australian Research Council funding (DP140103365).

Cite AsGet BibTex

Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, Andrea Orlandini, and Mark Reynolds. A Game-Theoretic Approach to Timeline-Based Planning with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TIME.2018.13

Abstract

In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behaviour over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesising control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of realistic problems. In this paper, we propose a novel game-theoretic approach to timeline-based planning problems, generalising the state of the art while uniformly handling temporal uncertainty and nondeterminism. We define a general concept of timeline-based game and we show that the notion of winning strategy for these games is strictly more general than that of control strategy for dynamically controllable flexible plans. Moreover, we show that the problem of establishing the existence of such winning strategies is decidable using a doubly exponential amount of space.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning under uncertainty
Keywords
  • Timeline-based planning with uncertainty
  • strategic games
  • decidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. J. F. Allen. Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11):832-843, 1983. Google Scholar
  2. R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time Temporal Logic. Journal of the ACM, 49(5):672-713, 2002. Google Scholar
  3. J. Barreiro, M. Boyce, M. Do, J. Frank, M. Iatauro, T. Kichkaylo, P. Morris, J. Ong, E. Remolina, T. Smith, and D. Smith. EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization. In Proc. of the 4superscriptth International Competition on Knowledge Engineering for Planning and Scheduling, 2012. Google Scholar
  4. M. Beetz and D. McDermott. Improving robot plans during their execution. In Proc. of the International Conference on Artificial Intelligence Planning Systems (AIPS), 1994. Google Scholar
  5. S. Borgo, A. Cesta, A. Orlandini, and A. Umbrico. A Planning-Based Architecture for a Reconfigurable Manufacturing System. In Proc. of the 26superscriptth International Conference on Automated Planning and Scheduling, pages 358-366, 2016. Google Scholar
  6. A. Camacho, E. Triantafillou, C. Muise, J. A. Baier, and S. A. McIlraith. Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces. In Proc. of the 31superscriptst AAAI Conference on Artificial Intelligence, 2017. Google Scholar
  7. A. Cesta, G. Cortellessa, S. Fratini, and A. Oddi. Developing an End-to-End Planning Application from a Timeline Representation Framework. In Proc. of the 21superscriptst Conference on Innovative Applications of Artificial Intelligence, pages 66-71, 2009. Google Scholar
  8. M. Cialdea Mayer and A. Orlandini. An Executable Semantics of Flexible Plans in Terms of Timed Game Automata. In Proc. of the 22superscriptnd International Symposium on Temporal Representation and Reasoning, pages 160-169, 2015. Google Scholar
  9. M. Cialdea Mayer, A. Orlandini, and A. Umbrico. Planning and Execution with Flexible Timelines: a Formal Account. Acta Informatica, 53(6-8):649-680, 2016. Google Scholar
  10. A. Cimatti, M. Do, A. Micheli, M. Roveri, and D. E. Smith. Strong temporal planning with uncontrollable durations. Artificial Intelligence, 256:1-34, 2018. Google Scholar
  11. A. Cimatti, A. Micheli, and M. Roveri. Timelines with Temporal Uncertainty. In Proc. the 27superscriptth AAAI Conference on Artificial Intelligence, 2013. Google Scholar
  12. A. Cimatti, M. Pistore, M. Roveri, and P. Traverso. Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence, 147(1):35-84, 2003. Google Scholar
  13. M. Fox and D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research, 20:61-124, 2003. Google Scholar
  14. J. Frank. What is a timeline? In Proc. of the 4superscriptth Workshop on Knowledge Engineering for Planning and Scheduling, pages 31-38, 2013. Google Scholar
  15. N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Timelines are Expressive Enough to Capture Action-based Temporal Planning. In Proc. of the 23superscriptrd International Symposium on Temporal Representation and Reasoning, pages 100-109, 2016. Google Scholar
  16. N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Complexity of timeline-based planning. In Proc. of the 27superscriptth International Conference on Automated Planning and Scheduling, pages 116-124, 2017. Google Scholar
  17. N. Gigante, A. Montanari, M. Cialdea Mayer, A. Orlandini, and M. Reynolds. A game-theoretic approach to timeline-based planning with uncertainty. CoRR, abs/1807.04837, 2018. URL: http://arxiv.org/abs/1807.04837.
  18. L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1):99-134, 1998. Google Scholar
  19. C. Muise, S. A. McIlraith, and J. C. Beck. Improved non-deterministic planning by exploiting state relevance. In Proc. of the 22superscriptnd International Conference on Automated Planning and Scheduling, 2012. Google Scholar
  20. C. Muise, S.A. McIlraith, and V. Belle. Non-deterministic planning with conditional effects. In Proc. of the 24superscriptth International Conference on Automated Planning and Scheduling, 2014. Google Scholar
  21. N. Muscettola. HSTS: Integrating Planning and Scheduling. In Monte Zweben and Mark S. Fox, editors, Intelligent Scheduling, chapter 6, pages 169-212. Morgan Kaufmann, 1994. Google Scholar
  22. F. Patrizi, N. Lipovetzky, and H. Geffner. Fair LTL synthesis for non-deterministic systems using strong cyclic planners. In Proc. of the 23superscriptrd International Joint Conference on Artificial Intelligence, 2014. Google Scholar
  23. S. Steel. Action under uncertainty. Journal of Logic and Computation, 4(5):767-795, 1994. Google Scholar
  24. A. Umbrico, A. Cesta, M. Cialdea Mayer, and A. Orlandini. PLATINUm: A New Framework for Planning and Acting in Human-Robot Collaborative Scenarios. In Proc. of the 16superscriptth International Conference of the Italian Association for Artificial Intelligence, pages 498-512, 2017. Google Scholar
  25. T. Vidal and H. Fargier. Handling Contingency in Temporal Constraint Networks: from Consistency to Controllabilities. Journal of Experimental and Theoretical Artificial Intelligence, 11(1):23-45, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact