Innovative Projects Realized

We are interested in understanding the power and limitations of families of algorithms for solving combinatorial search problems, in particular those whose decision versions are NP-complete.   In some application areas involving such problems, the state of the art involves representing a problem instance as a formula of propositional logic (or a natural extension, typical examples being cardinality constraints and Boolean combinations of linear inequalities), and using a program designed to find satisfying assignments (e.g., a SAT solver, or SMT solver) to attempt to construct a solution. (SMT stands for Satisfiability Modulo Theories, which means satisfiability of a set of ground first order formulas involving atoms whose interpretation is determined by some decidable theory, e.g., Presburger arithmetic or the theory of arrays.)

An interesting observation about practical experience is that “industrial” SAT and SMT solvers commonly solve instances with millions of variables and clauses.   In contrast, we know how to design families of formulas with a few hundreds of variables which no known method could decide satisfiability of in our lifetimes.   While industrial sources produce a continual source of increasingly hard instances which are too hard for current technology to solve, these instances are nonetheless very easy relative to their number of variables when we take into account how small a hard formula can be.  Such observations have lead to considerable speculation about the structure of comparatively hard or easy instances from various sources. 

A frequent suggestion is that many industrial instances are relatively easy because they are satisfy some particular structural property, such as (a graph associated with the formula) having small width, by one of a number of related notions of with of graph width, and thus being solvable by efficient algorithms for instances with this property.   Actual evidence is weak: it is not clear that the formulas satisfy any such a property, and in many cases we know they do not – or even cannot – satisfy the most obvious candidate properties.  It is even less clear that the algorithms used in practice should be able to efficiently solve instances because they have properties of the sorts proposed.  However, there are many intriguing possibilities.

The students role will be to help in answering some particular parts of the first question.  Their work would proceed in the following stages: Reading of appropriate background material, and selection of a small number of families of formulas (e.g., from hardware verification, automated planning, bioinformatics, combinatorial designs, etc.) and structural properties to study (notions of width, scale-freeness, etc.); Study of algorithms and existing implementations for the properties chosen; preliminary experiments.  It is anticipated that we will not be able to measure interesting properties precisely for large instances with existing implementations; Work, together with the supervisor and other students (and likely a post-doc) on refining the algorithms and data structures to improve speed and thus the size of instances that can be measured; Prepare a report on the progress made.

In this project, we aim to develop a mathematical model and perform numerical simulations for gravity-driven fingering instabilities that occur during the flow of groundwater in soils and aquifers.  Fingers form in response to gravitational forces that derive from the difference in density between invading water and displaced air.  These forces can destabilize an otherwise stable, planar wetting front, leading to a periodic array of rapidly propagating fingers.  These instabilities can play a very important role in the study of both contamination and remediation of soils, because fingers provide a route for rapid entry of rain or other surface water sources into the subsurface. Numerous models have been proposed for capturing fingered flow phenomena, which are mostly based on the well-known Richards equation for flow in porous media in combination with appropriate constitutive equations for soil properties.  In this project, we are interested in studying three specific models that employ different approaches for incorporating hysteresis and non-equilibrium effects in the dynamic equation that governs capillary pressure.  

Our aim in this project is to take the basic computational framework we have already developed in Matlab for Model A [1] and to extend it by implementing models B and C.  The governing equations in each case are a coupled nonlinear system of partial differential equations of parabolic type.  Based on the simple, rectangular geometry of the typical experimental soil sample, we will restrict ourselves to a two-dimensional rectangular domain and use a standard finite difference discretization in space.  The time discretization will be handled using a method-of-lines approach with the ODE solvers built-in to Matlab. We will then be prepared to perform a comprehensive comparison of the ability of all three models to simulate gravity-driven fingering phenomena, and to evaluate the advantages and disadvantages of each.  No such comparison has yet been done because models B and C [2,5] are relatively recent; neither has model B or C yet been systematically compared to the wealth of experimental data available in the literature (see the references in [1] for examples).

The project’s aims are to conduct research on geological carbon storage from the perspective of dynamic analysis and process systems engineering, looking in particular at the dynamics between the wellhead and the CO₂ storage reservoir. The main objective is to achieve closed loop operation and management of the reservoir with respect to CO₂ sequestration and storage, along with enhanced oil recovery in cases where the reservoir is not fully depleted. The main thrust areas of the project are described below.

The research aims to develop an integrated approach to the co-optimization of CO₂ storage and oil recovery, i.e., closed loop reservoir management. In order to develop closed loop strategies for reservoir management, the elements included in this research include the building of reduced order proxy/surrogate models, experiment design for well placement and parameter estimation, state estimation and model updating using variants of the ensemble Kalman filter. Since reservoir models and compositional simulators are computationally expensive to run, the development of reduced order models are crucial to enable experiment design, state estimation and optimization.

The student’s role in the project will be to work on the development of strategies for the optimal design of experiments in geological carbon storage. There are two main aspects to this work: the first is the use of surrogate / proxy reservoir models for D optimal experiment design, and comparison of the results with Bayesian sequential experiment design.  The second aspect is to obtain optimal subsets or groups of parameters that are identifiable from the experiment design.This project will involve the development and modification of MATLAB code for design of experiments and reparameterization. Code has already been developed in the group for these techniques, and the student’s main role will be to modify the code for use with reservoir simulations, and analysis of the results.

