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.

Microcantilever sensors for biochemical detection and analysis

Biochemical agents, including bacteria and toxins, are potentially dangerous and responsible for a wide variety of diseases. Reliable detection and characterization of small samples is necessary in order to reduce and eliminate their harmful consequences. Microcantilever sensors offer a potential alternative to the state of the art due to their small size, fast response time, and the ability to operate in air and liquid environments. At present, there are several technology limitations that inhibit application of microcantilever to biochemical detection and analysis, including difficulties in conducting temperature-sensitive experiments, material inadequacy resulting in insufficient cell capture, and poor selectivity of multiple analytes. This work aims to address several of these issues by introducing microcantilevers having integrated thermal functionality and by introducing nanocrystalline diamond as new material for microcantilevers. Microcantilevers are designed, fabricated, characterized, and used for capture and detection of cells and bacteria. The first microcantilever type described in this work is a silicon cantilever having highly uniform in-plane temperature distribution. The goal is to have 100 μm square uniformly heated area that can be used for thermal characterization of films as well as to conduct chemical reactions with small amounts of material. Fabricated cantilevers can reach above 300C while maintaining temperature uniformity of 2−4%. This is an improvement of over one order of magnitude over currently available cantilevers. The second microcantilever type is a doped single crystal silicon cantilever having a thin coating of ultrananocrystalline diamond (UNCD). The primary application of such a device is in biological testing, where diamond acts as a stable, electrically isolated reaction surface while silicon layer provides controlled heating with minimum variations in temperature. This work shows that composite cantilevers of this kind are an effective platform for temperature-sensitive biological experiments, such as heat lysing and polymerase chain reaction. The rapid heat-transfer of Si-UNCD cantilever compromised the membrane of NIH 3T3 fibroblast and lysed the cell nucleus within 30 seconds. Bacteria cells, Listeria monocytogenes V7, were shown to be captured with biotinylated heat-shock protein on UNCD surface and 90% of all viable cells exhibit membrane porosity due to high heat in 15 seconds. Lastly, a sensor made solely from UNCD diamond is fabricated with the intention of being used to detect the presence of biological species by means of an integrated piezoresistor or through frequency change monitoring. Since UNCD diamond has not been previously used in piezoresistive applications, temperature-denpendent piezoresistive coefficients and gage factors are determined first. The doped UNCD exhibits a significant piezoresistive effect with gauge factor of 7.53±0.32 and a piezoresistive coefficient of 8.12×10^−12 Pa^−1 at room temperature. The piezoresistive properties of UNCD are constant over the temperature range of 25−200C. 300 μm long cantilevers have the highest sensitivity of 0.186 m-Ohm/Ohm per μm of cantilever end deflection, which is approximately half that of similarly sized silicon cantilevers. UNCD cantilever arrays were fabricated consisting of four sixteen-cantilever arrays of length 20–90 μm in addition to an eight-cantilever array of length 120 μm. Laser doppler vibrometry (LDV) measured the cantilever resonant frequency, which ranged as 218 kHz−5.14 MHz in air and 73 kHz−3.68 MHz in water. The quality factor of the cantilever was 47−151 in air and 18−45 in water. The ability to measure frequencies of the cantilever arrays opens the possibility for detection of individual bacteria by monitoring frequency shift after cell capture.

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.