A Systematic Approach to reason with time and situations (Preliminary Report)

Chitta Baral Department of Computer Science University of Texas at El Paso El Paso, Texas 79968, U.S.A. chitta@cs.utep.edu

1 Introduction and Motivation

There has been several attempts to formalize reasoning about actions. Most attempt fall into three main categories: situation calculus approach, temporal reasoning approach, and event calculus approach.

The original situation calculus consists of three sorts: fluents, actions and situations. For example, in the description of the Yale Shooting Problem (YSP [5]) we have the statement that ‘shooting causes the turkey to be dead if the gun is loaded’. In this statement ‘shoot’ is an action, ‘dead’ is a fluent, and res(shoot, s) denotes the situation obtained after shooting happens in situation s. In the original situation calculus there is only one situation constant s_{0} representing the initial situation and situation terms are constructed using s_{0} and the the function symbol res of arity two. The original situation calculus assumes actions to be unbreakable in the sense that we can not reason about the effect of a partially executed action, and neither explicitly forbid concurrent actions^{1}, nor it gives them a special status as compound actions as in Lin and Shoham [6], Gelfond, Lifschitz and Rabinov [4], and Baral and Gelfond [2].

It seems to us that the spirit behind the original situation calculus is to reason at a high granularity; without worrying about value of fluents during the execution of an action, the duration of an action, the exact timing of actions that may overlap in time and the resultant interaction, or the exact time of occurance of actions. Most of the assumptions made about situation calculus were motivated by this spirit of reasoning at a high granularity. But even while reasoning at a high granularity, the original situation calculus did not allow reasoning about narratives, or actual occurance of actions. There are several recent attempts [8, 2, 7] (and McCarthy’s recent manuscript) to extend situation calculus to incorporate narratives. The basic idea is to extend the number of situation constants to a set of actual situations and to allow a ordering < between these situations. Here each actual situation can be thought of as a snapsort of the world at a particular time and by s_{1} < s_{2} we mean that the time corresponding to s_{1} is earlier than the time corresponding to s_{2}. Such an extension of the original situation calculus stays within the original spirit. The explicit use of time in Pinto and Reiter [8] and Miller and Shanahan [7] does not. There are some other proposed extensions of situation calculus [4] that do not follow the spirit of reasoning at a high granularity.

1This was pointed out by Mc Carthy in a recent draft. He also points out that Lifschitz and Reiter have axioms that forbid concurrent actions.

Approaches based on temporal reasoning [1] are concerned with a much lower level reasoning about the world. They are concerned with the value of fluent at different instances of time during the execution of an action, duration of actions, exact timing of the actions etc. It is no surprise then that the proponent of temporal reasoning point out that situation calculus can not model them. Our point is that \underline{‘Situation Calculus never intended to model them’.}

On the other hand most temporal reasoning approaches do not discuss ways to incorporate hypothetical reasoning, i.e. reasoning about effect of an action or a sequence of actions. This led to the belief that situation calculus approaches do only hypothetical reasoning (i.e. they do not do reasoning about actual situations) while temporal reasoning approach do only reasoning about actual situations. (i.e. they do not do reasoning about hypothetical situations.)

This may be true about the initial proposals based on both approaches. But the real difference between the two approach is that situation calculus intended to reason at a high granularity while temporal logic based approaches intended to reason at a lower granularity. For example, consider the action of ‘driving to the airport’. Situation calculus is interested in the effect that this action causes the passenger to be at the airport, while a temporal reasoning based approach would be interested in the time it takes to drive to the airport, if an accident occured in the freeway while driving to the airport etc.

Is situation calculus too optimistic then by not worrying about the details? Not, necessarily. If my goal is to be at London next month then I will use situation calculus and make a plan of driving to the El Paso airport, taking a flight from El Paso to Dallas and then a flight from Dallas to London. It is perhaps unnecessary^{2} and time consuming to worry about the details about if there will be an accident in the interstate at this point of time.

On the other hand on the day of my trip, while executing my plan and driving to the airport, if I find the interstate clogged I will go through the detail timings and hopefully make an alternative plan, say of taking a bypass to the airport, or a later flight.

