Information Technology Reference
In-Depth Information
f%
1
;:::;%
m
g
=
Ψ
n
n Ψ
n−
1
(2.12)
be the set of all fluent literals that are added to
Ψ
n−
1
to obtain
Ψ
n
. Then
there exist
m
causal relationships
"
1
causes
%
1
if
1
;:::;"
m
causes
%
m
if
m
such that
j
2 Ψ
n−
1
,
%
j
62 Ψ
n−
1
, and
"
j
2
n−
1
for each 1
j m
.
Consider the rst relationship, i.e.,
r
1
=
"
1
causes
%
1
if
1
. According to
the induction hypothesis, we know
Ψ
n−
1
Th
(
S
n−
1
) and
n−
1
=
E
n−
1
.
Consequently,
1
is true in
S
n−
1
and
"
1
2 E
n−
1
. Moreover, we have that
:%
1
2 S
n−
1
, for assuming the contrary leads to the following contradiction.
Given that
%
1
2 S
n−
1
, in case
%
1
2 E
n−
1
we nd that
%
1
2 Ψ
n−
1
due to
E
n−
1
=
n−
1
and
n−
1
Ψ
n−
1
|which contradicts
%
1
62 Ψ
n−
1
according
to Equation (2.12). In case
%
1
62 E
n−
1
,wehave
%
1
2 S
n−
1
implies
%
1
2 S
.
From
%
1
2 Ψ
n
S
i
=0
Ψ
i
=
T
it follows that
%
1
2
(
S \ T
)
Ψ
0
Ψ
n−
1
|
which again contradicts
%
1
62 Ψ
n−
1
according to Equation (2.12).
Thus we can apply relationship
r
1
to the state-eect pair (
S
n−
1
;E
n−
1
).
Consider, now, the second causal relationship
r
2
=
"
2
causes
%
2
if
2
. Just
like
r
1
, relationship
r
2
is applicable to (
S
n−
1
;E
n−
1
). We have to prove
that it is still applicable after having applied
r
1
. Condition
"
2
2 E
n−
1
does not become violated, for otherwise we had
"
2
=
:%
1
, which would
imply
:%
1
2 E
n−
1
=
n−
1
Ψ
n−
1
Ψ
n
, which contradicts
%
1
2 Ψ
n
according to Equation (2.12). Condition
:%
2
2 S
n−
1
as well does not be-
come violated, for otherwise we had
%
1
=
%
2
, which contradicts the left
hand side of Equation (2.12) being a set. Finally, condition
2
2Th
(
S
n−
1
)
does not become violated because
2
2 Ψ
n−
1
and
Ψ
n−
1
Th
(
S
n−
1
) imply
2
2Th
((
S
n−
1
nf:%
1
g
)
[f%
1
g
) since
Ψ
n−
1
does not contain
%
1
nor
:%
1
.
Thus we can successively apply all
m
causal relationships to (
S
n−
1
;E
n−
1
).
The overall resulting state-eect pair (
S
n
;E
n
), where
S
n
=(
S
n−
1
nf:%
1
;:::;:%
m
g
)
[f%
1
;:::;%
m
g
E
n
=
E
n−
1
[f%
1
;:::;%
m
g
satises the claim because
Ψ
n
Th
(
S
n
) and
n
=
E
n
.
Now, since there exists only a nite number of changes from
S
to
T
,
we have
T
=
f`
:
` 2
S
i
=0
Ψ
i
g
=
f`
:
` 2 Ψ
n
g
for some smallest number
n 2
IN
0
. The induction proof ensures the existence of some (
S
n
;E
n
) such
that
Ψ
n
Th
(
S
n
). Because
f`
:
` 2 Ψ
n
g
=
T
is a state, this implies
T
=
S
n
.
Consequently, ((
S n C
)
[ E;E
)
;
R
(
T;E
n
), that is,
T
is causal successor
state.
Qed.
While this result shows that causal relationships allow to obtain any
causal minimizing-change successor, the converse is not true. That is, there
may exist causal successor states which do not obey the request for mini-
mizing change. To illustrate this, we further extend (for the last time) our
electric circuit. This new example shows that minimizing change might be a
policy too restrictive to account for all possible successor states. It is obvi-
ously necessary to consider a non-deterministic action to this end, for there
must be at least two successor states, one of which is non-minimal.
