Decision Theory, the Situation Calculus and Conditional
Plans
Linköping Electronic Articles in Computer and Information
Science, Vol 3 (1998):nr 8. http://www.ep.liu.se/ea/cis/1998/008/
June 15, 1998.
Under discussion,
The Electronic Transactions on Artificial Intelligence.
Abstract
This paper shows how to combine decision theory and logical
representations of actions in a manner that seems natural for both.
In particular, we assume an axiomatization of the domain in terms of
situation calculus, using what is essentially Reiter's solution to the
frame problem, in terms of the completion of the axioms defining the
state change. Uncertainty is handled in terms of the independent
choice logic, which allows for independent choices and a logic program
that gives the consequences of the choices. The same framework handles
both frame and ramification axioms. As part of the
consequences are a specification of the utility of (final) states, and
how (possibly noisy) sensors depend on the state. The robot adopts
conditional plans, similar to the GOLOG programming language. Within
this logic, we can define the expected utility of a conditional plan,
based on the axiomatization of the actions, the sensors and the
utility. Sensors can be noisy and actions can be stochastic. The
planning problem is to find the plan with the highest expected
utility. This representation is related to recent structured
representations for partially observable Markov decision processes
(POMDPs); here we use stochastic situation calculus rules to specify
the state transition function and the reward/value function.
You can get the
pdf or postscript.
One of the features of ETAI is the Online
Discussion. You are welcome to participate.
There is also a complete
axiomatization of the example in ICL as well as ICL
interpreter that runs the code (this is both a latex file and a
Sicstuc Prolog file). Or you can get
the ICL code distribution.
Related Papers
D. Poole, The Independent Choice Logic for
modelling multiple agents under uncertainty.
D. Poole, Abducing Through Negation As
Failure: Stable models in the Independent Choice Logic.
Last updated 11 June 1998 - David Poole