Exact Solution of Bayes and Minimax Change-Detection Problems

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 change-detection problems with discrete time and discrete observations. Change-detection problems are classified as Bayes or minimax based on the availability of information on the change-time 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 worst-case change-time distribution. Both types of problems are addressed. The most important result of the dissertation is the development of a polynomial-time algorithm for the solution of important classes of Markov Bayes change-detection problems. Existing techniques for epsilon-exact 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 change-detection problems with a geometric change-time distribution and identically- and independently-distributed observations before and after the change are solvable in polynomial time. Also, change-detection problems on hidden Markov models with a fixed number of recurrent states are solvable in polynomial time. A detailed implementation and analysis of the constellation-induction algorithm are provided. Exact solution methods are also established for several types of minimax change-detection problems. Finite-horizon problems with arbitrary observation distributions are modeled as extensive-form games and solved using linear programs. Infinite-horizon problems with linear penalty for detection delay and identically- and independently-distributed observations can be solved in polynomial time via epsilon-optimal parameterization of a cumulative-sum procedure. Finally, the properties of policies for change-detection problems are described and analyzed. Simple classes of formal languages are shown to be sufficient for epsilon-exact solution of change-detection problems, and methods for finding minimally sized policy representations are described.

Improving the stability of an oxime based electrochemical microsensor for organo-phosphate vapor detection

A micro gas sensor has been developed by our group for the detection of organo-phosphate vapors using an aqueous oxime solution. The analyte diffuses from the high flow rate gas stream through a porous membrane to the low flow rate aqueous phase. It reacts with the oxime PBO (1-Phenyl-1,2,3,-butanetrione 2-oxime) to produce cyanide ions, which are then detected electrochemically from the change in solution potential. Previous work on this oxime based electrochemistry indicated that the optimal buffer pH for the aqueous solution was approximately 10. A basic environment is needed for the oxime anion to form and the detection reaction to take place. At this specific pH, the potential response of the sensor to an analyte (such as acetic anhydride) is maximized. However, sensor response slowly decreases as the aqueous oxime solution ages, by as much as 80% in first 24 hours. The decrease in sensor response is due to cyanide which is produced during the oxime degradation process, as evidenced by the cyanide selective electrode. Solid phase micro-extraction carried out on the oxime solution found several other possible degradation products, including acetic acid, N-hydroxy benzamide, benzoic acid, benzoyl cyanide, 1-Phenyl 1,3-butadione, 2-isonitrosoacetophenone and an imine derived from the oxime. It was concluded that degradation occurred through nucleophilic attack by a hydroxide or oxime anion to produce cyanide, as well as a nitrogen atom rearrangement similar to Beckmann rearrangement. The stability of the oxime in organic solvents is most likely due to the lack of water, and specifically hydroxide ions. The reaction between oxime and organo-phosphate to produce cyanide ions requires hydroxide ions, and therefore pure organic solvents are not compatible with the current micro-sensor electrochemistry. By combining a concentrated organic oxime solution with the basic aqueous buffer just prior to being used in the detection process, oxime degradation can be avoided while preserving the original electrochemical detection scheme. Based on beaker cell experiments with selective cyanide sensitive electrodes, ethanol was chosen as the best organic solvent due to its stabilizing effect on the oxime, minimal interference with the aqueous electrochemistry, and compatibility with the current microsensor material (PMMA). Further studies showed that ethanol had a small effect on micro-sensor performance by reducing the rate of cyanide production and decreasing the overall response time. To avoid incomplete mixing of the aqueous and organic solutions, they were pre-mixed externally at a 10:1 ratio, respectively. To adapt the microsensor design to allow for mixing to take place within the device, a small serpentine channel component was fabricated with the same dimensions and material as the original sensor. This allowed for seamless integration of the microsensor with the serpentine mixing channel. Mixing in the serpentine microchannel takes place via diffusion. Both detector potential response and diffusional mixing improve with increased liquid residence time, and thus decreased liquid flowrate. Micromixer performance was studies at a 10:1 aqueous buffer to organic solution flow rate ratio, for a total rate of 5.5 μL/min. It was found that the sensor response utilizing the integrated micromixer was nearly identical to the response when the solutions were premixed and fed at the same rate.