A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results

Authors Massimo Cairo, Luke Hunsberger, Roberto Posenato, Romeo Rizzi



PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.10.pdf
  • Filesize: 0.61 MB
  • 19 pages

Document Identifiers

Author Details

Massimo Cairo
Luke Hunsberger
Roberto Posenato
Romeo Rizzi

Cite AsGet BibTex

Massimo Cairo, Luke Hunsberger, Roberto Posenato, and Romeo Rizzi. A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.TIME.2017.10

Abstract

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network to include a new kind of time-points, called observation time-points. The execution of an observation time-point generates information in real time, specifically, the truth value of a propositional letter. In addition, time-points and temporal constraints may be labeled by conjunctions of (positive or negative) propositional letters. A CSTN is called dynamically consistent (DC) if there exists a dynamic strategy for executing its time-points such that no matter how the observations turn out during execution, the time-points whose labels are consistent with those observations have all been executed, and the constraints whose labels are consistent with those observations have all been satisfied. The strategy is dynamic in that its execution decisions may react to observations. The original formulation of CSTNs included propositional labels only on time-points, but the DC-checking algorithm was impractical because it was based on a conversion of the semantic constraints into an exponentially-sized Disjunctive Temporal Network. Later work added propositional labels to temporal constraints, and yielded a sound-and-complete propagation-based DC-checking algorithm, empirically demonstrated to be practical across a variety of CSTNs. This paper introduces a streamlined version of a CSTN in which propositional labels may appear on constraints, but not on time-points. This change simplifies the definition of the DC property, as well as the propagation rules for the DC-checking algorithm. It also simplifies the proofs of the soundness and completeness of those rules. This paper provides two translations from traditional CSTNs to streamlined CSTNs. Each translation preserves the DC property and, for any DC network, ensures that any dynamic execution strategy for that network can be extended to a strategy for its streamlined counterpart. Finally, this paper presents an empirical comparison of two versions of the DC-checking algorithm: the original version and a simplified version for streamlined CSTNs. The comparison is based on CSTN benchmarks from earlier work. For small-sized CSTNs, the original version shows the best performance, but the performance difference between the two versions decreases as the number of time-points in the CSTN increases. We conclude that the simplified algorithm is a practical alternative for checking the dynamic consistency of CSTNs.
Keywords
  • Conditional Simple Temporal Networks
  • Dynamic Consistency
  • Temporal Constraints

Metrics

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

References

  1. Massimo Cairo, Carlo Comin, and Romeo Rizzi. Instantaneous reaction-time in dynamic-consistency checking of conditional simple temporal networks. In 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016, pages 80-89, 2016. URL: http://dx.doi.org/10.1109/TIME.2016.16.
  2. Massimo Cairo and Romeo Rizzi. Dynamic controllability of conditional simple temporal networks is PSPACE-complete. In 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016, pages 90-99, 2016. URL: http://dx.doi.org/10.1109/TIME.2016.17.
  3. 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.
  4. 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.
  5. Carlo Combi, Mauro Gambini, Sara Migliorini, and Roberto Posenato. Representing business processes through a temporal data-centric workflow modeling language: An application to the management of clinical pathways. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 44(9):1182-1203, 2014. URL: http://dx.doi.org/10.1109/TSMC.2014.2300055.
  6. Carlo Comin. Complexity in Infinite Games on Graphs and Temporal Constraint Networks. PhD thesis, University of Trento and Universite Paris-Est, 2017. Google Scholar
  7. Carlo Comin and Romeo Rizzi. Dynamic consistency of conditional simple temporal networks via mean payoff games: A singly-exponential time dc-checking. In 22nd International Symposium on Temporal Representation and Reasoning (TIME 2015), pages 19-28, 2015. URL: http://dx.doi.org/10.1109/TIME.2015.18.
  8. Patrick R. Conrad and Brian C. Williams. Drake: An efficient executive for temporal plans with choice. Journal of Artificial Intelligence Research, 42(1):607-659, 2011. URL: http://dx.doi.org/10.1613/jair.3478.
  9. 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.
  10. Alfonso Gerevini, Anna Perini, and Francesco Ricci. Incremental algorithms for managing temporal constraints. Technical Report IRST-9605-07, IRST, 1996. Google Scholar
  11. Luke Hunsberger. Efficient execution of dynamically controllable Simple Temporal Networks with Uncertainty. Acta Informatica, 53(2):89-147, 2015. URL: http://dx.doi.org/10.1007/s00236-015-0227-0.
  12. Luke Hunsberger and Roberto Posenato. Checking the dynamic consistency of conditional simple temporal networks with bounded reaction times. In 26th International Conference on Automated Planning and Scheduling (ICAPS 2016), pages 175-183, 2016. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13108.
  13. Luke Hunsberger and Roberto Posenato. A new approach to checking the dynamic consistency of conditional simple temporal networks. In Principles and Practice of Constraint Programming (CP 2016), volume 9892 of LNCS, pages 268-286, 2016. URL: http://dx.doi.org/10.1007/978-3-319-44953-1_18.
  14. 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, June 2012. URL: http://arxiv.org/abs/1212.2005.
  15. 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 22nd International Symposium on Temporal Representation and Reasoning (TIME 2015), pages 4-18, 2015. URL: http://dx.doi.org/10.1109/TIME.2015.26.
  16. Andreas Lanz and Manfred Reichert. Enabling time-aware process support with the ATAPIS toolset. In Proceedings of the BPM Demo Sessions 2014, volume 1295 of CEUR Workshop Proceedings, pages 41-45, 2014. Google Scholar
  17. Roberto Posenato. A CSTN(U) consistency check algorithm implementation in Java, June 2017. URL: http://profs.scienze.univr.it/~posenato/software/cstnu.
  18. 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