Solving Markov Decision Processes with Partial State Abstractions
Samer B. Nashed, Justin Svegliato, Matteo Brucato, Connor Basich, Rod Grupen, Shlomo Zilberstein
Abstract
Autonomous systems often use approximate planners that exploit state abstractions to solve large MDPs in real-time decision-making problems. However, these planners can eliminate details needed to produce effective behavior in autonomous systems. We therefore propose a novel model, a partially abstract MDP, with a set of abstract states that each compress a set of ground states to condense irrelevant details and a set of ground states that expand from a set of expanded abstract states to retain relevant details. This papers offers (1) a definition of a partially abstract MDP that (2) generalizes its ground MDP and its abstract MDP and exhibits bounded optimality depending on its abstract MDP along with (3) a lazy algorithm for planning and execution in autonomous systems. The result is a scalable approach that computes near-optimal solutions to large problems in minutes rather than hours.
BibTeX
@inproceedings{icra2021_solvingmarkovdec,
title = {Solving Markov Decision Processes with Partial State Abstractions},
author = {Samer B. Nashed and Justin Svegliato and Matteo Brucato and Connor Basich and Rod Grupen and Shlomo Zilberstein},
booktitle = {ICRA 2021},
year = {2021}
}