The Rami cation Problem - Challenges for Action Theories - page 33

Proof. Let f be an arbitrary but xed fluent. By k f we denote the number
(possibly zero) of relationships r i = " i causes f if i , and by k f the number
(possibly zero, too) of relationships r j = " j causes :f if j (1 i; j n ).
Since a causal relationship " i causes f if i can only be applied to some
( S i− 1 ;E i− 1 )if :f 2 S i− 1 (and vice versa in case of indirect eect :f ), the
values for k f and k f

determine the nal truth-value of f as follows:

1. If f 2 S , then either k f = k f or k f = k f − 1. In the former case
we have f 2 S n . We also have f 2 E n if k f > 0, otherwise f 62 E n
and :f 62 E n since no causal relationship aects f . In the latter case
we have both :f 2 S n and :f 2 E n .
2. If :f 2 S , then either k f = k f or k f = k f + 1. In the former case we
have :f 2 S n . We also have :f 2 E n if k f > 0, otherwise :f 62 E n
and f 62 E n since no causal relationship aects f . In the latter case we
have both f 2 S n and f 2 E n .
Since the permutation r (1) ;:::;r ( n ) contains exactly the same causal re-
lationships as the original sequence, they do not dier in the values for k f
and k f .Thus S n and S 0 n agree as far as f is concerned, and so do E n
and E 0 n . Fluent f being an arbitrary choice proves the claim.

Qed.

While this result proves general invariance with regard to applicable per-
mutations of causal relationship sequences, it does not imply confluence of
the whole procedure in general. In fact, a dierent selection at the beginning
may allow for the application of a completely dierent collection of causal
relationships. If two chains of relationships do not contain identical elements,
then neither is a permutation of the other and our Proposition 2.4.1 does
not apply. This is, however, not at all a drawback or even fallacy, as one
might guess at rst. Rather it allows to accommodate actions which are de-
terministic as far as their direct eects are concerned but non-deterministic
as regards the indirect eects they possibly trigger. That is, even if a unique
preliminary successor exists, performing an action in some state may ad-
mit more than one possible causal successor state. An example for an action
that is non-deterministic in this sense occurs in a domain to be presented in
Section 2.6.
The opposite to the existence of multiple successor states is that no suc-
cessor at all can be found despite one or more action laws are applicable to the
state at hand. That is, no chain of causal relationships manages to transform
a preliminary successor into an acceptable state. This hints at additional,
implicit preconditions for the action in question|preconditions which derive
from state constraints. Section 2.8 will be devoted to this phenomenon. In
the following section, we rst raise another central issue, namely, how causal
relationships and the underlying state constraints are related|in particular,
we seek a way to automatically extract the former from the latter.