Chapter 1
Formal Theories of Time and Temporal Incidence
Lluis Vila
The design of intelligent agents acting in a changing environment must be based on some form of temporal reasoning system. Such a system should, in turn, be founded on a formal theory of time. Theories of time are based on some primitive time units (instants, intervals, etc. ) and determine both the expressiveness of the language and the completeness of the reasoning system.
The time theory of a temporal reasoning system is closely connected with the so-called theory of temporal incidence, meaning the set of domain-independent properties for the truth-value of temporal propositions throughout time. Classically, for a given domain, we distinguish between two classes of temporal propositions: changing domain properties (or fluents) and events whose occurrence may cause change on fluents.
Formal theories of time and temporal incidence involve some controversial issues such as (i) the expression of instantaneous events and fluents that hold instantaneously, (ii) the dividing instant problem and (iii) the formalization of the properties for non-instantaneous holding of fluents.
This chapter surveys the most relevant theories of time proposed in Artificial Intelligence according to various representational issues including the ones above. Also, the chapter presents a brief overview of temporal incidence theories and proposes a theory of temporal incidence defined upon a theory of instants and periods whose key insight is the distinction between continuous and discrete fluents.
1.1 Introduction
An intelligent agent interacting in a changing environment must be able to reason about these changes as well as the events and actions causing them, the effects it may have in the rest of the environment and the time when all these things happen or cease happening. Therefore, the design of intelligent agents acting in a changing environment must be based, among other components, on some form of temporal reasoning system. If we want this system to be well-founded and its properties formally studied it must be based upon a formal theory of time. Time theories are based in some time primitive unit (instants, intervals, etc. ) and determine both the expressiveness of the language as well as the completeness of the reasoning system.
As a matter of fact, time has been recognized as a fundamental notion in reasoning about changing domains and many frameworks for reasoning about change and action are built upon a temporal representation [McDermott, 1982; Allen, 1984; Kowalski and Sergot, 1986; Dean and McDermott, 1987; Williams, 1986; Shoham, 1987; Kuipers, 1988; Forbus, 1989; Galton, 1990; Schwalb et al., 1994; Pinto, 1994; Miller and Shanahan, 1994; Koubarakis, 1994a; Iwasaki et al., 1995; Fusaoka, 1996; Bacchus and Kabanza, 1996; Vila and Reichgelt, 1996]. In these frameworks, the domain at hand is formalized by expressing how propositions are true or false throughout time. Commonly there is a distinction between propositions describing the state of the world (fluents) and those representing occurrences that happen in the world and may change its state (events). Examples of fluents are “the light is on”, “the ball is moving at speed υ”, and “the battery charge is increasing”, and examples of events are “turn the light off”, “kick the ball” and “th...