VAL@SAIL.STANFORD.EDU.UUCP (02/06/87)
Commonsense and Nonmonotonic Reasoning Seminar
OPTIMAL HISTORIES: A TEMPORAL APPROACH TO DEFAULT REASONING
Van Nguyen
IBM T.J.Watson Research Center
Yorktown Heights, NY 10598
Thursday, February 12, 4pm
Bldg. 160, Room 161K
A new technique in default reasoning (non-monotonic reasoning)
is presented. It is based on the notion of optimal histories.
Intuitively, an optimal history contains a sequence of sets S(n),
n = 0, 1, ..., of first-order formulae. Each S(n) is a description of
the state of the world, as seen by some computing agent, at time
(situation) n. State S(n+1) is computed from S(n) and the event
(action) E(n+1) that occurs at time n+1 by a default-inference rule,
so that facts that are true in S(n) tend to stay true in S(n+1), unless
something falsifies them. Other parameters of an optimal history are
the deductive ability of the computing agent and a set of basic axioms
and constraints. Thus an optimal history is a description of how the
world changes with new events, as time passes.
The technique is applicable to such problems in default reasoning as
belief revision, dealing with exceptions to general rules, the frame
problem of McCarthy and Hayes, the qualification problem of McCarthy,
and the temporal projection problem of Hanks and McDermott. Optimal
histories can also be formulated in the framework of temporal logic of
Manna and Pnueli.