Theoretical Foundations for Abstraction-Based Probabilistic Planning
  Modeling worlds and actions under uncertainty is one of the central problems
in the framework of decision-theoretic planning. The representation must be
general enough to capture real-world problems but at the same time it must
provide a basis upon which theoretical results can be derived. The central
notion in the framework we propose here is that of the affine-operator, which
serves as a tool for constructing (convex) sets of probability distributions,
and which can be considered as a generalization of belief functions and
interval mass assignments. Uncertainty in the state of the worlds is modeled
with sets of probability distributions, represented by affine-trees while
actions are defined as tree-manipulators. A small set of key properties of the
affine-operator is presented, forming the basis for most existing
operator-based definitions of probabilistic action projection and action
abstraction. We derive and prove correct three projection rules, which vividly
illustrate the precision-complexity tradeoff in plan projection. Finally, we
show how the three types of action abstraction identified by Haddawy and Doan
are manifested in the present framework.