If I do not intend to use two different formalisms for my task my goal then would be to have a formalism which I can use for reasoning at both high and low granularities. The attempt in Miller and Shanahan [7] seems to us as a first step in this direction.

Before we introduce our approach, we would like to point out that event calculus is closer to situation calculus in the spirit that it reasons at a high granularity (even though it has explicit time the time is used only for ordering the occurance of events), but it reasons only about actual occurances. Because of the similar spirit, extensions of event calculus have been suggested that incorporate hypothetical situations, and these extensions are basically equivalent (See Denecker et al in ICLP95) to situation calculus extensions that incorporate actual occurances of actions.

2Under certain circumstances when I absolutely have to be in London at a particular time I might be extra careful and consider all the details, but normally I would worry about the details while executing the plan or when I am close to executing my plan.

Our goal in this paper is to develop a systematic approach where we can reason at high, medium and low granularities. We follow the systematic approach introduced in [3], where they introduce the language A to systematically reason about hypothetical effects of actions. We extend the language A and introduce the languages L_{H}, L_{HM} and L_{HML} that can reason at high and medium, and high, medium and low granularities.

Reasoning at high granularity means staying with the spirit of the original situation calculus. Although we will allow time in our frame work it will be only used for ordering occurances of actions. We will treat overlapping actions as being executed concurrently (similar to concurrent processes in a multiprogramming uniprocessor/multiprocessor environment). And we would only reason about situation times; i.e. time when no action is being executed. While reasoning at high granularity we will not worry about duration of actions or the exact timing of actions.

While reasoning at medium granularity we will consider duration of actions, exact timing of actions, and reason about non-situation times, but will assume that values of fluents do not change continuously with time.

While reasoning at the low granularity we will also consider fluents that may change continuously with time.

In this paper we will consider three languages L_{H}, L_{HM} and L_{HML}. The language L_{H} will reason at high granularity and will only reason about situation times. The language L_{HM} will reason at medium granularity and will reason about both situation times and non-situation times. We then extend L_{HM} and introduce the language L_{HML} to allow fluents whose values may change continuously with time and during the execution of actions.

Before we go on to discuss these languages, in the next section we further describe the difference in reasoning at different granularities.

2 Reasoning at different granularities

At all granularities we allow (rather we do not make any restrictions towards) concurrent and overlapping actions. But we view them differently at different granularities.

While reasoning at the high granularity an action is a compound action and is represented by a set of unit actions. The unit actions in the set are assumed to have taken place (or to take place) concurrently and are supposed to start and stop cotemporaneously. In reality this might not be the case and their might be overlapping.

While reasoning at the low granularity, when we represent an action by a set of basic actions, they must take place concurrently and must start and stop cotemporaneously.

The following example makes it clear how we view occurances of actions at different granularities.

Example 2.1 Consider the following description of occurances of actions where a_{i}’s are actions and t_{i}’s are time constants.

a_{1} begins at t_{1} ends at t_{2}
a_{2} begins at t_{3} ends at t_{5}
a_{3} begins at t_{4} ends at t_{6}
a_{4} begins at t_{7} ends at t_{8}
t_{1} < t_{2} < t_{3} < t_{4} < t_{5} < t < t_{6} < t_{7} < t_{8} < t_{9}

Intuitively, the statement a_{1} begins at t_{1} ends at t_{2} means that action a_{1} began at time t_{1} and ended at time t_{2}.

If we would like to know what is true at time t_{9}, since no action is taking place during that time we can reason at a high granularity and consider the effect of the sequence of actions a_{1}, {a_{2}, a_{3}}, a_{4}. (We then say that t_{9} corresponds to the action sequence a_{1}, {a_{2}, a_{3}}, a_{4}.) Here, even though a_{2} and a_{3} do not occur concurrently we assume that they do and reason accordingly.

But, if we are asked what is true at time t, if we are reasoning at a high granularity we say that t is not a situation-time (A situation-time is a time where no action takes place.) and hence we can not make any conclusion about that time.

But if we reason at the medium granularity then we represent the action sequence corresponding to t to be a_{1}, {a_{2}, a_{3}^{−}}. The ‘-’ in a_{3} is interpreted as a_{3} is not complete at time t.

