Collaborating Authors

The Design and Experimental Analysis of Algorithms for Temporal Reasoning

Journal of Artificial Intelligence Research

In this paper, we discuss the design and empirical analysis of algorithms for a temporal reasoning system based on Allen's influential interval-based framework for representing temporal information. At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information. Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm. For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation. For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm.

Online Qualitative Temporal Reasoning with Explanation

AAAI Conferences

This work is a confluence of three problems in constraint reasoning: qualitative temporal reasoning (QTR), incremental reasoning, and explanation generation. Our primary objective is to detect the cause of inconsistency in an incremental version of the QTR problem.

Retried Logic for Representing First Order Temporal Constraints

AAAI Conferences

The representation of, and reasoning about time play an important role in any intelligent activities. In this paper, we propose an ontology for representing quantitative first order temporal constraints. This logic that we propose in this paper uses instant and interval structures as primitives and has the expressive power of the popular temporal logics of Shoham's [9] and BTK's [4]. The advantage of our logic is that it uses the syntactic structures that explicitly implements the semantics of the temporal structures, such as, true throughout an interval (tt), or true at a point (at). Therefore, developing efficient inference rules and proof procedures for this logic is relatively easy. This paper is organized as the following: In section 2, we introduce the representation of temporal knowledge. In section 3 we introduce our temporal constraint language providing its syntax and semantics. The paper is concluded with a summary and a discussion in section 4.

An Introduction to Constraint-Based Temporal Reasoning

Morgan & Claypool Publishers

This book provides a concise introduction to the core computational elements of temporal reasoning for use in AI systems for planning and scheduling, as well as systems that extract temporal information from data. It presents a survey of temporal frameworks based on constraints, both qualitative and quantitative, as well as of major temporal consistency techniques. ISBN 9781608459674, 121 pages.

ITSAT: An Efficient SAT-Based Temporal Planner

Journal of Artificial Intelligence Research

Planning as satisfiability is known as an efficient approach to deal with many types of planning problems. However, this approach has not been competitive with the state-space based methods in temporal planning. This paper describes ITSAT as an efficient SAT-based (satisfiability based) temporal planner capable of temporally expressive planning. The novelty of ITSAT lies in the way it handles temporal constraints of given problems without getting involved in the difficulties of introducing continuous variables into the corresponding satisfiability problems. We also show how, as in SAT-based classical planning, carefully devised preprocessing and encoding schemata can considerably improve the efficiency of SAT-based temporal planning.