Control of dynamical systems with temporal logic specifications

This thesis is motivated by safety-critical applications involving autonomous air, ground, and space vehicles carrying out complex tasks in uncertain and adversarial environments. We use temporal logic as a language to formally specify complex tasks and system properties. Temporal logic specifications generalize the classical notions of stability and reachability that are studied in the control and hybrid systems communities. Given a system model and a formal task specification, the goal is to automatically synthesize a control policy for the system that ensures that the system satisfies the specification. This thesis presents novel control policy synthesis algorithms for optimal and robust control of dynamical systems with temporal logic specifications. Furthermore, it introduces algorithms that are efficient and extend to high-dimensional dynamical systems.

The first contribution of this thesis is the generalization of a classical linear temporal logic (LTL) control synthesis approach to optimal and robust control. We show how we can extend automata-based synthesis techniques for discrete abstractions of dynamical systems to create optimal and robust controllers that are guaranteed to satisfy an LTL specification. Such optimal and robust controllers can be computed at little extra computational cost compared to computing a feasible controller.

The second contribution of this thesis addresses the scalability of control synthesis with LTL specifications. A major limitation of the standard automaton-based approach for control with LTL specifications is that the automaton might be doubly-exponential in the size of the LTL specification. We introduce a fragment of LTL for which one can compute feasible control policies in time polynomial in the size of the system and specification. Additionally, we show how to compute optimal control policies for a variety of cost functions, and identify interesting cases when this can be done in polynomial time. These techniques are particularly relevant for online control, as one can guarantee that a feasible solution can be found quickly, and then iteratively improve on the quality as time permits.

The final contribution of this thesis is a set of algorithms for computing feasible trajectories for high-dimensional, nonlinear systems with LTL specifications. These algorithms avoid a potentially computationally-expensive process of computing a discrete abstraction, and instead compute directly on the system's continuous state space. The first method uses an automaton representing the specification to directly encode a series of constrained-reachability subproblems, which can be solved in a modular fashion by using standard techniques. The second method encodes an LTL formula as mixed-integer linear programming constraints on the dynamical system. We demonstrate these approaches with numerical experiments on temporal logic motion planning problems with high-dimensional (10+ states) continuous systems.

Bright-field and fluorescence chip-scale microscopy for biological imaging

Optical microscopy is an essential tool in biological science and one of the gold standards for medical examinations. Miniaturization of microscopes can be a crucial stepping stone towards realizing compact, cost-effective and portable platforms for biomedical research and healthcare. This thesis reports on implementations of bright-field and fluorescence chip-scale microscopes for a variety of biological imaging applications. The term “chip-scale microscopy” refers to lensless imaging techniques realized in the form of mass-producible semiconductor devices, which transforms the fundamental design of optical microscopes.

Our strategy for chip-scale microscopy involves utilization of low-cost Complementary metal Oxide Semiconductor (CMOS) image sensors, computational image processing and micro-fabricated structural components. First, the sub-pixel resolving optofluidic microscope (SROFM), will be presented, which combines microfluidics and pixel super-resolution image reconstruction to perform high-throughput imaging of fluidic samples, such as blood cells. We discuss design parameters and construction of the device, as well as the resulting images and the resolution of the device, which was 0.66 µm at the highest acuity. The potential applications of SROFM for clinical diagnosis of malaria in the resource-limited settings is discussed.

Next, the implementations of ePetri, a self-imaging Petri dish platform with microscopy resolution, are presented. Here, we simply place the sample of interest on the surface of the image sensor and capture the direct shadow images under the illumination. By taking advantage of the inherent motion of the microorganisms, we achieve high resolution (~1 µm) imaging and long term culture of motile microorganisms over ultra large field-of-view (5.7 mm × 4.4 mm) in a specialized ePetri platform. We apply the pixel super-resolution reconstruction to a set of low-resolution shadow images of the microorganisms as they move across the sensing area of an image sensor chip and render an improved resolution image. We perform longitudinal study of Euglena gracilis cultured in an ePetri platform and image based analysis on the motion and morphology of the cells. The ePetri device for imaging non-motile cells are also demonstrated, by using the sweeping illumination of a light emitting diode (LED) matrix for pixel super-resolution reconstruction of sub-pixel shifted shadow images. Using this prototype device, we demonstrate the detection of waterborne parasites for the effective diagnosis of enteric parasite infection in resource-limited settings.