To reason at the low granularity. we need to consider a more detailed sequence of actions. One such detailed representation is: a_{1}, a_{2} : d_{1}, {a_{2}, a_{3}} : d_{2}, a_{3} : d_{3}

where, a_{i}’s are actions and d_{i}’s are durations, and if an action does not have a corresponding duration then it is assumed that it is executed completely. □

We now precisely define several concepts related to reasoning at high and medium granularities.

Definition 2.1 1. If a ∈ A, then a^{−} denotes partial execution of the unit action a and is referred to as a partial unit action.

2. A unit action overlaps another unit action if there is some time when both are (to be) executed.

3. A unit action a_{1} t-overlaps another unit action a_{2} if a_{1} overlaps a_{2}, or if there exists a unit action a_{3} such that a_{1} overlaps a_{3} and a_{3} t-overlaps a_{2}.

4. An action (compound action) is a set of unit actions and partial unit actions, such that the corresponding unit actions t-overlap each other.

5. If an action has a partial unit action then it is referred to as a partial action, otherwise it is referred to as a complete action.

6. For any action a, c(a) denotes the set of complete unit actions in a.

7. We say an action a is part of another action a′ if (i) ∀a_{i} ∈ a, if a_{i} is an unit action then a_{i} ∈ a′, and (ii) ∀a_{j}^{−} ∈ a, either a_{j} ∈ a′ or a_{j}^{−} ∈ a′.

8. A realistic sequence of action consists of a sequence of complete actions possibly followed by a partial action.

9. Let α = a_{1}, … a_{n}, be a sequence of actions. By α^{1}, α^{1...N−1}, α^{N}, we denote the action a_{1}, the sequence of action a_{1}, … a_{n−1}, and the action a_{n}, respectively. The term α^{−} denotes the sequence a_{1}, … a_{n−1} if a_{n} is partial, otherwise it denotes α.

10. If α = a_{1}, … a_{n}, and β = a_{1}, … a_{m}, with n > m, then by α −β we denote the sequence of actions a_{m+1}, …, a_{n}.

11. Let α and β be realistic sequence of actions. We say β begins α if (i) β^{1...N−1} is a prefix

of α^{1...N−1}, and (ii) β^{N} is a part of (α − β^{1..N−1})^{1}.

□

Example 2.2 The partial action {a_{1}, a_{2}, a_{3}^{−}} is a part of {a_{1}, a_{2}, a_{3}, a_{4}^{−}}.

The realistic sequence of actions a_{1}, a_{2}, {a_{3}, a_{4}^{−}} begins the realistic sequence of actions a_{1}, a_{2}, {a_{3}, a_{4}, a_{5}}, a_{6}, {a_{7}, a_{8}^{−}} □

3 Syntax of L_{H} and L_{HM}

The alphabet of L_{H} and L_{HM} consists of four disjoint nonempty sets of symbols F, A, T and I, called fluents, unit actions, time constants, and time values. Elements of A and T will be denoted by (possibly indexed) letters a and t respectively. We will also assume that T contains two special situations t_{0} and t_{N} called initial and current time. The ‘N’ in t_{N} corresponds to the word ‘Now’. A fluent literal is a fluent possibly preceded by ¬. Fluent

literals will be denoted by (possibly indexed) letters f and p (possibly preceded by ¬). ¬¬f will be equated with f.

There are three kinds of propositions in L_{H} called causal laws, facts, and timing constraints. The langiage L_{HM} extends L_{H} by allowing action-duration rules.

An effect law is an expression of the form

a causes f if p_{1}, …, p_{n}  (1)

where a is an action^{3}, and f, p_{1}, …, p_{n} (n ≥ 0) are fluent literals. p_{1}, …, p_{n} are called preconditions of (1). We will read this law as “f is guaranteed to be true after the execution of action a in any state of the world in which p_{1} … p_{n} are true”.

If n = 0, we write the effect law as  a causes f  (1a)

A time-occurance fact is an expression of the form

a begins at t_{1} ends at t_{2}  (2)

where a is a unit-action, and t_{1} and t_{2} are either time constants or time values. It states that “the action a was observed to have begun at time t_{1} and ended at time t_{2}.

