Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
Full Text:
isaza.pdf 
In this paper, we consider planning in stochastic shortest path (SSP) problems, a subclass of Markov Decision Problems (MDP). We focus on medium-size problems whose state space can be fully enumerated. This problem has numerous important applications, such as navigation and planning under uncertainty. We propose a new approach for constructing a multi-level hierarchy of progressively simpler abstractions of the original problem. Once computed, the hierarchy can be used to speed up planning by first finding a policy for the most abstract level and then recursively refining it into a solution to the original problem. This approach is fully automated and delivers a speed-up of two orders of magnitude
over a state-of-the-art MDP solver on sample problems while returning near-optimal solutions. We also prove theoretical bounds on the loss of solution optimality resulting from the use of abstractions.
Citation
A. Isaza,
C. Szepesvari,
R. Greiner,
V. Bulitko.
"Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions".
Conference on Uncertainty in Artificial Intelligence (UAI), pp 306--314, July 2008.
| Keywords: |
planning, abstraction, stochastic shortest path, machine learning |
| Category: |
In Conference |
| Web Links: |
Tech. report |
BibTeX
@incollection{Isaza+al:UAI08,
author = {Alejandro Isaza and Csaba Szepesvari and Russ Greiner and Vadim
Bulitko},
title = {Speeding Up Planning in Markov Decision Processes via Automatically
Constructed Abstractions},
Pages = {306--314},
booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
year = 2008,
}Last Updated: August 20, 2008
Submitted by Russ Greiner 