Food safety is of paramount importance to Canada. Recent episode of Listeria out-break in a meat processing plant has created renewed interest in monitoring of food borne pathogens in ready-to-eat (RTE) meat products. The proposed device is aimed to detect Listeria monocytogenes in food samples within a few hours. This device integrates the microfluidics and the biosensor within a single platform, commonly referred to as a Lab-on-a-Chip (LOC). The proposed LOC will have a label free detection mechanism incorporating the state-of-art optofluidics principles and fabrications. The project will involve design, analysis and fabrication of the LOC and the prototype will be tested for its sensitivity and specificity towards L. monocytogenes. It is expected that the proposed LOC will provide timely early warning to any possible Listeria out-breaks in RTE meat products and will be an important tool for the regulators, like Canadian Food Inspection Agency, to monitor the meat processing units.

The student will be responsible for the following: Running microfluidics simulations, designing extraction process to be integrated with Lab-on-a-Chip (LOC) and working with other team members on various aspects of this industrial funded project.

The stochastic resonance (SR) is a phenomenon discovered recently in some nonlinear systems where addition of a certain amount of noise can, somewhat paradoxically, enhance its performance. It has found applications in biological sensory systems [1] such as visual, auditory systems, and tactile system as well as engineering applications such as ac-driven Schmitt triggers, and bistable ring lasers. The bistable systems (BS) are nonlinear systems [4] that are widely used as SR systems. The BS systems based detectors (henceforth referred to as BS-SR detectors) are constructed with a BS followed by an inner detector. The inner detector can be a matched filter (MF), a coherent detector or other types. It is also possible to directly apply the input to the inner detector and to make a decision. Therefore, the BS is considered as a preprocessor of the inner detector. Despite several achievements by researchers in the design of BS-SR detectors, there are still many unsolved issues and difficulties. The focus of this project is to address some of these issues.

Two potential applications of SR will be considered in this project. First, the SR detector will be used in digital watermarking in the DCT domain. The watermark information is considered as weak signal embedded in the DCT coefficients considered as noise. The statistics of the noise is difficult to estimate. The BS-detector provides a robust solution and the detection performance is expected to be improved significantly. Secondly, a SR detector will be used to detect features in MRI brain images. The MRI images do not have sharp features, and are noisy. It is difficult to detect small features (e.g., lesions or tumors) in an MRI image. We would investigate the use of SR detector in improving the feature detection performance.

The student will have a role both in theoretical development and experimental evaluation of the BS-SR detector, including the following three major tasks: The student will evaluate various measures of the BS performance for signal transmission, the student will investigate the relationship between the BS performance measure (MI or cross-correlation) and the BS system parameters, for given input signal and noise characteristics, the student will evaluate the efficacy of the developed performance measure by applying the SR detector in digital watermarking applications.

The project’s aims are to conduct research on geological carbon storage from the perspective of dynamic analysis and process systems engineering, looking in particular at the dynamics between the wellhead and the CO₂ storage reservoir. The main objective is to achieve closed loop operation and management of the reservoir with respect to CO₂ sequestration and storage, along with enhanced oil recovery in cases where the reservoir is not fully depleted.

The research aims to develop an integrated approach to the co-optimization of CO₂ storage and oil recovery, i.e., closed loop reservoir management. In order to develop closed loop strategies for reservoir management, the elements included in this research include the building of reduced order proxy/surrogate models, experiment design for well placement and parameter estimation, state estimation and model updating using variants of the ensemble Kalman filter. Since reservoir models and compositional simulators are computationally expensive to run, the development of reduced order models are crucial to enable experiment design, state estimation and optimization.

The student’s role in the project will be to develop proxy or surrogate models for reservoir simulators. In the literature, most proxy models have been developed using artificial neural networks (ANNs), with genetic algorithms being also being used in the development of the proxy models. The aim of this project is to use different, potentially better methods to develop reduced order models. The methods to be investigated include Karhunen-Loeve expansion, which is related to principal component analysis. Other methods include the use of suitable reparameterization techniques (e.g., discrete cosine transform, pseudo-parameter grouping) or analytical simplifications (e.g., streamline based models) of the detailed models.

Our research aims at developing highly interactive and inter-operative applications for use in complex simulation environments. Its goals are to develop a suite of modeling, simulation, and analysis tools for: (1) the planning and management of construction projects throughout their life phases from conception to operation, (2) the training of construction personnel, and (3) the exploration of construction management best practices.

To facilitate these distributed simulation and industrial applications, we have been focusing on frameworks for Construction Synthetic Environments (CSE), which integrate multiple individual simulations using High Level Architecture to achieve comprehensive, extensive modeling of an industrial application. One such application is tunnelling.  The Tunnelling CSE  is based on our experience with the construction domain – tunnel simulation in this case – our findings related to the applicability of the High Level Architecture in construction simulation, and the developments of COSYE framework.  The CSE is composed of a number of individual simulations that collaborate to achieve comprehensive and extensible modeling of the entire tunnelling project.  The development of this CSE demonstrates a number of important features not readily available in the simulation systems of today including concurrent and collaborative development of large scale systems, distributed simulation, integrated simulation systems and real time visualization. Future developments will include sophisticated techniques for forecasting and tracking tunnel construction, as well as expansion of its 3D visualization capabilities.