Incorporating Decision Nodes into Conditional Simple Temporal Networks

Authors Massimo Cairo, Carlo Combi, Carlo Comin, Luke Hunsberger, Roberto Posenato, Romeo Rizzi, Matteo Zavatteri



PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.9.pdf
  • Filesize: 0.68 MB
  • 18 pages

Document Identifiers

Author Details

Massimo Cairo
Carlo Combi
Carlo Comin
Luke Hunsberger
Roberto Posenato
Romeo Rizzi
Matteo Zavatteri

Cite AsGet BibTex

Massimo Cairo, Carlo Combi, Carlo Comin, Luke Hunsberger, Roberto Posenato, Romeo Rizzi, and Matteo Zavatteri. Incorporating Decision Nodes into Conditional Simple Temporal Networks. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.TIME.2017.9

Abstract

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters. Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network. This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs: (1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.
Keywords
  • Conditional Simple Temporal Networks with Decisions
  • Dynamic Consistency
  • SAT Solver
  • Hyper Temporal Networks
  • PSPACE

Metrics

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

References

  1. Claudio Bettini, Xiaoyang Sean Wang, and Sushil Jajodia. Temporal reasoning in workflow systems. Distributed and Parallel Databases, 11(3):269-306, 2002. URL: http://dx.doi.org/10.1023/A:1014048800604.
  2. 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.
  3. Massimo Cairo, Luke Hunsberger, Roberto Posenato, and Romeo Rizzi. A streamlined model of conditional simple temporal networks. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), volume 90 of LIPIcs, pages 10:1-10:19, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.TIME.2017.10.
  4. 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.
  5. Susan J. Chinn and Gregory R. Madey. Temporal representation and reasoning for workflow in engineering design change review. IEEE Transactions on Engineering Management, 47(4):485-492, 2000. URL: http://dx.doi.org/10.1109/17.895343.
  6. 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.
  7. 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.
  8. 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.
  9. 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 (ICAART 2013), volume 2, pages 144-156, 2013. URL: http://dx.doi.org/10.5220/0004256101440156.
  10. Carlo Combi and Roberto Posenato. Controllability in temporal conceptual workflow schemata. In Business Process Management (BPM 2009), volume 5701 of LNCS, pages 64-79, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03848-8_6.
  11. Carlo Combi and Roberto Posenato. Towards temporal controllabilities for workflow schemata. In 17th International Symposium on Temporal Representation and Reasoning (TIME 2010), pages 129-136, 2010. URL: http://dx.doi.org/10.1109/TIME.2010.17.
  12. Carlo Comin, Roberto Posenato, and Romeo Rizzi. Hyper temporal networks - A tractable generalization of simple temporal networks and its relation to mean payoff games. Constraints, 22(2):152-190, 2017. URL: http://dx.doi.org/10.1007/s10601-016-9243-0.
  13. 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.
  14. 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.
  15. Jing Cui and Patrik Haslum. Dynamic controllability of controllable conditional temporal problems with uncertainty. In 27th International Conference on Automated Planning and Scheduling (ICAPS 2017), 2017. URL: https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15738.
  16. 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.
  17. Johann Eder, Wolfgang Gruber, and Euthimios Panagos. Temporal modeling of workflows with conditional execution paths. In Database and Expert Systems Applications (DEXA 2000), volume 1873 of LNCS, pages 243-253, 2000. URL: http://dx.doi.org/10.1007/3-540-44469-6_23.
  18. Niklas Eén and Niklas Sörensson. An extensible SAT-solver. In Theory and Applications of Satisfiability Testing: 6th International Conference (SAT 2003), pages 502-518, 2004. URL: http://dx.doi.org/10.1007/978-3-540-24605-3_37.
  19. 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.
  20. 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.
  21. 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, 2012. URL: http://arxiv.org/abs/1212.2005.
  22. 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.
  23. Eleanna Kafeza and Kamalakar Karlapalem. Gaining control over time in workflow management applications. In Database and Expert Systems Applications: 11th International Conference (DEXA 2000), volume 1873 of LNCS, pages 232-241, 2000. URL: http://dx.doi.org/10.1007/3-540-44469-6_22.
  24. 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 2001), pages 494-502, 2001. Google Scholar
  25. 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.
  26. Matteo Zavatteri. Conditional simple temporal networks with uncertainty and decisions. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), volume 90 of LIPIcs, pages 23:1-23:17, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.TIME.2017.23.
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