A Case Study in Reasoning about Actions and Continuous Change

Rob Miller Department of Computing, Imperial College, 180 Queen’s Gate, London SW7 2BZ, U.K. rsm@doc.ic.ac.uk

http://www-lp.doc.ic.ac.uk/UserPages/staff/rsm/rsm.html

November 1995, latest revision 18th April 1996

Imperial College Research Report DoC 95/20

(A shorter version of this paper appears in the proceedings of ECAI’96, Budapest, Hungary, August 1996)

Abstract

This paper shows how the Situation Calculus can be extended to deal both with ‘narratives’ and with domains containing real-valued parameters, whose actual values may vary continuously between the occurrences of actions. In particular, a domain is represented where action occurrences may be ‘triggered’ at instants in time when certain parameters reach particular values. Its formalisation requires the integration of several types of default reasoning. Hence Baker’s circumscriptive solution to the frame problem is extended to reflect the assumptions that by default a given action does not occur at a given time point, that by default a given set of parameter values does not trigger a given action, and that by default a given action occurrence does not result in a discontinuity for a given parameter. Regarding the minimisation of discontinuities, the example illustrates how circumstances can arise where, at a particular time point, discontinuities in some parameters can be ‘traded’ for discontinuities in others. It is argued that, in general, in such cases extra domain-specific information will be necessary in order to eliminate anomalous models of the domain.

1 Introduction

This paper (which is an extended version of [7]) builds on the work of Miller and Shanahan [8], of Sandewall [12] [13] and of Pinto [9] to develop a Situation Calculus able to represent both ‘narrative’ information and information about real-valued parameters whose actual values may vary continuously in time. The need to represent continuous change raises several issues in reasoning about actions. In particular, a truly comprehensive solution to the frame problem must be applicable to domains involving both continuous and discrete change.

Narrative information is information about what actions have or have not actually occurred at particular instants of time. In order to represent narratives, the Situation Calculus’s usual ontology (of actions, Boolean-valued fluents and situations) is extended here, as in [8], with a time line (in fact, a real-number line). Using the extra predicate Happens, action occurrences are embedded at various points along this time line, thus dividing it into non-overlapping intervals. Extra axioms are included which equate all the time points within a single such interval to a single situation, using the function State (mapping time points to situations). The axiomatisation thus ensures that between action occurrences (the Boolean values of) all fluents persist. At points in time where actions occur, this principle of persistence is weakened to a default. Which fluents persist at such points is largely determined by the particular solution to the frame problem employed by the conventional Situation Calculus component of the theory. The solution used here is based on that of Baker [1]. As in [8], Baker’s circumscription policy is extended, in this case to model other modes of default reasoning relating either to continuous change or to narratives.

To deal with continuous change, the Situation Calculus’s ontology is further extended with the familiar mathematical notion of a parameter. Whereas fluents take on Boolean values at different moments of time, parameters take on real number values. As mentioned above, fluents are associated with the notion of persistence. The corresponding notion for parameters is that of continuity (in the usual mathematical sense). Following Sandewall [12], in this paper the view is taken that during periods of time in which no actions occur, both the principle of persistence of fluent values and the principle of continuity of parameter values are inviolate. At points in time where actions occur, both of these principles are weakened to defaults. A problem analogous to the frame problem arises for parameters – that is, how to succinctly express that most parameters remain continuous at most points where actions occur. To borrow some terminology from Sandewall, attention will be restricted here to narratives which are piecewise continuous, i.e. in which there are only a finite number of action occurrences in any given finite interval of time.

The paper is organised as follows. In Section 2, an example domain is introduced, and a conventional mathematical model constructed and examined in some detail. The example is of particular interest first because it involves negative feedback, and second because it includes an action occurrence which has been ‘triggered’ by parameters reaching certain values at the end of a period of continuous change. In Section 3 the domain-independent axioms of the extended Situation Calculus are described, and in Section 4 the formalism is applied to the example described in Section 2. The paper ends with a general discussion in Section 5.

2 The Water Tanks Example

This example involves two open-top water tanks, T ankA and T ankB. The two tanks have identical length and width, but T ankA is taller than T ankB. T ankA is suspended above T ankB, and in the bottom of T ankA are two taps, T apC and T apD, both of which (when open) discharge water into T ankB, at a rate proportional to the level of water in T ankA (i.e. at a rate proportional to the water pressure at the bottom of T ankA). Initially, T ankA contains more water than will fit into T ankB, T ankB is empty, and both taps are closed. This initial scenario is illustrated in Figure 1. L is the initial level of the water in T ankA, and H_{B} is the height of T ankB.

[figure: T ankA; T ankB; T apC; T apD; L; H_{B}; 0; T_{1}; T_{2}; T_{3}; t; \begin{matrix}T apC \\ opened \end{matrix}; \begin{matrix}T apD \\ opened \end{matrix}; T ankB ; overflows]

Figure 1

Suppose that at time T_{1}, T apC is opened causing water to flow from T ankA to T ankB, at time T_{2} (sometime later) T apD is also opened, and at time T_{3} (sometime later still) T ankB overflows. This course of events is also illustrated in Figure 1. Note that the overflowing event (i.e. action occurrence) at T_{3} is ‘triggered’ – T_{3} is determined by the times T_{1} and T_{2} and the functions describing the flow of water through the two taps.

A (naive) mathematical model of this domain can be formulated in a standard way. Four parameters are needed – all functions from time (represented by the non-negative reals) to the reals. LevelA(t) and LevelB(t) are the functions representing the levels of water in T ankA and T ankB respectively, and F lowC(t) and F lowD(t) represent the water flow through T apC and T apD. Let K be the constant of proportionality between the level of water in T ankA and the flow through either of the taps when open. It will be assumed that specific values have been given for T_{1} and T_{2} such that 0 < T_{1} < T_{2}. The specific value of T_{3} is obviously dependent on L, H_{B}, K, T_{1} and T_{2}, and it will also be assumed that L, H_{B}, K, T_{1} and T_{2} are such that T_{2} < T_{3}.