If t_{1} and t_{2} are the same then, we write the time-occurance fact as

a occurs at t_{1} (2a)

A fluent-time fact is an expression of the form

f holds between t_{1} and t_{2}  (3)

where f is a fluent literal and t_{1} and t_{2} are time constants or time values. The intuitive reading of (3) is “f is observed to be true between time t_{1} and t_{2}”.

If t_{1} and t_{2} are the same then, we write the time-occurance fact as

f at time t_{1} (3a)

An action-duration rule is an expression of the form

a has duration t if p_{1}, …, p_{n}  (4)

where a is a unit-action, t is a time value and p_{1}, …, p_{n} (n ≥ 0)are fluent literals. We will read this law as “Execution of action a takes a duration of t time units if a is executed in a state of the world where p_{1} … p_{n} are true”.

If n = 0, we write the action-duration rule as  a has duration t  (4a)

A time-constraint is an expression involving time constants and time values. For example t_{1} < t_{2} and t_{1} − t_{2} > 8 are time constraints. More formally,

Definition 3.1 A time term is defined inductively as follows:

(a) A time constant is a time term.

(b) A time value is a time term.

(c) If t_{1} and t_{2} are time terms then so are t_{1} + t_{2}, t_{1} − t_{2}, and t_{1} ∗ t_{2}.

A time constraint is an expression of the form t_{1} δ t_{2}, where t_{1}, and t_{2} are time terms and δ ∈ {<, >, ≤, ≥, =, ≠}. □

3Intuitively, an singleton set of actions {a_{i}} denotes a unit action while the set of actions {a_{1}, …, a_{n}} where n > 1 denotes a compound action – a set of unit actions which are performed concurrently and which start and stop cotemporaneously. For simplicity we will often identify a unit action name {a_{i}} with a_{i}.

Moreover, we will often refer to a set of action as a compound action or simply an action.

Propositions of the type (1) express general knowledge about effects of actions and hence are referred to as laws.

Propositions of the type (2), (3) and time constraints are called atomic facts or observations. A fact is a propositional combination of atomic facts.

Propositions of the type (4) express general knowledge about durations of unit actions and hence are referred to as action-duration rules.

A domain description of L_{H} is a collection of laws, facts, and time constraints while domain descriptions of L_{HM} also include action-duration rules. We will only consider domain descriptions whose propositions do not contain the time constant t_{N}.

The languages L_{H} and L_{HM} extend the language L_{0}. In L_{0} we do not take into account durations of actions, and do not worry about the exact time. In L_{0}, we only worry about relative order of time constants. Hence, in L_{0}, Propositions of the type (2) have t_{1} = t_{2}, time constraints are only of the form t_{1} < t_{2}, and action-duration rules are absent.

4 Semantics of L_{H} and L_{HM}

In this section we introduce a semantics of domain descriptions of L_{H} and L_{HM}. The semantics is defined in terms of models. The model of a domain description consists of four parts:

(i) a partial function Ψ from sequences of actions to states (where a state is a set of fluent names), (ii) a mapping H from action tokens to a pair of time values, (iii) a mapping Σ from time constants and time values to sequence of actions, and (iv) a mapping V from time constants to time values.

We start with defining causal models of D and proceed by explaining when effect laws are true in these models.

4.1 Causal Models

A state is a set of fluent names. A causal interpretation is a partial function Ψ from sequences of actions to states such that:

(1) Empty sequence [ ] belongs to the domain of Ψ and (2) Ψ is prefix-closed^{4}.

Ψ([ ]) is called the initial state of Ψ. The partial function Ψ serves as interpretations of the laws of D. If α belongs to the domain of Ψ we say that α is possible in the initial state of Ψ.

Given a fluent f and a state σ, we say that f holds in σ (f is true in σ) if f ∈ σ; ¬f holds in σ (f is false in σ) if f ∉ σ. The truth of a propositional formula C with respect to σ is defined as usual.

4By prefix closed we mean that for any sequence of actions α and action a, if α ∘ a is in the domain of Ψ then so is α. (Recall that ∘ denotes concatenation, and α ∘ a means the sequence of actions where a follows α ).