Then, we demonstrate the adaptation of a smartphone’s camera to function as a compact lensless microscope, which uses ambient illumination as its light source and does not require the incorporation of a dedicated light source. The method is also based on the image reconstruction with sweeping illumination technique, where the sequence of images are captured while the user is manually tilting the device around any ambient light source, such as the sun or a lamp. Image acquisition and reconstruction is performed on the device using a custom-built android application, constructing a stand-alone imaging device for field applications. We discuss the construction of the device using a commercial smartphone and demonstrate the imaging capabilities of our system.

Finally, we report on the implementation of fluorescence chip-scale microscope, based on a silo-filter structure fabricated on the pixel array of a CMOS image sensor. The extruded pixel design with metal walls between neighboring pixels successfully guides fluorescence emission through the thick absorptive filter to the photodiode layer of a pixel. Our silo-filter CMOS image sensor prototype achieves 13-µm resolution for fluorescence imaging over a wide field-of-view (4.8 mm × 4.4 mm). Here, we demonstrate bright-field and fluorescence longitudinal imaging of living cells in a compact, low-cost configuration.

正弦变化的振幅型光瞳滤波器

光瞳滤波器作为实现超分辨的基本元件之一，它的设计以及制作都非常重要。设计了一种正弦变化的振幅型光瞳滤波器，可以通过调节少量的参量实现各种不同的超分辨模式。选择正弦函数的周期以及光瞳中心点透过率变化两个参量来实现对最终超分辨效果的调节。数值计算结果表明：在整个人射光瞳上的透过率瞳函数分布具有0．5～2个正弦振幅周期时，较为合适。小于0．5个周期将不会有任何超分辨效果，大于2个周期超分辨效果反而变差。数值计算中还注意到，当周期数为整数时，斯特雷尔比将保持0．25不变。对正弦变化振幅型光瞳滤波器的计算结果，显示

Convex model predictive control for vehicular systems

In this work, the author presents a method called Convex Model Predictive Control (CMPC) to control systems whose states are elements of the rotation matrices SO(n) for n = 2, 3. This is done without charts or any local linearization, and instead is performed by operating over the orbitope of rotation matrices. This results in a novel model predictive control (MPC) scheme without the drawbacks associated with conventional linearization techniques such as slow computation time and local minima. Of particular emphasis is the application to aeronautical and vehicular systems, wherein the method removes many of the trigonometric terms associated with these systems’ state space equations. Furthermore, the method is shown to be compatible with many existing variants of MPC, including obstacle avoidance via Mixed Integer Linear Programming (MILP).

Horizontal Bloch line motion in magnetic bubble materials

The purpose of this work is to extend experimental and theoretical understanding of horizontal Bloch line (HBL) motion in magnetic bubble materials. The present theory of HBL motion is reviewed, and then extended to include transient effects in which the internal domain wall structure changes with time. This is accomplished by numerically solving the equations of motion for the internal azimuthal angle ɸ and the wall position q as functions of z, the coordinate perpendicular to the thin-film material, and time. The effects of HBL's on domain wall motion are investigated by comparing results from wall oscillation experiments with those from the theory. In these experiments, a bias field pulse is used to make a step change in equilibrium position of either bubble or stripe domain walls, and the wall response is measured by using transient photography. During the initial response, the dynamic wall structure closely resembles the initial static structure. The wall accelerates to a relatively high velocity (≈20 m/sec), resulting in a short (≈22 nsec ) section of initial rapid motion. An HBL gradually forms near one of the film surfaces as a result of local dynamic properties, and moves along the wall surface toward the film center. The presence of this structure produces low-frequency, triangular-shaped oscillations in which the experimental wall velocity is nearly constant, v_s≈ 5-8 m/sec. If the HBL reaches the opposite surface, i.e., if the average internal angle reaches an integer multiple of π, the momentum stored in the HBL is lost, and the wall chirality is reversed. This results in abrupt transitions to overdamped motion and changes in wall chirality, which are observed as a function of bias pulse amplitude. The pulse amplitude at which the n^th punch- through occurs just as the wall reaches equilibrium is given within 0.2 0e by H_n = (2v_sH'/γ)^1/2 • (nπ)^1/2 + H_sv), where H' is the effective field gradient from the surrounding domains, and H_sv is a small (less than 0.03 0e), effective drag field. Observations of wall oscillation in the presence of in-plane fields parallel to the wall show that HBL formation is suppressed by fields greater than about 40 0e (≈2πM_s), resulting in the high-frequency, sinusoidal oscillations associated with a simple internal wall structure.

