×

zbMATH — the first resource for mathematics

Handling contingency in temporal constraint networks: From consistency to controllabilities. (English) Zbl 1054.68664
Summary: Temporal Constraint Networks (TCN) allow one to express minimal and maximal durations between time-points. Although being used in many research areas, this model disregards the contingent nature of some constraints, whose effective duration cannot be decided by the system but is provided by the external world. We propose an extension of TCN based on the definition of the simple temporal problem under uncertainty in which the classical network consistency property must be redefined in terms of controllability: intuitively, we would like to say that a network is controllable iff it is consistent in any situation (i.e., any assignment of the whole set of contingent intervals) that may arise in the external world. Three levels of controllability must be distinguished, namely the strong, the weak and the dynamic ones. This paper provides a full characterization of those properties and their usefulness in practice, and proposes algorithms for checking them. Complexity issues and tractable equivalence classes are only partially tackled, since it is still the topic of on-going work. All the same, hardness is discussed and argued, giving evidence for the general intractability of dynamic controllability, which is the most commonly required property in domains such as planning or scheduling.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1145/182.358434 · Zbl 0519.68079 · doi:10.1145/182.358434
[2] DOI: 10.1016/0304-3975(94)90010-8 · Zbl 0803.68071 · doi:10.1016/0304-3975(94)90010-8
[3] Bessière, C., Isli, A. and Ligozat, G. Global consistency in interval algebra networks: tractable subclasses. Proceedings of the 12th European Conference on Artificial Intelligence (ECAI -96). Budapest, Hungary. pp.3–7.
[4] Brusoni V., Methodologies for Intelligent Systems 8, Lecture Notes in Computer Science 869 pp 255– (1994) · doi:10.1007/3-540-58495-1_26
[5] Cervoni, R., Cesta, A. and Oddi, A. Managing dynamical temporal constraint networks. Proceedings of the 2nd International Conference on AI Planning Systems (AIPS-94). Chicago, Illinois, USA. pp.13–17.
[6] DOI: 10.1016/0004-3702(87)90061-0 · doi:10.1016/0004-3702(87)90061-0
[7] DOI: 10.1016/0004-3702(91)90006-6 · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6
[8] Dorn, J. Hybrid temporal reasoning. Proceedings of the 11th European Conference on Artificial Intelligence (ECAI-94). Amsterdam, Netherlands. pp.625–629.
[9] Dousson, C., Gaborit, P. and Ghallab, M. Situation recognition: representation and algorithms. Proceedings of the 13th International Joint Conference on AI (IJCAI -93). Chambéry, France.
[10] Drabble, B. and Kirby, R. Associating AI planner entities with an underlying time point network. Proceedings of the 1st European WorkShop on Planning (EWSP-91). Sankt Augustin, Germany. pp.27–38.
[11] Drakengren T., Journal of Artificial Intelligence Research (JAIR) 7 pp 25– (1997)
[12] Dubois, D., Fargier, H. and Prade, H. The use of fuzzy constraints in job-shop scheduling. IJCAI-93 Workshop on Knowledge-Based Planning, Scheduling and Control. Chambéry, France.
[13] Fargier, H., Jourdan, M., Layaïda, N. and Vidal, T. Using temporal constraint networks to manage temporal scenario of multimedia documents. ECAI-98 Workshop on Spatio-Temporal Reasoning. Brighton, UK.
[14] Fargier, H., Lang, J. and Schiex, T. Mixed constraint satisfaction: a framework for decision problems under incomplete knowledge. Proceedings of the 12th National Conference on AI (AAAI-96). Portland, Oregon, USA. pp.175–180.
[15] DOI: 10.1145/359642.359654 · Zbl 0386.68065 · doi:10.1145/359642.359654
[16] Frühwirth T., Chapter in Logic Programming in Action 636 (1992)
[17] Garey M., Computers and Intractability–A Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039
[18] Ghallab, M. and Mounir-Alaoui, A. Managing effciently temporal relations through indexed spanning trees. Proceedings of the 11th International Joint Conference on AI (IJCAI-89). Detroit, USA. pp.1297–1303. · Zbl 0718.68080
[19] Ghallab, M. and Vidal, T. Focusing on a sub-graph for managing efficiently numerical temporal constraints. Florida AI Research Symposium (FLAIRS-95). Melbourne Beach, FL, USA.
[20] Jonsson, P. and Bäckström, C. A linear programming approach to temporal reasoning. Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96). Portland, OR, USA. pp.1235–1240.
[21] Jourdan M., Proceedings SPIE 3020, in: Multimedia Computing and Networking 1997 pp 68– (1997) · doi:10.1117/12.264310
[22] Kumar V., AI Magazine 13 pp 32– (1992)
[23] DOI: 10.1016/0004-3702(92)90003-G · Zbl 0782.68104 · doi:10.1016/0004-3702(92)90003-G
[24] DOI: 10.1016/0004-3702(85)90041-4 · doi:10.1016/0004-3702(85)90041-4
[25] Meiri, I. Combining qualitative and quantitative constraints in temporal reasoning. Proceedings of the 9th National Conference on AI (AAAI-91). Anaheim, CA, USA. pp.260–267.
[26] DOI: 10.1145/200836.200848 · Zbl 0886.68077 · doi:10.1145/200836.200848
[27] Pearl J., Heuristics: Intelligent Search Strategies for Computer Problem Solving (1984)
[28] Rutten E., AI Communications 6 pp 18– (1993)
[29] Schrag, R., Boddy, M. and Carciofini, J. Managing disjunction for practical temporal reasoning. Proceedings of the 3rd Internat ional Conference on Principles of Knowledge Representation and Reasoning (KR-92). Edited by: Nebel, B., Rich, C. and Swartaut, W. pp.36–46. San Francisco, CA: Morgan Kaufmann.
[30] DOI: 10.1016/S0004-3702(97)00009-X · Zbl 1017.68536 · doi:10.1016/S0004-3702(97)00009-X
[31] Tsang E., Foundations of Constraint Satisfaction (1993)
[32] DOI: 10.1016/0933-3657(91)90004-U · doi:10.1016/0933-3657(91)90004-U
[33] van Hentenryck, P. Constraint solving for combinatorial problems: a tutorial. 1st International Conference on Principles and Practice of Constraint Programming (CP-95). Cassis, France. pp.564–587.
[34] Vidal, T. and Ghallab, M. Dealing with uncertain durations in temporal constraint networks dedicated to planning. Proceedings of the 12th European Conference on Artificial Intelligence (ECAI-96). Budapest, Hungary. pp.48–52.
[35] Vilain M., Readings in Qualitative Reasoning about Physical Systems (1989)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.