The process of constructing the model may be summarised as follows. (i) Formulate some equations relating the functions LevelA(t), LevelB(t), F lowC(t) and F lowD(t) and/or their derivatives under various different physical circumstances of the system. (ii) Divide the time line into several intervals (such as the interval between T_{1} and T_{2}, where T apC is open but T apD is closed). For each such interval, pick a subset of these equations which are applicable throughout the interval, and solve them simultaneously to derive explicit independent expressions for each parameter in terms of time alone. Generally, because the initial equations are often differential equations, these solutions will contain unknown constants. (iii) Use knowledge of the physics of the system to assign particular values to these unknown constants. As will be seen, these assignments are in fact determined either by ‘initial conditions’, or by decisions as to which parameters of the system are continuous at the points T_{1}, T_{2} and T_{3}.

To simplify the discussion, a particular convention concerning the points of transition between one interval and the next is adopted in this section. Whenever the interval of time under consideration has a greatest lower bound T_{l} (other than 0), it is assumed that T_{l} is not contained in the interval, but whenever the interval has a least upper bound T_{u}, it is assumed that T_{u} is contained in the interval. Hence, for example, it is assumed that the interval where T apC is open but T apD is closed is the half-open interval (T_{1}, T_{2}]. Furthermore, at all points in each such interval (T_{l}, T_{u}], except possibly at T_{u}, it is assumed that each parameter is continuous, and that all its derivatives are well defined and are also continuous. At points such as T_{u}, it is simply stipulated that for each parameter P (which may be a derivative of some other parameter)

P (T_{u}) =^{def} lim_{t→T_{u}^{−}} P (t)

i.e. the value of each parameter at T_{u} is defined as its limit from the left at T_{u}. The successive derivatives of P at t are written as P′(t), P′′(t), etc.

The following equations are each applicable in the circumstances indicated

Always:  LevelA′(t) = −(F lowC(t) + F lowD(t))  (1)
T ankB not full: LevelB′(t) = F lowC(t) + F lowD(t)  (2)
T ankB full:  LevelB′(t) = 0  (3)
T apC closed:  F lowC(t) = 0  (4)
T apC open:  F lowC(t) = K.LevelA(t)  (5)
T apD closed:  F lowD(t) = 0  (6)

T apD open: F lowD(t) = K.LevelA(t)  (7)

In the interval [0, T_{1}] the relevant equations are (1), (2), (4) and (6). Their simultaneous solution is

LevelA(t) = C_{1}
LevelB(t) = C_{2}
F lowC(t) = 0
F lowD(t) = 0

where C_{1} and C_{2} are arbitrary real valued constants. Since it is also known that LevelA(0) = L and LevelB(0) = 0 (because these values have been given as initial conditions), then for t ∈ [0, T_{1}]

\begin{matrix}LevelA(t) = L & (S1) \\ LevelB(t) = 0 & (S2) \\ F lowC(t) = 0 & (S3) \\ F lowD(t) = 0 & (S4) \end{matrix}

At time T_{1}, T apC is opened, so that in the interval (T_{1}, T_{2}] the equations to solve are (1), (2), (5) and (6). Their simultaneous solution is

LevelA(t) = C_{3}.e^{−Kt}
LevelB(t) = C_{4} − C_{3}.e^{−Kt}
F lowC(t) = C_{3}.Ke^{−Kt}
F lowD(t) = 0

where C_{3} and C_{4} are arbitrary real valued constants. In fact, it is implicit in the description of the domain that no ‘sudden’ change in the level of T ankA or of T ankB occurs at T_{1} – i.e. it is known that LevelA(t) and LevelB(t) are both continuous at T_{1}. Hence, with a little algebra, it is easy to see that C_{3} = Le^{KT_{1}} and C_{4} = L. Hence the overall solution for t ∈ (T_{1}, T_{2}] is

\begin{matrix}LevelA(t) = Le^{−K(t−T_{1})} & (S5) \\ LevelB(t) = L − Le^{−K(t−T_{1})} & (S6) \\ F lowC(t) = LKe^{−K(t−T_{1})} & (S7) \\ F lowD(t) = 0 & (S8) \end{matrix}

Notice that this solution forces a discontinuity in LevelA′(t), LevelB′(t) and F lowC(t) at the point T_{1}, and also forces discontinuities in all their derivatives. Merely mechanically limiting the number of discontinuous parameters at this point, without considering the physical realities of the system, could have resulted in trading all these discontinuities for a single discontinuity in LevelA(t), by putting C_{3} = C_{4} = 0. In physical terms, this alternative assignment of values corresponds to all of the water in T ankA instantaneously disappearing at the moment that T apC is opened.

In the interval (T_{2}, T_{3}], both T apC and T apD are open, and the equations to solve are (1), (2), (5) and (7). Their simultaneous solution is

LevelA(t) = C_{5}.e^{−2Kt}
LevelB(t) = C_{6} − C_{5}.e^{−2Kt}
F lowC(t) = C_{5}.Ke^{−2Kt}
F lowD(t) = C_{5}.Ke^{−2Kt}

where again C_{5} and C_{6} are arbitrary real valued constants. Again, it is known that LevelA(t) and LevelB(t) are both continuous at T_{2}. Hence C_{5} = Le^{K(T_{1}+T_{2})} and C_{6} = L. Hence the overall solution for t ∈ (T_{2}, T_{3}] is

\begin{matrix}LevelA(t) = Le^{K(T_{1}+T_{2}−2t)} & (S9) \\ LevelB(t) = L − Le^{K(T_{1}+T_{2}−2t)} & (S10) \\ F lowC(t) = LKe^{K(T_{1}+T_{2}−2t)} & (S11) \\ F lowD(t) = LKe^{K(T_{1}+T_{2}−2t)} & (S12) \end{matrix}

