CS&E logo University of Washington Computer Science & Engineering
  MDP Solvers That Scale
 CSE Home  AI Home  About CSE  Search  Contact Info 

Project faculty
 Dan Weld
Project students
 Peng Dai
 Andrey Kolobov

MDP Solvers That Scale


Being PSPACE-complete, even MDPs that describe relatively simple planning problems often defeat modern solvers by forcing them to run out of physical memory or take unreasonably long to produce a solution. Increasing scalability of techniques for solving MDPs is thus a central research topic in planning under uncertainty, and we address it in multiple ways.

One approach is based on the insight that, although an MDP's state space may be too small to fit in main memory, we can spill parts of the state-value table to disk without large sacrifices in speed. Namely, to efficiently perform value iteration, we partition the state space so that the number of state transitions between the partition cells is small. The cells are then loaded into main memory from disc one-by-one in a specially chosen order and have their states' values iteratively updated. The resulting method, called PEMVI, finds optimal policies and does only a few disk accesses in the process.

Unfortunately, some MDPs are too large to be solved optimally by any of the existing methods; the best we can hope for is an approximation. This motivates our other MDP solver, ReTrASE. ReTrASE employs a deterministic planner to automatically extract helpful structural features of a probabilistic planning problem and analyzes them to construct a policy. Experiments show ReTrASE to outperform state-of-the-art algorithms in terms of both efficiency and policy quality on many large MDPs. Ideas realized in ReTrASE also form the basis of heuristic functions GOTH and SixthSense.


  1. Andrey Kolobov, Mausam, Daniel S. Weld, Classical Planning in MDP Heuristics: With a Little Help from Generalization, ICAPS 2010, Toronto, Canada, May 2010.
  2. Peng Dai, Mausam, Daniel S. Weld, Focused Topological Value Iteration, ICAPS 2009, Thessaloniki, Greece, September 2009.
  3. Andrey Kolobov, Mausam, Daniel S. Weld, ReTrASE: Intergating Paradigms for Approximate Probabilistic Planning, IJCAI 2009, Pasadena, CA, July 2009.
  4. Peng Dai, Mausam, Daniel S. Weld, Domain-Independent, Automatic Partitioning for Probabilistic Planning, IJCAI 2009, Pasadena, CA, July 2009.
  5. Peng Dai, Mausam, Daniel S. Weld, Partitioned External Memory Value Iteration, AAAI 2008, Chicago, IL, July 2008.
  6. Mausam, Piergiorgio Bartoli, Daniel S. Weld, A Hybridized Planner for Stochastic Domains, IJCAI 2007, Hyderabad, India, January 2007.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Dan Weld]