A Framework for Decision-Theoretic Planning I: Combining the Situation
  Calculus, Conditional Plans, Probability and Utility
  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.