As before, this solution forces discontinuities at the point T_{2}, this time in LevelA′(t), LevelB′(t), F lowC′(t) and F lowD(t) and all their derivatives. In this case there are two other sets of assignments to C_{5} and C_{6} which would have resulted in trade-offs in discontinuities. The assignments C_{5} = 0 and C_{6} = L − Le^{K(T_{1}−T_{2})} would have kept F lowD(t) and its derivatives continuous at T_{2} (as well as maintaining the continuity of LevelB(t)). Alternatively, to keep LevelA′(t), LevelB′(t) and F lowC′(t) continuous at T_{2} the assignment C_{5} = \frac{L}{2}e^{K(T_{1}+T_{2})} and C_{6} = L(1+\frac{1}{2}e^{K(T_{1}+T_{2})}+e^{K(T_{1}−T_{2})}) could have been made. However, both of these alternative sets of assignments would have resulted in discontinuities in LevelA(t) – i.e. ‘sudden disappearances’ of water from T ankA, as well as a discontinuity in F lowC(t).

The specific value for T_{3} can now also be computed, using (S10) and the knowledge that LevelB(T_{3}) = H_{B}. This gives

T_{3} = \frac{T_{1}+T_{2}}{2} + \frac{1}{2K} ln(\frac{L}{L−H_{B}})

Finally, in the region (T_{3}, +∞), T ankB is overflowing, and the equations to solve are (1), (3), (5) and (7). Their simultaneous solution is

LevelA(t) = C_{7}.e^{−2Kt}
LevelB(t) = C_{8}
F lowC(t) = C_{7}.Ke^{−2Kt}
F lowD(t) = C_{7}.Ke^{−2Kt}

where again C_{7} and C_{8} are arbitrary real valued constants. Again, it is known that LevelA(t) and LevelB(t) are both continuous at T_{3}. Hence C_{7} = Le^{K(T_{1}+T_{2})} (= C_{5}) and C_{8} = H_{B}. Hence the overall solution for t ∈ (T_{3}, +∞) is

\begin{matrix}LevelA(t) = Le^{K(T_{1}+T_{2}−2t)} & (S13) \\ LevelB(t) = H_{B} & (S14) \\ F lowC(t) = LKe^{K(T_{1}+T_{2}−2t)} & (S15) \\ F lowD(t) = LKe^{K(T_{1}+T_{2}−2t)} & (S16) \end{matrix}

At T_{3}, no trade-offs in discontinuities are possible. The inclusion of equation (3) in the model for this last region guarantees a discontinuity in LevelB′(t) and all its derivatives. Since (S13), (S15) and (S16) are identical to (S9), (S11) and (S12) respectively, all other parameters are continuous at this point.

For the sake of discussion, expressions such as (1) – (7) will be referred to here as equality constraints, and expressions such as (S1) – (S16) as trajectories. (Trajectories are thus a special case of equality constraint which mention only one parameter, and no derivatives of parameters.)

There are several points to note about mathematical models such as the one above. First, notice that there is often a natural association between individual equality constraints such as (1) – (7) and individual or ‘local’ properties of the domain. For example, (5) must hold if and only if T apC is open. Second, for other more complex domains, perhaps involving non-linear relationships between parameters and derivatives, it might not be easy to formulate explicit trajectories for each parameter – it may be necessary for example to employ numerical or approximation methods to provide a simultaneous solution to a given set of equality constraints. Third, notice that the equality constraints such as (1), (2), etc. persist through the transition points T_{1}, T_{2} and T_{3} to a greater degree than the trajectories (S1), (S2), etc. For example, expression (1) is relevant throughout all four intervals, whereas the expressions (S1), (S5) and (S9) are all different.

For these reasons, a suitably extended Situation Calculus will be used in this paper to describe transitions from one set of equality constraints such as {(1), (2), (4), (6)} to another such as {(1), (2), (5), (6)}, and mathematics will be relied upon to transform a given set of equality constraints such as {(1), (2), (4), (6)} into a set of trajectories such as {(S1), (S2), (S3), (S4)}. As has been seen, the mathematics sometimes generates arbitrary constant symbols in trajectories, such as C_{1}, …, C_{8}. The extended Situation Calculus must therefore enable the inference of the specific numerical values of these constants. Such inferences will be based in part on the general principle of minimising discontinuities at points of transition, and in part on domain-specific information, such as the ‘commonsense’ knowledge that opening a tap does not cause a body of water to instantaneously disappear.

3 A Situation Calculus for Piecewise Continuous Domains

3.1 The Language

Following the usual practice, the Situation Calculus presented here will be written in a sorted predicate calculus, with sorts A, S and F, for actions, situations and fluents respectively, as well as a sort X for ‘domain objects’ (blocks, water-tanks, or whatever). It will also include a sort T of time-points, a sort P of parameters, and a sort R of values which parameters can take at specific time-points. In fact, models will be considered only in which terms of sort R are interpreted as real numbers, and terms of sort T are interpreted as non-negative reals. The sorting of the logic is summarised in Figure 2 below.

NAME OF SORT  SYMBOL VARIABLES
Actions  A  a, a_{1}, a_{2}, …
Situations  S  s, s_{1}, s_{2}, …
Fluents  F  f, f_{1}, f_{2}, …
Times  T  t, t_{1}, t_{2}, …
Parameters  P  p, p_{1}, p_{2}, …
Reals  R  r, r_{1}, r_{2}, …
Domain objects  X  x, x_{1}, x_{2}, …
F-preds (predicate sort)  H = 2^{F} h, h_{1}, h_{2}, …
Valuations (function sort) V : P ↦ R v, v_{1}, v_{2}, …

Figure 2

Figure 2 also includes the second order sorts H (f-preds) and V (valuations). F-preds, which are predicates ranging over fluents, are included so that the second-order version of Baker’s solution to the frame problem [1] can be incorporated in the framework. They help in establishing a large enough space of situations in each model, so that the solution to the frame problem cannot be compromised by failing to take into account a particular hypothetical combination of fluents (see [1] for further explanation).

