Causality and Minimal Change Demystified

1 Introduction

The problem of reasoning about action and change has been one of the major preoccupations for artificial intelligence researchers since the inception of the field. One of the early tenets applied when reasoning about such phenomena was that as little as possible should change in the world when performing an action; what we might call the Principle of Minimal Change. 1 This principle is manifest in many guises: preferential-style systems [Shoham, 1988], persistence approaches [Krautz, 1986], circumscription [McCarthy, 1980], etc. Over the years, aspects of this principle have been called into question leading to a variety of suggested fixes: fixed versus variable predicates in circumscription, occluded fluents [Sandewall, 1989], frame fluents [Lifschitz, 1990], to name but a few. Moreover, in the more recent literature explicit representations of causality have found favour [Lin, 1995; McCain and Turner, 1995; 1997; Thielscher, 1997]. However, what is not clear-beyond some simple representative

1 Although, one might be tempted to say that the Principle of Minimal Change is more general in scope.

Pavlos Peppas

Dept. of Business Administration University of Patras Patras 26500, Greece ppeppas@otenet.gr

examples-is the purchase afforded by explicitly representing causality over the more traditional minimal change approaches. It is this imbalance that this paper seeks to redress in a clear and objective manner. In fact, the results we present here have further reaching consequences, giving a rather lucid characterisation of the extent of applicability of minimal change. By this we mean that, given a framework for reasoning about action and change, it will be clear whether such a framework can be modelled by minimal change once certain properties of the framework can be established.

We achieve our aims through a correspondence between two formal systems which we call dynamic systems and preferential models respectively. Intuitively, the dynamic system is an abstract modelling of the dynamic domain under consideration (the behaviour of which we wish to reason about). Essentially, this abstract model captures the domain at hand by a result function a0 ✁ ✄ ✆ ✞ ✠ which returns the states (of the domain) that could possibly result from the application of an action with direct effects ✞ (i.e., postconditions) at the initial state ✄ . A preferential model on the other hand is a formal structure that encodes the Principal of Minimal Change in an abstract and quite general manner. With the aid of preferential models we are able to provide a precise characterisation of the class of dynamic systems that are amenable to theories of action based on minimal change; we call such dynamic systems minimisable. Having a precise characterisation of minimisable dynamic systems we can then examine whether theories of action adopting an explicit representation of causality, which we shall call causal theories of action are capable of forms of reasoning that cannot be captured by the Principle of Minimal Change; more precisely, we can examine whether causal theories of action are applicable outside the scope of minimisable dynamic systems. According to the results reported herein, the logic of action proposed by Thielscher [1997] is indeed applicable to non-minimisable dynamic systems, whereas, perhaps surprisingly, McCain and Turner's causal theory of action [McCain and Turner, 1995] has a range of applicability that is subsumed by the class of minimisable dynamic systems.

In the following section we introduce both dynamic systems and preferential models. Moreover, we state clearly the notion of minimal change that we shall adopt here. In Section 3 we examine the formal properties that the result function of a dynamic system must obey in order for it to be minimisable. Section 4 presents an analysis of some of the theories of ☛ action found in the literature. We endwith a discussion and conclusions, including pointers to future work.

2 Dynamic Systems and Preferential Systems

As mentioned above, the main results in this paper will be achieved by demonstrating a correspondence between two formal systems. The first, called a dynamic system, is meant to serve as a general abstraction of domains (such as the blocks world, or the domain described by the Yale Shooting Problem, etc.), for which theories of action are designed to reason about. Our main interest shall be in the properties of the dynamic system's result function. In particular, we shall formulate necessary and sufficient conditions under which the system's result function can be characterised in terms of an appropriately defined minimisation policy. Minimisation policies are in turn encoded by our second formal system called a preferential model. Dynamic systems and preferential models are formally defined below.

2.1 Dynamic Systems

Throughout this article we shall be working with a finitary propositional language ☞ the details of which shall be left open. 2 We shall often refer to ☞ as the object language. We shall call the propositional variables of ☞ fluents. The set of all fluents will be denoted by ✌ ✍ . A literal is either a fluent or the negation of a fluent. We shall denote the set of all literals by ✏ ✍ . A state of ☞ (also referred to as an object state) is a maximally consistent set of literals. The set of all states of ☞ is denoted by ✑ ✍ . For a set of sentences ✓ of ☞ , by ✔ ✓ ✕ we denote the set of all states of ☞ that satisfy ✓ , i.e. ✔ ✓ ✕ = ✗ ✘ ✚ ✑ ✍ ✜ ✘ ✣ ✓ ✤ . Finally, for a sentence ✦ of ☞ we shall use ✔ ✦ ✕ as an abbreviation for ✔ ✗ ✦ ✤ ✕ .

