Document Open Access Logo

Conditional Simple Temporal Networks with Uncertainty and Decisions

Author Matteo Zavatteri

PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.23.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Matteo Zavatteri

Cite As Get BibTex

Matteo Zavatteri. Conditional Simple Temporal Networks with Uncertainty and Decisions. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.TIME.2017.23

Abstract

A conditional simple temporal network with uncertainty (CSTNU) is a framework able to model temporal plans subject to both conditional constraints and uncertain durations. The combination of these two characteristics represents the uncontrollable part of the network. That is, before the network starts executing, we do not know completely which time points and constraints will be taken into consideration nor how long the uncertain durations will last. Dynamic controllability (DC) implies the existence of a strategy scheduling the time points of the network in real time depending on how the uncontrollable part behaves. Despite all this, CSTNUs fail to model temporal plans in which a few conditional constraints are under control and may therefore influence (or be influenced by) the uncontrollable part. To bridge this gap, this paper proposes conditional simple temporal networks with uncertainty and decisions (CSTNUDs) which introduce decision time points into the specification in order to operate on this conditional part under control. We model the dynamic controllability checking (DC-checking) of a CSTNUD as a two-player game in which each player makes his moves in his turn at a specific time instant. We give an encoding into timed game automata for a sound and complete DC-checking. We also synthesize memoryless execution strategies for CSTNUDs proved to be DC. The proposed approach is fully automated.

Subject Classification

Keywords
  • cstnud
  • dynamic controllability
  • timed game automata
  • controller synthesis
  • advanced temporal planning under uncertainty

Metrics

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

References

  1. Rajeev Alur and David L. Dill. A theory of timed automata. Theoretical Computer Science, 126(2):183-235, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90010-8.
  2. Gerd Behrmann, Agnès Cougnard, Alexandre David, Emmanuel Fleury, Kim G. Larsen, and Didier Lime. Uppaal-tiga: Time for playing games! In CAV 2007. Springer Berlin Heidelberg, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73368-3_14.
  3. Massimo Cairo, Carlo Combi, Carlo Comin, Luke Hunsberger, Roberto Posenato, Romeo Rizzi, and Matteo Zavatteri. Incorporating decision nodes into conditional simple temporal networks. In S. Schewe, T. Schneider, and J. Wijsen, editors, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), volume 91 of LIPIcs, pages 9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.TIME.2017.9.
  4. Alessandro Cimatti, Luke Hunsberger, Andrea Micheli, Roberto Posenato, and Marco Roveri. Sound and complete algorithms for checking the dynamic controllability of temporal networks with uncertainty, disjunction and observation. In 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), pages 27-36, 2014. URL: http://dx.doi.org/10.1109/TIME.2014.21.
  5. Alessandro Cimatti, Luke Hunsberger, Andrea Micheli, Roberto Posenato, and Marco Roveri. Dynamic controllability via timed game automata. Acta Informatica, 53(6-8):681-722, 2016. URL: http://dx.doi.org/10.1007/s00236-016-0257-2.
  6. Alessandro Cimatti, Luke Hunsberger, Andrea Micheli, and Marco Roveri. Using timed game automata to synthesize execution strategies for simple temporal networks with uncertainty. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada., pages 2242-2249, 2014. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8512.
  7. Carlo Combi, Luke Hunsberger, and Roberto Posenato. An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty. In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, pages 144-156. INSTICC, ScitePress, 2013. URL: http://dx.doi.org/10.5220/0004256101440156.
  8. Carlo Combi, Roberto Posenato, Luca Viganò, and Matteo Zavatteri. Access controlled temporal networks. In Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, pages 118-131. INSTICC, ScitePress, 2017. URL: http://dx.doi.org/10.5220/0006185701180131.
  9. Patrick R. Conrad and Brian C. Williams. Drake: An efficient executive for temporal plans with choice. J. Artif. Int. Res., 42(1):607-659, September 2011. Google Scholar
  10. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: http://dx.doi.org/10.1016/0004-3702(91)90006-6.
  11. Johann Eder, Euthimios Panagos, Heinz Pozewaunig, and Michael Rabinovich. Time Management in Workflow Systems, pages 265-280. Springer London, 1999. URL: http://dx.doi.org/10.1007/978-1-4471-0875-7_22.
  12. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  13. Luke Hunsberger, Roberto Posenato, and Carlo Combi. The Dynamic Controllability of Conditional STNs with Uncertainty. In Workshop on Planning and Plan Execution for Real-World Systems (PlanEx) at ICAPS-2012, pages 1-8, Atibaia, June 2012. URL: http://arxiv.org/abs/1212.2005.
  14. Luke Hunsberger, Roberto Posenato, and Carlo Combi. A sound-and-complete propagation-based algorithm for checking the dynamic consistency of conditional simple temporal networks. In 22st International Symposium on Temporal Representation and Reasoning (TIME 2015), pages 4-18, 2015. URL: http://dx.doi.org/10.1109/TIME.2015.26.
  15. Oded Maler, Amir Pnueli, and Joseph Sifakis. On the synthesis of discrete controllers for timed systems. In Ernst W. Mayr and Claude Puech, editors, STACS'95: 12th Annual Symposium on Theoretical Aspects of Computer Science Munich, Germany, March 2-4, 1995 Proceedings, pages 229-242, Berlin, Heidelberg, 1995. Springer. URL: http://dx.doi.org/10.1007/3-540-59042-0_76.
  16. Paul Morris. The mathematics of dispatchability revisited. In Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, ICAPS'16, pages 244-252. AAAI Press, 2016. Google Scholar
  17. Paul Morris and Nicola Muscettola. Temporal Dynamic Controllability Revisited. In Proceedings of the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, pages 1193-1198. AAAI Pr., 2005. Google Scholar
  18. Paul H. Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pages 494-502, 2001. Google Scholar
  19. Andrea Orlandini, Alberto Finzi, Amedeo Cesta, and Simone Fratini. TGA-Based Controllers for Flexible Plan Execution. In Joscha Bach and Stefan Edelkamp, editors, KI 2011: Advances in Artificial Intelligence: 34th Annual German Conference on AI, Berlin, Germany, October 4-7,2011. Proceedings, pages 233-245. Springer Berlin Heidelberg, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24455-1_22.
  20. Ioannis Tsamardinos, Thierry Vidal, and Martha E. Pollack. CTP: A new constraint-based formalism for conditional, temporal planning. Constraints, 8(4):365-388, 2003. URL: http://dx.doi.org/10.1023/A:1025894003623.
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 About DROPS Imprint Privacy Contact