Valuations, which are functions from P to R, are included here for an analogous reason. As stated in the introduction, and following the approach in [8], in the axiomatization given below a function State will be used to associate particular (half-open) intervals along the time line with a single situation. But in domains involving continuous change, the effects of a particular action may not depend only on which fluents hold throughout such intervals of time. They may also depend on the instantaneous values of the (continuously varying) parameters at the particular instants of time at which the action occurs. Therefore, to fully describe action preconditions it is sometimes necessary to be able to refer to specific parameters’ values. Here (as in [1]) situations may be thought of as sets of fluents. Similarly, valuations are in effect sets of parameter values. Since action preconditions may be expressed partly in terms of parameter values, the Result function is extended here so as to range over valuations as well as over actions and situations. For example, the fact that turning a car ignition key starts the engine if the battery is connected and has sufficient voltage might be axiomatized using the fluents Connected and EngineOn, the parameter Voltage and the action T urn, as

Holds(EngineOn, Result(T urn, v, s)) ←
[Holds(Connected, s) ∧ v(Voltage) > 12]

The use of universally quantified variables of sort V effectively establishes a large enough space of sets of parameter values, irrespective of whether the values in

FUNCTION  SORT
Sit  2^{F} ↦ S
Result  A × V × S ↦ S
State  T ↦ S
Function  P × T ↦ R
Values  T ↦ V
δ  P ↦ P

PREDICATE  SORT
Holds  F × S
Ab  A × F × V × S
Absit  2^{F}
Happens  A × T
Performed  A × T
T riggers  V × S × A
Continuous  P × T
Differentiable  P × T
LeftContinuous  P × T
RightLimit  P × T × R
Breaks  A × P × V × S
InstantEffect A × P × V × S × R
<  R × R
<  T × T

CONSTANT  SORT
S0  S
all real numbers  R
0 and all +ve real numbers  T

Figure 3 a particular such set ever simultaneously occur at any point in time. This becomes especially important when attempting to describe all the hypothetical instantaneous circumstances under which an action (such as the overflow action in the example of the previous section) could be triggered. The formalisation below will incorporate a default assumption that a given hypothetical circumstance does not trigger a given action. To avoid problems analogous to the Yale Shooting Problem, it is therefore important not to index triggering information with a temporal argument.

The domain-independent predicate, function and constant symbols of the formalism are listed in Figure 3. The equality predicate is also included in the language, as are the standard arithmetical function symbols +, ×, etc. It is assumed that these are interpreted in the standard way.

3.2 Domain-independent Axioms

The following six domain-independent axioms, which do not directly concern continuous change, are included in every theory. All variables are assumed to be universally quantified with maximum scope unless otherwise stated. Axiom (F1) is a frame axiom. Note that, for the reasons described above, both the function Result and the predicate Ab range over valuations as well as situations. As usual, Ab is minimised to provide a non-monotonic solution to the frame problem. Axiom (ES1) is Baker’s second order ‘existence of situations’ axiom (the second conjunct of which simply expresses the uniqueness-of-names property for Sit terms). Absit is minimised at a higher priority than Ab so as to establish a large enough space of situations in each minimal model (see [1] for further explanation).

¬Ab(a, f, v, s) → [Holds(f, Result(a, v, s)) ↔ Holds(f, s)]  (F1)

\begin{matrix}[¬Absit(h) → [Holds(f, Sit(h)) ↔ h(f)]] ∧ & (ES1) \\ [Sit(h_{1}) = Sit(h_{2}) → (h_{1}(f) ↔ h_{2}(f))] \end{matrix}

State(t) = S0 ← ¬∃a_{1}, t_{1}[Happens(a_{1}, t_{1}) ∧ t_{1} < t]  (N1)
State(t) = Result(a_{1}, Values(t_{1}), State(t_{1})) ←  (N2)
[Happens(a_{1}, t_{1}) ∧ t_{1} < t ∧
¬∃a_{2}, t_{2}[Happens(a_{2}, t_{2}) ∧ t_{1} < t_{2} ∧ t_{2} < t]]
[Happens(a_{1}, t) ∧ Happens(a_{2}, t)] → a_{1} = a_{2}  (N3)
Happens(a, t) ↔ [Performed(a, t) ∨ T riggers(Values(t), State(t), a)] (N4)

Axioms (N1)–(N4) concern the narrative aspect of each theory. Axioms (N1) and (N2) associate half-open intervals along the time line to situations in a straightforward way. (N2) is shorter than its counterpart in [8], because the simplifying assumption is made here that two or more actions do not occur simultaneously – this assumption is expressed in Axiom (N3). The issue of concurrency is orthogonal to the main concerns of this paper. To deal with concurrency and the combined effects of simultaneous actions, the axioms can be extended in the manner described in [8].

Axiom (N4) provides a definition of Happens in terms of the predicates Performed and T riggers. It expresses that an action A happens at a particular time T either if it is performed at T (implicitly by an external agent), or if it is triggered by the instantaneous set of circumstances at T. This set of circumstances is captured partly by the situation term State(T), which enables indirect reference to the set of fluents which hold at T, and partly by the valuation term Values(T), which represents the instantaneous values of all parameters at T. Both the predicates Performed and T riggers are minimised (this is discussed in more detail below).

To deal with continuous change, two extra function symbols, Function and δ, have been included in the language (see Figure 3). Mathematically, parameters can be regarded as functions of time. To reflect this, Function takes a parameter and a time point and returns a real number. Standard axiomatizations of the usual mathematical definitions of continuity, differentiability, left-continuity and right-limit, in terms of the predicates Continuous, Differentiable, LeftContinuous and RightLimit, are given in the appendix, as well as an appropriate axiom constraining the operator \frac{∂}{∂t}. Given a parameter P, the term δ(P) names the ‘derivative of P ’. Hence the following two axioms are included in every theory.