Definition 2.1 A dynamic system is a triple ✩ = ✪ ✫ ✆ ✬ ✆ a0 ✰ where,

• ✱ ✫ is a nonempty subset of ✑ ✍ the elements of which we shall call valid states.
• ✱ ✬ is a nonempty set of sentences of ☞ . The intended meaning of the sentences in ✬ is that they correspond to the postconditions (or direct effects) of actions. For simplicity, we shall identify actions with their postconditions and refer to the sentences in ✬ as actions.
• ✱ a0 ✜ ✫ ✲ ✬ ✴ ✶ ✫ , is called the result function.

Intuitively, the result function a0 ✁ ✄ ✆ ✞ ✠ returns the set of object states considered to be possible resultant states after applying the action with postcondition ✞ at the object state ✄ . If for a certain ✄ , ✞ , it happens that a0 ✁ ✄ ✆ ✞ ✠ = ✻ , this is taken to mean that ✞ is not applicable at ✄ .

2.2 Extensions of the Object Language

Despite the many different ways in which the principle of minimal change has been encoded [McCarthy, 1980; Winslett, 1988; Katsuno and Mendelzon, 1992; Doherty, 1994;

2 By a language, we intend all well formed formulae of that language.

Sandewall, 1996], a feature that is common to all these approaches is the existence of an ordering ✼ on states used to determine which inferences are drawn about the effects of actions. In some of these approaches [Winslett, 1988; Katsuno and Mendelzon, 1992; Sandewall, 1996] the ordering ✼ is defined over the set ✑ ✍ of object states. For example, according to the Possible Models Approach (PMA), the ordering ✼ ✽ associated with an (initial) state ✄ is defined as follows: for any ✘ ✆ ✘ ✾ ✚ ✑ ✍ , ✘ ✼ ✽ ✘ ✾ if and only if Diff ✁ ✄ ✆ ✘ ✠ ❂ Diff ✁ ✄ ✆ ✘ ✾ ✠ . 3 There are however many theories of action for which the ordering ✼ is defined, not over the set of object states, but rather over an extended set of meta-states. Consider, for example, a theory of action based on circumscription [McCarthy, 1980]. Circumscription's minimisation policy induces an ordering ✼ that is defined over a set of meta-states ✑ ✍ ✾ , generated from the set of object states ✑ ✍ with the addition of the abnormality predicate ❃ ❄ . More precisely, if the object language has ❆ fluents, and ❇ actions, there will be ✶ ❈ object states in ✑ ✍ ; with the addition of the abnormality predicate ❃ ❄ , each objects state ✄ "splits" into ✶ ❈ ❋ ❍ meta-states, all of which agree with ✄ on the truth value of the ❆ (object) fluents, and differ only on the value of the abnormality predicate ❃ ❄ for each pair of (object) fluent and action. Thus there will be a total of ✶ ❈ ❏ ❑ ❈ ❋ ❍ ◆ meta-states over which the ordering ✼ is defined.

As we prove later in this paper, moving the minimisation policy from object states to meta-states results in significant gains in the range of applicability of minimal change approaches. Given the major role of meta-states in our study, in the rest of this section we introduce some further notation and formally define the concepts related to meta-states.

A propositional language ☞ ✾ is called an extension of ☞ if and only if firstly, ☞ ✾ is finitary and secondly, the propositional variables of ☞ are included in ☞ ✾ . If ☞ ✾ is an extension of ☞ we shall refer to the additional propositional variables of ☞ ✾ (i.e., those that do not appear in ☞ ) as control variables or control fluents. 4 We shall say that ☞ ✾ is a a80 -extension of ☞ , for a natural number a80 ✚ ◗ , if and only if ☞ ✾ is an extension of ☞ and it contains precisely a80 control fluents. Clearly, any ❙ -extension of ☞ is identical with ☞ .

