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.
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  and BTK's . 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.
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.
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.