Values(t)(p) = Function(p, t)  (C1)
Differentiable(p, t) → Function(δ(p), t) = \frac{∂}{∂t}Function(p, t)  (C2)

To respect the convention regarding parameter values at end points of half-open intervals of time, described at the beginning of Section 2, it is sufficient to axiomatize the mathematical constraint that, at every time-point, the function associated with each parameter is left-hand continuous:

LeftContinuous(p, t)  (C3)

To describe instantaneous changes in the values of parameters at times when actions occur, and discontinuities in their corresponding functions of time, the predicates InstantEffect and Breaks are introduced. Both predicates are minimised. InstantEffect(A, P, V, S, R) should be read as ‘in the circumstance represented by the valuation V and situation S, the action A causes the parameter P to instantaneously take on the value R’. More precisely, Axiom (C7) below states that if A also happens at time T, and V and S describe the circumstances at T, then R is the value of the right-hand limit of P at T. (In fact, InstantEffect is not used in the domain specific axioms of the next section, describing the water tanks example. But it is useful for domains such as Sandewall’s ‘bouncing ball’ scenario [12], where it is necessary to express that a ‘bounce’ action instantaneously reverses the horizontal velocity of a moving ball.)

Breaks(A, P, V, S) can be read as ‘in the circumstance represented by the valuation V and situation S, the action A can potentially cause a discontinuity in parameter P ’. This predicate is somewhat analogous to the predicate Ab, but with its second argument of sort P rather than F. The following four domainindependent axioms make direct use of InstantEffect and Breaks. Axioms (C4) and (C5) can be regarded as kinds of ‘frame axioms’ for parameters.

\begin{matrix}¬[Happens(a, t) ∧ Breaks(a, p, Values(t), State(t))] → & (C4) \\ Continuous(p, t) \end{matrix}

\begin{matrix}¬[Happens(a, t) ∧ Breaks(a, δ(p), Values(t), State(t))] → & (C5) \\ Differentiable(p, t) \end{matrix}

Breaks(a, p, v, s) → Breaks(a, δ(p), v, s)  (C6)
InstantEffect(a, p, v, s, r) → Breaks(a, p, v, s)  (C7)

\begin{matrix}[InstantEffect(a, p, Values(t), State(t), r) ∧ Happens(a, t)] → & (C8) \\ RightLimit(p, t, r) \end{matrix}

Finally, an axiom is needed expressing the condition of piecewise continuity:

\begin{matrix}∃r∀a_{1},t_{1},a_{2},t_{2}[[Happens(a_{1}, t_{1}) ∧ Happens(a_{2}, t_{2}) ∧ t_{1} < t_{2}] → & (C9) \\ 0 < r ≤ (t_{2} − t_{1})] \end{matrix}

Circumscription will be used here to model the various modes of default reasoning associated with narrative domains involving continuous change. The predicates Absit, Ab, Performed, T riggers, InstantEffect and Breaks all need to be minimised. The exact circumscription policy and its effects will be discussed in the next section, following an axiomatization of the water tanks example.

4 An Axiomatization of the Water Tanks Example

The following constant symbols will be used to axiomatize the water tanks example of Section 2. T urnOnC, T urnOnD and StartSpillB of sort A, OpenC, OpenD and OverflowingB of sort F, and LevelA, LevelB, F lowC and F lowD of sort P. Uniqueness-of-names axioms are assumed which state that the constants of each sort are distinct, and that each ground term of sort P constructed with the function δ is distinct from any other. As in Section 2, the meta-variables T_{1} and T_{2} of sort T and L, H_{B} and K of sort R are also used in the axiomatization below – these should simply be thought of as real number constants.

Given the domain-independent axioms of the previous section, the example can now be described with 29 extra domain-dependent axioms. For readability they are grouped below into ‘action rules’, ‘instantaneous effect rules’, ‘initial situation facts’, ‘occurrence facts’, ‘triggering rules’, ‘initial value facts’ and ‘equality constraint rules’. In axioms (T19)–(T29) below, abbreviations have been used for terms of sort R constructed with the function symbols Function and δ. For example, the terms Function(F lowC, 0) and Function(δ(LevelA), t) have been abbreviated to ‘F lowC(0)’ and ‘LevelA′(t)’ respectively.

Action rules:

\begin{matrix}Holds(OpenC, Result(T urnOnC, v, s)) & (T1) \\ Holds(OpenD, Result(T urnOnD, v, s)) & (T2) \\ Holds(OverflowingB, Result(StartSpillB, v, s)) & (T3) \end{matrix}

Instantaneous effect rules:

Breaks(T urnOnC, F lowC, v, s)  (T4)
Breaks(T urnOnC, δ(LevelA), v, s)  (T5)
Breaks(T urnOnC, δ(LevelB), v, s)  (T6)
Breaks(T urnOnC, δ(F lowD), v, s)  (T7)
Breaks(T urnOnD, F lowD, v, s)  (T8)
Breaks(T urnOnD, δ(LevelA), v, s)  (T9)
Breaks(T urnOnD, δ(LevelB), v, s)  (T10)
Breaks(T urnOnD, δ(F lowC), v, s)  (T11)
Breaks(StartSpillB, δ(LevelB), v, s)  (T12)

Initial situation facts:

\begin{matrix}¬Holds(OpenC, S0) & (T13) \\ ¬Holds(OpenD, S0) & (T14) \\ ¬Holds(OverflowingB, S0) & (T15) \end{matrix}

Occurrence facts:

\begin{matrix}Performed(T urnOnC, T_{1}) & (T16) \\ Performed(T urnOnD, T_{2}) & (T17) \end{matrix}

Triggering rules:

\begin{matrix}[v(LevelB) = H_{B} ∧ v(δ(LevelB)) > 0] & (T18) \\ → T riggers(v, s, StartSpillB) \end{matrix}

Initial value facts:

