Information Technology Reference
In-Depth Information
toggle
1
, and action laws
toggle
(
x
)
transforms
f
up
(
x
)
g
into
f:
up
(
x
)
g
toggle
(
x
)
transforms
f:
up
(
x
)
g
into
f
up
(
x
)
g
Suppose further given the
n
state constraints
light
i
(
s
0
)
^
(
s
i
)
up
up
(1
i n
) and, for each
i
=1
;:::;n
, these four causal relationships:
up
(
s
0
) causes
light
i
if
up
(
s
i
)
:
up
(
s
0
) causes
:
light
i
if
>
light
i
if
>
(2.8)
(Notice the size of this specication, which is linear in
n
as opposed to
the exponential number of action laws needed when formalizing this do-
main without the concept of indirect eects.) Now, suppose all switches
are closed except for
(
s
i
) causes
light
i
if
(
s
0
)
:
(
s
i
) causes
:
up
up
up
and, hence, all light bulbs are o. That is, let
s
0
S
=
f:
light
n
g
be the current,
acceptable state. Performing action
toggle
(
s
0
) in this state yields the pre-
liminary successor
S
0
=
f
(
s
0
)
;
(
s
1
)
;:::;
(
s
n
)
; :
light
1
;:::;:
up
up
up
light
n
g
along with the direct eect
E
=
f
up
(
s
0
)
g
. Apparently, the state-eect pair
(
S
0
;E
) allows the application of all
n
causal relationships of the form
up
(
s
0
) causes
light
i
if
up
(
s
i
) where
i
=1
;:::;n
. Whichever of these is
executed rst, the other
n −
1 relationships remain applicable in the result-
ing state-eect pair, and so forth. Thus there exist
n
! dierent sequences,
all of which obviously result in the same causal successor state, namely,
f
(
s
0
)
;
(
s
1
)
;:::;
(
s
n
)
; :
light
1
;:::;:
up
up
up
(
s
0
)
;
(
s
1
)
;:::;
(
s
n
)
;
light
1
;:::;
light
n
g
, i.e., where all light bulbs
up
up
up
are now active.
All application sequences coming to the identical result in this example
raises the question whether order irrelevance holds in general. The following
proposition states that indeed any permutation of a sequence of causal rela-
tionships arrives at the same conclusion, provided the permuted sequence is
applicable.
Proposition 2.4.1.
Let E and F be sets of entities and fluent names,
respectively, S
0
be a state, and E
0
a set of fluent literals. Furthermore, let
r
1
;:::;r
n
be a sequence of causal relationships (n
0
) which is applicable
to
(
S
0
;E
0
)
and which yields
(
S
0
;E
0
)
;
fr
1
g
(
S
1
;E
1
)
;
fr
2
g
::: ;
fr
n
g
(
S
n
;E
n
)
Then, for any permutation r
(1)
;:::;r
(
n
)
which is also applicable to
(
S
0
;E
0
)
and which yields
(
S
0
;E
0
)
;
fr
(1)
g
(
S
1
;E
1
)
;
fr
(2)
g
::: ;
r
f
(
n
)
g
(
S
0
n
;E
0
n
)
we have S
n
=
S
0
n
and E
n
=
E
0
n
.