For an extension ☞ ✾ of ☞ , any maximally consistent set of literals of ☞ ✾ is called a meta-state. For a set of sentences ✓ of ☞ ✾ , we define the restriction of ✓ to ☞ , denoted ✓ ❚ ☞ , to be the set ✓ ❯ ☞ . Finally, we define the restriction to ☞ of a collection ❲ of sets of sentences of ☞ ✾ , denoted ❲ ❚ ☞ , to be the set consisting of the restriction to ☞ of the elements of ❲ ; in symbols, ❲ ❚ ☞ ✾ ❨ ✗ ✓ ❚ ☞ ✜ ✓ ✚ ❲ ✤ .

2.3 Preferential Models

Having formally defined meta-states it remains to introduce a general model that encodes the concept of minimisation over meta-states.

Definition 2.2 A preferential structure for ☞ is a triple ❬ = ✪ ☞ ✾ ✆ ✫ ✾ ✆ ❭ ✰ where:

3 For any two states ❴ ❵ ❛ , Diff ❜ ❴ ❵ ❛ ❢ denotes the symmetric difference of ❴ and ❛ .

4 Like the abnormality predicate, control fluents are meant to be variables guiding the minimisation policy.

• ✱ ☞ ✾ is an extension of ☞ .
• ✱ ✫ ✾ is a nonempty collection of maximally consistent sets of literals of ☞ ✾ ; we shall call the elements of ✫ ✾ valid meta-states.
• ✱ ❭ is a function mapping each object state ✄ ✚ ✑ ✍ to a (partial) preorder over ✑ ✍ ❣ (the set of all maximally consistent sets of literals of ☞ ✾ ); we shall denote the preorder assigned to ✄ , by ✼ ✽ . 5

As mentioned earlier, a preferential structure ❬ = ✪ ☞ ✾ ✆ ✫ ✾ ✆ ❭ ✰ is meant to be the basis for encoding formally (and in a quite abstract manner) the concept of minimal change. More precisely, let ✄ ✚ ✑ ✍ be any object state. The preorder ✼ ✽ associated with ✄ represents the comparative similarity of meta-states to ✄ . Using ✼ ✽ (and the principle of minimal change), one can then determine the states a0 ✁ ✄ ✆ ✞ ✠ that can possibly result from the application of an action ✞ to ✄ by means of the condition (M) given below:

In the above condition, ✔ ✞ ✕ ✍ ❣ denotes the set of meta-states consistent with the sentence ✞ and ❇ ❧ ❆ ✁ ✔ ✞ ✕ ✍ ❣ ✆ ♦ ✽ ✠ is the set of such meta-states that are minimal ("most preferred") with respect to ♦ ✽ .

The intuition behind condition (M) should be clear. Essentially, we select those meta-states consistent with formula ✞ (representing the postcondition of an action) that are minimal under the ordering ♦ ✽ , filter out the valid ones and then restrict these to the language of the dynamic system under consideration.

We shall say that a preferential structure ❬ = ✪ ☞ ✾ ✆ ✫ ✾ ✆ ❭ ✰ is a preferential model for the dynamic system ✩ = ✪ ✫ ✆ ✬ ✆ a0 ✰ if its result function can be reproduced from ❬ by means of condition (M); more precisely, if and only if for all ✄ ✚ ✫ and ✞ ✚ ✬ , condition (M) is satisfied. If a dynamic system ✩ has a preferential model a116 , we shall say that ✩ is minimisable; moreover, if there are precisely a80 control fluents in ☞ ✾ , we shall say that ✩ is a80 -minimisable or that it has a preferential model with degree a80 . Clearly, if a dynamic system ✩ has a preferential model with degree a80 for some a80 ✚ ◗ it also has a preferential model with degree ❇ for any ❇ ✈ a80 .

3 Minimisable Dynamic Systems

Our aim in this section is to provide a characterisation of the class of minimisable dynamic systems, in terms of conditions imposed on the result function a0 .

Let ✩ = ✪ ✫ ✆ ✬ ✆ a0 ✰ be a dynamic system, ✄ a state in ✫ , and ✞ ✆ ✞ ✾ any two actions in ✬ . Consider the conditions (P1) - (P3) below:

• (P1) If ✄ ✚ ✫ and ✘ ✚ a0 ✁ ✄ ✆ ✞ ✠ , then ✘ ✣ ✞
• (P2) If ✄ ✚ ✫ and ✣ ✞ ④ ✞ ✾ , then a0 ✁ ✄ ✆ ✞ ✠ ❨ a0 ✁ ✄ ✆ ✞ ✾ ✠
• (P3) If ✞ ✣ ✞ ✾ , ✄ ✚ ✫ , ✘ ✚ a0 ✁ ✄ ✆ ✞ ✾ ✠ and ✘ ✚ ✔ ✞ ✕ , then ✘ ✚ a0 ✁ ✄ ✆ ✞ ✠

5 We shall also use ⑧ ⑨ to refer to the strict (non-reflexive) part of ⑩ ⑨ .

These conditions can be interpreted quite simply. Condition (P1) says that the postconditions of an action (i.e., ✞ ) should be true at all possible resultant states. Condition (P2) is an irrelevance of syntax condition stating that actions having logically equivalent postconditions should predict the same resultant states. Condition (P3) states that if a state ✘ is chosen as a possible outcome of an action ✞ ✾ , then ✘ should also be chosen as a possible outcome of any action ✞ which is stronger than ✞ ✾ and consistent with ✘ . (NB: ✞ ✣ ✞ ✾ implies ✔ ✞ ✕ ❂ ✔ ✞ ✾ ✕ ). This last condition is similar to the choice theoretic condition know as ( ✞ ) in the literature [Sen, 1977]. These three, simply stated conditions suffice to exactly characterise the class of minimisable dynamic systems.

Theorem 3.1 A dynamic system is minimisable if and only if it satisfies the conditions (P1) - (P3).

Theorem 3.1 is the central result of this article. What is perhaps surprising about this theorem is that it manages to provide a characterisation of minimality defined over metastates via conditions on the result function, which operates on object states.

The proof of Theorem 3.1 is omitted due to space limitations. The most interesting part of the proof is a construction that, given a dynamic system ✩ with ❆ fluents satisfying (P1) - (P3), generates a preferential model for ✩ with degree ✶ ❈ . An immediate corollary of this is that, if a dynamic system is at all minimisable, then it is minimisable with degree ✶ ❈ . We shall call the smallest number a80 for which a minimisable dynamic system ✩ has a preferential model with degree a80 , the minimality rank of ✩ . As already mentioned, the corollary below follows directly from the proof of Theorem 3.1.

Corollary 3.1 The minimality rank of a minimisable dynamic system with ❆ fluents is no greater than ✶ ❈ .

Having provided a general characterisation of minimisable dynamic systems by means of (P1) - (P3), we shall now turn to special cases. More precisely, we shall impose certain constraints on preferential models and examine their implications on minimisable dynamic systems via condition (M).

The first such constraint is totality on the preorders of a preferential model. More precisely, we shall say that a preferential model ❬ = ✪ ☞ ✾ ✆ ✫ ✾ ✆ ❭ ✰ is linear if and only if all preorders in ❭ are total (sometimes referred to as connected). We shall say that a dynamic system ✩ = ✪ ✫ ✆ ✬ ✆ a0 ✰ is strictly minimisable if and only if ✩ has a linear preferential model. In the presence of (P1) - (P3), condition (P4) below characterises precisely the class of strictly minimisable dynamic systems. The term a0 ✁ ✄ ✆ ✬ ✾ ✠ in (P4), where ✬ ✾ is a subset of ✬ , is used as an abbreviation for ❷ ✞ ✾ ❸ ✬ ✾ a0 ✁ ✄ ✆ ✞ ✾ ✠ .

• (P4) For any nonempty ✬ ✾ ❂ ✬ such that a0 ✁ ✄ ✆ ✞ ✾ ✠ ❹ ❨ ✻ for all ✞ ✾ ✚ ✬ ✾ , there exists a nonempty subset ❻ of a0 ✁ ✄ ✆ ✬ ✾ ✠ , such that a0 ✁ ✄ ✆ ✞ ✠ = ✔ ✞ ✕ ❯ ❻ , for all ✞ ✚ ✬ such that ✔ ✞ ✕ ❂ ✔ ✬ ✾ ✕ and ✔ ✞ ✕ ❯ ❻ ❹ ❨ ✻ .