Multipole moments in general relativity and dynamical perturbations of black-hole magnetospheres

This thesis consists of two parts. In Part I, we develop a multipole moment formalism in general relativity and use it to analyze the motion and precession of compact bodies. More specifically, the generic, vacuum, dynamical gravitational field of the exterior universe in the vicinity of a freely moving body is expanded in positive powers of the distance r away from the body's spatial origin (i.e., in the distance r from its timelike-geodesic world line). The expansion coefficients, called "external multipole moments,'' are defined covariantly in terms of the Riemann curvature tensor and its spatial derivatives evaluated on the body's central world line. In a carefully chosen class of de Donder coordinates, the expansion of the external field involves only integral powers of r ; no logarithmic terms occur. The expansion is used to derive higher-order corrections to previously known laws of motion and precession for black holes and other bodies. The resulting laws of motion and precession are expressed in terms of couplings of the time derivatives of the body's quadrupole and octopole moments to the external moments, i.e., to the external curvature and its gradient.

In part II, we study the interaction of magnetohydrodynamic (MHD) waves in a black-hole magnetosphere with the "dragging of inertial frames" effect of the hole's rotation - i.e., with the hole's "gravitomagnetic field." More specifically: we first rewrite the laws of perfect general relativistic magnetohydrodynamics (GRMHD) in 3+1 language in a general spacetime, in terms of quantities (magnetic field, flow velocity, ...) that would be measured by the ''fiducial observers” whose world lines are orthogonal to (arbitrarily chosen) hypersurfaces of constant time. We then specialize to a stationary spacetime and MHD flow with one arbitrary spatial symmetry (e.g., the stationary magnetosphere of a Kerr black hole); and for this spacetime we reduce the GRMHD equations to a set of algebraic equations. The general features of the resulting stationary, symmetric GRMHD magnetospheric solutions are discussed, including the Blandford-Znajek effect in which the gravitomagnetic field interacts with the magnetosphere to produce an outflowing jet. Then in a specific model spacetime with two spatial symmetries, which captures the key features of the Kerr geometry, we derive the GRMHD equations which govern weak, linealized perturbations of a stationary magnetosphere with outflowing jet. These perturbation equations are then Fourier analyzed in time t and in the symmetry coordinate x, and subsequently solved numerically. The numerical solutions describe the interaction of MHD waves with the gravitomagnetic field. It is found that, among other features, when an oscillatory external force is applied to the region of the magnetosphere where plasma (e⁺e^-) is being created, the magnetosphere responds especially strongly at a particular, resonant, driving frequency. The resonant frequency is that for which the perturbations appear to be stationary (time independent) in the common rest frame of the freshly created plasma and the rotating magnetic field lines. The magnetosphere of a rotating black hole, when buffeted by nonaxisymmetric magnetic fields anchored in a surrounding accretion disk, might exhibit an analogous resonance. If so then the hole's outflowing jet might be modulated at resonant frequencies ω=(m/2) Ω_H where m is an integer and Ω_H is the hole's angular velocity.

The possibilities and dangers in using malachite green in pisciculture.[Translation from: Informatsionnyi Byulleten Biologiya Vnutrennikh Vod No.3 17-21, 1969.]

For many years a dye has been used in the practise of pisciculture and pond management, which is known by the name of malachite green, and is used to combat fungus on fish, fish eggs and external animal parasites on fish. The authors describe the problem of the application of malachite green in pisciculture and undertake special, complementary research.

