Information Technology Reference
In-Depth Information
The condition
T n S
T
0
n S
for
T
S
T
0
states that
S
and
T
dier in
strictly less fluent literals than
S
and
T
0
do. The denition then says that a
minimizing-change successor is a state which contains the direct eect of the
action in question (clause 1), which satises the state constraints (clause 2),
and which is closest to a preliminary successor
S
0
in so doing (clause 3).
Example 2.2.1.
Let
D
be the domain consisting of entity
s
1
, fluent names
up
1
and
light
0
, action name
toggle
1
, and the familiar action laws
toggle
(
x
)
transforms
f
up
(
x
)
g
into
f:
up
(
x
)
g
(
x
)
transforms
f:
(
x
)
g
into
f
(
x
)
g
toggle
up
up
Along with state constraint
C
=
f
light
up
(
s
1
)
g
, this formalizes our
circuit of Fig. 2.1.
Let the current state be the acceptable
f:
g
. The only pre-
liminary successor state of
S
and
toggle
(
s
1
)is
S
0
=
f
up
(
s
1
)
; :
light
g
, ob-
tained through direct eect
E
=
f
up
(
s
1
)
g
. Now, there is just one acceptable
state containing
E
, viz.
f
up
(
s
1
)
;
light
g
. Being the only candidate, this state
is of course the one closest to
S
0
, hence it is the unique minimizing-change
successor when performing
toggle
(
s
1
) in the state
f:
up
(
s
1
)
; :
light
g
.
Our rst approach to the Ramication Problem works ne with our small
example domain. The interested reader may verify, for instance, that if in the
successor state obtained above we toggle the switch again, then not only does
it take its original position but also the light is o in the resulting minimizing-
change successor. Or, suppose that in the current state depicted in Fig. 2.1
we perform a non-deterministic action to the eect that the switch may or
may not get closed, then there are two minimizing-change successor states:
Either the switch is up and light is on, or else the position of the switch has
not changed and the light stays o.
For a general assessment of the approach of minimizing change, this ob-
servation is crucial: All fluents of a state constraint which are not among the
direct eects have equal right to change their value in case this constraint is
violated by the preliminary successor at hand. This appears to be no prob-
lem as long as only two fluents are involved in a constraint, one of which
must have changed so that this constraint became violated.
5
As soon as a
state constraint relates three or more fluents, however, it may be erroneous
to consider equally possible all state adaptations that correct a violation. To
illustrate this, we enhance our electric circuit by a second switch as shown in
Fig. 2.3. This|at rst glance innocent|modication has a surprising eect
on the applicability of our rst approach to the Ramication Problem.
up
(
s
1
)
; :
light
Example 2.2.2.
Let
D
be the domain consisting of entities
s
1
and
s
2
, fluent
names
up
1
and
light
0
, action name
toggle
1
, and the following action laws.
5
Surprisingly enough, even in this simple case the approach may lead to the
wrong conclusion, e.g., if applied to a scenario discussed later, in Section 2.8.
