Temporal constraint networks. (English) Zbl 0737.68070

Dechter, Rina; Meiri, Itay; Pearl, Judea

Artif. Intell. 49, No. 1-3, 61-95 (1991).

Summary: This paper extends network-based methods of constraint satisfaction to include continuous variables, thus providing a framework for processing temporal constraints. In this framework, called temporal constraint satisfaction problem (TCSP), variables represent time points and temporal information is represented by a set of unary and binary constraints, each specifying a set of permitted intervals. The unique feature of this framework lies in permitting the processing of metric information, namely, assessments of time differences between events. We present algorithms for performing the following reasoning tasks: finding all feasible times that a given event can occur, finding all possible relationships between two given events, and generating one or more scenarios consistent with the information provided.
We distinguish between simple temporal problems (STPs) and general temporal problems, the former admitting at most one interval constraint on any pair of time points. We show that the STP, which subsumes the major part of Vilain and Kautz’s point algebra, can be solved in polynomial time. For general TCSPs, we present a decomposition scheme that performs the three reasoning tasks considered, and introduce a variety of techniques for improving its efficiency. We also study the applicability of path consistency algorithms as preprocessing of temporal problems, demonstrate their termination and bound their complexities.

MSC:

68T15	Theorem proving (deduction, resolution, etc.) (MSC2010)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

decomposition; path consistency algorithm; Floyd-Warshall all pairs- shortest paths algorithm; temporal reasoning; temporal constraint satisfaction problem

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, 11, 832-843 (1983) · Zbl 0519.68079
[3]	Allen, J. F., Towards a general theory of action and time, Artif. Intell., 23, 2, 123-154 (1984) · Zbl 0567.68025
[4]	Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, BIT, 25, 2-23 (1985) · Zbl 0573.68018
[5]	Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 2, 177-184 (1987)
[6]	Aspvall, B.; Shiloach, Y., A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality, SIAM J. Comput., 9, 4, 827-845 (1980) · Zbl 0447.68036
[7]	Backhouse, R. C.; Carré, B. A., Regular algebra applied to path-finding problems, J. Inst. Math. Appl., 15, 161-186 (1975) · Zbl 0304.68082
[8]	Bell, C. E.; Tate, A., Use of a longest path algorithm to manage temporal information and restrict search in an automated planner, (Working Paper Series No. 85-34 (1985), Artificial Intelligence Applications Institute, University of Edinburgh: Artificial Intelligence Applications Institute, University of Edinburgh Scotland)
[9]	Bertelé, U.; Brioschi, F., (Nonserial Dynamic Programming (1972), Academic Press: Academic Press New York)
[10]	Dantzig, G. B., (Linear Programming and Extensions (1962), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0108.33103
[11]	Davis, E., Constraint propagation with interval labels, Artif. Intell., 32, 3, 281-331 (1987) · Zbl 0642.68176
[13]	Dean, T. L.; McDermott, D. V., Temporal data base management, Artif. Intell., 32, 1-55 (1987)
[14]	Dechter, R., Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition, Artif. Intell., 41, 3, 273-312 (1990)
[15]	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
[16]	Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artif. Intell., 34, 1, 1-38 (1987) · Zbl 0643.68156
[17]	Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 3, 353-366 (1989) · Zbl 0665.68084
[18]	Even, S., (Graph Algorithms (1979), Computer Science Press: Computer Science Press Rockville, MD) · Zbl 0441.68072
[19]	Freuder, E. C., Synthesizing constraint expressions, Commun. ACM, 21, 11, 958-965 (1978) · Zbl 0386.68065
[20]	Freuder, E. C., A sufficient condition of backtrack-free search, J. ACM, 29, 1, 24-32 (1982) · Zbl 0477.68063
[21]	Gaschnig, J., Performance measurement and analysis of certain search algorithms, (Tech. Rept. CMU-CS-79-124 (1979), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh, PA)
[22]	Hanks, S.; McDermott, D. V., Default reasoning, nonmonotonic logics, and the frame problem, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 328-333
[23]	Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artif. Intell., 14, 263-313 (1980)
[24]	Kahn, K.; Gorry, G. A., Mechanizing temporal knowledge, Artif. Intell., 9, 87-108 (1977)
[25]	Khachiyan, L. G., A polynomial algorithm in linear programming, Soviet Math. Dokl., 20, 191-194 (1979) · Zbl 0414.90086
[26]	Ladkin, P. B., Metric constraint satisfaction with intervals, (Tech. Rept. TR-89-038 (1989), International Computer Science Institute: International Computer Science Institute Berkeley, CA)
[27]	Ladkin, P. B.; Maddux, R. D., On binary constraint networks, (Tech. Rept. (1989), Kestrel Institute: Kestrel Institute Palo Alto, CA) · Zbl 0813.03045
[28]	Lehmann, D. J., Algebraic structures for transitive closure, Theor. Comput. Sci., 4, 59-76 (1977) · Zbl 0358.68061
[29]	Leiserson, C. E.; Saxe, J. B., A mixed-integer linear programming problem which is efficiently solvable, (Proceedings 21st Annual Allerton Conference on Communications, Control, and Computing (1983)), 204-213
[30]	Liao, Y. Z.; Wong, C. K., An algorithm to compact a VLSI symbolic layout with mixed constraints, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 2, 2, 62-69 (1983)
[31]	Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 1, 99-118 (1977) · Zbl 0341.68061
[32]	Mackworth, A. K.; Freuder, E. C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artif. Intell., 25, 1, 65-74 (1985)
[33]	Malik, J.; Binford, T. O., Reasoning in time and space, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, FRG (1983)), 343-345
[34]	McDermott, D. V., A temporal logic for reasoning about processes and plans, Cogn. Sci., 6, 101-155 (1982)
[35]	Meiri, I., Faster constraint satisfaction algorithms for temporal reasoning, (Tech. Rept. R-151 (1990), UCLA Cognitive Systems Laboratory: UCLA Cognitive Systems Laboratory Los Angeles, CA)
[36]	Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[37]	Nudel, B., Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artif. Intell., 21, 135-178 (1983)
[38]	Papadimitriou, C. H.; Steiglitz, K., (Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0503.90060
[39]	Parker, D. S., Partial order programming, (Tech. Rept. CSD-870067 (1987), UCLA: UCLA Los Angeles, CA)
[40]	Purdom, P. W., Search rearrangement backtracking and polynomial average time, Artif. Intell., 21, 117-133 (1983)
[41]	Shoham, Y., (Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence (1988), MIT Press: MIT Press Cambridge, MA)
[42]	Shostak, R., Deciding linear inequalities by computing loop residues, J. ACM, 28, 4, 769-779 (1981) · Zbl 0468.68073
[43]	Tarjan, R. E., A unified approach to path problems, J. ACM, 28, 3, 577-593 (1981) · Zbl 0462.68041
[44]	Tarjan, R. E., Fast algorithms for solving path problems, J. ACM, 28, 3, 594-614 (1981) · Zbl 0462.68042
[45]	Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 3, 566-579 (1984) · Zbl 0545.68062
[46]	Valdés-Pérez, R. E., Spatio-temporal reasoning and linear inequalities, (Artificial Intelligence Laboratory, AIM-875 (1986), MIT: MIT Cambridge, MA)
[47]	Van Beek, P., Approximation algorithms for temporal reasoning, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 1291-1296 · Zbl 1050.81563
[48]	Van Beek, P., Reasoning about qualitative temporal information, (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 728-734
[49]	Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 377-382
[50]	Wald, J. A.; Colbourn, C. J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036