InteLLigence

Research on Constraint Programming

Description

Cardinal Direction Constraints
We have investigated a new model for cardinal direction information which works with points, lines, line segments and extended regions. We have investigated the use of this model in spatial database management systems based on constraint technology. We have studied the composition operation in this model and proposed polynomial time algorithms for the consistency checking problem. This work is led by Spiros Skiadopoulos.

Tractable Disjunctive Constraints
We are interested in precise characterizations of classes of tractable constraints. In 1995 we studied the problems of deciding consistency and performing variable elimination for Horn disjunctive linear constraints. Horn disjunctive linear constraints are disjunctions of weak linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. The most important result here is that deciding consistency of a set of constraints in this class can be done in PTIME. This has also been proved independently by Peter Jonsson and Christer Backstrom.

Together with David Cohen, Peter Jeavons and Peter Jonsson we have extended the above PTIME result and showed that a certain intuitive property called independence is sufficient to ensure tractability of a general form of disjunctive constraints. Many previous results on tractable classes of disjunctive constraints can now be seen to be instances of our general theory. More recently Matthias Broxvall, Peter Jonsson and Jochen Renz have extended this result and showed that independence is also necessary. All of us think that these results are very nice!

Temporal Disjunctive Constraints
Kostas Stergiou and Manolis Koubarakis have extended the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to consider disjunctions of the form

X1-Y1 <= R1 OR X2-Y2 <= R2 OR ... OR Xn-Yn <= Rn

where X1, X2, ...,Xn, Y1, Y2, ...,Yn are variables ranging over the real numbers, R1, R2, ...,Rn are real constants, and n >= 1.

We have implemented four progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints: backtracking, backjumping, forward checking and forward checking with backjumping. We have also implemented the fail first heuristic in conjunction with 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. To achieve this result, we modified slightly the methodology and proofs of Kondrak and van Beek, for binary constraint satisfaction problems, although our problem is non-binary. We have also studied the performance of the above algorithms experimentally using randomly generated sets of data. Finally, we have carried out a series of experimental results on the location of the hard region. The results show that hard problems occur at a critical value of the ratio of disjunctions to variables.

The Scheme of Indefinite Constraint Databases
In the Ph.D. thesis of Manolis Koubarakis (National Technical University of Athens, 1994) we developed the scheme of indefinite constraint databases and concentrated on instances of this scheme where the constraints are temporal. Our work starts from the premise that an important requirement of advanced temporal applications (e.g., planning and scheduling) is the ability to deal with definite, indefinite, finite and infinite temporal information. We proposed that a combination of classical relational databases and temporal constraint networks offers a powerful framework which addresses the database needs of these applications. We have also studied the complexity of query processing in such databases.

In this context we have also studied the complexity of query processing in the case that the constraints belong to various subclasses of linear constraints.

Related Publications

Koubarakis M.: Query Evaluation in Temporal Constraint Databases, In M. Fischer, D. Gabbay and L. Villa (eds.) Handbook of Temporal Reasoning in Artificial Intelligence. Volume 1 in the series “Foundations of Artificial Intelligence”, B. Nebel, J.Hendler and H. Kitano (eds). Elsevier Science. 2005.

Publication Type: Book Chapters [abstract]

Grumbach S., Koubarakis M., Scholl M., Rigaux P., Skiadopoulos S.: Spatiotemporal models and languages: an approach based on constraints, In M. Koubarakis, T. Sellis et. al. Spatiotemporal Databases: The Chorochronos Approach, Lecture Notes in Computer Science, Vol. 2520, June 2003, Springer.

Publication Type: Book Chapters [abstract]

Skiadopoulos S., Koubarakis M.: Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions, CP 2002, pages 341-355.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: Querying Temporal Constraint Networks: A Unifying Approach, Applied Intelligence,Vol. 17, No. 3, pages 297-311, November-December 2002.

Publication Type: Journal Publications [abstract] [file]

Skiadopoulos S., Koubarakis M.: Composing Cardinal Direction Relations, Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD-2001), Los Angeles, California, July 12-15, 2001.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: Tractable Disjunctions of Linear Constraints: Basic Results and Applications to Temporal Reasoning, Theoretical Computer Science, Vol. 266, pages 311-339, September 2001.

Publication Type: Journal Publications [abstract] [file]

Stergiou K., Koubarakis M.: Backtracking Algorithms for Disjunctions of Temporal Constraints, Artificial Intelligence, Vol. 120 (1) (2000) pp. 81-117.

Publication Type: Journal Publications [abstract]