To better understand the role Ψ plays in interpreting domain descriptions let us first use it to define models of descriptions consisting entirely of effect laws. To this goal we will attempt to carefully define effects of actions as determined by such a description D and our informal assumptions (a)-(e).

A fluent f is an immediate effect of (executing) a in σ if there is an effect law “a causes f if p_{1}, …, p_{n}” in D whose preconditions hold in σ.

For unit actions these are the only effects possible. For compound actions effects may also be determined by the assumption which says that compound actions may inherit effects of their sub-actions.

Definition 4.1 A fluent f is an inherited effect of (executing) a in σ if there is b ⊂ a such that

(a) f is an immediate effect of b in σ.

(b) There is no action c such that b ⊂ c ⊆ a and ¬f is an immediate effect of c in σ.

□

Definition 4.2 f is an effect of (executing) a in σ if either f is an immediate effect of (executing) a in σ or f is an inherited effect of (executing) a in σ. □

Let

E_{a}^{+}(σ) = {f : f is an effect of a in σ}, E_{a}^{−}(σ) = {f : ¬f is an effect of a in σ} and

Res(a, σ) = σ ∪ E_{a}^{+}(σ) \ E_{a}^{−}(σ).

The following definition captures the meaning of effect laws of D.

Definition 4.3 A causal interpretation Ψ is an h-causal model of D (i.e. satisfies at a high granularity effect laws of D) if for any realistic sequence α ∘ a of actions from the language of D

Ψ(α ∘ a) = Ψ(α) ∪ E_{a}^{+}(Ψ(α)) \ E_{a}^{+}(Ψ(α))

if E_{a}^{+}(Ψ(α)) ∩ E_{a}^{−}(Ψ(α)) = ∅ and a is a complete action

and undefined otherwise. □

Definition 4.4 A causal interpretation Ψ is an m-causal model of D (i.e. satisfies at a medium granularity effect laws of D) if for any realistic sequence α ∘ a of actions from the language of D

Ψ(α) ∪ E_{c(a)}^{+}(Ψ(α)) \ E_{a}^{−}(Ψ(α)) ⊆ Ψ(α ∘ a)

and (F \ Ψ(α)) ∪ E_{c(a)}^{−}(Ψ(α)) \ E_{a}^{+}(Ψ(α)) ∩ Ψ(α ∘ a) = ∅

if E_{c(a)}^{+}(Ψ(α)) ∩ E_{c(a)}^{−}(Ψ(α)) = ∅

and undefined otherwise. □

Example 4.1 Suppose a = {a_{1}, a_{2}, a_{3}^{−}}.

□

4.2 Interpreting Time constants, Time values and Occurances of Actions

Let D be an arbitrary domain description and let a causal interpretation Ψ be a (h or m) causal model of D. To interpret the other propositions of D we need to define the meaning of time constants and time values. To do that we now need to consider

(i) the mapping V from time constants to time values, (ii) the mapping H from unit action tokens to pair of time values (iii) the mapping Σ from T ∪ I to sequences of actions from the language of D.

Intuitively, the mapping V assigns a value to the time constants. But for convenience we consider it to be a mapping from T ∪ I to I, and for elements from I it maps to the element itself. Such a V is referred to as a time valuation.

Intuitively, H(a) = (t, t′) means unit action a begins at time t and ends at time t′. Hence we require that we only consider mappings where for all a, if H(a) = (t_{a}, t′_{a}), then t_{a} ≤ t′_{a}.

A time t is said to be a situation-time (w.r.t. H) if there does not exist a with H(a) = (t_{1}, t_{2}) such that t_{1} ≤ t < t_{2}, other wise it is referred to as a non-situation time or an intermediate time. Intuitively, situation-time refers to a time when the world is static and no action is taking place.

Intuitively, for a time^{5} t, if t is not a situation time then Σ(t) is the sequence of actions that has already taken place before t. If t is a situation time, then Σ(t) is the sequence of actions that has already taken place before t, followed by the set of partial actions taking place during t.

A mapping Σ from T ∪ I to sequences of actions will be called a time assignment of T if it satisfies the following properties:

1. Σ(t_{0}) = Σ(0) = [ ]

