×

Reasoning about qualitative temporal information. (English) Zbl 0782.68106

Summary: Representing and reasoning about incomplete and indefinite qualitative temporal information is an essential part of many artificial intelligence tasks. An interval-based framework and a point-based framework have been proposed for representing such temporal information. We address two fundamental reasoning tasks that arise in applications of these frameworks: Given possibly indefinite and incomplete knowledge of the relationships between some intervals or points, (i) find a scenario that is consistent with the information provided, and (ii) find the feasible relations between all pairs of intervals or points.
For the point-based framework and a restricted version of the interval- based framework, we give computationally efficient procedures for finding a consistent scenario and for finding the feasible relations. Our algorithms are marked improvements over the previously known algorithms. In particular, we develop an \(O(n^ 2)\)-time algorithm for finding one consistent scenario that is an \(O(n)\) improvement over the previously known algorithm, where \(n\) is the number of intervals or points, and we develop an algorithm for finding all the feasible relations that is of far more practical use than the previously known algorithm. For the unrestricted version of the interval-based framework, finding a consistent scenario and finding the feasible relations have been shown to be NP-complete. We show how the results for the point algebra aid in the design of a backtracking algorithm for finding one consistent scenario that is shown to be useful in practice for planning problems.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0326.68005
[2] Allen, J. F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 832-843 (1983) · Zbl 0519.68079
[3] Allen, J. F., Towards a general theory of action and time, Artif. Intell., 23, 123-154 (1984) · Zbl 0567.68025
[4] Allen, J. F.; Koomen, J. A., Planning using a temporal world model, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, Germany (1983)), 741-747
[5] Almeida, M. J., Reasoning about the temporal structure of narrative, (Ph.D. Thesis. Ph.D. Thesis, Tech. Rept. 87-10 (1987), Department of Computer Science, State University of New York at Buffalo)
[6] Bruce, B. C., A model for temporal references and its application in a question answering program, Artif. Intell., 3, 1-25 (1972)
[7] Chvátal, V., (Linear Programming (1983), Freeman: Freeman San Francisco, CA) · Zbl 0537.90067
[8] Dean, T. L.; McDermott, D. V., Temporal data base management, Artif. Intell., 32, 1-55 (1987)
[9] Dechter, R., Enhancement schemes for constraint processing: backjumping, learning and cutset decomposition, Artif. Intell., 41, 273-312 (1990)
[10] Dechter, R., Constraint networks, (Encyclopedia of Artificial Intelligence (1992), Wiley: Wiley Chicester, UK), 276-285
[11] Dechter, R.; Meiri, I., Experimental evaluation of preprocessing techniques in constraint satisfaction problems, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 271-277 · Zbl 0707.68081
[12] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artif. Intell., 49, 61-95 (1991) · Zbl 0737.68070
[13] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[14] Freuder, E. C., Synthesizing constraint expressions, Commun. ACM, 21, 958-966 (1978) · Zbl 0386.68065
[15] Gaschnig, J., Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems, (Proceedings Second Biennial Conference of the Canadian Society for Computational Studies of Intelligence. Proceedings Second Biennial Conference of the Canadian Society for Computational Studies of Intelligence, Toronto, Ont. (1978)), 268-277
[16] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York) · Zbl 0541.05054
[17] Güther, S., Zur Repräsentation temporaler Beziehungen in SRL, (KIT Report 69 (1984), Fachbereich Informatik, Technische Universität: Fachbereich Informatik, Technische Universität Berlin, Germany)
[18] Hamlet, I.; Hunter, J., A representation of time for medical expert systems, (Lecture Notes in Medical Informatics, 33 (1987), Springer: Springer Berlin), 112-119
[19] Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artif. Intell., 14, 263-313 (1980)
[20] Kautz, H. A., A formal theory of plan recognition, (Ph.D. Thesis. Ph.D. Thesis, Tech. Rept. 215 (1987), Department of Computer Science, University of Rochester: Department of Computer Science, University of Rochester Rochester, NY)
[21] Knuth, D. E., (The Art of Computer Programming, Vol. 1: Fundamental Algorithms (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010
[22] Ladkin, P. B.; Maddux, R., The algebra of constraint satisfaction problems and temporal reasoning, (Tech. Rept. (1988), Kestrel Institute: Kestrel Institute Palo Alto, CA)
[23] Ladkin, P. B.; Maddux, R., On binary constraint networks, (Tech. Rept. (1988), Kestrel Institute: Kestrel Institute Palo Alto, CA) · Zbl 0813.03045
[24] Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 99-118 (1977) · Zbl 0341.68061
[25] Mackworth, A. K.; Freuder, E. C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artif. Intell., 25, 65-74 (1985)
[26] Malik, J.; Binford, T. O., Reasoning in time and space, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, Germany (1983)), 343-345
[27] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[28] Nadel, B. A., Constraint satisfaction algorithms, Comput. Intell., 5, 188-224 (1989)
[29] Nökel, K., Temporal matching: recognizing dynamic situations from discrete measurements, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 1255-1260 · Zbl 0718.68092
[30] Nudel, B., Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artif. Intell., 21, 135-178 (1983)
[31] Papadimitriou, C. H.; Steiglitz, K., (Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0503.90060
[32] Purdom, P. W., Search rearrangement backtracking and polynomial average time, Artif. Intell., 21, 117-133 (1983)
[33] Reinefeld, A.; Ladkin, P. B., Fast solution of large interval constraint networks, (Proceedings Ninth Biennial Conference of the Canadian Society for Computational Studies of Intelligence. Proceedings Ninth Biennial Conference of the Canadian Society for Computational Studies of Intelligence, Vancouver, BC (1992)) · Zbl 0880.68012
[34] Seidel, R., A new method for solving constraint satisfaction problems, (Proceedings IJCAI-81. Proceedings IJCAI-81, Vancouver, BC (1981)), 338-342
[35] Song, F.; Cohen, R., The interpretation of temporal relations in narrative, (Proceedings AAAI-88. Proceedings AAAI-88, St. Paul, MN (1988)), 745-750
[36] Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 745-750 (1972)
[37] Valdés-Pérez, R. E., The satisfiability of temporal constraint networks, (Proceedings AAAI-87. Proceedings AAAI-87, Seattle, WA (1987)), 745-750
[38] van Beek, P., Approximation algorithms for temporal reasoning, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 745-750
[39] van Beek, P., Temporal query processing with indefinite information, Artif. Intell. Med., 3, 745-750 (1991), (Special Issue on Temporal Reasoning)
[40] van Beek, P.; Cohen, R., Exact and approximate reasoning about temporal relations, Comput. Intell., 6, 132-144 (1990)
[41] Vilain, M.; Kautz, H. A., Constraint propagation algorithms for temporal reasoning, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 132-144
[42] Vilain, M.; Kautz, H. A.; van Beek, P., Constraint propagation algorithms for temporal reasoning: a revised report, (Weld, D. S.; de Kleer, J., Readings in Qualitative Reasoning about Physical Systems (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 373-381
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.