Numerical Studies of Topological Phases

The topological phases of matter have been a major part of condensed matter physics research since the discovery of the quantum Hall effect in the 1980s. Recently, much of this research has focused on the study of systems of free fermions, such as the integer quantum Hall effect, quantum spin Hall effect, and topological insulator. Though these free fermion systems can play host to a variety of interesting phenomena, the physics of interacting topological phases is even richer. Unfortunately, there is a shortage of theoretical tools that can be used to approach interacting problems. In this thesis I will discuss progress in using two different numerical techniques to study topological phases.

Recently much research in topological phases has focused on phases made up of bosons. Unlike fermions, free bosons form a condensate and so interactions are vital if the bosons are to realize a topological phase. Since these phases are difficult to study, much of our understanding comes from exactly solvable models, such as Kitaev's toric code, as well as Levin-Wen and Walker-Wang models. We may want to study systems for which such exactly solvable models are not available. In this thesis I present a series of models which are not solvable exactly, but which can be studied in sign-free Monte Carlo simulations. The models work by binding charges to point topological defects. They can be used to realize bosonic interacting versions of the quantum Hall effect in 2D and topological insulator in 3D. Effective field theories of "integer" (non-fractionalized) versions of these phases were available in the literature, but our models also allow for the construction of fractional phases. We can measure a number of properties of the bulk and surface of these phases.

Few interacting topological phases have been realized experimentally, but there is one very important exception: the fractional quantum Hall effect (FQHE). Though the fractional quantum Hall effect we discovered over 30 years ago, it can still produce novel phenomena. Of much recent interest is the existence of non-Abelian anyons in FQHE systems. Though it is possible to construct wave functions that realize such particles, whether these wavefunctions are the ground state is a difficult quantitative question that must be answered numerically. In this thesis I describe progress using a density-matrix renormalization group algorithm to study a bilayer system thought to host non-Abelian anyons. We find phase diagrams in terms of experimentally relevant parameters, and also find evidence for a non-Abelian phase known as the "interlayer Pfaffian".

Some experiments on solving multistage stochastic mixed 0-1 programs with time stochastic dominance constraints

In this work we extend to the multistage case two recent risk averse measures for two-stage stochastic programs based on first- and second-order stochastic dominance constraints induced by mixed-integer linear recourse. Additionally, we consider Time Stochastic Dominance (TSD) along a given horizon. Given the dimensions of medium-sized problems augmented by the new variables and constraints required by those risk measures, it is unrealistic to solve the problem up to optimality by plain use of MIP solvers in a reasonable computing time, at least. Instead of it, decomposition algorithms of some type should be used. We present an extension of our Branch-and-Fix Coordination algorithm, so named BFC-TSD, where a special treatment is given to cross scenario group constraints that link variables from different scenario groups. A broad computational experience is presented by comparing the risk neutral approach and the tested risk averse strategies. The performance of the new version of the BFC algorithm versus the plain use of a state-of-the-artMIP solver is also reported.

Some central limit theorems for doubly restricted partitions

Let P_{K, L}(N) be the number of unordered partitions of a positive integer N into K or fewer positive integer parts, each part not exceeding L. A distribution of the form

Ʃ/N≤x P_K,L(N)

is considered first. For any fixed K, this distribution approaches a piecewise polynomial function as L increases to infinity. As both K and L approach infinity, this distribution is asymptotically normal. These results are proved by studying the convergence of the characteristic function.

The main result is the asymptotic behavior of P_K,K(N) itself, for certain large K and N. This is obtained by studying a contour integral of the generating function taken along the unit circle. The bulk of the estimate comes from integrating along a small arc near the point 1. Diophantine approximation is used to show that the integral along the rest of the circle is much smaller.

Thermopower in Two-Dimensional Electron Systems

The subject of this thesis is the measurement and interpretation of thermopower in high-mobility two-dimensional electron systems (2DESs). These 2DESs are realized within state-of-the-art GaAs/AlGaAs heterostructures that are cooled to temperatures as low as T = 20 mK. Much of this work takes place within strong magnetic fields where the single-particle density of states quantizes into discrete Landau levels (LLs), a regime best known for the quantum Hall effect (QHE). In addition, we review a novel hot-electron technique for measuring thermopower of 2DESs that dramatically reduces the influence of phonon drag.