\begin{matrix}LevelA(0) = L & (T19) \\ LevelB(0) = 0 & (T20) \\ F lowC(0) = 0 & (T21) \\ F lowD(0) = 0 & (T22) \end{matrix}

Equality constraint rules:

LevelA′(t) = −(F lowC(t) + F lowD(t))  (T23)
Holds(OverflowingB, State(t)) → LevelB′(t) = 0  (T24)
¬Holds(OverflowingB, State(t))  (T25)
→ LevelB′(t) = F lowC(t) + F lowD(t)
Holds(OpenC, State(t)) → F lowC(t) = K.LevelA(t)  (T26)
¬Holds(OpenC, State(t)) → F lowC(t) = 0  (T27)
Holds(OpenD, State(t)) → F lowD(t) = K.LevelA(t)  (T28)
¬Holds(OpenD, State(t)) → F lowD(t) = 0  (T29)

The aim in considering this example is to construct a representation, in a principled way, from which the trajectories (S1)–(S16) can be inferred (in the relevant time intervals). Let Π_{wt} be the theory consisting of the domain independent axioms (F1), (ES1), (N1)–(N4) and (C1)–(C9), together with the domain dependent axioms (T1)–(T29) and uniqueness-of-names axioms for actions, fluents and parameters. By itself, Π_{wt} does not entail these trajectories. As discussed above, various modes of default reasoning also need to be represented – namely the assumptions that by default a given action does not affect a given fluent, that by default a given action does not occur at a given time point, that by default a given set of parameter values does not trigger a given action, and that by default a given action occurrence does not result in a discontinuity for a given parameter. Prioritized and parallel circumscription will be used here to model these assumptions (see [6] for a full explanation of the notation used below). The complete representation of the domain is

CIRC[Π_{wt} ; Absit > Ab, Performed, T riggers, InstantEffect, Breaks ;

Holds, Sit, Result, S0, Happens, State, Values, Function, δ]

This expression will be referred to as CIRC_{cc}[Π_{wt}]. Much further investigation needs to be done to ascertain the extent to which CIRC_{cc} is an appropriate policy in general for domains involving continuous change. It could be, for example, that for other domains extra priorities have to be introduced. However, it is not hard to show that it yields the correct results in the case of the water tanks scenario, so that for example

CIRC_{cc}[Π_{wt}] ⊧ Happens(StartSpillB, \frac{T_{1}+T_{2}}{2} + \frac{1}{2K} ln(\frac{L}{L−H_{B}}))

The full proof of this and the fact that CIRC_{cc}[Π_{wt}] entails the trajectories (S1)-(S16) is somewhat tedious, but the following is an outline of its main steps.

Given any model M of Π_{wt}, a corresponding model M′ can be constructed with the same universe of discourse, which contains the same interpretations for all ground action, fluent and parameter terms, and which is also a model for Axioms (circ1)–(circ6) below. (M′ is constructed using the trajectories (S1)–(S16) to define the interpretations of F unction and V alues, and equating S0 and all situation terms constructed with the Result function to an appropriate Sit term. State(T) is equated with S0 for T ≤ T_{1}, with Result(T urnOnC, V alues(T_{1}), S0) for T_{1} < T ≤ T_{2}, etc.)

¬Absit(h)  (circ1)
¬InstantEffect(a, p, v, s, r)  (circ2)
Ab(a, f, v, s) ↔  (circ3)

[[a = T urnOnC ∧ ¬Holds(OpenC, s)] ∨ [a = T urnOnD ∧ ¬Holds(OpenD, s)] ∨ [a = StartspillB ∧ ¬Holds(OverflowingB, s)]]

Performed(a, t) ↔  (circ4)

[[a = T urnOnC ∧ t = T_{1}] ∨ [a = T urnOnD ∧ t = T_{2}]]

\begin{matrix}T riggers(v, s, a) ↔ & (circ5) \\ [a = StartSpillB ∧ v(LevelB) = H_{B} ∧ v(δ(LevelB)) > 0] \end{matrix}

Breaks(a, p, v, s) ↔  (circ6)

[∃p_{1}[p=δ(p_{1}) ∧ Breaks(a, p_{1}, v, s)] ∨ [a=T urnOnC ∧ p=F lowC] ∨ [a=T urnOnC ∧ p=δ(LevelA)] ∨ [a=T urnOnC ∧ p=δ(LevelB)] ∨ [a=T urnOnC ∧ p=δ(F lowD)] ∨ [a=T urnOnD ∧ p=F lowD] ∨ [a=T urnOnD ∧ p=δ(LevelA)] ∨ [a=T urnOnD ∧ p=δ(LevelB)] ∨ [a=T urnOnD ∧ p=δ(F lowC)] ∨ [a=StartspillB ∧ p=δ(LevelB)]]

It is clear that, since the ‘if’ halves of (circ3)–(circ6) follow from Π_{wt}, the interpretations in M′ of all the predicates to be minimised must each be contained in their corresponding interpretations in M. In other words, since M is an arbitrary model of Π_{wt}, (circ1)–(circ6) are entailed by CIRC_{cc}[Π_{wt}]. It is therefore sufficient to show that the trajectories (S1)–(S16) follow from Π_{wt}^{+} = Π_{wt} ∪ {(circ1), …, (circ6)}.

Axiom (C9), expressing the property of piecewise continuity, plays a crucial role in the derivation of (S1)–(S16) from Π_{wt}^{+}. For example, to derive (S1)–(S4) in the region [0, T_{1}], axioms (N4), (T20), (circ4) and (circ5) are first used to establish that no action occurs at time 0. Axiom (C9) ensures that there can only be a finite number of time points in [0, T_{1}] at which actions occur, and hence that (by (circ4)) there exists a least such time point. Finally, using (N1), (N4), (T13)–(T15), (T23), (T25), (T27), (T29) and (circ5), it is possible to show that if this least time point were before T_{1} this would contradict either the continuity condition of axiom (C4), or the left-hand continuity condition of axiom (C8).

5 Discussion

