A Framework for Decision-Theoretic Planning I: Combining the Situation Calculus, Conditional Plans, Probability and Utility
This work addresses the challenge of combining logical and probabilistic reasoning for AI planning, offering a foundational approach that could impact decision-making systems, though it is incremental in building on existing frameworks like situation calculus and GOLOG.
The paper tackles the problem of integrating logical action representations with decision theory for planning under uncertainty, proposing a framework that combines situation calculus, conditional plans, probability, and utility to define expected utility and find optimal plans, and demonstrates that their representation is exponentially more compact than probabilistic STRIPS.
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.