Details of Grant 

EPSRC Reference:	GR/H46343/01
Title:	THEORY OF INTERVAL TIME HANDLING
Principal Investigator:	Hodkinson, Professor I
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computing
Organisation:	Imperial College London
Scheme:	Standard Research (Pre-FEC)
Starts:	01 August 1992	Ends:	31 July 1995	Value (£):	90,117
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:
Summary on Grant Application Form
To use the Allen interval algebra as a base for studying the expressive power and tractability of a variety of point and interval temporal formalisms, assisting applications in temporal planning and general temporal reasoning.Progress:The intractability of the Allen interval algebra is tackled by defining the notion of independent subnetworks and giving an algorithm that detects such networks. These independent subnetworks generalise Koomens reference intervals. Dually, we define a dependency in a network and use this to solve the collapsing problem in the Allen and Koomen planner. We also show that the collapsing problem manifests itself, in other forms, in various planners (e.g. Dean and McDermotts TMM or Kowalskis event calculus) and is a form of the persistence problem. Thus our solution to the collapsing problem has very wide practical application to planning and temporal reasoning. A detailed study of the Allen and Koomen planner was undertaken and a number of corrections, refinements and generalisations were made. These include the use of domain variables, the notion of reversibility (which allows the planner to work forwards and backwards) and work on stretching and clipping. This work appeared in a Technical Report entitled The problem of persistence in planning (Imperial College 1992) and has been accepted for publication in Computational Intelligence under the title Intractability in the Allen and Koomen Planner .The work on the Allen interval algebra was generalised to the study of relation algebra and algebraic logic. Thus, for example, we were able to define a general construction of a pair or interval algebra from a point algebra. These, more general, pair and interval algebras can be applied to a range of temporal reasoning problems where the underlying flow of time is not linear. Various properties of these algebras were obtained. For example, an interval algebra is w-categorical if the point algebra is. This generalises an important result of Ladkin and Maddux. Furthermore, we were able to prove that nearly all pair algebras are necessarily intractable. This negative result has repercussions for temporal reasoning, particularly over intervals. These results were compiled in a paper called Relation algebras of intervals which has been submitted to the Artificial Intelligence Journal. We applied techniques from game theory to algebraic logic and solved one of the outstanding problems in the field by giving neat axiomatisations for the representable relation algebras and cylindric algebras. This appears in Step by step - building representations in algebraic logic which has been submitted to the Journal of Symbolic Logic. The same techniques were used to characterise various other types of representation. Some of this appears in Completely representable relation algebras which is to be published in the March issue of the Bulletin of the Interest Group for Propositional and Predicate Logics.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.imperial.ac.uk