2. V(t_{i}) < V(t_{j}) implies Σ(t_{i}) begins Σ(t_{j}).

3. ∀t ∈ T , Σ(t_{i}) begins Σ(t_{N}).

4. An action (possibly compound) a is an element of the sequence Σ(t_{N}) if (a) all element of a t-overlap each other, and

(b) No other action overlaps an action in a.

5. If t is a situation time then the last action in the sequence Σ(t) is not a partial action.

6. If t is not a situation time then (a) for all completed actions a in (Σ(t))^{N}, if H(a) = (t_{1}, t_{2}), then V(t_{2}) < V(t),

(b) for all the other actions a^{−} in (Σ(t))^{N}, H(a) = (t_{1}, t_{2}) and V(t_{1}) ≤ V(t) < V(t_{2}), and (c) there is no other action a with H(a) = (t_{1}, t_{2}) that overlaps an action in (Σ(t))^{N} such

that V(t_{1}) < V(t).

Definition 4.5 An interpretation M of L_{H} or L_{HM} is a four-tuple (Ψ, H, Σ, V), where Ψ is a (h or m)-causal model of D, H is a mapping from actions to time value pairs, Σ is a time assignment of T ∪ I, Σ(t_{N}) belongs to the domain of Ψ, and V is a time valuation. □

5By time we mean a time constant or a time value.

Σ(t_{N}) will be called the actual path of M and for simplicity will often be denoted by Σ_{N}. Now we can define truth of facts of D w.r.t. an interpretation M. Facts which are not true in M will be called false in M. Definition 4.6 For any interpretation M = (Ψ, H, Σ, V). (1a) (f holds between t_{1} and t_{2}) is true (at the high granularity) in M (or h-satisfied by M) if V(t_{1}) ≤ V(t_{2}) and for all t, t_{1} ≤ t ≤ t_{2}, if t is a situation time then f is true in Ψ(Σ(t)). (1b) (f holds between t_{1} and t_{2}) is true (at the medium granularity) in M (or m-satisfied by M) if V(t_{1}) ≤ V(t_{2}) and for all t, t_{1} ≤ t ≤ t_{2}, f is true in Ψ(Σ(t)).

(2) (a begins at t ends at t′) is true in M if H(a) = (t, t′) and Σ(t)^{−} ∘ {a} begins the actual path of M.

(3) a has duration d if p_{1}, …, p_{n} is true in M if H(a) = (t, t′) implies if p_{1}, …, p_{n} are true in Ψ(Σ(t)^{−}) then V(t′) − V(t) = d.

(4) A time constraint fact t_{1}δ t_{2}, where δ ∈ {<, >, =, ≤, ≥, ≠} is true in M if t_{1}δ t_{2} evaluates to true (in a standard way) w.r.t. V.

(5) Truth of non-atomic facts in M is defined as usual. □ A set of facts is true in interpretation M if all its members are true in M. To complete the definition of the model we need only to formalize the following underlying assumption of domain descriptions of L_{H} and L_{HM}: “ No actions occur except those needed to explain the facts in the domain description.” This is done by imposing a minimality condition on the time assignments of T which leads to the following definitions. Definition 4.7 Let α = [a_{1}, …, a_{n}] and β = [b_{1}, …, b_{m}] be sequence of actions. We say that α ≤ β if there exists a subsequence^{6} [b_{i_{1}}, …, b_{i_{n}}] of β such that for every a_{k} ∈ α, a_{k} ⊆ b_{i_{k}}. □ Definition 4.8 An interpretation M = (Ψ, H, Σ, V) will be called a h-model (similarly mmodel) of a domain description D in L_{H} (or L_{HM}) if the following conditions are satisfied:

(1) Ψ is a h-causal model (or m-causal model) of D,

(2) facts of D are true in M, (3)If D is a domain description in L_{HM} then action-duration rules of D are true in M, and (4) there is no other interpretation N = (Ψ, H, Σ′, V′) such that N satisfies (1), (2) and (3) and Σ′(t_{N}) ≤ Σ(t_{N}). □ A domain description D is said to be h-consistent (m-consistent) if it has an h-model (mmodel).

