|
|
|
|
Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
Alejandro Isaza, Csaba Szepesvari, Vadim Bulitko, Russell Greiner
Abstract:
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.
Keywords: null
Pages: 306-314
PS Link:
PDF Link: /papers/08/p306-isaza.pdf
BibTex:
@INPROCEEDINGS{Isaza08,
AUTHOR = "Alejandro Isaza
and Csaba Szepesvari and Vadim Bulitko and Russell Greiner",
TITLE = "Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "306--314"
}
|
|
