Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
Alejandro Isaza, Csaba Szepesvari, Vadim Bulitko, Russell Greiner
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.
PDF Link: /papers/08/p306-isaza.pdf
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"