- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Approximate value-directed belief state monitoring...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Approximate value-directed belief state monitoring for partially observable Markov decision processes Poupart, Pascal
Abstract
Partially observable Markov decision processes (POMDPs) provide a principled approach to planning under uncertainty. Unfortunately, several sources of intractability currently limit the application of POMDPs to simple problems. The following thesis is concerned with one source of intractability in particular, namely the belief state monitoring task. As an agent executes a plan, it must track the state of the world by updating its beliefs with respect to the current state. Then, based on its current beliefs, the agent can look up the next action to execute in its plan. In many situations, an agent may be required to decide in real-time which action to execute next. Thus, efficient algorithms to update the current belief state would be desirable. Unfortunately, exact belief state monitoring turns out to be very time consuming for many domains. This thesis introduces a value-directed framework to analyze and design approximation methods that speed up the monitoring task. The goal of approximate belief state monitoring is to trade monitoring accuracy for efficiency. Thus, this framework outlines a principled approach to quantify the impact of approximating belief states on the original plan. Since at any point in time, an action is executed based on the current belief state, it may be possible that a less desirable action ends up being executed as a result of the approximations used to infer the current belief state. The framework developped covers a wide range of approximation methods including projection schemes and density trees. First, several bounds on the loss in decision quality due to approximate belief state monitoring are derived. Then, given a class of approximation methods, a few search algorithms are proposed to seek a relatively good approximation scheme within the given class. These algorithms essentially try to minimize the bounds derived. Next, a vector space analysis is performed to gain some insights regarding which properties of approximation methods are likely to ensure a minimal impact on decision quality. Finally, faster algorithms (than the previous ones) are designed to search for approximation methods that exhibit such properties.
Item Metadata
Title |
Approximate value-directed belief state monitoring for partially observable Markov decision processes
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2000
|
Description |
Partially observable Markov decision processes (POMDPs) provide a principled approach
to planning under uncertainty. Unfortunately, several sources of intractability
currently limit the application of POMDPs to simple problems. The following
thesis is concerned with one source of intractability in particular, namely the belief
state monitoring task. As an agent executes a plan, it must track the state of the
world by updating its beliefs with respect to the current state. Then, based on its
current beliefs, the agent can look up the next action to execute in its plan. In
many situations, an agent may be required to decide in real-time which action to
execute next. Thus, efficient algorithms to update the current belief state would be
desirable. Unfortunately, exact belief state monitoring turns out to be very time
consuming for many domains.
This thesis introduces a value-directed framework to analyze and design approximation
methods that speed up the monitoring task. The goal of approximate
belief state monitoring is to trade monitoring accuracy for efficiency. Thus, this
framework outlines a principled approach to quantify the impact of approximating
belief states on the original plan. Since at any point in time, an action is executed
based on the current belief state, it may be possible that a less desirable action ends
up being executed as a result of the approximations used to infer the current belief
state.
The framework developped covers a wide range of approximation methods
including projection schemes and density trees. First, several bounds on the loss
in decision quality due to approximate belief state monitoring are derived. Then,
given a class of approximation methods, a few search algorithms are proposed to seek
a relatively good approximation scheme within the given class. These algorithms
essentially try to minimize the bounds derived. Next, a vector space analysis is performed
to gain some insights regarding which properties of approximation methods
are likely to ensure a minimal impact on decision quality. Finally, faster algorithms
(than the previous ones) are designed to search for approximation methods that
exhibit such properties.
|
Extent |
5567790 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-07-29
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0051693
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2001-05
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.