Condition (P4) essentially says that, under certain conditions, a collection of states ❲ contains a subset ❻ of "best" elements. Consequently, whenever an action ✞ is such that all ✞ - states are contained in ❲ , and moreover, among the ✞ -states there are some of the "best" elements of ❲ , then any state resulting from ✞ is among those "best" ✞ -states (i.e., a0 ✁ ✄ ✆ ✞ ✠ =

✔ ✞ ✕ ❯ ❻ ). Notice that (P4) collapses to the (much more familiar) condition ❽ (P4 ✾ ) below, whenever a0 ✁ ✄ ✆ ✞ ✠ is defined for all pairs of states ✄ , and sentences ✞ . In the principal case however where a0 is defined over a proper subset of ✑ ✍ ✲ ☞ , (P4 ✾ ) is strictly weaker than (P4).

This is essentially the (U6) postulate of Katsuno and Mendelzon [1992]. It is also found as property (3.13) in G¨ ardenfors [1988, p. 57].

Theorem 3.2 A dynamic system is strictly minimisable if and only if it satisfies the conditions (P1) - (P4).

A direct consequence of the (only-if part of the) above proof is the following corollary.

Corollary 3.2 The minimality rank of a strictly minimisable dynamic system is no greater than 1.

Corollary 3.2 shows that by imposing totality on the preorders of the preferential model, we get very close to zerominimisable dynamic systems. Very close indeed, but not quite there. In this paper we do not provide a complete characterisation of zero-minimisable dynamic systems as it is not central to our aims here; we do however provide some preliminary results in this direction. More precisely, consider the conditions (P5) - (P7) below (we implicitly assume that ✄ ✚ ✫ in each case):

• (P6) If ✔ ✞ ✕ ❂ ✫ , then a0 ✁ ✄ ✆ ✞ ✠ ❹ ❨ ✻ .

Condition (P5) says that if all non-valid ✞ -states together with those ✞ -states "chosen" by the result function are compatible with another action's postconditions ( ✞ ✾ ), then any ✞ -states chosen when performing ✞ ✾ should also be chosen when performing ✞ . Notice that this condition implies condition (P3) above. (P6) states that the result function must return at least one possible resultant state if all states satisfying the postconditions of the action are valid. (P7) says that if a state ✘ is chosen as a possible next state when either ✞ or ✞ ✾ is performed, then ✘ should also be chosen when the action (with postcondition) ✞ ➄ ✞ ✾ is performed.

Theorem 3.3 Every zero-minimisable dynamic system satisfies the conditions (P1) - (P3), (P5) - (P7).

The converse of Theorem 3.3 is not true in general. However, for a restricted class of dynamic systems, which we call dense, the conditions (P1) - (P3) and (P5) - (P7) suffice to characterise zero-minimisability. More precisely, we shall say that a dynamic system is dense if and only if every sentence of the object language ☞ corresponds to an action (i.e., ✬ ❨ ☞ ).

Theorem 3.4 If a dense dynamic system satisfies (P1) - (P3), (P5) - (P7), then it is zero-minimisable.

We conclude this section with a brief comment on previous frameworks that encode the concept of minimal change. Perhaps the framework most closely related to our own comes from the area of theory change and it is the one developed by Katsuno and Mendelzon [1992] for modelling belief update. We shall leave a detailed comparison between the conditions presented herein and the postulates proposed by Katsuno and Mendelzon (known as the KM postulates) for future work. Here we simply note that the main difference between the two is that the KM postulates are designed to apply only to dense, zero-minimisable, dynamic systems.

4 Causality andMinimal Change

Recall that one of the main motivations for this work was the desire to formally evaluate claims about the strength of causal theories of action over ones based on the notion of minimal change. In this section we use the foregoing results to analyse two of the most prominent causal theories of action, the first developed by McCain and Turner [1995], and the second by Thielscher [1997].

4.1 McCain and Turner

McCain and Turner [1995] have developed a theory of action that represents causality explicitly. In their framework they introduce a causal connective ➆ where ➇ ➆ ➈ can be read as " ➇ causes ➈ " and referred to as a causal rule. Here ➇ and ➈ are propositional sentences that do not contain ➆ (i.e., ➆ cannot be nested). They then introduce the notion of causal closure ➊ ➋ ✁ ➌ ✠ for a set of sentences ➌ with respect to a set of causal rules ➍ as the smallest set closed under classical deduction that includes ➌ and applies causal rules in the direction of the "arrow" (i.e., no contrapositive-the interested reader is referred to the citation above for the full details). The notation ➎ ➏ ➋ refers to the corresponding (causal) consequence relation: ➌ ➎ ➏ ➋ ➐ if and only if ➐ ✚ ➊ ➋ ✁ ➌ ✠ . The result function can be defined using the following fixed-point equation to be found in McCain and Turner [1995].

