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.