Information Technology Reference
In-Depth Information
Σ
be a fluent of
Γ
, and
-
G
=(
V,E
)
be a fluent graph for
Γ
.
Furthermore, let
s
1
→
-
f
∈
s
2
→
...
→
s
m
+1
denote a legal sequence of states of
Γ
, that
is, for all
i
with
0
<i
≤
m
there is a joint action
A
i
, such that:
s
i
+1
=
u
(
A
i
,s
i
)
∧
(
∀r ∈ R
)
l
(
r, A
i
(
r
)
,s
)
If
Δ
(
s
1
,f
)=
n
, then there is no legal sequence of states
s
1
→ ... → s
m
+1
with
f
∈
s
m
+1
and
m<n
.
Proof.
We prove the theorem by contradiction. Assume that
Δ
(
s
1
,f
)=
n
and there is a
legal sequence of states
s
1
→
s
m
+1
and
m<n
. By Definition 2,
for every two consecutive states
s
i
,
s
i
+1
of the sequence
s
1
→
...
→
s
m
+1
with
f
∈
...
→
s
m
+1
and for
every
f
i
+1
∈
s
i
+1
there is an edge
(
f
i
,f
i
+1
)
∈
E
such that
f
i
∈
s
i
or
f
i
=
∅
.
Therefore, there is a path
f
j
,...,f
m
,f
m
+1
in
G
with
1
≤
j
≤
m
and the following
properties:
-
f
i
∈
s
i
for all
i
=
j, ..., m
+1
,
-
f
m
+1
=
f
,and
-
either
f
j
∈
s
1
(e.g., if
j
=1
)or
f
j
=
∅
.
Thus, the path
f
j
,...,f
m
,f
m
+1
has a length of at most
m
.
Consequently,
Δ
(
s
1
,f
)
≤
m
because
f
j
∈
s
1
∪ {∅}
and
f
m
+1
=
f
.However,
Δ
(
s
1
,f
)
≤
m
together with
m<n
contradicts
Δ
(
s
1
,f
)=
n
.
4
Constructing Fluent Graphs from Rules
We propose an algorithm to construct a fluent graph based on the rules of the game.
The transitions of a state
s
to its successor state
s
are encoded fluent-wise via the
next
rules. Consequently, for each
f
∈
s
there must be at least one rule with the head
next
(f')
. All fluents occurring in the body of these rules are possible sources for an
edge to
f
in the fluent graph.
For each ground fluent
f
of the game:
1. Construct a ground disjunctive normal form
φ
of
next
(
f
)
,i.e.,aformula
φ
such
that
next
(
f
)
φ
.
2. For every disjunct
ψ
in
φ
:
-
Pick one literal
true
(
f
)
from
ψ
or set
f
=
∅
⊃
if there is none.
-
Add the edge
(
f,f
)
to the fluent graph.
Note, that we only select one literal from each disjunct in
φ
. Since, the distance function
Δ
(
s, f
)
obtained from the fluent graph is admissible, the goal is to construct a fluent
graph that increases the lengths of the shortest paths between the fluents as much as
possible. Therefore, the fluent graph should contain as few edges as possible. In general
the complete fluent graph (i.e., the graph where every fluent is connected to every other
fluent) is the least informative because the maximal distance obtained from this graph
is
1
.
