Temporal and Probabilistic Reasoning

Select By Year:

Select Another Subject Area:

Google Scholar

You can also find out about my published research on Google Scholar, which, as well as providing links to the papers and their abstracts, additionally provides the latest citation counts and index values.

Overview

This page contains several constraint satisfaction papers that are specifically concerned with temporal and probabilistic reasoning (and representation). The temporal reasoning papers grew out of my collaboration with Matthew Beaumont after I became a co-supervisor for his PhD thesis. My main insight was to see how local search algorithms could be applied to the interval algebra problems that Matthew was studying. This work continued in Duc Nghia Pham’s PhD thesis and culminated in our showing how interval algebra problems can be more efficiently solved by representing them as satisfiability problems (see AIJ 2008).

There are also two papers (ADC 2004 and TIME-ICTL 2003) connected with an idea that occurred to me in a research group meeting about how to represent the present moment (i.e. now) in bitemporal database systems. And finally I assisted in the preparation of two probabilistic reasoning papers (PRICAI 2012 and JIST 2011) as part of a collaboration with Kewen Wang on an Australian Research Council Discovery Grant.

2012

Ramachandran, R., Wang, K., Wang, J. & Thornton, J. R. (2012). Probabilistic Reasoning in DL-Lite. PRICAI 2012: 12th Pacific Rim International Conference on Artificial Intelligence, Lecture Notes in Computer Science. 7458, 480-491, Springer, ISSN 0302-9743.

2011

Sotomayor, M., Wang, K., Shen, Y. & Thornton, J. R. (2011). Probabilistic Multi-context Systems. JIST 2011: Joint International Semantic Technology Conference. Lecture Notes in Computer Science, 7185, 366-375, Springer, ISSN 0302-9743.

2008

Pham, D. N., Thornton, J. R. & Sattar, A. (2008). Modelling and Solving Temporal Reasoning as Propositional Satisfiability. Artificial Intelligence. 172(15), 1752-1782, ISSN 0004-3702.

Abstract: Representing and reasoning about time dependent information is a key research issue in many areas of computer science and artificial intelligence. One of the best known and widely used formalisms for representing interval-based qualitative temporal information is Allen’s interval algebra (IA). The fundamental reasoning task in IA is to find a scenario that is consistent with the given information. This problem is in general NP-complete.
In this paper, we investigate how an interval-based representation, or IA network, can be encoded into a propositional formula of Boolean variables and/or predicates in decidable theories. Our task is to discover whether satisfying such a formula can be more efficient than finding a consistent scenario for the original problem. There are two basic approaches to modelling an IA network: one represents the relations between intervals as variables and the other represents the end-points of each interval as variables. By combining these two approaches with three different Boolean satisfiability (SAT) encoding schemes, we produced six encoding schemes for converting IA to SAT. In addition, we also showed how IA networks can be formulated into satisfiability modulo theories (SMT) formulae based on the quantifier-free integer difference logic (QF-IDL). These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. More specifically, we show that the new point-based 1-D support SAT encoding of IA produces consistently better results than the other alternatives considered. In comparison with the six different SAT encodings, the SMT encoding came fourth after the point-based and interval-based 1-D support schemes and the point-based direct scheme. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT or SMT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.

2006

Pham, D. N., Thornton, J. R. & Sattar, A. (2006). Towards an Efficient SAT Encoding for Temporal Reasoning. CP 2006: 12th International Conference on the Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, 4204, 421-436, Springer, ISSN 0302-9743.

2005

Pham, D. N., Thornton, J. R. & Sattar, A. (2005). Modelling and Solving Temporal Reasoning as Satisfiability. Proceedings of the 4th International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, Sitges, Spain. pp. 117-131.

2004

Beaumont, M., Thornton, J. R., Sattar, A. & Maher, M. (2004). Solving Over-constrained Temporal Reasoning Problems using Local Search. PRICAI 2004: 8th Pacific Rim International Conference on Artificial Intelligence, Lecture Notes in Computer Science, 3157, 134-143, Springer, ISSN 0302-9743..

Stantic, B., Khanna, S. & Thornton, J. R. (2004). An Efficient Method for Indexing Now-relative Bitemporal Data. In ADC 2004: Proceedings of the 15th Australasian Database Conference, Australian Computer Society, pp. 113-122.

Thornton, J. R., Beaumont, M., Sattar, A. & Maher, M. (2004). A Local Search Approach to Modelling and Solving Interval Algebra Problems. Journal of Logic and Computation, 14(1), 93-112, Oxford University Press, ISSN 0955-792X.

2003

Stantic, B., Thornton, J. R., & Sattar, A. (2003). A Novel Approach to Model NOW in Temporal Databases. In TIME-ICTL 2003: Proceedings of the 10th International Symposium on Temporal Representation and Reasoning / 4th International Conference on Temporal Logic, IEEE, pp. 174-181.

2002

Thornton, J. R., Beaumont, M., Sattar, A. & Maher, M. (2002). Applying Local Search to Temporal Reasoning. In: TIME 2002: 9th International Symposium on Temporal Reasoning and Representation, IEEE, pp. 94-99, ISSN 1530-1311.

2001

Beaumont, M., Sattar, A., Maher, M., & Thornton, J. R. (2001). Solving Overconstrained Temporal Reasoning Problems. AI 2001: 14th Australian Joint Conference on Artificial Intelligence, Lecture Notes in Computer Science, 2556, 603-614, ISSN 0302-9743.