Approximate value-directed belief state monitoring for partially observable Markov decision processes
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Poupart, Pascal
issued: 2009-07-29T18:06:32Z
issued: 2000
related degree: Master of Science - MSc
degree grantor: University of British Columbia
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…
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/11462
extent: 5567790 bytes
format: application/pdf
note: Approximate Value-Directed Belief State Monitoring for Partially Observable Markov Decision Processes by Pascal Poupart B.Sc, McGill University, 1998 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science in T H E F A C U L T Y O F G R A D U A T E STUDIES (Department of Computer Science) We accen^Hris^thesis as) conforming required jjfcandard The University of British Columbia November 2000 © Pascal Poupart, 2000 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the Un i v e r s i t y of B r i t i s h Columbia, I agree that the Li b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I further agree that permission for extensive copying of t h i s thesis f o r s c h o l a r l y purposes may be granted by the head of my department or by his or her representatives. It i s understood that copying or p u b l i c a t i o n of t h i s thesis f o r f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of C O M P T E R S C I E N C E The U n i v e r s i t y of B r i t i s h Columbia Vancouver, Canada Date 2QQG>- 1\ ~TJ\ A b s t r a c t Partially observable Markov decision processes (POMDPs) provide a principled ap-proach to planning under uncertainty. Unfortunately, several sources of intractabil-ity currently limit the application of P O M D P s 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…
has type: Thesis/Dissertation
date issued: 2001-05
is shown at: 10.14288/1.0051693
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
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.
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/11462