Filter Preferential Entailment for the Logic of Action in Almost Continuous Worlds

1 Topic

Our ultimate research goal is to find a coherent theory for temporal reasoning, knowledge based planning, and qualitative reasoning. In that context the present paper addresses the following problem. Assume that one has obtained:

1. a description of a mechanical or other physical sys­ tem
2. axioms characterizing physical laws which hold in that system
3. axioms characterizing conditions and effects of ac­ tions which can be performed by an agent in the world
4. axioms characterizing the observed or desired state of the world at certain point(s) in time

all expressed as logic formulas (wff) in a suitable logic. By what logical criteria can one then derive formulas characterizing a set of actions which together explain the observed state of the world resp. which obtain the desired state of the world?

*This research was supported by the Swedish Board of Technical Development and the IT4 research program

This general problem includes both "planning" in the A.l. sense (knowledge based planning) and "temporal ex­ planation", the difference being that in knowledge based planning the axioms in the last group express the goals, whereas in temporal explanation they express the given observations. For simplicity we shall refer to the last group of axioms as observations in the sequel, regardless of whether the application is planning or explanation.

2 Combining logic and differential equations for describing the physical system

In a previous paper [San89a] we have described an ap­ proach to integrating non-monotonic logic and differen­ tial equations for characterizing physical systems. The solution described there was however limited to the case in which there are no agents or actions in the world. The present paper extends the same approach to the case where actions may occur.

The key ideas in the approach of the previous paper are as follows. Object systems are assumed to be char­ acterized by a number of parameters, or fluents, which have a real-number value at each point in time. Time is also measured as real numbers, not only as discrete time-points. All parameters are assumed to be piecewise continuous and differentiable, with all their derivatives. For example a scenario with a bouncing ball will be char­ acterized by the position, velocity, acceleration etc. of the ball as functions of time. These functions are contin­ uous except (some of them) for those moments when the ball bounces, where they are taken to be discontinuous.

The properties of, and relationships between the pa­ rameters can then be described by logic formulas, in a language which has been suitably extended to allow time derivatives, and left and right limit values of parameters at the breakpoints (i.e. the timepoints where disconti­ nuities may occur). The following are examples of such formulas:

saying that at time Ts, the temperature of the object b4 is greater than zero degrees Celsius,

saying that the temperature of the object is always less than or equal to 100 degrees C,

saying that the rate of change of the temperature of the objects is always between 0.1 degrees C per second de­ creasing, and 0.05 degrees per second increasing,

saying that whenever the current coordinates (:cb, Yb) of the object at hand, is a point where the object bounces, then the left limit value of the vertical velocity has the same magnitude, but the opposite sign, as the right limit value of the vertical velocity. In this way the logic can characterize the behavior of the parameters around their discontinuities. For additional details and for a more systematic exposition please refer to [San89a].

Interpretations for such formulas must contain the fol­ lowing parts:

1. a specification of a set of breakpoints i.e. those time­ points at which discontinuities may occur
2. a mapping from time points x parameter symbols to parameter values (where the set of parameter sym­ bols is closed under prefixing of o)
3. appropriate mappings from constant symbols, such as r 5 .and b4 above, to corresponding numbers, ob­ jects, etc.

Also certain general conditions must be placed on the interpretations, in particular that for each particular pa­ rameter symbol, the mapping in the second item must be continuous, as a function of time, at all time points which are not break points. (In the break points it is allowed but not required to be continuous).

3 Actions

For the purpose of the present paper, the formula lan­ guage and the interpretations are extended with actions. Formulas are allowed such as

saying that an action of the action type Keepwarm(b4) is performed from time t5 to time t8 · Correspondingly interpretations are amended with one more component, namely an action set which should be a set of triples; each triple consisting of the time point when the action starts, the descriptor for the action, and the time point when the action ends. Action descriptors may be atomic, or may have a structure for example ( "Keepwarm", b:) i.e. the tuple consisting of the symbol "Keepwarm" and the object which is being kept warm.

