Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty

Authors Massimo Cairo, Luke Hunsberger, Romeo Rizzi



PDF
Thumbnail PDF

File

LIPIcs.TIME.2018.8.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Massimo Cairo
  • Department of Mathematics, University of Trento, Italy
Luke Hunsberger
  • Computer Science Department, Vassar College, Poughkeepsie, NY USA
Romeo Rizzi
  • Department of Computer Science, University of Verona, Italy

Cite AsGet BibTex

Massimo Cairo, Luke Hunsberger, and Romeo Rizzi. Faster Dynamic Controllability Checking for Simple Temporal Networks with Uncertainty. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TIME.2018.8

Abstract

Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, together with a set of binary constraints, each of the form Y <= X+w. The problem of finding a feasible schedule (i.e., an assignment of real numbers to time-points such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph. Simple Temporal Networks with Uncertainty (STNUs) augment STNs to include contingent links that can be used, for example, to represent actions with uncertain durations. The duration of a contingent link is not controlled by the planner, but is instead controlled by a (possibly adversarial) environment. Each contingent link has the form, <A,l,u,C>, where 0 < l <= u < infty. Once the planner executes the activation time-point A, the environment must execute the contingent time-point C at some time A+Delta, where Delta in [l,u]. Crucially, the planner does not know the value of Delta in advance, but only discovers it when C executes. An STNU is dynamically controllable (DC) if there is a strategy that the planner can use to execute all of the non-contingent time-points, such that all of the constraints are guaranteed to be satisfied no matter which durations the environment chooses for the contingent links. The strategy can be dynamic in that it can react in real time to the contingent durations it observes. Recently, an upper bound of O(N^3) was given for the DC-checking problem for STNUs, where N is the number of time-points. This paper introduces a new algorithm, called the RUL^- algorithm, for solving the DC-checking problem for STNUs that improves on the O(N^3) bound. The worst-case complexity of the RUL^- algorithm is O(MN+K^2N+KN log N), where N is the number of time-points, M is the number of constraints, and K is the number of contingent time-points. If M is O(N^2), then the complexity reduces to O(N^3); however, in sparse graphs the complexity can be much less. For example, if M is O(N log N), and K is O(sqrt{N}), then the complexity of the RUL^- algorithm reduces to O(N^2 log N). The RUL^- algorithm begins by using the Bellman-Ford algorithm to compute a potential function. It then performs at most 2K rounds of computations, interleaving novel applications of Dijkstra's algorithm to (1) generate new edges and (2) update the potential function in response to those new edges. The constraint-propagation/edge-generation rules used by the RUL^- algorithm are distinguished from related work in two ways. First, they only generate unlabeled edges. Second, their applicability conditions are more restrictive. As a result, the RUL^- algorithm requires only O(K) rounds of Dijkstra's algorithm, instead of the O(N) rounds required by other approaches. The paper proves that the RUL^- algorithm is sound and complete for the DC-checking problem for STNUs.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
Keywords
  • Simple Temporal Networks with Uncertainty
  • Dynamic Controllability
  • Temporal Planning under Uncertainty

Metrics

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

References

  1. Massimo Cairo and Romeo Rizzi. Dynamic Controllability Made Simple. In Sven Schewe, Thomas Schneider, and Jef Wijsen, editors, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), volume 90 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.TIME.2017.8.
  2. Carlo Combi, Luke Hunsberger, and Roberto Posenato. An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty. In ICAART 2013, volume 2, pages 144-156, 2013. URL: http://dx.doi.org/10.5220/0004256101440156.
  3. Patrick R. Conrad and Brian C. Williams. Drake: An efficient executive for temporal plans with choice. Journal of Artificial Intelligence Research (JAIR), 42:607-659, 2011. URL: http://dx.doi.org/10.1613/jair.3478.
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2001. Google Scholar
  5. 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.
  6. Robert Effinger, Brian Williams, Gerard Kelly, and Michael Sheehy. Dynamic controllability of temporally-flexible reactive programs. In 19th International Conference on Automated Planning and Scheduling (ICAPS-2009), 2009. Google Scholar
  7. Luke Hunsberger. Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In TIME 2009, pages 155-162, 2009. URL: http://dx.doi.org/10.1109/TIME.2009.25.
  8. 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.
  9. Luke Hunsberger. New techniques for checking dynamic controllability of simple temporal networks with uncertainty. In Lecture Notes in Computer Science, volume 8946, pages 170-193. Springer, 2015. Google Scholar
  10. Lina Khatib, Paul H. Morris, Robert A. Morris, and Francesca Rossi. Temporal constraint reasoning with preferences. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), pages 322-327, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers, Inc. Google Scholar
  11. Paul Morris. A structural characterization of temporal dynamic controllability. In CP 2006, volume 4204, pages 375-389, 2006. URL: http://dx.doi.org/10.1007/11889205_28.
  12. Paul Morris. Dynamic controllability and dispatchability relationships. In Integration of AI and OR Techniques in Constraint Programming, volume 8451 of Lecture Notes in Computer Science, pages 464-479. Springer, 2014. Google Scholar
  13. Paul H. Morris and Nicola Muscettola. Temporal dynamic controllability revisited. In AAAI-05/IAAI-05, pages 1193-1198, 2005. Google Scholar
  14. Paul H. Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In IJCAI 2001, pages 494-502, 2001. Google Scholar
  15. Francesca Rossi, Kristen Brent Venable, and Neil Yorke-Smith. Uncertainty in soft temporal constraint problems: A general framework and controllability algorithms for the fuzzy case. Journal of Artificial Intelligence Research, 27:617-674, 2006. 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