(For a postscript version of this text, click here for latex version) or latex2e version).
The class of problems being addressed here will first be defined in abstract terms, and will then be discussed from a more applied point of view.
In more complex cases, chronicles may contain observations
that refer to multiple timepoints, action statements that refer
to conditional or composite actions, and other ontologies for
time such as branching time. Also, action symbols and
features/properties may have objects as arguments, for example
......H(25, stateof(tralite4), Green),
expressing that the state of traffic light number 4 is
Green at time 25. Logics whereby one can express and reason
about chronicles are called logics of actions and change.
The research problem and the research task can of course be equivalently formulated in terms of the ``set of conclusions'' instead of the ``set of models''. Possible conclusions from a given chronicle include derived facts (syntactically similar to observations) about the state of the world at other times or in other properties than those that were directly observed.
Different variants of this research problem are obtained by varying the assumptions that lead to the mismatch between intended and classical models. The basic assumption is inertia or ``no change without a known reason''. In the simplest case it means that actions only change those properties of the world which are indicated in the action law, whereas other properties remain constant. This simple case is referred to as strict inertia. Less trivial cases are obtained e.g. if certain static constraints are known for the state of the world, and if it is then necessary to assume that actions cause additional changes, besides those indicated by the action law, in order that the situation resulting from a particular action shall satisfy the static constraints. This case is referred to as ramification, and it will be addressed towards the end of the present article.
Non-deterministic actions pose particular problems in the context of the inertia assumption. One way of dealing with them is to introduce an additional occlusion predicate X(f,t), expressing that the value of the feature f may change during the timestep [t-1,t].
The other usage is for cognitive robotics, that is, for allowing an intelligent robot to reason about its own actions and its effects, as well as about the effects of natural events and of actions taken by other robots in the same habitat. In this case, the actions are implemented as programs in the robot controller system, and reasoning about the actions is a particular kind of reasoning about programs. It is particular in the sense that one reasons not only about the program itself, but also about spontaneous events in the world where the robot (and indirectly, the program) is set to operate.
The notation for chronicles that was exemplified above allows one to characterize the duration of an action in terms of metric time. The consequent side of an action law is not restricted to specifying the final result of an action; it may also characterize the duration of the action (as a constraint on the combination of s and t), and the state of the world at intermediate points during the execution of the action. Logics of actions and change are therefore potential candidates for reasoning about hard real-time programs. However, that aspect has not been investigated very much yet, and will not be addressed in the present article.
Typically, one wishes action laws to be as compact as possible, so ideally they should only have to specify some of the changes that are due to an action, leaving other resulting changes to be inferred by logical means. This topic is closely related to the update problem in databases.
A preference relation is a strict partial order on models.
Many simple cases of selection functions can be defined directly
in terms of a preference relation <<, so that the set of
selected models is
......Min(<<, Y),
meaning the set of <<-minimal classical models. More sophisticated
selection functions can be obtained in the following fashions:
The reasons for analyzing the range of applicability should be fairly evident. One is not always interested in finding and using the method with the largest range of applicability: it is to be expected that there are some methods with a fairly narrow range of applicability, but which allow more efficient implementation. If such a method exists, and its range of applicability does include those chronicles that may arise in a given application, then one will be happy to use that method for the application at hand.
The range of applicability may be significantly improved
through the use of the following concepts. A pretransformation
G is a mapping from chronicles to chronicles such that
Mod(Y) = Mod(G(Y)).
An entailment method is a pair
< G, S > where
G is a pretransformation and S is a selection
function
whose arity corresponds to the structure of the chronicle.
If S is unary, then an entailment method
<G,S>
assigns the set
S[G(Y)]
of models to each chronicle Y. It is correct for
the chronicle Y iff
......S[G(Y)] = Mod(Y).
Similarly, if S is a binary selection function, and
G(<Y1,Y2 >) =
<Y1',Y2'>,
then <G,S> is correct for
<Y1,Y2>
iff
S(<[Y1'],[Y2']>) =
Mod(<Y1,Y2>).
Pretransformations may be used, for example, for adding timing
statements which exclude concurrent execution of actions, if the
intended models only allow sequentially executed actions.
In order to identify the range of applicability for an entailment method, one needs the following formal tools:
In the earlier publications I have defined the underlying semantics and the taxonomy for the case of strict inertia, together with precise formulations of the syntax and of the classical semantics, which are of course also needed.