Additional formal details are not necessary here. The important point is that each interpretation characterizes a possible "history" of the object world in two parallel ways: partly as a set of snapshots i.e. assignments of values to parameters at each point in time, and partly as a set of actions each of which has a starting time, an ending time, and a descriptor saying what the action is. Logic formulas refer to such interpretations, and the truth value of a formula in each interpretation is defined. It should be clear how one can, for example, write axioms which specify the effects of actions i.e. the values of parameters at the time when an action ends.

The topic of the present paper is now re-phrased for­ mally as follows. Let r o be a set of formulas representing observations (or goals, in a planning problem); let r be a set of formulas representing all the other given informa­ tion; we look for a formula <P which characterizes the set of actions, or plan, that accounts for or obtains the ob­ servations. Often <P would be a disjunction of expressions each of which characterizes an alternative explanation or plan.

4 Semantic entailment

For the purpose of the present work it was necessary to introduce a non-standard notion of semantic entailment. Let us first relate it to the traditional notions. In general a definition of whether r F= <P should consist of two parts:

1. model set criterium: determine the model set for r
2. formula criterium: identify which formulae <P one wants to conclude from the model set

where in classical logic the model set is of course simply M od(r), the set of all interpretations in which all mem­ bers of r are true, and the formula criterium is to choose a formula which is true in all members of the model set. In non-monotonic logic the model set for r is chosen differently, using model minimization, but the formula criterium remains unchanged. For reasoning about ac­ tions, however, both criteria have to be reconsidered.

In preferential entailment, as defined by [Sho88], one assumes the existence of a preference relation~ which is a partial order on interpretations, and defines the model set for r in the simplest case as

i.e. as the set of ~-minimal members of M od(r). How­ ever since there may be infinite chains of successively more preferred models, whose limit does not exist or is not a model for r' an alternative is to define the model set of r as a set of paths of interpretations,

where Paths(~. S) is the set of all maximal subsets of S within which ~is a total order. The formula criterium is then, that in each preference path of the model set, there must be some member J such that <P is true in all elements ~ J in that path.

Our previous paper proposes a definition for the pref­ erence relation ~ for the logic that was outlined in the previous section. The criterium, chronological minimiza­ tion of discontinuities (CMD) is basically that if J and J' are interpretations, then J ~ J' iff there is some time-point t such that J and J' assign the same value to all parameter for all times < t, and the set of pa­ rameters in J which have a discontinuity in t is a true subset of the set of parameters in J' that have a dis­ continuity in t. We showed that preferential entailment using CMD, and with a reasonable set of axioms, obtains the intended set of models for a simple but prototypical example. From the example and from general consider­ ations we concluded that CMD is a plausible choice of semantic entailment condition for piecewise continuous systems.

In the following sections we address the question whether and how the model set criterium has to be re­ vised when observations and actions also occur as axioms and in the interpretations. First however a brief remark on the formula criterium, how to go from model set to proposed conclusions. It has sometimes been debated whether one should let "goals entail plans" [Kau88] or vice versa, i.e. schematically whether one should require

In a separate paper [San89b] we argue that neither of these alternatives constrains ¢ correctly, and that both of them should be used together at least approximatively. The requirement should therefore be that the model set for r, r 0 be approximatively equal to the model set for r, ¢. Since the issue is somewhat complex, it merits a paper of its own. We therefore omit additional detail from the present paper, and focus on the first question of identifying the model set for r' r o·

Of course the criterium for a proposed definition of se­ mantic entailment is not that it in itself obtains the cor­ rect model set, since what models are obtained depends also on the axioms. For the conventional "frame prob­ lem", for example, it is perfectly possible to obtain the correct model set with standard, monotonic entailment, but the problem is that it may be very cumbersome to write out the axioms. The criterium for a definition of entailment is therefore whether it makes it easy to write axiomatizations which obtain the right model sets. This is the claim that is tentatively made for chronological minimization of discontinuities.

5 Model set criteria for axioms with observations

