Information Technology Reference
In-Depth Information
relationships. Formally, this so-called
influence information
is specied as a
binary relation on the set of fluents.
Denition 2.5.1.
Let E and F be sets of entities and fluent names, respec-
tively. An irreflexive binary relation I on the set of fluents is called
influence
information
.
If (
f
1
;f
2
)
2I
, then this is intended to denote that a change of fluent
f
1
's
truth-value potentially aects the truth-value of fluent
f
2
. For convenience, a
pair in
I
may contain variables, thus representing all of its ground instances.
Example 2.5.1.
Consider the entities
E
=
f
s
1
;
s
2
;
s
3
g
along with the fluents
F
=
f
s
2
may influence the
light but not vice versa nor do they mutually interfere (c.f. Fig. 2.4). Likewise,
s
1
up
1
;
light
0
;
relay
0
g
. The two switches
s
1
and
and
may influence the relay, which in turn potentially aects the
s
3
position of
s
2
. Thus the correct influence information
I
is
f
(
up
(
s
1
)
;
light
)
;
(
up
(
s
2
)
;
light
)
;
(
up
(
s
1
)
;
relay
)
;
(
up
(
s
3
)
;
relay
)
;
(
relay
;
up
(
s
2
))
g
(2.9)
Notice how the twofold nature of
up
(
s
2
) is reflected in this influence
information: The fluent occurs both as rst (the active) component in
the pair (
up
(
s
2
;
light
) and as second (the passive) component in the
pair (
relay
;
up
(
s
2
)). This is why it was impossible to globally categorize
this fluent as either primary or secondary.
Our two switches which are connected by a spring (recall Fig. 2.5) show
that influence information may induce cycles and even be symmetrical.
Example 2.5.2.
Let
E
=
f
s
1
;
s
2
g
and
F
=
f
up
1
g
. The two switches being
mutually dependent, the correct influence information
I
is the following.
f
(
up
(
s
1
)
;
up
(
s
2
))
;
(
up
(
s
2
)
;
up
(
s
1
))
g
Given correct information of potential influence, causal relationships are
extractible from state constraints as follows. For the sake of clarity, let us
rst focus on quantier-free, i.e., propositional fluent formulas. The general
idea is investigating all potential ramications and excluding those which
do not respect the notion of influence. To this end, we consider all possible
violations of a state constraint and formulate suitable causal relationships
which help `correct' this. Let us get more precise. Suppose
C
is a state
constraint. First we construct the minimal conjunctive normal form (CNF, for
short)
11
of this formula. Obviously,
C
is violated if and only if some conjunct
11
A CNF of a (non-tautological, non-contradictory) formula
C
is some logical
equivalent of the form
C
1
^ :::^ C
n
(
n
1) such that each
C
i
is of the form
`
i
1
_ ::: _ `
im
i
(
m
i
1) with each
`
ij
being a fluent literal. The
minimal
CNF is a CNF such that for each conjunct
C
i
=
`
i
1
_ :::_ `
im
i
there is no
strict subset
L
f`
i
1
_ :::_ `
im
i
g
such that
C j
=
W
`2L
`
. The minimal CNF
is unique modulo associativity, commutativity, and idempotency of
^
and
_
.
