Algorithms for Simple Temporal Reasoning

This dissertation describes research into new methods for automated temporal reasoning. For this purpose, several frameworks are available in literature. Chapter 1 presents a concise literature survey that provides a new overview of their interrelation. In the remainder of the dissertation, the focus is on quantitative frameworks, i.e. temporal constraint networks. Specifically, it is aimed at the subclass of Simple Temporal Networks (STNs) with the goal of assembling an algorithmic toolkit for dealing with the full set of temporal constraint networks. Temporal constraint networks find application in such diverse areas as space exploration, operation of Mars rovers, medical informatics, factory scheduling, and coordination of disaster relief efforts. Chapter 2 describes properties of the STN, both known and previously unknown, and investigates the question: "What is the Simple Temporal Problem (STP)?" Although the STP is the subject matter of many publications, a formal definition was not yet available. In fact, the various approaches for the STP available in literature do not all solve the same problem -- although each of the variants has an STN as underlying object. In the second part of Chapter 2, we therefore present theoretical research in the field of computational complexity and give an inventory of nine different Simple Temporal Queries (STQs), all of which have often been posed implicitly in existing literature. For all of these STQs, we prove membership in a theoretical complexity class. We also present the concept of a normal form for simple temporal information and prove that several STQs become significantly easier once time and effort have been spent for converting an STN into such a normal form. In Chapter 3, attention is devoted to graph and constraint theory and the links between these fields are explored. Although part of the graph theory we present already formed the basis for existing methods for temporal reasoning, we uncover and prove new relations with constraint networks. By the end of the chapter, we show how the presented concepts of directional, partial, and full path consistency (DPC, PPC, and FPC, respectively) relate to the STQs from Chapter 2. We show that both PPC and FPC STNs can be considered as a normal form for simple temporal information. The remaining chapters investigate algorithms for enforcing PPC (Chapter 4) and FPC (Chapter 5), and for maintaining either of these normal forms in the face of new information becoming available (Chapter 6). Each of these chapters follows the same general structure. New algorithms are presented, and their correctness and computational complexity are formally established. These are then compared to existing approaches, both theoretically and empirically. It turns out that each of the new algorithms can be considered as the new state of the art in its respective class for sparse temporal networks, and sometimes even across the board