The extension of the logic to allowing actions, is closely tied to the use of observations. Without actions there are good reasons to study the consequences of the general axioms combined with observations at an initial point in time, or at no time at all. (The latter case corresponds essentially to the notion of "envisionment" in qualitative reasoning, [dKB85]). With actions, observations at two or more points in time are needed, for example for spec­ ifying the initial condition and the goal for the required action-plan.

We therefore first consider the case where there are observations but no actions. The set r 0 , by the notation at the beginning of the previous section, is assumed to be non-empty, while the action set is empty. Consider the following two candidate model sets:

where Filter(r 0 , S) is a subset of S consisting of those members of S which are also models for r o· The defini­ tion of M2 can therefore be written equivalently as

or These definitions have been made in terms of minimal models; corresponding definitions in terms of preference paths are easily constructed.

The definition for M1 is the most straightforward one from the point of view of the inference system: one just combines all the available knowledge and applies prefer­ ential entailment as usual. The definition for M2 how­ ever has an intuitive appeal: since

is the set of all possible developments in the world re­ gardleu of any observations, it would make sense to take that whole set and "filter" it with the given observations.

It is easily seen that M2 ~ M1, since every member of M2 satisfies all conditions for being a member of M1 · The opposite is however not always the case, as the fol­ lowing example shows. Consider a one-dimensional ob­ ject system where an object (with zero size) is known to have coordinate 0 at time 0, and coordinate 2 at time 10. It is also known that the object's coordinate is contin­ uous at all times (including breakpoints), and that the velocity of the object is always ~ 10. Finally it is known that the object's acceleration is zero at all times. This is all one knows.

In the absence of any reason for a discontinuity in the object's velocity, one would expect to have one single member of the model set, namely where the velocity of the object is 0.2 at all times. We shall refer to it as the standard model. Consider however also a model where the velocity ofthe object is 0.1 from time 0 to some time­ point shortly before time 10, where the velocity changes discontinously to a larger value which allows the object to be at coordinate 2 in time. Such an interpretation sat­ isfies both the observation axiom (coordinate 2 at time 10) and the other axioms, and is therefore a member of Mod(ruro) 1 .

Since the initial velocity in such a non-standard model is different from a standard model, the chronological minimization of discontinuities will not prefer standard over non-standard models. On the other hand for a given initial velocity (e.g. 0.1), CMD will prefer those models where the discontinuity occurs as late as possible, or in other words the model where the object uses the maxi­ mum speed after the discontinuity. Thus for every choice of initial velocity there is exactly one preferred model in M1.

In M2 on the other hand, only the standard model is obtained. This is because Min(«:, M od(r)) will not contain any model with a discontinuity: for every model with a discontinuity there is a corresponding model with­ out the discontinuity which is preferred according to«:, and which also satisfies all the axioms in r. The set Min(«:, M od(r)) will contain one member for every pos­ sible value of the object's velocity, but only one of them will remain after filtering with the observation axiom.

Based on this discussion and example, we suggest that the definition of M2 is the one which should be used for identifying model sets in piecewise continuous worlds, and as the first step in the definition of semantic entail­ ment there. The term filter preferential entailment is proposed for semantic entailment using the definition of M2 as its model set criterium.

1 It may seem strange that the velocity may have a discon­ tinuity while at the same time the acceleration is constantly zero. It is OK, however; see [San89a] for the explanation.

Parenthetically, it is interesting to note that if the maximal speed condition is dropped (or is changed from a ~ condition to a < condition), and the model mini­ mization is performed in terms of minimal models rather than preference paths, then M1 as well as M 2 contains only the standard model. This is because there is an infi­ nite progression of non-standard models where the break point occurs later and later, and the velocity after the break point is greater and greater. In the interpretation at the limit of that progression, the object's coordinate has a discontinuity at time 10, which means that the limit interpretation is not a model of the given axioms in r. Therefore non-standard models are de-selected. However we can not see this as a reason for reconsid­ ering the M 1 definition - it would be too ad hoc as a method for de-selecting unintended models.

