This paper provides a formal and practical framework for sound abstraction of prob abilistic actions. We start by precisely defining the concept of sound abstraction within the context of finite-horizon plan ning (where each plan is a finite sequence of actions). Next we show that such abstrac tion cannot be performed within the tra ditional probabilistic action representation, which models a world with a single prob ability distribution over the state space. We then present the constraint mass as signment representation, which models the world with a set of probability distributions and is a generalization of mass assignment representations. Within this framework, we present sound abstraction procedures for three types of action abstraction. We end the paper with discussions and related work on sound and approximate abstraction. We give pointers to papers in which we discuss other sound abstraction-related issues, in cluding applications, estimating loss due to abstraction, and automatically generating abstraction hierarchies. Recently there have been a number of proposed tech niques to reduce the running time complexity of prob abilistic and decision-theoretic planning [2, 11, 8, 1, 7] . [2, 1] . These approaches suggest that approximate abstraction is used to reduce the size of the input planning problem by abstracting away unim portant detail. In contrast, sound abstraction . tends to be employed only in some phases of the planmng algo rithm and aims at reducing the time necessary to find the optimal plans. The distinguishing characteristic of sound abstraction is that it guarantees the plan ner never jumps to false conclusions because inferences made at abstract levels must be consistent with those made at lower levels. Examples of sound abstraction approaches are BURIDAN [11] and DRIPS [7] . There has been little work attempting to formal ize sound abstraction techniques for probabilistic planning despite the fact that such techniques are commonly used by several planners (e.g ., BURIDAN, DRIPS ) , and that they are promising f � r Bayesian net work inference, decision tree evaluatiOn, as well as qualitative planning approaches. Developing a for mal framework for sound abstraction involves several major tasks, including the following: First, a gene : al representation framework must be developed, wh1ch defines the concepts of state , world, action, plan, pro jection, expected utility, etc . . Within this frame "':' ork , the concept of sound abstractiOn can then be prec1sely defined. Second, a concrete representation framework must be developed. This means giving well-defi ned syntax and semantics for worlds, actions, and plans; as well as developing procedures for projecting plans, and procedures for computing the expected utility of a plan. Third, within the concrete representation frame work, sound abstraction types must be identified. Pro cedures for creating an abstract entity from member entities -such as creating the description of an ab stract actions from the member actions -must be de veloped. And fourth, procedures for estimating infor mation loss due to abstraction must be developed. In a previous paper [8], we attempted to address the first three issues. We gave justifications for sound action abstraction. We then identified several use ful types of action abstraction and presented proce dures for creating the abstractions. But because we were working within the traditional probabilistic ac tion representation (henceforth the SPD representa tion), which models a world with a single probabil ity distribution, the abstraction techniques presented in that paper cannot be applied to abstract actions. This is a severe limitation since one expects to use such techniques to create abstraction hierarchies. So we need to find a new representation framework that accomodates sound abstraction, and to develop sound abstraction techniques within this framework. This paper offers such a formal framework for sound abstraction of actions. First, we define sound ab straction in the context of finite-horizon probabilis tic planning, where each plan is a finite sequence of actions. Second, we present the constraint mass as signment representation, which models a world with a set of probability distributions and is a generaliza tion of mass assignment representations. Third, we present sound abstraction procedures for three types of action abstraction. Finally, we end the paper with a discussion of related work on sound and approximate abstraction. Due to space limitation, the reader is re ferred to [5] for a more detailed discussion of the top ics of this paper, as well as discussions of applications, estimating loss due to abstraction, and automatically constructing abstraction hierarchies. 2 In this section we present a general representation framework for finite-horizon decision-theoretic plan ning. We discuss the relationship among states, worlds, actions, and plans. We also discuss the need for projection procedures and define sound projection procedures. Within this framework we define sound abstraction. A state completely specifies the planning domain at a particular moment. We denote the set of all possible states with !.1. A world represents the uncertainty about the state of the planning domain at a particular moment. We interpret each world as representing a set of probabil ity distributions over !.1. Typically, worlds are repreSound Abstraction of Probabilistic Actions 229 sented using some representation mechanism that can not represent all possible sets of probability distribu tions. A concrete action maps a set of probability distri butions into a set of probability distributions. This mapping is represented with the function exec{ action, set of probability distributions). The equation Ppost = exec( a, Ppre) specifies that the action a maps the set of probability distributions f;Jpre into the set of proba bility distributions f;Jpost. Concrete plans are finite sequences of concrete actions. Like actions, plans also map sets of probability distri butions into sets of probability distributions. We re p resent this mapping with the function exec( plan, set of probability distributions). For a plan p = a1 a2 · · ·a,, where the ai are concrete actions, we have In executing a plan, computing the post-execution set of probability distributions exactly is typically impossible in all but very small domains. A com mon approach to solve this problem is to develop a projection procedure that yields a p ost-proje cti on set of probability distributions that is an approxi mation of the post-execution set. Denote the map ping induced by this projection procedure with the function project(action, world)1, the equation Wpost = project( a, Wpre) specifies that when the action a is pro jected in the world W p re (or rather on the set of proba bility distributions represented by the world W p re ) we obtain as the post-projection result the (set of proba bility distributions represented by) world Wpost. Pro jecting a plan p = a1a2 ···an in a world Wpre yields a world W p ost that is computed as We say the projection procedure associated with the funtion project is sound if and only if for any concrete plan p and world w we have project(p, w)�exec(p, w). An example of a sound projection procedure is the FORWARD procedure presented in [11] . An abstract action is built from concrete or lower-level abstract actions using a number of abstraction opera tors; each concrete znstantiation of an abstract action is a sequence of concrete actions. An abstract plan is a finite sequence of abstract and concrete actions. If the abstract plan p* is a*1 a* 2 · · · a• "' where the a• i are abstract or concrete actions, then a concrete instanti iatzon of the plan p* is St s2 · · · Sn, where each s; is a concrete instantiation of a \ . We say an abstraction framework that satisfies the 1The function project is defined for worlds because we are concerned only with the cases where plans are executed on sets of probability distributions that can be represented with worlds.  In the previous section we presented a general rep� resentation framework for probabilistic planning in which worlds are represented with sets of probability distributions over the state space. In this section we in� traduce a concrete representation framework that will serve as our substrate fo r sound abstraction. Motivation
We haven't been able to show in general how loose the post-projection set is compared to the post execution set, but see REF for some partial results, as well as preliminary results on estimating utility loss due to abstraction and on methods to construct ab straction hierarchies.
Sound Abstraction of Probabilistic Actions in The Constraint Mass Assignment Framework
ArXiv
ArXiv
Computer Science