We can now establish the following results.

Theorem 4.1 For any set of causal rules ➍ , the result function a0 ➒ ➓ ➋ ✁ ✄ ✆ ✞ ✠ defined by means of (MT), satisfies the conditions (P1) - (P3).

From Theorem 4.1 it follows that the theory of action developed by McCain an Turner is applicable only to minimisable dynamic systems. This is a most curious result for it shows that the conclusions drawn with the aid of causality (as encoded by McCain and Turner) can be reproduced by an appropriately defined minimisation policy. It is also especially interesting in light of recent results reported by Peppas et al. [1999] who show that for McCain and Turner's approach it is in general not possible to construct an ordering over object states such that the minimal object states satisfying the postconditions of an action are those predicted by the McCain and Turner fixed-point equation. This tells us that this approach is not zero-minimisable. We have, however, just shown that this approach is minimisable in a more general sense ↕ (i.e., if one considers meta-states) so this system has a minimality rank greater than zero.

4.2 Thielscher

We shall not describe Thielscher's [1997] approach in depth here. However, the underlying principle is to consider trajectories of state-effect pairs each of which is the result of applying a causal law at a previous state-effect pair (starting with the initial state and action postcondition). The resultant states are those at the end of a trajectory where causal laws no longer apply. We note that Thielscher's system does not satisfy postulates (P1) - (P3) and hence is not minimisable. In particular, Thielscher's result function, which we denote by a0 ➓ violates condition (P1); the postconditions of the action do not necessarily have to hold after applying the action. What would be of some interest however, is to generate from a0 ➓ a new result function a0 ✾ that chooses among the resultant states selected by a0 ➓ the ones that satisfy the postconditions of the occurring action; in symbols, a0 ✾ = ✔ ✞ ✕ ❯ a0 ➓ . One can then examine whether the new function a0 ✾ satisfies the conditions (P2) and (P3). We leave this for future investigation.

5 Discussion

Let us take a step back and examine what we have accomplished thus far. The main result reported herein is a characterisation of the class of dynamic systems amenable to minimisation, in terms of conditions on the result function. Existing causal theories of actions can then be assessed against these conditions to determine the added value (if any) of explicit representations of causality. This is clearly a significant step towards "demystifying" the (comparative) strengths and weaknesses of the notions of causality and minimal change in reasoning about action. Admittedly though in this paper we have not given the whole story (especially as far as "demystifying" causality is concerned). What is missing is a generic model of the use of the concept of causality in reasoning about action (in the same way that preferential structures are such a model for the concept of minimality), based on which a general, formal comparison between causality and minimality can be made. Until such a generic model is available, the best that can be done is evaluations of specific causal theories of action (such as the ones by McCain and Turner [1995] or Thielscher [1997]) against the conditions (P1) - (P3). There is of course still a lot of value in such assessments; showing for example that all existing causal approaches satisfy these conditions would be strong evidence in support of the claim that minimality subsumes causality (at least as far as the range of applicability is concerned). Showing, on the other hand, that some causal approach violates one of the conditions (P1) - (P3), would prove that causality is essential in reasoning about action since it covers domains that are "unreachable" by minimal change approaches. Similar (although weaker) conclusions can be drawn from the satisfaction or violation of (P4) and (P5) - (P7). We have already witnessed that Thielscher's [1997] approach does not satisfy condition (P1). Thus some causal approaches do indeed go beyond what is possible with minimal change. More work needs to be done here to properly classify causal approaches both in regard to each other (with respect to the different causal notions they employ) and also with regard to the Principle of Minimal Change.