6Given a sequence X = x_{1}, …, x_{m}, another sequence Z = z_{1}, …, z_{n} is a subsequence of X if there exists a strictly increasing sequence i_{1}, …, i_{n} of indices of X such that for all j = 1, 2 …, n, we have x_{i_{j}} = z_{j}.

Definition 4.9 A domain description D entails a fact p (written as D ⊧ p) iff p is true in all models of D. □

Definition 4.10 A domain description D is said to define a unique actual path if for any two times (from T ∪ I) t_{1} and t_{2} that are explicitly mentioned in D, D ⊧ t_{1} ≤ t_{2} or D ⊧ t_{2} < t_{1}. □

5 Examples of reasoning at a high and medium granularity

5.1 Reasoning at High Granularity

In this section we give examples where we reason at high granularity and about situation times.

Example 5.1 Yale Shooting

\begin{matrix}alive at t_{0} \\ ¬loaded at t_{0} \\ t_{0} < t_{1} \\ load begins at t_{1} ends at t_{2} \\ shoot occurs at t_{3} \\ t_{2} < t_{3} \\ load causes loaded \\ shoot causes ¬alive if loaded \\ shoot causes ¬loaded \end{matrix} \} D_{1}

□

Proposition 5.1 D_{1} ⊧ (t > t_{3} ⇒ ¬alive at t)

Example 5.2 Hiding Turkey Scenario

\begin{matrix}alive at t_{0} \\ ¬hidden at t_{0} \\ ¬loaded at t_{0} \\ t_{0} < t_{1} \\ load begins at t_{1} ends at t_{2} \\ shoot occurs at t_{3} \\ t_{2} < t_{3} \\ load causes hidden if ¬deaf \\ load causes loaded \\ shoot causes ¬loaded \\ shoot causes ¬alive if loaded, ¬hidden \end{matrix} \} D_{2}

□

Proposition 5.2 D_{2} ⊧ (deaf at t_{0} ∧ t > t_{3} ⇒ ¬alive at t) Example 5.3 Stanford Murder Mystery

\begin{matrix}alive at t_{0} \\ t_{0} < t_{1} \\ shoot occurs at t_{1} \\ ¬alive at t_{2} \\ t_{1} < t_{2} \\ load causes loaded \\ shoot causes ¬alive if loaded \\ shoot causes ¬loaded \end{matrix} \} D_{3}

□

Proposition 5.3 D_{3} ⊧ (t > t_{1} ⇒ loaded at t) Example 5.4 Stolen car scenario

\begin{matrix}t_{0} < t_{1} \\ car at t_{0} \\ steal causes ¬car \\ ¬car at t_{1} \end{matrix} \} D_{4}

□

Proposition 5.4 D_{4} ⊧ ∃t, t′(t_{0} < t < t′ < t_{1}) ∧ steal begins at t ends at t′ Example 5.5 Ticketed car scenario

\begin{matrix}¬ticketed at t_{0} \\ t_{0} < t_{1} < t_{2} < t_{3} \\ ticketed at t_{2} \\ ?????? \end{matrix} \} D_{5}

□

Example 5.6 Stockholm delivery scenario

\begin{matrix}¬box in car at 0 \\ box at(l) at 0 \\ car at(l) at 0 \\ load to car begins at 8 : 15 ends at 8 : 20 \\ drive car to(s) begins at 8 : 40 ends at 11 : 15 \\ load to car causes box in car \\ drive car to(X) causes car at(X) \\ drive car to(X) causes ¬car at(Y) if car at(X), X ≠ Y \\ drive car to(X) causes ¬box at(X) if box in car \end{matrix} \} D_{6}

□

5.2 Reasoning at medium granularity

Example 5.7 Ferry-boat Connection Scenario

\begin{matrix}atF at 0 \\ depart begins at 100 ends at 110 \\ atL at t \\ 99 ≤ t ≤ 101 \\ depart causes atJ if atL \\ drivetoL causes atL \end{matrix} \} D_{7}

□

Example 5.8 Furniture assembly scenario

\begin{matrix}assemble has duration 60 if ¬has instructions \\ assemble has duration 20 if has instructions \\ assemble causes assembled \\ ¬assembled at t_{0} \\ assemble occurs at t_{0} \end{matrix} \} D_{8}

