×

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure. (English) Zbl 1216.68266

Summary: Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper.
In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to \(O(n^{2})\) from \(O(n^{3})\), where \(n\) is the number of variables involved in the CSP.
An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.

MSC:

68T27 Logic in artificial intelligence

Software:

SHOP2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J. F., Maintaining knowledge about temporal intervals, Communication of the ACM, 26, 1, 832-843 (1983) · Zbl 0519.68079
[2] Allen, J. F., Temporal reasoning and planning, (Allen, J. F.; Kautz, H. A.; Pelavin, R.; Tenenberg, J., Reasoning About Plans (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA) · Zbl 0765.68195
[3] C. Bessière, A simple way to improve path-consistency in Interval Algebra networks, in: Proceedings of the 13th National Conference of the American Association for Artificial Intelligence (AAAI-96), Portland, OR, 1996, pp. 375-380.; C. Bessière, A simple way to improve path-consistency in Interval Algebra networks, in: Proceedings of the 13th National Conference of the American Association for Artificial Intelligence (AAAI-96), Portland, OR, 1996, pp. 375-380.
[4] Dechter, R., Constraint Processing (2003), Morgan Kaufmann
[5] Delgrande, J.; Gupta, A.; Van Allen, T., A comparison of point-based approaches to qualitative temporal reasoning, Artificial Intelligence, 131, 135-170 (2001) · Zbl 0996.68196
[6] Delgrande, J. P.; Gupta, A., A representation for efficient temporal reasoning, (Proceedings of the Thirteenth National Conference of the American Association for Artificial Intelligence (AAAI-96) (1996), AAAI Press/The MIT Press), 381-388
[7] Dorn, J., Temporal reasoning in sequence graphs, (Proceedings of the Tenth National Conference of the American Association for Artificial Intelligence (AAAI-92) (1992), AAAI Press/The MIT Press), 735-740
[8] Drakengren, T.; Jonsson, P., Twenty-one large tractable subclasses of Allen’s algebra, Artificial Intelligence, 93, 1-2, 297-319 (1997) · Zbl 1017.03514
[9] Fisher, M.; Gabbay, D.; Vila, L., Handbook of Temporal Reasoning in Artificial Intelligence (2005), Elsevier Science · Zbl 1099.68106
[10] Gerevini, A., Incremental qualitative temporal reasoning: algorithms for the point algebra and the ORD-Horn class, Artificial Intelligence, 166, 1-2, 37-80 (2005) · Zbl 1132.68730
[11] Gerevini, A.; Saetti, A., Efficient computation of minimal point algebra constraints by metagraph closure, (Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP-07). Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP-07), Lecture Notes in Computer Science, vol. 4741 (2007), Springer-Verlag), 301-316 · Zbl 1145.68515
[12] Gerevini, A.; Renz, J., Combining topological and size information for spatial reasoning, Artificial Intelligence, 137, 1-42 (2002) · Zbl 0995.68073
[13] Gerevini, A.; Schubert, L., Efficient algorithms for qualitative reasoning about time, Artificial Intelligence, 74, 207-248 (1995) · Zbl 1013.68553
[14] Gerevini, A.; Schubert, L., On computing the minimal labels in time point algebra networks, Computational Intelligence, 11, 3, 443-448 (1995)
[15] Ghallab, M.; Mounir Alaoui, A., Managing efficiently temporal relations through indexed spanning trees, (Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89) (1989), Morgan Kaufmann), 1297-1303 · Zbl 0718.68080
[16] Golumbic, C. M.; Shamir, R., Complexity and algorithms for reasoning about time: a graph-theoretic approach, Journal of the Association for Computing Machinery (ACM), 40, 5, 1108-1133 (1993) · Zbl 0795.68095
[17] P.B. Ladkin, R. Maddux, On binary constraint networks, Technical Report KES.U.88.8, Kestrel Institute, Palo Alto, CA, 1988.; P.B. Ladkin, R. Maddux, On binary constraint networks, Technical Report KES.U.88.8, Kestrel Institute, Palo Alto, CA, 1988. · Zbl 0813.03045
[18] Ladkin, P. B.; Maddux, R., On binary constraint problems, Journal of the Association for Computing Machinery (ACM), 41, 3, 435-469 (1994) · Zbl 0813.03045
[19] Ligozat, G., Reasoning about cardinal directions, Journal of Visual Languages & Computing, 9, 1, 23-44 (1998)
[20] Long, D.; Fox, M., The 3rd international planning competition: Results and analysis, Journal of Artificial Intelligence Research (JAIR), 20, 1-59 (2003) · Zbl 1036.68097
[21] Mackworth, A. K., Consistency in network of relations, Artificial Intelligence, 8, 1, 99-118 (1977) · Zbl 0341.68061
[22] Mackworth, A. K.; Freuder, E. C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, 25, 65-73 (1985)
[23] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, Artificial Intelligence, 87, 1-2, 343-385 (1996) · Zbl 1506.68142
[24] I. Meiri, J. Pearl, Faster constraint satisfaction algorithms for temporal reasoning, Technical Report R-151, Department of Computer Science, University of California, Los Angeles, CA 90024-1596, 1991.; I. Meiri, J. Pearl, Faster constraint satisfaction algorithms for temporal reasoning, Technical Report R-151, Department of Computer Science, University of California, Los Angeles, CA 90024-1596, 1991.
[25] Miller, S. A.; Schubert, L. K., Time revisited, Computational Intelligence, 6, 108-118 (1990)
[26] Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Information Science, 7, 3, 95-132 (1974) · Zbl 0284.68074
[27] Nau, D.; Au, T.; Ilghami, O.; Kuter, U.; Munoz-Avila, H.; Murdock, J.; Wu, D.; Yaman, F., Applications of SHOP and SHOP2, IEEE Intelligent Systems, 20, 2, 34-41 (2005)
[28] Nau, D.; Au, T.; Ilghami, O.; Kuter, U.; Murdock, W.; Wu, D.; Yaman, F., SHOP2: An HTN planning system, Journal of Artificial Intelligence Research (JAIR), 20, 379-404 (2003) · Zbl 1058.68106
[29] Nebel, B., Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-horn class, (Proceedings of the Fifteenth European Conference on Artificial ec Intelligence (ECAI-96) (1996), John Wiley and Sons), 38-42
[30] Nebel, B.; Bürckert, H. J., Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra, Journal of the Association for Computing Machinery (ACM), 42, 1, 43-66 (1995) · Zbl 0886.68077
[31] Nökel, K., Temporally Distributed Symptoms in Technical Diagnosis, Lecture Notes in Artificial Intelligence, vol. 517 (1991), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York · Zbl 0786.68088
[32] S. Penberthy, J. Planning with continuous change, PhD thesis, University of Washington, 1993. Available as Technical Report UW-CSE-93-12-01.; S. Penberthy, J. Planning with continuous change, PhD thesis, University of Washington, 1993. Available as Technical Report UW-CSE-93-12-01.
[33] Ragni, M.; Wölfl, S., Temporalizing cardinal directions: From constraint satisfaction to planning, (Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (2006), AAAI Press), 472-480
[34] Song, F.; Cohen, R., The interpretation of temporal relations in a narrative, (Proceedings of the Seventh National Conference of the American Association for Artificial Intelligence (AAAI-88) (1988), Morgan Kaufmann), 745-750
[35] Tarski, A., On the calculus of relations, Journal of Symbolic Logic, 6, 73-89 (1941) · JFM 67.0973.02
[36] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series parallel digraphs, SIAM Journal of Computing, 11, 2, 298-313 (1982) · Zbl 0478.68065
[37] van Beek, P., Reasoning about qualitative temporal information, (Proceedings of the Eighth National Conference of the American Association for Artificial Intelligence (AAAI-90) (1990), AAAI Press/The MIT Press), 728-734
[38] van Beek, P., Temporal query processing with indefinite information, Artificial Intelligence in Medicine, 3, 325-339 (1991)
[39] van Beek, P., Reasoning about qualitative temporal information, Artificial Intelligence, 58, 1-3, 297-321 (1992) · Zbl 0782.68106
[40] van Beek, P.; Cohen, R., Exact and approximate reasoning about temporal relations, Computational Intelligence, 6, 132-144 (1990)
[41] van Beek, P.; Manchak, D. W., The design and experimental analysis of algorithms for temporal reasoning, Journal of Artificial Intelligence Research (JAIR), 4, 1-18 (1996) · Zbl 0900.68389
[42] Vilain, M.; Kautz, H. A., Constraint propagation algorithms for temporal reasoning, (Proceedings of the Fifth National Conference of the American Association for Artificial Intelligence (AAAI-86) (1986), Morgan Kaufmann), 377-382
[43] 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 (1990), Morgan Kaufmann), 373-381
[44] Weida, R.; Litman, D., Terminological reasoning with constraint networks and an application to plan recognition, (Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR-92) (1992), Morgan Kaufmann), 282-293
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.