It should be noted, that when assessing a theory of action, apart from its range of applicability, a second criterion that is equally important is the conciseness of its representations (a solution to the frame problem ought to be both correct and concise). In this article, conciseness has been left out of the picture altogether. What we have mainly done herein was to axiomatically characterise certain classes of dynamic systems whose result function a0 can be reproduced in terms of preorders ✼ ✽ on states. No consideration was given as to whether ✼ ✽ can be represented concisely or not. As far as our results are concerned, describing ✼ ✽ could be as "expensive" as listing the frame axioms corresponding to a0 , which of course defeats the whole purpose of using minimality. A much more useful result (for practical purposes) would be one that characterises the class of what we might call concisely minimisable dynamic systems; that is, dynamic systems whose result function a0 can be reproduced by preorders ✼ ✽ , which in turn can be represented concisely. 6

Similar considerations apply to causality. Characterising the class of dynamic systems for which causality (in one form or another) can duplicate the result function, although an interesting theoretical result, would not fully address the issue of the applicability of causality in reasoning about action. Further work would be required to identify the domains that are amenable to concise causal descriptions.

Notice, also, that in cases where the range of applicability does not differentiate between causal and minimality-based approaches, conciseness considerations may well favour one over the other. More precisely, if the class of domains at focus is within the range of applicability of both causal and minimal change approaches, the determining factor in choosing between the two could be the "information cost" associated with the usage of each approach.

Notice that, while the concept of minimality has typically been used in the literature to deal with the frame and ramification problems, the nature of condition (M) is such that it requires minimality to deal with the qualification problem as well. Indeed, via condition (M), the preorders of a preferential model are used, not only to determine the set of states a0 ✁ ✄ ✆ ✞ ✠ that result from the application of an action ✞ at an initial state ✄ (frame and ramification problems), but also to determine whether ✞ is at all applicable at ✄ (qualification problem). The latter is decided based on whether a0 ✁ ✄ ✆ ✞ ✠ is the empty set or not (cf. McCain and Turner [1995] who claim this is a derived qualification). One could argue that such an additional burden is perhaps too much from minimality to carry (or that it is even counter-intuitive), and maybe, if liberated from it, minimality could be used in many more situations. More formally, consider the condition (M ✾ ) below:

6 It should be noted that all existing approaches that are based on the concept of minimal change are indeed of that nature; that is, their preorders on states have a concise description, typically in the form of a second-order axiom (sometimes coupled with limited domainspecific information).

Clearly (M ✾ ) is weaker than (M). In fact, it is exactly the weakening of (M) that is needed to disengage minimality from the qualification problem. It would be a worthwhile exercise to reproduce the results of this article, having replaced (M) with (M ✾ ). The class of minimisable systems could be larger, and moreover, we conjecture that under (M ✾ ), strictly minimisable systems are a proper subclass of zerominimisable dynamic systems.

We conclude this section with a remark on minimality ranks. Preliminary considerations suggest that there is a close relation between the minimality rank of a dynamic system on the one hand, and its ontological properties on the other. For example, domains where actions have no ramifications, tend to have lower minimality ranks than domains where ramifications do appear. If this connection can be generalised and formally proved, the minimality rank of a domain could serve as a precise measure of its complexity. More work however needs to be done in this direction.

6 Conclusions

We have developed a formal framework within which we were able to formulate necessary and sufficient conditions under which a dynamic system is minimisable; that is, its result function can be reproduced by an appropriately defined minimisation policy. What is particularly pleasing about these conditions is that they are few in number and relatively easy and intuitive to understand. Our original motivation in this study was to answer the question as to whether recently proposed theories of action involving explicit representations of causality are capable of forms of reasoning not possible via minimal change. We have seen that this is not the case with some approaches (McCain and Turner [1995]) but in others (Thielscher [1997]) the causal reasoning cannot be characterised by the Principle of Minimal Change. Perhaps of wider significance is the fact that the results reported here clearly indicate the range of applicability of the Principle of Minimal Change; one simply needs to verify three properties (viz. (P1) - (P3)).

This work opens up many interesting avenues for future work, various of which were mentioned in the discussion. One of the more pressing is to consider a variety of theories of action, particularly causal ones, and verify which properties they satisfy. This task is well under way and reserved for a much lengthier work. Also of much interest would be to further categorise levels of minimisability and what distinguishes them together with the various theories of action at those levels of minimisability.

Acknowledgments

The authors would like to thank three anonymous referees for their inciteful and generous comments. They would also like to thank Norman Foo, Abhaya Nayak, Mikhail Prokopenko, members of the Cognitive Robotics Group at the University of Toronto, and attendees of the Seminar in Applications of Logic at the City University of New York for enlightening discussions.