Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains
Thesis (Ph. D.)--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/53200 |
| _version_ | 1811070919778500608 |
|---|---|
| author | Brunskill, Emma Patricia |
| author2 | Nicholas Roy. |
| author_facet | Nicholas Roy. Brunskill, Emma Patricia |
| author_sort | Brunskill, Emma Patricia |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. |
| first_indexed | 2024-09-23T08:43:42Z |
| format | Thesis |
| id | mit-1721.1/53200 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:43:42Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/532002019-04-14T06:58:43Z Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains Brunskill, Emma Patricia Nicholas Roy. 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 (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009. Cataloged from PDF version of thesis. Includes bibliographical references (p. 137-144). Within artificial intelligence and robotics there is considerable interest in how a single agent can autonomously make sequential decisions in large, high-dimensional, uncertain domains. This thesis presents decision-making algorithms for maximizing the expected sum of future rewards in two types of large, high-dimensional, uncertain situations: when the agent knows its current state but does not have a model of the world dynamics within a Markov decision process (MDP) framework, and in partially observable Markov decision processes (POMDPs), when the agent knows the dynamics and reward models, but only receives information about its state through its potentially noisy sensors. One of the key challenges in the sequential decision making field is the tradeoff between optimality and tractability. To handle high-dimensional (many variables), large (many potential values per variable) domains, an algorithm must have a computational complexity that scales gracefully with the number of dimensions. However, many prior approaches achieve such scalability through the use of heuristic methods with limited or no guarantees on how close to optimal, and under what circumstances, are the decisions made by the algorithm. Algorithms that do provide rigorous optimality bounds often do so at the expense of tractability. This thesis proposes that the use of parametric models of the world dynamics, rewards and observations can enable efficient, provably close to optimal, decision making in large, high-dimensional uncertain environments. (cont.) In support of this, we present a reinforcement learning (RL) algorithm where the use of a parametric model allows the algorithm to make close to optimal decisions on all but a number of samples that scales polynomially with the dimension, a significant improvement over most prior RL provably approximately optimal algorithms. We also show that parametric models can be used to reduce the computational complexity from an exponential to polynomial dependence on the state dimension in forward search partially observable MDP planning. Under mild conditions our new forward-search POMDP planner maintains prior optimality guarantees on the resulting decisions. We present experimental results on a robot navigation over varying terrain RL task and a large global driving POMDP planning simulation. by Emma Patricia Brunskill. Ph.D. 2010-03-25T15:13:53Z 2010-03-25T15:13:53Z 2009 2009 Thesis http://hdl.handle.net/1721.1/53200 526682008 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 144 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Brunskill, Emma Patricia Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title | Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title_full | Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title_fullStr | Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title_full_unstemmed | Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title_short | Compact parametric models for efficient sequential decision making in high-dimensional, uncertain domains |
| title_sort | compact parametric models for efficient sequential decision making in high dimensional uncertain domains |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/53200 |
| work_keys_str_mv | AT brunskillemmapatricia compactparametricmodelsforefficientsequentialdecisionmakinginhighdimensionaluncertaindomains |