Files in this item
Files  Description  Format 

application/pdf Isom_Dissertation.pdf (2MB)  Dissertation 
Description
Title:  Exact Solution of Bayes and Minimax ChangeDetection Problems 
Author(s):  Isom, Joshua D. 
Doctoral Committee Chair(s):  Braatz, Richard D. 
Doctoral Committee Member(s):  Meyn, Sean P.; LaBarre, Robert E.; Rao, Christopher V. 
Department / Program:  Chemical Engineering 
Discipline:  Chemical Engineering 
Degree Granting Institution:  University of Illinios at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  change detection
stochastic optimal control formal languages cumulative sum (CUSUM) Bayes minimax partially observable Markov decision process 
Abstract:  The challenge of detecting a change in the distribution of data is a sequential decision problem that is relevant to many engineering solutions, including quality control and machine and process monitoring. This dissertation develops techniques for exact solution of changedetection problems with discrete time and discrete observations. Changedetection problems are classified as Bayes or minimax based on the availability of information on the changetime distribution. A Bayes optimal solution uses prior information about the distribution of the change time to minimize the expected cost, whereas a minimax optimal solution minimizes the cost under the worstcase changetime distribution. Both types of problems are addressed. The most important result of the dissertation is the development of a polynomialtime algorithm for the solution of important classes of Markov Bayes changedetection problems. Existing techniques for epsilonexact solution of partially observable Markov decision processes have complexity exponential in the number of observation symbols. A new algorithm, called constellation induction, exploits the concavity and Lipschitz continuity of the value function, and has complexity polynomial in the number of observation symbols. It is shown that changedetection problems with a geometric changetime distribution and identically and independentlydistributed observations before and after the change are solvable in polynomial time. Also, changedetection problems on hidden Markov models with a fixed number of recurrent states are solvable in polynomial time. A detailed implementation and analysis of the constellationinduction algorithm are provided. Exact solution methods are also established for several types of minimax changedetection problems. Finitehorizon problems with arbitrary observation distributions are modeled as extensiveform games and solved using linear programs. Infinitehorizon problems with linear penalty for detection delay and identically and independentlydistributed observations can be solved in polynomial time via epsilonoptimal parameterization of a cumulativesum procedure. Finally, the properties of policies for changedetection problems are described and analyzed. Simple classes of formal languages are shown to be sufficient for epsilonexact solution of changedetection problems, and methods for finding minimally sized policy representations are described. 
Issue Date:  20090420 
Citation Info:  Dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Chemical Engineering in the Graduate College of the University of Illinois at UrbanaChampaign, 2009 
Genre:  Dissertation / Thesis 
Type:  Text 
URI:  http://hdl.handle.net/2142/11062 
Publication Status:  unpublished 
Date Available in IDEALS:  20090420 
This item appears in the following Collection(s)

Illinois Research and Scholarship (Open Community)
This is the default collection for all research and scholarship developed by faculty, staff or students at the University of Illinois at UrbanaChampaign 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Chemical and Biomolecular Engineering
Dissertations and Theses  Chemical and Biomolecular Engineering