Issues in Constructing and Learning Abstract Decision Models

Decision-Theoretic Planning

Volume

Papers from the 1994 AAAI Spring Symposium

Contents

When applying decision theory to problems in planning, the complexity of the domain raises several issues. In particular, planning domains generally require choosing among sequences of actions, whose possible number grows exponentially with length. When each action is described in terms of a mapping from an initial state to a distribution over possible resulting states (as in [Tash 1993]), calculating the consequences of each sequence and maximizing over expected utility of the resulting histories is a huge computational chore. The difficulty of this task demands careful control of computational expenditures, and often simplifying assumptions must be made in order to preserve tractability. One common simplification is to apply decision theory to a reduced decision model, one whose states are sets of finer states in a more complete model. For example, [Dean et al. 1993] apply decision theoretic methods to planning on a stochastic automaton, and cluster together all states lying outside of a certain envelope for purposes of policy determination. This paper discusses some of the issues arising in trying to form a coarse, or abstract, decision model so that work done in planning using such a model provides reasonable results for the original problem. It should be noted that other approaches to controlling the computational expenditures of a planner often involve decisions made on a reduced decision model, so these issues are quite general. For example, when computational effort is controlled using a metalevel architecture, as in [Russell and Wefald 1991], allocation of resources to a computation is not determined on the basis of all the information available to the planner, which is generally adequate to determine the result of the computation itself, but rather on the basis of certain features of the situation which are more easily computed and are used to indicate the expected value of doing the computation. Thus, the metalevel is controlling computations using a decision model which treats various computations sharing certain features as the same. It is a general characteristic of abstract models that the feature set used to condition decisions is reduced from that of the complete model because distinctions between fine states in the same abstract state are ignored.