Approximation algorithms for temporal reasoning

ABSTRACT

We consider a representation for temporal relations between intervals introduced by James Allen, and its associated computational or reasoning problem: given possibly indefinite knowledge of the relations between some intervals, how do we compute the strongest possible assertions about the relations between some or all intervals. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We give new approximation algorithms, examine their effectiveness, and determine under what conditions the algorithms are exact.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: James F. Allen, Towards a general theory of action and time, Artificial Intelligence, v.23 n.2, p.123-154, July 1984 [doi>10.1016/0004-3702(84)90008-0]
• 3: Allen, J. F., and J. A. Koomen. 1983. Planning Using a Temporal World Model. Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI), Karlsruhe, W. Germany, 741-747.
• 4: Dijkstra, E. W. 1959. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269-271.
• 5: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 6: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• 7: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• 8: Donald B. Johnson, A Note on Dijkstra's Shortest Path Algorithm, Journal of the ACM (JACM), v.20 n.3, p.385-388, July 1973 [doi>10.1145/321765.321768]
• 9: Koubarakis, M., J. Mylopoulos, M. Stanley, and A. Borgida. 1989. Telos: Features and Formalization. Forthcoming Technical Report, Computer Systems Research Institute, University of Toronto, Feb.
• 10: Ladkin, P. B. 1988. Satisfying First-Order Constraints About Time Intervals. Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI), Saint Paul, Minn., 512-517.
• 11: Ladkin, P. B. 1989. Unpublished manuscript. Kestrel Institute, Palo Alto, Calif.
• 12: Mackworth, A. K. 1977. Consistency in Networks of Relations. Artificial Intelligence 8, 99-118.
• 13: Montanari, U. 1974. Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Inform. Sci. 7, 95-132.
• 14: Song, F., and R. Cohen. 1988. The Interpretation of Temporal Relations in Narrative. Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI), Saint Paul, Minn., 745-750.
• 15: Tsang, E. P. K. 1987. The Consistent Labeling Problem in Temporal Reasoning. Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI), Seattle, Wash., 251-255.
• 16: Valdes-Perez, R. E. 1987. The Satisfiability of Temporal Constraint Networks. Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI), Seattle, Wash., 256-260.
• 17: van Beek, P. 1989. Approximation Algorithms for Temporal Reasoning. Department of Computer Science Technical Report CS-89-12, University of Waterloo.
• 18: Vilain, M., and H. Kautz. 1986. Constraint Propagation Algorithms for Temporal Reasoning. Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI), Philadelphia, Pa., 377-382.