Information Technology Reference
In-Depth Information
obviously belongs to that category. But to stick to our current domain, sup-
pose it is totally dark so that it is impossible to tell the two switches apart.
Nonetheless we want to switch up one of them (knowing both are currently
down). Putting this plan into execution, there are two possible outcomes: We
either hit the rst or else the second switch. This may be formalized by the
two action laws
transforms
f:
up
(
s
1
)
g
into
f
up
(
s
1
)
g
switch-one-up
(1.3)
transforms
f:
(
s
2
)
g
into
f
(
s
2
)
g
switch-one-up
up
up
According to Denition 1.2.2 these two laws are simultaneously applicable
to the state
f:
up
(
s
1
)
; :
up
(
s
2
)
; :
light
g
. Their respective application de-
termines two dierent successor states, viz.
f
up
(
s
1
)
; :
up
(
s
2
)
; :
light
g
and
f:
up
(
s
1
)
;
up
(
s
2
)
; :
light
g
.Inany
particular
situation of course only one of
these possibilities will actually occur. Which one this will be, however, cannot
be predicted, at least not on the basis of the (restricted) knowledge about
the domain. This is what makes the action in question non-deterministic.
7
The concept of action laws dening how the execution of actions aects
the particles of state descriptions, viz. the fluents, provides us with a basic
formalism to specify action domains. The semantics of these specications is
given by complete state transition models.
Denition 1.2.3.
A
basic action domain
D is a 4-tuple
(
E; F; A; L
)
where
E is a set of entities, F a set of fluent names, A a set of action names, and
L is a set of action laws. The
transition model
of D is a total mapping
from state-action pairs into (possibly empty) sets of states such that S
0
2
(
S; a
)
i S
0
is a preliminary successor of S and a.
Any (basic) action domain provides general, i.e., situation-independent knowl-
edge as to the impact of performing actions. Exploiting this knowledge when
drawing conclusions about particular scenarios within a domain is our next
concern.
A scenario is given by information as to particular developments of the
part of the world which has been specied as action domain. In most cases,
this information is incomplete in that only for some fluents at some stages the
truth-values are known. The general task then is to draw the right conclusions
as to the truth-values of other fluents at other stages. Of course this requires
knowledge of the general eects of actions, given by the formal specication
of the underlying action domain.
As a very simple example, suppose we observe that after switch
s
1
has
been toggled it is in the upper position. Then it is reasonable to conclude
that the switch was down beforehand. This should follow from our knowl-
edge as to the general eects of toggling switches, which is provided by
the two action laws dened in (1.2). Formally, we will use expressions like
7
Although non-determinism is not amongst the basic requirements for action
theories, it will be vital for both the Ramication and Qualication Problem.