Early chapters concentrate on experimental materials and methods. A brief overview of GaAs/AlGaAs heterostructures and device fabrication is followed by details of our cryogenic setup. Next, we provide a primer on thermopower that focuses on 2DESs at low temperatures. We then review our experimental devices, temperature calibration methods, as well as measurement circuits and protocols.

Latter chapters focus on the physics and thermopower results in the QHE regime. After reviewing the basic phenomena associated with the QHE, we discuss thermopower in this regime. Emphasis is given to the relationship between diffusion thermopower and entropy. Experimental results demonstrate this relationship persists well into the fractional quantum Hall (FQH) regime.

Several experimental results are reviewed. Unprecedented observations of the diffusion thermopower of a high-mobility 2DES at temperatures as high as T = 2 K are achieved using our hot-electron technique. The composite fermion (CF) effective mass is extracted from measurements of thermopower at LL filling factor ν = 3/2. The thermopower versus magnetic field in the FQH regime is shown to be qualitatively consistent with a simple entropic model of CFs. The thermopower at ν = 5/2 is shown to be quantitatively consistent with the presence of non-Abelian anyons. An abrupt collapse of thermopower is observed at the onset of the reentrant integer quantum Hall effect (RIQHE). And the thermopower at temperatures just above the RIQHE transition suggests the existence of an unconventional conducting phase.

Smooth Banach spaces and approximations

If E and F are real Banach spaces let C^p,q(E, F) O ≤ q ≤ p ≤ ∞, denote those maps from E to F which have p continuous Frechet derivatives of which the first q derivatives are bounded. A Banach space E is defined to be C^p,q smooth if C^p,q(E,R) contains a nonzero function with bounded support. This generalizes the standard C^p smoothness classification.

If an L^p space, p ≥ 1, is C^q smooth then it is also C^q,q smooth so that in particular L^p for p an even integer is C^∞,∞ smooth and L^p for p an odd integer is C^p-1,p-1 smooth. In general, however, a C^p smooth B-space need not be C^p,p smooth. C_o is shown to be a non-C^2,2 smooth B-space although it is known to be C^∞ smooth. It is proved that if E is C^p,1 smooth then C_o(E) is C^p,1 smooth and if E has an equivalent C^p norm then c_o(E) has an equivalent C^p norm.

Various consequences of C^p,q smoothness are studied. If f ϵ C^p,q(E,F), if F is C^p,q smooth and if E is non-C^p,q smooth, then the image under f of the boundary of any bounded open subset U of E is dense in the image of U. If E is separable then E is C^p,q smooth if and only if E admits C^p,q partitions of unity; E is C^p,psmooth, p ˂∞, if and only if every closed subset of E is the zero set of some C^P function.

f ϵ C^q(E,F), 0 ≤ q ≤ p ≤ ∞, is said to be C_p,q approximable on a subset U of E if for any ϵ ˃ 0 there exists a g ϵ C^p(E,F) satisfying

sup/xϵU, O≤k≤q ‖ D^k f(x) - D^k g(x) ‖ ≤ ϵ.

It is shown that if E is separable and C^p,q smooth and if f ϵ C^q(E,F) is C_p,q approximable on some neighborhood of every point of E, then F is C_p,q approximable on all of E.

In general it is unknown whether an arbitrary function in C¹(l², R) is C_2,1 approximable and an example of a function in C¹(l², R) which may not be C_2,1 approximable is given. A weak form of C_∞,q, q≥1, to functions in C^q(l², R) is proved: Let {U_α} be a locally finite cover of l² and let {T_α} be a corresponding collection of Hilbert-Schmidt operators on l². Then for any f ϵ C^q(l²,F) such that for all α

sup ‖ D^k(f(x)-g(x))[T_αh]‖ ≤ 1.

xϵU_α,‖h‖≤1, 0≤k≤q

Distributed Control and Optimization for Communication and Power Systems