The formalism developed in this paper is in some respects similar to the extended Situation Calculus of Pinto [9], in that in both approaches it is possible to describe mathematical constraints between parameters, as well as their explicit trajectories. The main advantage of the approach described here over Pinto’s is that it deals with what Pinto describes as ‘inter-state constraints’, by introducing axioms and default reasoning mechanisms involving the predicates InstantEffect and Breaks. It also avoids the need to ‘name’ many different types of mathematical function, and encode various properties of these names, and avoids the need to identify a special class of ‘natural’ actions as the only type of action that can be triggered.

There is an important advantage of both the axiomatization presented here and Pinto’s over approaches which depend on encapsulating the behaviour of at least one parameter inside an explicit T rajectory predicate (or similar), e.g. [14], [16], [15]. This is that information about a parameter’s behaviour, in the form of various mathematical constraints, may be distributed in a natural way throughout the domain-dependent part of the theory. For example, in the water tanks scenario the mathematical knowledge of the domain is expressed in axioms (T19)–(T29); it was not necessary to solve the relevant sets of simultaneous differential equations before axiomatizing the domain. Hence these formalisms may be used together with various mathematical techniques or modes of mathematical reasoning as and where necessary (Pinto assumes the availability of an ‘oracle’ to deal with mathematical aspects of his theories). For example, once the Situation Calculus has been used to establish that a collection of mathematical constraints holds during a particular interval, numerical methods may be used to solve these constraints simultaneously.

In this paper, attention has been restricted to domains in which the set of time points at which actions occur is sparse, i.e. where every finite interval of time contains only a finite number of such points. Further work needs to be done in investigating the consequences of lifting this restriction. Davis [2] provides an interesting general discussion of this and related issues.

As regards default reasoning about discontinuities, the water tanks example shows that, on its own, Sandewall’s default mechanism [12] for inferring continuity of parameters across breakpoints (which builds on the idea of chronological minimisation) is not always sufficient. The same point is made by Rayner in [10]. In the water tanks example, a choice has to be made at particular time points between discontinuities in some parameters or discontinuities in others. The introduction and minimisation here of the predicates Breaks and InstantEffect allows such choices to be made based partly on domain-specific information. The inclusion of these predicates also facilitates the construction of domain descriptions which are, in McCarthy’s words, “elaboration tolerant”. For example, the extra information that a “Scoop” action (i.e. the action of scooping a container-full of water from T ankA) occurs at time T_{4} (where T_{4} is some timepoint other than T_{1}, T_{2} or T_{3}) and instantaneously decreases LevelA by R_{s} can be described by the addition of the domain-dependent axioms:

Performed(Scoop, T_{4})

\begin{matrix}InstantEffect(Scoop, LevelA, v, s, r) ← \\ [v(LevelA)>R_{s} ∧ r =v(LevelA)−R_{s}] \end{matrix}

InstantEffect(Scoop, LevelA, v, s, 0) ← v(LevelA)≤R_{s}

\begin{matrix}Breaks(Scoop, F lowC, v, s) ← \\ [Holds(OpenC, s) ∧ v(LevelA)>0] \end{matrix}

\begin{matrix}Breaks(Scoop, F lowD, v, s) ← \\ [Holds(OpenD, s) ∧ v(LevelA)>0] \end{matrix}

Breaks(Scoop, δ(LevelB), v, s) ←

[¬Holds(OverflowingB, s) ∧ v(LevelA)>0
∧ [Holds(OpenC, s) ∨ Holds(OpenD, s)]]

Such elaboration would not be possible (without altering the existing axioms) if axioms (analogous to those in Sandewall’s bouncing ball example) such as

∀t.Continuous(LevelA, t)

had been included in the domain description, or if a monotonic framework were being used to describe the domain.

As Sandewall points out [12], ‘qualitative statements’ are as much a part of mathematics as ‘quantitative statements’. Ordinary mathematical language together with standard logic is rich enough to express incomplete knowledge about the functions associated with particular parameters, perhaps using mathematical inequalities or existentially quantified numerical variables. For example, within the framework of this paper, domains such as the water tanks scenario could be (partially) described using axioms such as

∃r∀t[Holds(OpenC, State(t)) →
F lowC(t) = r.LevelA′(t)]

or

Holds(OpenC, State(t)) →
[LevelA′(t)<0 ↔ F lowC′(t)<0]

The second of these two axioms simply expresses that, whenever T apC is open, the flow through it increases monotonically with the depth of the water in T ankA. As has been pointed out in the literature on Qualitative Reasoning (e.g. [5], [3]), it is important to be able to express and reason with such information when describing “commonsense” domains. In principle, axioms such as the two above are perfectly compatible with the domain independent theory of the previous sections. However, further investigation will be necessary to ascertain the effects of circumscrption policies such as CIRC_{cc}, or equivalent default reasoning techniques, on such sentences. Were it possible to prove an equivalence between a class of such axiomatizations and a class of Q.R. models, it would obviously also be possible to utilise the corresponding Q.R. simulation techniques to compute entailments for this class.

As mentioned in Section 4, further work needs to be done in examining the general properties of the circumscription policy CIRC_{cc}. However, its effect as regards the water tanks example is quite straightforward. The fact that axioms (circ1)–(circ6) are entailed by the circumscribed theory shows that, in this case, the various default assumptions are ‘mutually independent’. Although this will clearly not always be the case, it could be that for a class of domains at least, some kind of ‘separation property’ could be proved (analogous to Theorem 3.1 in [8]), perhaps showing the equivalence of sentences such as CIRC_{cc}[Π_{wt}] to conjunctions of more manageable expressions. It also seems likely that for domains such as Π_{wt}, circumscription could be replaced by some more specialised procedure for generating expressions such as (circ1)–(circ6), which are, in effect, simply a form of closure axiom for each minimised predicate. (circ3), for example, is analogous to a conjunction of Reiter’s successor state axioms [11].

