Temporal constraint networks.

*(English)*Zbl 0737.68070Summary: 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.

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
PDF
BibTeX
XML
Cite

\textit{R. Dechter} et al., Artif. Intell. 49, No. 1--3, 61--95 (1991; Zbl 0737.68070)

Full Text:
DOI

##### References:

[1] | Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., () |

[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, () |

[9] | Bertelé, U.; Brioschi, F., () |

[10] | Dantzig, G.B., () |

[11] | Davis, E., Constraint propagation with interval labels, Artif. intell., 32, 3, 281-331, (1987) · Zbl 0642.68176 |

[12] | E. Davis, Private communication (1989). |

[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, (), 271-277 |

[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., () |

[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, () |

[22] | Hanks, S.; McDermott, D.V., Default reasoning, nonmonotonic logics, and the frame problem, (), 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, () |

[27] | Ladkin, P.B.; Maddux, R.D., On binary constraint networks, () · 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, (), 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, (), 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, () |

[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., () |

[39] | Parker, D.S., Partial order programming, () |

[40] | Purdom, P.W., Search rearrangement backtracking and polynomial average time, Artif. intell., 21, 117-133, (1983) |

[41] | Shoham, Y., () |

[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, () |

[47] | Van Beek, P., Approximation algorithms for temporal reasoning, (), 1291-1296 · Zbl 1050.81563 |

[48] | Van Beek, P., Reasoning about qualitative temporal information, (), 728-734 |

[49] | Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (), 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 |

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.