6 Model set criteria for interpretations with action sets

We proceed now to the case where interpretations con­ tain not only the "snapshots" i.e. the state of the world or the parameter values at each point in time, but also a set of actions each specified by starting time, ending time, and action type, as described in section 3. This means in particular that M od(f) is going to contain in­ terpretations containing no, one, or several actions in their action sets.

An additional preference condition must be involved when action sets occur in interpretations, namely a pref­ erence relation between interpretation which is due to preference between their respective action sets. Suppose for given rand given r 0 we have a model set with in par­ ticular two interpretations J and J', where J contains an action set which is in fact necessary for explaining or achieving the observations, and J' is essentially the same as J except its action set also contains a redundant ac­ tion which does not influence the value obtained for the observations. In such a case one would obviously prefer J over J', both as an explanation of the observations and as a plan for the agent's own actions.

There may however also be other preferences which are not so obvious, all the way to the criteria based on a cost function on plans. The question is then, how shall the model set be modified to account for our preference between action sets, or plans?

The choice in CMD to apply observation enforcement "after" the (chronological) minimization condition, gen­ eralizes naturally to plan minimization. We therefore propose the following model set criterium:

where ~ only compares interpretations with the 8ame action 8et, and ~ compares interpretations according to the preference of their respective action sets, so that at least if the set of actions in the interpretation J is C the set of actions in J' then J ~ J'. Other action-set preferences may of course also be added.

The first preference relation ~ was defined in the pre­ vious paper and described above. However it now has to be slightly revised, since one should not do chronological minimization of those discontinuities which are caused by actions. Only discontinuities which occur "sponta­ neously" as consequences of the laws of nature, for ex­ ample when a ball falls over an edge, or heated water arrives to the boiling point, should be chronologically minimized. Otherwise the preference according to ~ will prefer all actions to take place as late as possible!

Formally this modification can be achieved by intro­ ducing two ma8king relation$ X, and X .. on

timepoints x properties

where X 1(t, u} waives the CMD preference for interpreta­ tions where u 1 (t) = u(t), and similarly for X ... (Notice if u 1 (t) = u(t) = u .. (t) then u is continuous at timet). The relations X, and X.. are themselves minimized by the relation ~. Also modes (propositional fluents) are dealt with in the same way. The resulting formal semantics is as follows.

Definition. An interpretation is a tuple

where H is a set of action type symbols, M is a set of mode symbols (for truth valued parameters), U is a set of parameter symbols closed under prefixing by a, S C R is a "sparse" set of time-points namely the set of breakpoints, X 1 C R x (M U U) and X .. with the same type, are the masks on where modes and parameters are "allowed" to be discontinuous, P C S x H x S is the "plan" i.e. the set of actions, R is a mapping

which gives the (truth-)value of a mode at each point in time, Q is a mapping

which similarly gives the (real-)value of a parameter at each point in time, and W is a mapping from temporal constant symbols (such as Tt) to the domain R of real numbers understood as time-points.

Interpretations are subject to the continuity require­ ment that for every t ¢ S, R(t, m) and Q(t, u) shall be continuous as functions of t. For t not in S it is also required

Logic formulas which can be evaluated in such inter­ pretations are defined as desired.

Definition. A parameter u is euentially continuous at timet, and we write ec(t, u), iff

where the index 1 and .. on Q represent the left and right limit values, as used in section 2 above.

Essential continuity for modes is defined similarly.

Definition. For every interpretation J and timepoint t E R we define breakset(J, t) as

Definition. If J and J' are interpretations, whose elements are H, M, ... and H', M', ... respectively, then J «: J' iff P = P', X, ~X{, X .. ~ x;, and either of the following applies: either X, C X{, or X .. C x;, or there is some time-point t0 such that

