×

Dynamic controllability of simple temporal networks with uncertainty: simple rules and fast real-time execution. (English) Zbl 1434.68544

Summary: Simple Temporal Networks (STNs) are a well-studied model for representing temporal constraints. They comprise a set of time-points (real-valued variables representing execution times) and binary difference constraints among them. Simple Temporal Networks with Uncertainty (STNUs) extend STNs in that some time-points (called contingent) are treated as exogenous variables, whose execution times, bound to fall within a given interval from the corresponding activation time-points (as specified by a “contingent link”), get revealed only during real-time execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the execution times of contingent time-points revealed during execution.
In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying any of our rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the previous efficient algorithms for DC-checking.
Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of the notion of DC among several variants of the semantics of STNUs, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in \(O(K N)\) total time in a network with \(K \geq 1\) contingent links and \(N \geq K\) time points, considerably improving the previous \(O(N^3)\)-time bound.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M14 Distributed systems
68Q60 Specification and verification (program logics, model checking, etc.)
93B05 Controllability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Morris, P. H.; Muscettola, N.; Vidal, T., Dynamic control of plans with temporal uncertainty, (Nebel, B., Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001 (2001), Morgan Kaufmann), 494-502
[2] Shah, J. A.; Stedl, J.; Williams, B. C.; Robertson, P., A fast incremental algorithm for maintaining dispatchability of partially controllable plans, (Boddy, M. S.; Fox, M.; Thiébaux, S., Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling. Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, September 22-26, 2007 (2007), AAAI), 296-303
[3] Nilsson, M.; Kvarnström, J.; Doherty, P., Incremental dynamic controllability revisited, (Borrajo, D.; Kambhampati, S.; Oddi, A.; Fratini, S., Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, ICAPS 2013, Rome, Italy, June 10-14, 2013 (2013), AAAI)
[4] Morris, P. H.; Muscettola, N., Temporal dynamic controllability revisited, (Veloso, M. M.; Kambhampati, S., Proceedings, the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference. Proceedings, the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, Pittsburgh, Pennsylvania, USA, July 9-13, 2005 (2005), AAAI Press/The MIT Press), 1193-1198
[5] Morris, P., A structural characterization of temporal dynamic controllability, (Benhamou, F., Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, Proceedings. Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, Proceedings, CP 2006, Nantes, France, September 25-29, 2006. Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, Proceedings. Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, Proceedings, CP 2006, Nantes, France, September 25-29, 2006, Lecture Notes in Computer Science, vol. 4204 (2006), Springer), 375-389
[6] Nilsson, M.; Kvarnström, J.; Doherty, P., EfficientIDC: a faster incremental dynamic controllability algorithm, (Chien, S. A.; Do, M. B.; Fern, A.; Ruml, W., Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling. Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, ICAPS 2014, Portsmouth, New Hampshire, USA, June 21-26, 2014 (2014), AAAI)
[7] Morris, P., Dynamic controllability and dispatchability relationships, (Simonis, H., Integration of AI and OR Techniques in Constraint Programming - 11th International Conference, Proceedings. Integration of AI and OR Techniques in Constraint Programming - 11th International Conference, Proceedings, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Integration of AI and OR Techniques in Constraint Programming - 11th International Conference, Proceedings. Integration of AI and OR Techniques in Constraint Programming - 11th International Conference, Proceedings, CPAIOR 2014, Cork, Ireland, May 19-23, 2014, Lecture Notes in Computer Science, vol. 8451 (2014), Springer), 464-479 · Zbl 1407.68460
[8] Nilsson, M.; Kvarnström, J.; Doherty, P., Incremental dynamic controllability in cubic worst-case time, (Cesta, A.; Combi, C.; Laroussinie, F., 21st International Symposium on Temporal Representation and Reasoning. 21st International Symposium on Temporal Representation and Reasoning, TIME 2014, Verona, Italy, September 8-10, 2014 (2014), IEEE Computer Society), 17-26
[9] Hunsberger, L., Efficient execution of dynamically controllable simple temporal networks with uncertainty, Acta Inform., 53, 2, 89-147 (2016) · Zbl 1336.68250
[10] Rossi, F.; Venable, K. B.; Yorke-Smith, N., Uncertainty in soft temporal constraint problems: a general framework and controllability algorithms for the fuzzy case, J. Artificial Intelligence Res., 27, 617-674 (2006) · Zbl 1182.68266
[11] Khatib, L.; Morris, P. H.; Morris, R. A.; Rossi, F., Temporal constraint reasoning with preferences, (Nebel, B., Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, August 4-10, 2001 (2001), Morgan Kaufmann), 322-327
[12] Conrad, P. R.; Williams, B. C., Drake: an efficient executive for temporal plans with choice, CoRR · Zbl 1234.68361
[13] Effinger, R. T.; Williams, B. C.; Kelly, G.; Sheehy, M., Dynamic controllability of temporally-flexible reactive programs, (Gerevini, A.; Howe, A. E.; Cesta, A.; Refanidis, I., Proceedings of the 19th International Conference on Automated Planning and Scheduling. Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS 2009, Thessaloniki, Greece, September 19-23, 2009 (2009), AAAI)
[14] Combi, C.; Hunsberger, L.; Posenato, R., An algorithm for checking the dynamic controllability of a conditional simple temporal network with uncertainty, (Filipe, J.; Fred, A. L.N., ICAART 2013 - Proceedings of the 5th International Conference on Agents and Artificial Intelligence, vol. 2. ICAART 2013 - Proceedings of the 5th International Conference on Agents and Artificial Intelligence, vol. 2, Barcelona, Spain, 15-18 February, 2013 (2013), SciTePress), 144-156
[15] Cairo, M.; Rizzi, R., Dynamic controllability made simple, (Schewe, S.; Schneider, T.; Wijsen, J., 24th International Symposium on Temporal Representation and Reasoning. 24th International Symposium on Temporal Representation and Reasoning, TIME 2017, October 16-18, 2017, Mons, Belgium. 24th International Symposium on Temporal Representation and Reasoning. 24th International Symposium on Temporal Representation and Reasoning, TIME 2017, October 16-18, 2017, Mons, Belgium, LIPIcs, vol. 90 (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 8:1-8:16 · Zbl 1515.68289
[16] Hunsberger, L., Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies, (Lutz, C.; Raskin, J., TIME 2009, 16th International Symposium on Temporal Representation and Reasoning, Proceedings. TIME 2009, 16th International Symposium on Temporal Representation and Reasoning, Proceedings, Bressanone-Brixen, Italy, 23-25 July 2009 (2009), IEEE Computer Society), 155-162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.