A Framework for Decision-Theoretic Planning I:
Combining the Situation Calculus, Conditional Plans, Probability and Utility
In E. Horvitz and F. Jensen (Eds.) Proc. Twelfth Conference on Uncertainty in
Artificial Intelligence, Portland Oregon, August 1996, 436-445.
Abstract
This paper shows how we can combine logical representations of actions
and decision theory in such 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. As part of the
consequences are a specification of the utility of (final) states.
The robot adopts robot 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
uncertainty and the utility. The `planning' problem is to find the
plan with the highest expected utility. This is related to recent structured
representations for POMDPs; here we use stochastic situation
calculus rules to specify the state transition function and the
reward/value function. Finally we show that with stochastic frame
axioms, actions representations in probabilistic STRIPS are
exponentially larger than using the representation proposed here.
You can get the paper.
Last updated 14 May 96 - David Poole