Representations for Decision-Theoretic Planning: Utility Functions for Deadline Goals

Symbolic (AI) planning techniques and decision theory have complementary strengths and weaknesses. Symbolic planning provides a computational theory of plan generation, but under unrealistic assumptions: perfect information and control over the world and a restrictive model of actions and goals. Decision theory provides a normative model of choice under uncertainty, but offers no guidance as to how the planning options are to be generated. Our goal is to integrate the two approaches into a theory that preserves decision theory's model of choice while exploiting the computational techniques of symbolic planners. In order to do so we must confront the relationship between a symbolic planner's goals and a decision-theoretic agent's utility function. This paper focuses on a particular class of goals: those involving a temporal deadline. We provide a formal definition for deadline goals, show how to represent partial goal satisfaction, demonstrate how corresponding utility functions can be built relative to those goals, and suggest how the goal information can be used to limit a planning algorithm's inference.