□

Proposition 5.5 1. D_{8} ⊧ (t > 20 ⇒ has instructions at t_{0} ⇒ assembled at 20)

2. D_{8} ⊧ (¬has instructions at t_{0} ⇒ assembled at 60)

Example 5.9 Tampering notes scenario [7]

\begin{matrix}has notes at 7 \\ eat begins at 8 ends at 8.5 \\ drive begins at 9 ends at 10 \\ tampering notes begins at 8.3 ends at 8.7 \\ tampering notes causes ¬has notes \end{matrix} \} D_{9}

□

Proposition 5.6 D_{9} ⊧ (t > 8.7 ⇒ ¬has notes at t)

6 Reasoning at low granularity: The language L_{HML}

While reasoning at the low granularity we allow fluents that change values continuously. Hence, it is preferable that we use non-boolean fluents instead of boolean fluents used in L_{HM}. In general if the domain of a fluent is finite then we can replace it by a set of boolean fluents. This is less elegant when the fluent is non-boolean.

A fluent expression is a formula of the form

f is v  (5)

Intuitively it means that fluent f has value v. The domain of f is denoted by Dom(f) and v above must belong to Dom(f).

We now define a fluent literal to be either a fluent expression or a fluent expression preceded by ¬. Intuitively, the fluent expression ¬(fisv) means that the fluent f does not have value v.

We extend T by allowing f in (1) and (2) to be fluent expressions, and p_{i}’s in (1) and (4) to be fluent literals and allowing affect laws, which are expressions of the form

a affects f through F (t, f_{1}, …, f_{n}) if p_{1}, …, p_{n}  (6)

where a, is an action, f and f_{i}’s are fluent names, p_{i}’s are fluent literals, t refers to time duration, and F is a function from I × Dom(f_{1}) × … × Dom(f_{n}) to Dom(f). Intuitively, the above affect law means that the value of the continuously changing fluent f after t units of execution of the action a is given by F (t, f_{1}, …, f_{n}), and we assume that the value of fluents f_{1}, …, f_{n} remain constant during the execution of a.

For example, we can express that action drop ball affects the height of the ball by the following affect law:

drop ball affects height ball through initial height − 0.5 ∗ g ∗ t^{2}

6.1 Semantics of L_{HML}

The semantics of L_{HML} is based on the idea of mapping each time to a detailed sequence of actions. Affect laws are used on the detailed sequence of actions to determine values of fluents that change continuously with time and the detailed sequence of actions are compressed to a sequence of action (in the sense of reasoning at medium granularity) and effect laws are used on it (same way as in reasoning at medium granularity). Both are then combined to reason about values of fluents at a particular time.

References

[1] J. Allen and G. Ferguson. Actions and events in interval temporal logic. Journal of Logic and Computation, 4(5):531–580, october 1994.

[2] C. Baral and M. Gelfond. Representing concurrent actions in extended logic programming. In Proc. of 13th International Joint Conference on Artificial Intelligence, Chambery, France, pages 866–871, 1993.

[3] M. Gelfond and V. Lifschitz. Representing actions and change by logic programs. Journal of Logic Programming, 17(2,3,4):301–323, 1993.

[4] M. Gelfond, V. Lifschitz, and A. Rabinov. What are the limitations of the situation calculus? In R. Boyer, editor, Automated Reasoning: Essays in Honor of Woody Bledsoe. Kluwer Academic, Dordrecht, 1991.

[5] S. Hanks and D. McDermott. Nonmonotonic logic and temporal projection. Artificial Intelligence, 33(3):379–412, 1987.

[6] F. Lin and Y. Shoham. Concurrent actions in the situation calculus. In Proc. of AAAI–92, pages 590–595, 1992.

[7] R. Miller and M. Shanahan. Narratives in the situation calculus. Journal of Logic and Computation, 4(5):513–530, october 1994.

[8] J. Pinto and R. Reiter. Temporal reasoning in logic programming: A case for the situation calculus. In Proceedings of 10th International Conference in Logic Programming, Hungary, pages 203–221, 1993.