Scalable Probabilistic Planning
MDP Solvers That Scale
Overview
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.
This project is supported by National Science Foundation grants IIS-1016713 and IIS-1016465.
Publications
|
Artificial Intelligence for Artificial Artificial Intelligence Peng Dai, Mausam and Daniel S. Weld AAAI Conference on Artificial Intelligence, 2011. Full Paper (PDF) |
|
Artificial Intelligence for Artificial Artificial Intelligence Peng Dai, Mausam and Daniel S. Weld Human Computation Workshop, 2011. Full Paper (PDF) |
|
Human Intelligence Needs Artificial Intelligence Daniel S. Weld, Mausam and Peng Dai Human Computation Workshop, 2011. Full Paper (PDF) |
|
Heuristic Search for Generalized Stochastic Shortest Path MDPs Andrey Kolobov, Mausam, Daniel S. Weld and Hector Geffner International Conference on Automated Planning and Scheduling, 2011. Full Paper (PDF) |
|
Decision-Theoretic Control for Crowdsourced Workflows Peng Dai, Mausam and Daniel S. Weld AAAI Conference on Artificial Intelligence, 2010. Full Paper (PDF) |
|
SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs Andrey Kolobov, Mausam and Daniel S. Weld AAAI Conference on Artificial Intelligence, 2010. Full Paper (PDF) |
|
Classical Planning in MDP Heuristics: With a Little Help from Generalization Andrey Kolobov, Mausam and Daniel S. Weld International Conference on Automated Planning and Scheduling, 2010. Full Paper (PDF) |
|
Focused Topological Value Iteration Peng Dai, Mausam and Daniel S. Weld International Conference on Automated Planning and Scheduling, 2009. Full Paper (PDF) |
|
Domain-Independent, Automatic Partitioning for Probabilistic Planning Peng Dai, Mausam and Daniel S. Weld International Joint Conference on Artificial Intelligence, 2009. Full Paper (PDF) |
|
ReTrASE: Intergating Paradigms for Approximate Probabilistic Planning Andrey Kolobov, Mausam and Daniel S. Weld International Joint Conference on Artificial Intelligence, 2009. Full Paper (PDF) |
|
A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains Nicolas Meuleau, Emmanuel Benazera, Ronen Brafman, Eric Hansen and Mausam Journal of Artificial Intelligence Research, 2009. Journal Article (PDF) |
|
Partitioned External Memory Value Iteration Peng Dai, Mausam and Daniel S. Weld AAAI Conference on Artificial Intelligence, 2008. Full Paper (PDF) |
|
A Hybridized Planner for Stochastic Domains Mausam, Piergiorgio Bertoli and Daniel S. Weld International Joint Conference on Artificial Intelligence, 2007. Full Paper (PDF) |
|
Planning with Continuous Resources in Stochastic Domains Mausam, Emmanuel Benazera, Ronen Brafman, Nicolas Meuleau and Eric Hansen International Joint Conference on Artificial Intelligence, 2005. Full Paper (PDF) |