Information Technology Reference
In-Depth Information
a scenario description. Our theory satises the most fundamental adequacy
requirement, namely, that action laws concentrate on the part of the world
which is aected when the action is performed. On the other hand, the ba-
sic theory makes two very strong assumptions. First, it requires any action
law to contain the entire eect of the action it describes, that is, not only
the direct but also all possible indirect eects. This is a consequence of the
assumption that no fluent changes which is not mentioned in an action law.
Second, the theory asserts that an action is guaranteed to succeed once all
of the specied conditions are true in a state. Both assumptions, their inad-
equacy, and a much more sophisticated action theory which overcomes these
assumptions are subject of the remaining chapters.
1.3 Bibliographic Remarks
Formal action theories have not been developed until very recently. The un-
derlying idea of formalizing reasoning about actions and planning, however, is
much older. In fact, automating the ability of common sense to reason about
actions and their eects was among the very rst issues raised in Articial
Intelligence research [75]. There the belief was advocated that multifarious
intelligent behavior relies on the ability to maintain a mental model of the
world and to draw the right conclusions about observations and intentions.
The historically rst formal approach to reasoning about actions was a
pure rst-order encoding of some example action domains and scenarios.
This encoding introduced the so-called
Situation Calculus
paradigm, which
satises the fundamental requirement for adequacy in that actions are spec-
ied by their eects. In so doing, the Situation Calculus brings along the
Frame Problem
[74], which denotes the problem both of how to represent,
in logic, the general assumption that any non-aected fluent keeps its truth-
value when an action is performed, and of how to reason eciently with this
representation.
10
While the earliest Situation Calculus-based encodings were intuitively
plausible, the solutions to the Frame Problem suggested and employed in
this context were cumbersome and inecient [43]. Most of subsequent work
in this eld was therefore devoted to nding better solutions to this prob-
lem. It is beyond all question that conceivable progress had been made in
this regard,
11
but it turned out that a considerable price has been paid to-
wards this end: Axiomatizations of action scenarios seem to become lesser
10
Philosophers have dealt with problems related to actions and their eects for
much longer, in the context of causality. Interestingly enough, however, they
seem never to have struggled with the adequacy of action specications. This
is indicated by the fact that the Frame Problem has not been encountered
until AI researchers started to investigate action formalisms [22]. Even later
formal approaches to the causality phenomenon, such as [120, 1], presuppose
exhaustive state transition functions.
11
more to this in Section 2.10
