Fast approximate hierarchical solution of MDPs
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/53202 |
| _version_ | 1811069969947951104 |
|---|---|
| author | Barry, Jennifer L. (Jennifer Lynn) |
| author2 | Leslie Pack Kaelbling and Tomáz Lozano-Pérez. |
| author_facet | Leslie Pack Kaelbling and Tomáz Lozano-Pérez. Barry, Jennifer L. (Jennifer Lynn) |
| author_sort | Barry, Jennifer L. (Jennifer Lynn) |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. |
| first_indexed | 2024-09-23T08:19:46Z |
| format | Thesis |
| id | mit-1721.1/53202 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:19:46Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/532022019-04-09T17:59:57Z Fast approximate hierarchical solution of MDPs Barry, Jennifer L. (Jennifer Lynn) Leslie Pack Kaelbling and Tomáz Lozano-Pérez. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. Cataloged from PDF version of thesis. Includes bibliographical references (p. 89-91). In this thesis, we present an efficient algorithm for creating and solving hierarchical models of large Markov decision processes (MDPs). As the size of the MDP increases, finding an exact solution becomes intractable, so we expect only to find an approximate solution. We also assume that the hierarchies we create are not necessarily applicable to more than one problem so that we must be able to construct and solve the hierarchical model in less time than it would have taken to simply solve the original, flat model. Our approach works in two stages. We first create the hierarchical MDP by forming clusters of states that can transition easily among themselves. We then solve the hierarchical MDP. We use a quick bottom-up pass based on a deterministic approximation of expected costs to move from one state to another to derive a policy from the top down, which avoids solving low-level MDPs for multiple objectives. The resulting policy may be suboptimal but it is guaranteed to reach a goal state in any problem in which it is reachable under the optimal policy. We have two versions of this algorithm, one for enumerated-state MDPs and one for factored MDPs. We have tested the enumerated-state algorithm on classic problems and shown that it is better than or comparable to current work in the field. Factored MDPs are a way of specifying extremely large MDPs without listing all of the states. Because the problem has a compact representation, we suspect that the solution should, in many cases, also have a compact representation. We have an implementation for factored MDPs and have shown that it can find solutions for large, factored problems. by Jennifer L. Barry. S.M. 2010-03-25T15:14:07Z 2010-03-25T15:14:07Z 2009 2009 Thesis http://hdl.handle.net/1721.1/53202 526697273 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 91 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Barry, Jennifer L. (Jennifer Lynn) Fast approximate hierarchical solution of MDPs |
| title | Fast approximate hierarchical solution of MDPs |
| title_full | Fast approximate hierarchical solution of MDPs |
| title_fullStr | Fast approximate hierarchical solution of MDPs |
| title_full_unstemmed | Fast approximate hierarchical solution of MDPs |
| title_short | Fast approximate hierarchical solution of MDPs |
| title_sort | fast approximate hierarchical solution of mdps |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/53202 |
| work_keys_str_mv | AT barryjenniferljenniferlynn fastapproximatehierarchicalsolutionofmdps |