Using Abstractions for Decision-Theoretic Planning with Time Constraints

Recently Markov decision processes and optimal control policies have been applied to the problem of decision-theoretic planning. However, the classical methods for generating optimal policies are highly intractable, requiring explicit enumeration of large state spaces. We explore a method for generating abstractionsthat allow approximately optimal policies to be constructed; computational gains are achieved through reduction of the state space. Abstractions are generated by identifying propositions that are “relevant” either through their direct impact on utility, or their influence on actions. This information is gleaned from the representation of utilitiesand actions. We prove boundson the loss in value due to abstraction and describe some preliminary experimentalresults.

Authors

• Craig Boutilier Google Research

Keywords

No keywords are indexed for this paper.