Information Technology Reference
In-Depth Information
weakened version of this postulate. The general diculty with this is that
one has to perform some sort of a tightrope walk. On the one hand, rigorous
persistence of all non-aected fluents is still required; on the other hand,
arbitrarily complex chains of indirect eects need to be accounted for.
Let us try a rst step forward on the tightrope. Indirect eects are to be
considered whenever the application of an action law results in a state which
violates one or more state constraints. Obviously, such a state perfectly ac-
counts for persistence|but not at all for indirect eects. On the other hand,
notice that the successor state we look for, that is, which accounts for all
indirect eects, is obviously to be found among the acceptable states, i.e.,
those which satisfy all constraints. In the worst case, however, an arbitrary
one of these states does not at all account for persistence. But now suppose
we combine the one extreme with the other. Namely, we select among all
acceptable states the one that shares the most fluent literals with the prelim-
inary successor state.
4
Then we have accounted both for indirect eects (since
no constraint is violated) and for persistence to the largest possible extent
(since no more fluents have changed than absolutely necessary to obtain an
acceptable state). In other words, and from a more constructive perspective,
the idea is to take the preliminary successor and to change the truth-values
of as few as possible fluents|of course without touching one of the direct
eects|until a state results that satises the state constraints.
To see how this approach works, recall the circuit of Fig. 2.1. We have
seen that toggling the switch in the current state, viz.
f:
g
,
yields the preliminary successor
S
0
=
f
up
(
s
1
)
; :
light
g
, which violates the
underlying state constraint,
(
s
1
)
; :
up
light
light
up
(
s
1
). The state closest to
S
0
in
satisfying this formula and in still containing the direct eect,
up
(
s
1
), is
T
=
f
g
. This is indeed the intended and intuitively expected
successor state: The light went on as indirect eect of closing the switch.
The following formal account of this approach is based on a comparative
notion of distance between states. We introduce the concept of
minimizing-
change successors
, which are obtained according to the above description.
Denition 2.2.1.
Let D be a basic action domain. If S; T; T
0
are states,
then T is
closer
to S than T
0
, written T
S
T
0
,i T n S
T
0
n S.Let
C be a set of state constraints, S a state which is acceptable (wrt. C), and
a an action. A state T is
minimizing-change successor
of S and a i the
following holds: There exists a preliminary successor S
0
(
s
1
)
;
up
light
of S and action a
obtained through direct eect E such that
1. E T ,
2. T is acceptable, and
3. there is no T
0
S
0
T such that E T
0
and T
0
is acceptable.
4
Actually this state `closest' to the preliminary successor need not be unique,
see below.
