Reasoning about qualitative temporal information.

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

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

\textit{P. van Beek}, Artif. Intell. 58, No. 1--3, 297--326 (1992; Zbl 0782.68106)

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, 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, (), 741-747 |

[5] | Almeida, M.J., Reasoning about the temporal structure of narrative, () |

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

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

[11] | Dechter, R.; Meiri, I., Experimental evaluation of preprocessing techniques in constraint satisfaction problems, (), 271-277 |

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

[16] | Golumbic, M.C., () |

[17] | Güther, S., Zur repräsentation temporaler beziehungen in SRL, () |

[18] | Hamlet, I.; Hunter, J., A representation of time for medical expert systems, (), 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, () |

[21] | Knuth, D.E., () |

[22] | Ladkin, P.B.; Maddux, R., The algebra of constraint satisfaction problems and temporal reasoning, () |

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

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

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

[34] | Seidel, R., A new method for solving constraint satisfaction problems, (), 338-342 |

[35] | Song, F.; Cohen, R., The interpretation of temporal relations in narrative, (), 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, (), 745-750 |

[38] | van Beek, P., Approximation algorithms for temporal reasoning, (), 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, (), 132-144 |

[42] | Vilain, M.; Kautz, H.A.; van Beek, P., Constraint propagation algorithms for temporal reasoning: a revised report, (), 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.