We are at the cusp of a historic transformation of both communication system and electricity system. This creates challenges as well as opportunities for the study of networked systems. Problems of these systems typically involve a huge number of end points that require intelligent coordination in a distributed manner. In this thesis, we develop models, theories, and scalable distributed optimization and control algorithms to overcome these challenges.

This thesis focuses on two specific areas: multi-path TCP (Transmission Control Protocol) and electricity distribution system operation and control. Multi-path TCP (MP-TCP) is a TCP extension that allows a single data stream to be split across multiple paths. MP-TCP has the potential to greatly improve reliability as well as efficiency of communication devices. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP-friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algorithms and motivate a new algorithm Balia (balanced linked adaptation) which generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscillation. We have implemented Balia in the Linux kernel. We use our prototype to compare the new proposed algorithm Balia with existing MP-TCP algorithms.

Our second focus is on designing computationally efficient algorithms for electricity distribution system operation and control. First, we develop efficient algorithms for feeder reconfiguration in distribution networks. The feeder reconfiguration problem chooses the on/off status of the switches in a distribution network in order to minimize a certain cost such as power loss. It is a mixed integer nonlinear program and hence hard to solve. We propose a heuristic algorithm that is based on the recently developed convex relaxation of the optimal power flow problem. The algorithm is efficient and can successfully computes an optimal configuration on all networks that we have tested. Moreover we prove that the algorithm solves the feeder reconfiguration problem optimally under certain conditions. We also propose a more efficient algorithm and it incurs a loss in optimality of less than 3% on the test networks.

Second, we develop efficient distributed algorithms that solve the optimal power flow (OPF) problem on distribution networks. The OPF problem determines a network operating point that minimizes a certain objective such as generation cost or power loss. Traditionally OPF is solved in a centralized manner. With increasing penetration of volatile renewable energy resources in distribution systems, we need faster and distributed solutions for real-time feedback control. This is difficult because power flow equations are nonlinear and kirchhoff's law is global. We propose solutions for both balanced and unbalanced radial distribution networks. They exploit recent results that suggest solving for a globally optimal solution of OPF over a radial network through a second-order cone program (SOCP) or semi-definite program (SDP) relaxation. Our distributed algorithms are based on the alternating direction method of multiplier (ADMM), but unlike standard ADMM-based distributed OPF algorithms that require solving optimization subproblems using iterative methods, the proposed solutions exploit the problem structure that greatly reduce the computation time. Specifically, for balanced networks, our decomposition allows us to derive closed form solutions for these subproblems and it speeds up the convergence by 1000x times in simulations. For unbalanced networks, the subproblems reduce to either closed form solutions or eigenvalue problems whose size remains constant as the network scales up and computation time is reduced by 100x compared with iterative methods.

基于低速面阵CCD的正弦相位调制干涉测量

正弦相位调制(SPM)干涉测量技术用于表面形貌测量时, 需要帧速高于300 frame/s的图像传感器, 同时要求调制信号频率与图像传感器帧速成确定的整数倍关系。提出一种基于低速CCD(30 frame/s)的帧速可调的高速图像传感技术, 通过控制每帧像素总数提高CCD帧速, 研制出一种高帧速图像传感器, 帧速可达300～1600 frame/s, 且每帧大小连续可调。将该CCD传感器用于正弦相位调制干涉泰曼-格林干涉仪, 测量镀膜玻璃板表面形貌, 当CCD图像传感器的帧速与调制信号频率呈16, 8, 4

A bibliography of works for the identification of freshwater invertebrates in the British Isles

This bibliography covers the literature up to the end of 1978. The criteria used in the selection of references were that they should aid identification of invertebrates directly; thus, works solely concerned with the taxonomy of a particular group are in general omitted unless they contain a key. Some check-lists are however included where they give current nomenclature. The references are arranged alphabetically within each group and deal mainly with macro-invertebrates but include available keys to some microscopic invertebrates. Internal parasites and hymenopterous parasitoids are omitted. For insects the life stages to which the key applies are given where this is not clear in the reference. A number of keys to non-aquatic stages have been included in the hope that they may prove useful in certain circumstances. In addition, under a general head, latest check-lists are referred to together with bibliographies of algal keys and a guide for the identification of British water plants.