2. breakset(J, t) C breakset(J', t)

Definition. If J and J' are interpretations whose ele­ ments are like in the previous definition, then J ~ J' iff P C P'. (Additional conditions may be added).

Definition. The filter preferential model set of the gen­ eral axioms r and the observation axioms r 01 using the preference relations «: and ~.is

The hypothesis is that for prototypical applications one can conveniently write axiomatizations for which the filter preferential model set, with CMD as the first pref­ erence relation, obtains the intended model set.

7 Example: the covered shaft

The following example illustrates the proposed entail­ ment criterium and the issues involved in choosing it. Two small objects called h and k are bouncing indefi­ nitely back and forth at constant speed in a fixed hori­ zontal range. In figure 1 the z dimension is "horizontal", the y dimension is "vertical", and the range is between the points (a,e) and (d,e) in the (z,y) plane. Also the part of the range which is between the z coordinates b and c (where a< b < c < d) is the lid of a shaft which extends indefinitely downwards. At each point in time the lid is either on or off. If the lid is off at a time when either of the objects is between (z coordinate) band c, then the object starts falling into the shaft, with constant vertical acceleration -10 during the fall. The horizon­ tal coordinate of the object during the fall is considered irrelevant, so we omit axioms that constrain it.

In the absence of any action the lid is on. There is an action liftlid which always takes two seconds, and which has the effect that the lid starts being off at some time between 0 and 0.5, and starts being on again at some time between 1.5 and 2, counted from the beginning of the liftlid action. Also of course it is not possible to do two liftlid actions during overlapping time intervals.

The scenario starts at time 0, with the two objects at opposite ends of the range, and moving towards each other each with velocity 1. There is no interference when the objects meet along the way. (They may e.g. be thought of as having different but constant coordinates in a third dimension z).

The scenario is illustrated in figure 1, and can be used for a number of deduction exercises, such as:

* what are the possible interpretations in the sce­ nario world, each interpretation being a possible course of events there from time 0 and onwards? (envisioning)

*given additional observations also at some time(s) > 0, what remaining courses of events are compatible with those observations but without assuming any actions?

* given additional observations like in the previous case, but in such a way that some action(s) must be assumed, what formulas characterizing the set of actions are entailed

For example, the formula saying that there is a time > 0 at which the y coordinate of k is < e, can only be true in interpretations where there is an openlid action which has been chosen in such a way as to let through k and not let through h.

The following is a partial set of axioms characterizing the scenario. Let (zh, Yh) be the coordinates of h as a function of time, let (z~:,YJ:) be the same for k, and let j range over the two objects h and k. Most of the axioms are similar to the axioms which were defined and discussed in [San89a].

1. Da < b < c < d

2. a, b, c, d, e are constants over time

3. [0]( Zh = a 1\ Yh = e 1\ azh = 1)

4. [O](z~: = d 1\ Yk = e 1\ 8z~: = -1)

5. D(z; =a V z; =d) 1\ Yi = e-+ (8z~ = -8zj)

6. D8 2 z; = 0

8. Dy; =/; e V (b < z; < c 1\ lidoiJ)-+ 8y; = -10

7. Dy; = e 1\ ·(b < z; < c 1\ lidoiJ) -+ 8y; = 0

1. Do[t1, openlid, t2] -+ t 2 = t1 + 2 1\ 3t33t4[tl < t3 ~ tl + 0.5 1\

tl + 1.5 < t4 < t2 1\

[tlt t3l·iidojJ A

[t3, t4llidojJ 1\

[t4, t2]·lidojJ 1\

lt11 t2]X,( lidoiJ) 1\ [tlt t2l X .. ( lidoff)]

10. DC(X;)

11. Da < z; < d-+ C(8z;)

The following notation is used for intervals: [t, v] rep­ resents the closed interval from t to v inclusive, and rt, v l represents the open interval not containing tor v. Mixed intervals (left open, right closed and vice versa) are writ­ ten in the obvious way, and [t] represents the interval whose only member t is. The interval It, tl is the empty set.

Let us now add the observation axiom saying that ob­ ject k has fallen into the shaft and object h has not, nor is it just going to:

The third conjunct is needed in order to exclude in­ terpretations where the lid opens for both objects, but k falls in first. Notice that the t, are temporal variables and Ti are temporal constant symbols. Furthermore we add axioms for the exact range and lid size in the sce­ nano:

This set of axioms is still somewhat incomplete, but not in any way that matters for the continued argument.

8 Discussion of example

With the sizes stated in axiom 13 there are two primary good "strategies" for achieving the "goal" expressed in axiom 12. One strategy is to perform the openlid action so that it catches the object k as it is travelling right, and with a timing that makes sure that one does not trap h as well. This is satisfied if the action is initiated between 0 and 0.5 seconds before k bounces at coordinate a. The other strategy is to catch k as it is travelling left, and around the time that the objects pass each other. The timing may be e.g. to initiate the action exactly when the objects meet, or more generelly when the :z: coordinate of k is between 3.5 and 2.5.

These two alternative strategies can be characterized by the following "strategy formula"

It would be ideal if the model set for the axioms were exactly the set of interpretations where either of these two strategies is performed, while also the "laws of na­ ture" in axioms 1 through 11 are also satisfied. If this were the case then the given axioms would entail the strategy formula (the disjunction of the possible plans) using the filter preferential model set criterium, and the conventional formula criterium in the sense of section 4.

Unfortunately there will also be other interpretations which satisfy all the axioms, but which rely on "coin­ cidence" for obtaining their results. For example if the openlid action starts when h is in coordinate 2. 75 and travelling in the positive direction, then k will certainly go into the shaft, and h may or may not go into the shaft depending on how quickly the lid opens. There will be some interpretations where the lid opens late enough for all the axioms to be satisfied.

The question of how to deal with such coincident mod­ el.s is discussed in [San89b], in the context of how to choose the formula criterium. Our concern here is only to make sure that the filter preferential model set for axioms such as those given above, obtains exactly those interpretations where the course of events in the world has been decoded correctly. In particular it must be re­ quired that all interpretations which are in accordance with either of the two primary strategies, and which are in accordance with the general laws, remain in the filter preferential model set.

It is easily seen that all interpretations of that kind, which have only one openlid action in their P compo­ nent, satisfy all the axioms. It is also clear that they are minimal with respect to -< since no interpretation with an empty P component could satisfy all the axioms. Fur­ thermore if the interpretations only have discontinuities where "necessary" i.e. where the objects bounce against the ends of the range, and when k starts falling, they will be minimal with respect to «::.

Interpretations with more than one action in their P components can not be members of the model set. Even if they satisfy all the axioms, they are still not «::­ minimal since one can remove the redundant actions and obtain another interpretation which also satisfies all the axioms.

Interpretations where the objects are allowed to bounce several times before the lid is opened, will also be members of the model set and rightfully so.

Other possible forms of entailment conditions or model set criteria exhibit various kinds of interesting bugs. For example, one concern in the choice of criteria is to not introduce unnecessary actions which may account for natural discontinuities. Suppose there is some type of discontinuity, for example an object falling over an edge, which may both be the direct result of an action, and be the natural effect of previous movements. One does not wish an interpretation where the discontinuity oc­ curs as a natural effect, to be dominated in the sense of the preference relations, by another interpretation con­ taining an extra action which has the discontinuity as an effect. The filter preferential model set does not have that bug. However if the definition of «:: is changed by omitting the condition P = P', then exactly this bug is obtained.

Chronological minimization of discontinuities is a nat­ ural preference criterium; it captures the one-way, non­ symmetric character of time in the real world. However one must make an exception from chronological mini­ mization within the time-span of actions. The mask­ ing "X" relations are of course the technical device for realizing those exceptions. This was illustrated also by the example above: without the exceptions, CMD would prefer interpretations where the lid opens and closes as late as possible.

In our particular example the action involved discon­ tinuities, at arbitrarily chosen times, of a propositional fluent ("mode"). Actions involving quantitative feed­ back, which proliferate in many real-world applications, are seen in our system as introducing discontinuities for quantitative parameters at arbitrary times.