In [4], Gelfond, Lifschitz and Rabinov briefly discuss a somewhat different approach to representing continuous change in the Situation Calculus. Periods of continuous change are represented as actions with a non-zero duration. However, it is unclear how phenomena such as triggered action occurrences would be represented using this type of approach.

Acknowledgements

Many thanks to Ben Kuipers and Eugenia Ternovskaia for helpful comments on earlier drafts of this paper, and to Murray Shanahan for useful discussions on this topic. This research was funded by the U.K. Engineering and Physical Sciences Research Council (EPSRC).

References

[1] Andrew Baker, Nonmonotonic Reasoning in the Framework of the Situation Calculus, Artificial Intelligence 49, Elsevier Science Publishers, page 5, 1991.

[2] Ernest Davis, Infinite Loops in Finite Time: Some Observations, Proceedings KR 92 (3rd International Conference on Principles of Knowledge Representation and Reasoning), Cambridge, Massachusetts, ed.s B. Nebel, C. Rich and W. Swartout, Morgan Kaufmann, 1992.

[3] Ken Forbus, Qualitative Process Theory, in Artifical Intelligence 24, reprinted in Weld and de Kleer (eds.), Readings in Qualitative Reasoning about Physical Systems, Morgan Kaufmann (1990), 1984.

[4] Michael Gelfond, Vladimir Lifschitz and A. Rabinov, What Are the Limitations of the Situation Calculus?, in Essays for Bledsoe, ed. R. Boyer, Kluwer Academic, page 167, 1991.

[5] Ben Kuipers, Qualitative Simulation, in Artifical Intelligence 29, pages 289-338, reprinted in Weld and de Kleer (eds.), Readings in Qualitative Reasoning about Physical Systems, Morgan Kaufmann (1990), 1986.

[6] Vladimir Lifschitz, Circumscription, in Handbook of Logic in Artificial Intelligence, ed.s D. Gabbay, C. Hogger and J.A. Robinson, Oxford University Press, pages 297-352, 1995.

[7] Rob Miller, A Case Study in Reasoning about Actions and Continuous Change, in Proceedings of the 12th European Conference on Artificial Intelligence (ECAI’96), Budapest, Hungary, Pub. John Wiley & Sons, Ltd., 1996.

[8] Rob Miller and Murray Shanahan, Narratives in the Situation Calculus, in Journal of Logic and Computation, Special Issue on Actions and Processes, vol 4 no 5, Oxford University Press, 1994.

[9] Javier Pinto, Temporal Reasoning in the Situation Calculus, PhD. Thesis, University of Toronto, 1994.

[10] Manny Rayner, On the Applicability of Nonmonotonic Logic to Formal Reasoning in Continuous Time, Artificial Intelligence, vol 49, pages 345-360, Elsevier Science Publishers, 1991.

[11] Ray Reiter, The Frame Problem in the Situation Calculus: a Simple Solution (Sometimes) and a Completeness Result for Goal Regression, in Artificial Intelligence and Mathematical Theory of Computation: Papers in Honour of John McCarthy, ed. V. Lifschitz, Academic Press, page 418, 1991.

[12] Erik Sandewall, Combining Logic and Differential Equations for Describing Real World Systems, In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ontario, Canada, May 1989, ed.s R. Brachman, H. Levesque and R. Reiter, pages 412-420, Morgan Kaufman, 1989.

[13] Erik Sandewall, Filter Preferential Entailment for the Logic of Action in Almost Continuous Worlds, In Proceedings of the 1989 International Joint Conference on Artificial Intelligence (IJCAI’89), pages 894-899, 1989.

[14] Murray Shanahan, Representing Continuous Change in the Event Calculus, In Proceedings ECAI’90, pages 598-603, 1990.

[15] Murray Shanahan, A Circumscriptive Calculus of Events, Artificial Intelligence, vol 77 no 2, pages 249-284, Elsevier Science Publishers, 1995.

[16] Kristof Van Belleghem, Marc Deneker and Danny De Schreye, Representing Continuous Change in the Abductive Event Calculus, in proceedings of the 1994 International Conference on Logic Programming, ed. P. Van Hentenrijck, pages 225-240, 1994.

Appendix: Some Mathematical Details

The following axioms provide appropriate definitions of continuity and differentiability. To define derivatives a new function sort is needed, M : P × T ↦ R. Notice that Function is of sort M. The function \frac{∂}{∂t} is of sort M ↦ M. The term \frac{∂}{∂t}Function(p, t) which appears in Axiom (C2) should more properly be written as \frac{∂}{∂t}(Function)(p, t).

Continuous(p, t) ↔  (A1)
∀r∃t_{1}∀t_{2}[[|t − t_{2}| < t_{1} ∧ 0 < r]
→ |Function(p, t) − Function(p, t_{2})| < r]

Differentiable(p, t) ↔  (A2)

∃r∀r_{1}∃t_{1}∀t_{2}[[0 < |t − t_{2}| < t_{1} ∧ 0 < r_{1}] → |(\frac{Function(p,t)−Function(p,t_{2})}{t−t_{2}}) − r| < r_{1}]

[Differentiable(p, t) ∧ \frac{∂}{∂t}(Function)(p, t) = r] →  (A3)

∀r_{1}∃t_{1}∀t_{2}[[0 < |t − t_{2}| < t_{1} ∧ 0 < r_{1}] → |(\frac{Function(p,t)−Function(p,t_{2})}{t−t_{2}}) − r| < r_{1}]

LeftContinuous(p, t) ↔  (A4)

∀r∃t_{1}∀t_{2}[[t_{2} < t ∧ (t − t_{2}) < t_{1} ∧ 0 < r] → |Function(p, t) − Function(p, t_{2})| < r]

RightLimit(p, t, r) ↔  (A5)

∀r_{1}∃t_{1}∀t_{2}[[t < t_{2} ∧ (t_{2} − t) < t_{1} ∧ 0 < r_{1}] → |Function(p, t_{2}) − r| < r_{1}]