Koubarakis M., Skiadopoulos S.: Querying temporal and spatial constraint networks in PTIME, Artificial Intelligence, Vol. 123, No. 1-2, pages 223-263, 2000.

Publication Type: Journal Publications [abstract] [file]

Cohen D., Jeavons P., Jonsson P., Koubarakis M.: Building Tractable Disjunctive Constraints, Journal of ACM, Vol. 47, No. 5, pages 826-853, September 2000.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M., Skiadopoulos S.: Querying Temporal Constraint Networks in PTIME, Proceedings of AAAI-99. Orlando, Florida, July 18-22, 1999.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M., Skiadopoulos S.: Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatio-Temporal Information In Spatio-Temporal Database Management, (Proceedings of the International Workshop STDBM'99), Lecture Notes in Computer Science, Vol. 1678, Bohlen, M.H. and Jensen, C. and Scholl, M. (eds.), pages 204-223, Springer, 1999.

Publication Type: Workshop Proceedings [abstract]

Koubarakis M., Skiadopoulos S.: Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatio-Temporal Information, In M. H. Bohlen, C.S. Jensen and M.O. Scholl, Spatio-Temporal Database Management (Proceedings of the International Workshop STDBM'99, Edinburgh, Scotland, September 1999), LNCS vol. 1678, Springer, pages 204-223.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M., Skiadopoulos S.: Querying Indefinite Temporal and Spatial Information: A New Frontier, Proceedings of the IJCAI-99 Workshop on Hot Topics in Temporal and Spatial Reasoning, Stockholm, Sweden, August 2, 1999.

Publication Type: Workshop Proceedings [abstract] [file]

Stergiou K., Koubarakis M.: Backtracking Algorithms for Disjunctions of Temporal Constraints, Proceedings of AAAI-98, pages 248-253. Madison, Wisconsin, July 26-30, 1998.

Publication Type: Conference Publications [abstract] [file]

Cohen D., Jeavons P., Koubarakis M.: Tractable Disjunctive Constraints, Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP97). Lecture Notes in Computer Science, Vol. 1330, pages 478-490.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: From Local to Global Consistency in Temporal Constraint Networks, Theoretical Computer Science, Vol. 173, pages 89-112, February 1997. Invited submission to the special issue for the 1st International Conference on Principles and Practice of Constraint Programming (CP95), Editors: U. Montanari and F. Rossi.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M.: The Complexity of Query Evaluation in Indefinite Temporal Constraint Databases, Theoretical Computer Science, Vol. 171, pages 25-60, January 1997. Special Issue on Uncertainty in Databases and Deductive Systems, Editor: L.V.S. Lakshmanan.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M.: Tractable Disjunctions of Linear Constraints, Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP96), Lecture Notes in Computer Science, Vol. 1118, pages 297-307.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: From Local to Global Consistency in Temporal Constraint Networks, Proceedings of the 1st International Conference on Principles and Practice of Constraint Programming (CP95), Lecture Notes in Computer Science, Vol. 976, pages 53-69, September 1995.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: Databases and Temporal Constraints: Semantics and Complexity, In Clifford, J. and Tuzhilin, A. (eds.), Recent Advances in Temporal Databases (Proceedings of the International Workshop on Temporal Databases, Zurich, Switzerland, September 1995), Workshops in Computing, Springer, pages 93-109.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M.: Complexity Results for First-Order Theories of Temporal Constraints, Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR'94), pages 379-390, May 1994.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: Database Models for Infinite and Indefinite Temporal Information, Information Systems, Vol. 19, No. 2, March 1994, pages 141-173.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M.: Foundations of Indefinite Constraint Databases, In A. Borning (ed.), Proceedings of the 2nd International Workshop on the Principles and Practice of Constraint Programming (PPCP'94), Lecture Notes in Computer Science vol. 874, pages 266-280, Springer Verlag, 1994.

Publication Type: Workshop Proceedings [abstract] [file]

Papadias D., Frank A., Koubarakis M.: Constraint-Based Reasoning in Geographic Databases: the Case of Symbolic Arrays, Proceedings of the 2nd ICLP Workshop on Deductive Databases and Logic Programming, Santa Margherita Ligure, Italy, June 1994. Published as GMD-Studien Nr. 231, U. Geske, D. Seipel (eds.)

Publication Type: Workshop Proceedings [abstract]

Koubarakis M.: Representation and Querying in Temporal Databases: the Power of Temporal Constraints, Proceedings of the 9th International Conference on Data Engineering, pages 327-334, April 1993.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M.: Dense Time and Temporal Constraints with "not equals", Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR'92), pages 24-35, October 1992.

Publication Type: Conference Publications [abstract] [file]