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 that ReTrASE outperforms 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.

This project is supported by National Science Foundation grants IIS-1016713 and IIS-1016465.