×

Backtracking algorithms for disjunctions of temporal constraints. (English) Zbl 0945.68038

Summary: We extend the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to consider constraints of the form \(x_{1}-y_{1}\leq r_{1} \lor \cdots \lor x_{n}-y_{n}\leq r_{n}\) , where \(x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}\) are variables ranging over the real numbers, \(r_{1},\ldots,r_{n}\) are real constants, and \(n\geq 1\). This is a wide class of temporal constraints that can be used to model a variety of problems in temporal reasoning, scheduling, planning, and temporal constraint databases. We have implemented several progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints: backtracking, backjumping, three variations of forward checking, and forward checking with backjumping. We have partially ordered the above algorithms according to the number of visited search nodes and the number of performed consistency checks. Although our problem is non-binary, our results agree with the results of Kondrak and van Beek who consider only binary constraints. We have also studied the performance of the above algorithms experimentally using randomly generated sets of data and job shop scheduling problems. The experiments with random instances allowed us to locate the hard region for this class of problems. The results show that hard problems occur at a critical value of the ratio of disjunctions to variables.

MSC:

68P15 Database theory
68T01 General topics in artificial intelligence
68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J. F., Towards a general model of action and time, Artificial Intelligence, Vol. 23, 2, 123-154 (1984) · Zbl 0567.68025
[2] (Allen, J. F.; Kautz, H.; Pelavin, R., Reasoning about Plans (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA) · Zbl 0759.68077
[3] Armando, A.; Castellini, C.; Giunchiglia, E., Sat-based procedures for temporal reasoning, (Proc. European Conference on Planning (ECP-99) (1999)) · Zbl 1098.68693
[4] Bacchus, F.; van Run, P., Dynamic variable ordering in CSPs, (Proc. 1st International Conference on Principles and Practice of Constraint Programming (CP-95), Cassis, France (1995)), 258-275
[5] Baptiste, P.; Le Pape, C., A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling, (Proc. IJCAI-95, Montreal, Quebec, Vol. 1 (1995)), 600-606
[6] Beck, C.; Davenport, A.; Fox, M., Five pitfalls of empirical scheduling research, (Proc. 3rd International Conference on Principles and Practice of Constraint Programming (CP-97), Linz, Austria (1997)), 390-404
[7] Belhadji, S.; Isli, A., Temporal constraint satisfaction techniques in job shop scheduling problem solving, CONSTRAINTS, Vol. 3, 203-211 (1998) · Zbl 0911.68188
[8] Bessière, C.; Meseguer, P.; Freuder, E.; Larrosa, J., On forward checking for non-binary constraint satisfaction, (Proc. 5th International Conference on Principles and Practice of Constraint Programming (CP-99), Alexandria, VA (1999)), 88-102 · Zbl 0957.68104
[9] Brelaz, D., New methods to color the vertices of a graph, J. ACM, Vol. 22, 4, 251-256 (1979) · Zbl 0394.05022
[10] Cheeseman, P.; Kanefsky, B.; Taylor, W., Where the really hard problems are, (Proc. IJCAI-91, Sydney, Australia, Vol 1 (1991)), 331-337 · Zbl 0747.68064
[11] Cheng, C. C.; Smith, S. F., Generating feasible schedules under complex metric constraints, (Proc. AAAI-94, Seattle, WA (1994))
[12] Chleq, N., Efficient algorithms for networks of quantitative temporal constraints, (Proc. CONSTRAINTS-95, Melbourne Beach, FL (1995)), 40-45
[13] Chomicki, J.; Revesz, P. Z., Constraint-based interoperability of spatiotemporal databases, (Proc. SSD-97. Proc. SSD-97, Lecture Notes in Computer Science, Vol. 1262 (1997), Springer: Springer Berlin), 142-161
[14] Crawford, J.; Auton, D., Experimental results on the crossover point in random 3-SAT, Artificial Intelligence, Vol. 81, 31-57 (1996) · Zbl 1508.68324
[15] Currie, K.; Tate, A., O-plan: The open planning architecture, Artificial Intelligence, Vol. 52, 1, 49-86 (1991)
[16] Dechter, R., From local to global consistency, Artificial Intelligence, Vol. 55, 87-107 (1992) · Zbl 0762.68053
[17] Dechter, R.; Meiri, I., Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artificial Intelligence, Vol. 68, 211-241 (1994) · Zbl 0942.68576
[18] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, (Brachman, R.; Levesque, H.; Reiter, R., Proc. 1st International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ontario (1989)), 83-93
[19] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial Intelligence (Special Volume on Knowledge Representation), Vol. 49, 1-3, 61-95 (1991) · Zbl 0737.68070
[20] Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artificial Intelligence, Vol. 34, 1, 1-38 (1988) · Zbl 0643.68156
[21] Drakengren, T.; Jonsson, P., Towards a complete classification of tractability in Allen’s algebra, (Proc. IJCAI-97, Nagoya, Japan, Vol. 2 (1997)), 1466-1471
[22] Drakengren, T.; Jonsson, P., Twenty-one large tractable subclasses of Allen’s algebra, Artificial Intelligence, Vol. 93, 297-319 (1997) · Zbl 1017.03514
[23] El-Kholy, A.; Richards, B., Temporal and resource reasoning: The \(parc\) Plan approach, (Proc. 12th European Conference on Artificial Intelligence (ECAI-96), Budapest, Hungary (1996)), 614-618
[24] (Frank, A. U.; Campari, I.; Formentini, U., Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Computer Science, Vol. 639 (1992), Springer: Springer Berlin)
[25] Freuder, E., Synthesizing constraint expressions, Comm. ACM, Vol. 21, 11, 958-966 (1978) · Zbl 0386.68065
[26] Freuder, E., A sufficient condition for backtrack-free search, J. ACM, Vol. 29, 24-32 (1982) · Zbl 0477.68063
[27] Frost, D.; Dechter, R., In search of the best constraint satisfaction search, (Proc. AAAI-94, Seattle, WA (1994)), 301-306
[28] Gent, I.; MacIntyre, E.; Prosser, P.; Smith, B.; Walsh, T., An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem, (Proc. 2nd International Conference on Principles and Practice of Constraint Programming (CP-96), Cambridge, MA (1996)), 179-193
[29] Gent, I. P.; Walsh, T., The satisfiability constraint gap, Artificial Intelligence, Vol. 81, 59-80 (1996) · Zbl 1508.68330
[30] Gerevini, A.; Cristani, M., On finding a solution in temporal constraint satisfaction problems, (Proc. IJCAI-97, Nagoya, Japan (1997))
[31] Gerevini, A.; Schubert, L., Efficient temporal reasoning through timegraphs, (Proc. IJCAI-93, Chambéry, France (1993)), 648-654
[32] Gerevini, A.; Schubert, L., Efficient algorithms for qualitative reasoning about time, Artificial Intelligence, Vol. 74, 207-248 (1995) · Zbl 1013.68553
[33] Gerevini, A.; Schubert, L.; Schaeffer, S., Temporal reasoning in timegraph I-II, SIGART Bulletin, Vol. 4, 3, 21-25 (1993)
[34] Ghallab, M.; Laruelle, H., Representation and control in IxTeT, a temporal planner, (Proc. 2nd International Conference on AI Planning Systems, Chicago, IL (1994)), 61-67
[35] Ginsberg, M., Dynamic backtracking, J. Artificial Intelligence Res., Vol. 1, 25-46 (1993) · Zbl 0900.68179
[36] Golomb, S.; Baumert, L., Backtrack programming, J. ACM, Vol. 12, 516-524 (1965) · Zbl 0139.12305
[37] Haralick, R.; Elliot, G., Increasing tree efficiency for constraint satisfaction problems, Artificial Intelligence, Vol. 14, 263-314 (1980)
[38] Jonsson, P.; Bäckström, C., A linear programming approach to temporal reasoning, (Proc. AAAI-96, Portland, OR (1996)) · Zbl 0939.68828
[39] Kambhampati, S.; Yang, X., On the role of disjunctive representations and constraint propagation in refinement planning, (Proc. 5th International Conference on the Principles of Knowledge Representation and Reasoning (KR-96), Cambridge, MA (1996))
[40] Kautz, H.; Ladkin, P., Integrating metric and qualitative temporal reasoning, (Proc. AAAI-91, Anaheim, CA (1991)), 241-246
[41] Kondrak, G., A theoretical evaluation of selected backtracking algorithms, Technical Report TR94-10 (1994), University of Alberta
[42] Kondrak, G.; van Beek, P., A theoretical evaluation of selected backtracking algorithms, Artificial Intelligence, Vol. 89, 365-387 (1997) · Zbl 1042.68671
[43] Koubarakis, M., Complexity results for first-order theories of temporal constraints, (Proc. 4th International Conference on the Principles of Knowledge Representation and Reasoning (KR-94), Bonn, Germany (1994), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 379-390
[44] Koubarakis, M., Database models for infinite and indefinite temporal information, Information Systems, Vol. 19, 2, 141-173 (1994)
[45] Koubarakis, M., Tractable disjunctions of linear constraints, (Proc. 2nd International Conference on Principles and Practice of Constraint Programming (CP-96), Cambridge, MA (1996)), 297-307 · Zbl 0989.68134
[46] Koubarakis, M., From local to global consistency in temporal constraint networks, Theoret. Comput. Sci., Vol. 173, 89-112 (1997), Invited submission to the special issue dedicated to the 1st International Conference on Principles and Practice of Constraint Programming (CP-95), U. Montanari, F. Rossi (Eds.) · Zbl 0902.68016
[47] Koubarakis, M., The complexity of query evaluation in indefinite temporal constraint databases, Theoret. Comput. Sci., Vol. 171, 25-60 (1997), Special Issue on Uncertainty in Databases and Deductive Systems, L.V.S. Lakshmanan (Ed.) · Zbl 0887.68029
[48] Laborie, P.; Ghallab, M., Planning with sharable resource constraints, (Proc. IJCAI-95, Montreal, Quebec (1995)), 1643-1649
[49] Ladkin, P.; Maddux, R., On binary constraint problems, J. ACM, Vol. 41, 3, 435-469 (1994) · Zbl 0813.03045
[50] Ladkin, P.; Reinefeld, A., Effective solution of qualitative interval constraint problems, Artificial Intelligence, Vol. 57, 105-124 (1992)
[51] Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, Vol. 8, 99-118 (1977) · Zbl 0341.68061
[52] Meiri, I., Combining quantitative and qualitative constraints in temporal reasoning, Artificial Intelligence, Vol. 87, 343-384 (1996) · Zbl 1506.68142
[53] Minton, S.; Johnston, M. D.; Philips, A. B.; Laird, P., Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, Vol. 58, 161-205 (1992) · Zbl 0782.90054
[54] Mitchell, D.; Levesque, H., Some pitfalls for experimenters with random SAT, Artificial Intelligence, Vol. 81, 111-125 (1996) · Zbl 1508.68340
[55] Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences, Vol. 7, 95-132 (1974) · Zbl 0284.68074
[56] Nebel, B.; Bürckert, H.-J., Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra, J. ACM, Vol. 42, 1, 43-66 (1995) · Zbl 0886.68077
[57] Nuijten, W. P.M., Time and resource-constrained scheduling: A constraint satisfaction approach, Ph.D. Thesis (1994), Department of Mathematics and Computer Science, Eindhoven University of Technology · Zbl 0837.90068
[58] Penberthy, J. S.; Weld, D., Temporal planning with continuous change, (Proc. AAAI-94, Seattle, WA (1994)), 1010-1015
[59] Prosser, P., Hybrid algorithms for the constraint satisfaction problem, Comput. Intelligence, Vol. 9, 3, 268-299 (1993)
[60] Prosser, P., An empirical study of phase transitions in binary constraint satisfaction problems, Artificial Intelligence, Vol. 81, 81-109 (1996) · Zbl 1523.68093
[61] Sadeh, N.; Sycara, K.; Xiong, Y., Backtracking techniques for the job shop scheduling constraint satisfaction problem, Artificial Intelligence, Vol. 76, 455-480 (1995)
[62] Schwalb, E.; Dechter, R., Processing disjunctions in temporal constraint networks, Artificial Intelligence, Vol. 93, 29-61 (1997) · Zbl 1017.68536
[63] Selman, B.; Mitchell, D.; Levesque, H., Generating hard satisfiability problems, Artificial Intelligence, Vol. 81, 17-29 (1996) · Zbl 1508.68347
[64] Smith, B.; Dyer, M., Locating the phase transitions in constraint satisfaction problems, Artificial Intelligence, Vol. 81, 155-181 (1996) · Zbl 1508.68348
[65] Staab, S., On non-binary temporal relations, (Proc. ECAI-98, Brighton, UK (1998)), 567-571
[66] Stergiou, K., Backtracking algorithms for checking the consistency of disjunctions of temporal constraints, Master’s Thesis (1997), Department. of Computation, UMIST: Department. of Computation, UMIST Manchester, UK
[67] Tsang, E., Foundations of Constraint Satisfaction (1993), Academic Press: Academic Press New York
[68] Ullman, J., Principles of Data Base and Knowledge Base Systems, Vol. 1 (1988), Computer Science Press: Computer Science Press Rockville, MD
[69] van Beek, P., Temporal query processing with indefinite information, Artificial Intelligence in Medicine, Vol. 3, 325-339 (1991)
[70] van Beek, P., Reasoning about qualitative temporal information, Artificial Intelligence, Vol. 58, 297-326 (1992) · Zbl 0782.68106
[71] van Beek, P.; Manchak, D., The design and experimental analysis of algorithms for temporal reasoning, J. Artificial Intelligence Res., Vol. 4, 1-18 (1996) · Zbl 0900.68389
[72] Vilain, M.; Kautz, H.; 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 (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 373-381
[73] Wilkins, D. E., Practical Planning: Extending the Classical AI Planning Paradigm (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[74] Wilkins, D. E., Can AI planners solve practical problems, Comput. Intelligence, Vol. 6, 4, 232-246 (1990)
[75] Wilkins, D. E.; Myers, K., A common knowledge representation for plan generation and reactive execution, Technical Report 532R (1994), SRI International: SRI International Menlo Park, CA, Available from http://www.ai.sri.com/people/wilkins/papers.html. To appear in Journal of Logic and Computation
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.