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.

Characterization of the human SCF ubiquitin ligases - structure, function, and regulation

The SCF ubiquitin ligase complex of budding yeast triggers DNA replication by cata lyzi ng ubiquitination of the S phase CDK inhibitor SIC1. SCF is composed of several evolutionarily conserved proteins, including ySKP1, CDC53 (Cullin), and the F-box protein CDC4. We isolated hSKP1 in a two-hybrid screen with hCUL1, the human homologue of CDC53. We showed that hCUL1 associates with hSKP1 in vivo and directly interacts with hSKP1 and the human F-box protein SKP2 in vitro, forming an SCF-Iike particle. Moreover, hCUL1 complements the growth defect of yeast CDC53^(ts) mutants, associates with ubiquitination-promoting activity in human cell extracts, and can assemble into functional, chimeric ubiquitin ligase complexes with yeast SCF components. These data demonstrated that hCUL1 functions as part of an SCF ubiquitin ligase complex in human cells. However, purified human SCF complexes consisting of CUL1, SKP1, and SKP2 are inactive in vitro, suggesting that additional factors are required.

Subsequently, mammalian SCF ubiquitin ligases were shown to regulate various physiological processes by targeting important cellular regulators, like lĸBα, β-catenin, and p27, for ubiquitin-dependent proteolysis by the 26S proteasome. Little, however, is known about the regulation of various SCF complexes. By using sequential immunoaffinity purification and mass spectrometry, we identified proteins that interact with human SCF components SKP2 and CUL1 in vivo. Among them we identified two additional SCF subunits: HRT1, present in all SCF complexes, and CKS1, that binds to SKP2 and is likely to be a subunit of SCF5^(SKP2) complexes. Subsequent work by others demonstrated that these proteins are essential for SCF activity. We also discovered that COP9 Signalosome (CSN), previously described in plants as a suppressor of photomorphogenesis, associates with CUL1 and other SCF subunits in vivo. This interaction is evolutionarily conserved and is also observed with other Cullins, suggesting that all Cullin based ubiquitin ligases are regulated by CSN. CSN regulates Cullin Neddylation presumably through CSNS/JAB1, a stochiometric Signalosome subunit and a putative deneddylating enzyme. This work sheds light onto an intricate connection that exists between signal transduction pathways and protein degradation machinery inside the cell and sets stage for gaining further insights into regulation of protein degradation.

Developmentally regulated transcription factors in Drosophila melanogaster

During early stages of Drosophila development the heat shock response cannot be induced. It is reasoned that the adverse effects on cell cycle and cell growth brought about by Hsp70 induction must outweigh the beneficial aspects of Hsp70 induction in the early embryo. Although the Drosophila heat shock transcription factor (dHSF) is abundant in the early embryo, it does not enter the nucleus in response to heat shock. In older embryos and in cultured cells the factor is localized within the nucleus in an apparent trimeric structure that binds DNA with high affinity. The domain responsible for nuclear localization upon stress resides between residues 390 and 420 of the dHSF. Using that domain as bait in a yeast two-hybrid system we now report the identification and cloning of a nuclear transport protein Drosophila karyopherin-α3(dKap- α3). Biochemical methods demonstrate that the dKap-α3 protein binds specifically to the dHSF's nuclear localization sequence (NLS). Furthermore, the dKap-α3 protein does not associate with NLSs that contain point mutations which are not transported in vivo. Nuclear docking studies also demonstrate specific nuclear targeting of the NLS substrate by dKap-α3.Consistant with previous studies demonstrating that early Drosophila embryos are refractory to heat shock as a result of dHSF nuclear exclusion, we demonstrate that the early embryo is deficient in dKap-α3 protein through cycle 12. From cycle 13 onward the transport factor is present and the dHSF is localized within the nucleus thus allowing the embryo to respond to heat shock.

The pair-rule gene fushi tarazu (ftz) is a well-studied zygotic segmentation gene that is necessary for the development of the even-numbered parasegments in Drosophila melanogastor. During early embryogenesis, ftz is expressed in a characteristic pattern of seven stripes, one in each of the even-numbered parasegments. With a view to understand how ftz is transcriptionally regulated, cDNAs that encode transcription factors that bind to the zebra element of the ftz promoter have been cloned. Chapter Ill reports the cloning and characterization of the eDNA encoding zeb-1 (zebra element binding protein), a novel steroid receptor-like molecule that specifically binds to a key regulatory element of the ftz promoter. In transient transfection assays employing Drosophila tissue culture cells, it has been shown that zeb-1 as well as a truncated zeb-1 polypeptide (zeb480) that lacks the putative ligand binding domain function as sequencespecific trans-activators of the ftz gene.

The Oct factors are members of the POU family of transcription factors that are shown to play important roles during development in mammals. Chapter IV reports the eDNA cloning and expression of a Drosophila Oct transcription factor. Whole mount in-situ hybridization experiments revealed that the spatial expression patterns of this gene during embryonic development have not yet been observed for any other gene. In early embryogenesis, its transcripts are transiently expressed as a wide uniform band from 20-40% of the egg length, very similar to that of gap genes. This pattern progressively resolves into a series of narrower stripes followed by expression in fourteen stripes. Subsequently, transcripts from this gene are expressed in the central nervous system and the brain. When expressed in the yeast Saccharomyces cerevisiae, this Drosophila factor functions as a strong, octamer-dependent activator of transcription. The data strongly suggest possible functions for the Oct factor in pattern formation in Drosophila that might transcend the boundaries of genetically defined segmentation genes.

A fundamental approach to phase noise reduction in hybrid Si/III-V lasers

Spontaneous emission into the lasing mode fundamentally limits laser linewidths. Reducing cavity losses provides two benefits to linewidth: (1) fewer excited carriers are needed to reach threshold, resulting in less phase-corrupting spontaneous emission into the laser mode, and (2) more photons are stored in the laser cavity, such that each individual spontaneous emission event disturbs the phase of the field less. Strong optical absorption in III-V materials causes high losses, preventing currently-available semiconductor lasers from achieving ultra-narrow linewidths. This absorption is a natural consequence of the compromise between efficient electrical and efficient optical performance in a semiconductor laser. Some of the III-V layers must be heavily doped in order to funnel excited carriers into the active region, which has the side effect of making the material strongly absorbing.

This thesis presents a new technique, called modal engineering, to remove modal energy from the lossy region and store it in an adjacent low-loss material, thereby reducing overall optical absorption. A quantum mechanical analysis of modal engineering shows that modal gain and spontaneous emission rate into the laser mode are both proportional to the normalized intensity of that mode at the active region. If optical absorption near the active region dominates the total losses of the laser cavity, shifting modal energy from the lossy region to the low-loss region will reduce modal gain, total loss, and the spontaneous emission rate into the mode by the same factor, so that linewidth decreases while the threshold inversion remains constant. The total spontaneous emission rate into all other modes is unchanged.

Modal engineering is demonstrated using the Si/III-V platform, in which light is generated in the III-V material and stored in the low-loss silicon material. The silicon is patterned as a high-Q resonator to minimize all sources of loss. Fabricated lasers employing modal engineering to concentrate light in silicon demonstrate linewidths at least 5 times smaller than lasers without modal engineering at the same pump level above threshold, while maintaining the same thresholds.

Literature Review of Integrated Impact Assessment Models of Climate Change with Emphasis on Damage Functions

35 p.

Experimental study of the upper hybrid echo in plasmas

The two-pulse stimulated radiation of dense (10^9/cm^3 < ne ≤ 10^(11) /cm^3) nonuniform neon and argon afterglow plasma columns longitudinally immersed in a magnetic field is studied. The magnetic field is very homogeneous over the plasma volume (∆B/B~.01%). If the S-band microwave pulses' center frequency is such that they resonantly excite a narrow band of plasma upper hybrid oscillations close to the maximum upper hybrid frequency of the column, strong two pulse echoes are observed. This new echo process is called the upper hybrid echo. The echo spectrum, echo power and echo width were studied as a function of the pulse peak power P, pulse separation τ, relative density (ω_(po)/ω)^2, and relative cyclotron frequency (ω_c/ω). The complex but systematic variations of the echo properties as a function of the above-mentioned parameters arc found to be in qualitative agreement with those predicted by a theory of Gould and Blum based upon a simple nonuniform unidimensional cold plasma slab model. The possible effects of electron neutral and electron ion collisions not retained in the theoretical model are discussed.

The existence of a new type of cyclotron echo, different from that of Hill and Kaplan and not predicted by the Blum and Gould model is documented. It is believed to be also of a collective effect nature and can probably be described in terms of a theory retaining some hot plasma effects.

Upper hybrid resonance absorption and scattering from a plasma column

The electromagnetic scattering and absorption properties of small (kr~1/2) inhomogeneous magnetoplasma columns are calculated via the full set of Maxwell's equations with tensor dielectric constitutive relation. The cold plasma model with collisional damping is used to describe the column. The equations are solved numerically, subject to boundary conditions appropriate to an infinite parallel strip line and to an incident plane wave. The results are similar for several density profiles and exhibit semiquantitative agreement with measurements in waveguide. The absorption is spatially limited, especially for small collision frequency, to a narrow hybrid resonant layer and is essentially zero when there is no hybrid layer in the column. The reflection is also enhanced when the hybrid layer is present, but the value of the reflection coefficient is strongly modified by the presence of the glass tube. The nature of the solutions and an extensive discussion of the conditions under which the cold collisional model should yield valid results is presented.

Observations on the behaviour of Polyphemus pediculus and functions of its extremities in the process of feeding. [Translation of: Materialy po biologii i gidrologii Volzhskikh vodokhranilishch, pp. 13-16. Moscow, 1965]

The author summarises observations on the behaviour of Polyphemus pediculus and functions of its extremities in the process of feeding. The crustacean Polyphemus pediculus seizes its prey, kills it and pulverises its food with the help of its extremities. Therefore for a study of its feeding method was necessary not only to have been acquainted in detail with the structure of its extremities, but also to have observed their interaction for the accomplishment of the stated functions.

Information processing and higher psychological functions in the disconnected hemispheres of human commissurotomy patients

Several patients of P. J. Vogel who had undergone cerebral commissurotomy for the control of intractable epilepsy were tested on a variety of tasks to measure aspects of cerebral organization concerned with lateralization in hemispheric function. From tests involving identification of shapes it was inferred that in the absence of the neocortical commissures, the left hemisphere still has access to certain types of information from the ipsilateral field. The major hemisphere can still make crude differentiations between various left-field stimuli, but is unable to specify exact stimulus properties. Most of the time the major hemisphere, having access to some ipsilateral stimuli, dominated the minor hemisphere in control of the body.

Competition for control of the body between the hemispheres is seen most clearly in tests of minor hemisphere language competency, in which it was determined that though the minor hemisphere does possess some minimal ability to express language, the major hemisphere prevented its expression much of the time. The right hemisphere was superior to the left in tests of perceptual visualization, and the two hemispheres appeared to use different strategies in attempting to solve the problems, namely, analysis for the left hemisphere and synthesis for the right hemisphere.

Analysis of the patients' verbal and performance I.Q.'s, as well as observations made throughout testing, suggest that the corpus callosum plays a critical role in activities that involve functions in which the minor hemisphere normally excels, that the motor expression of these functions may normally come through the major hemisphere by way of the corpus callosum.

Lateral specialization is thought to be an evolutionary adaptation which overcame problems of a functional antagonism between the abilities normally associated with the two hemispheres. The tests of perception suggested that this function lateralized into the mute hemisphere because of an active counteraction by language. This latter idea was confirmed by the finding that left-handers, in whom there is likely to be bilateral language centers, are greatly deficient on tests of perception.

Extension theorems for functions of vanishing mean oscillation

A locally integrable function is said to be of vanishing mean oscillation (VMO) if its mean oscillation over cubes in R^d converges to zero with the volume of the cubes. We establish necessary and sufficient conditions for a locally integrable function defined on a bounded measurable set of positive measure to be the restriction to that set of a VMO function.

We consider the similar extension problem pertaining to BMO(ρ) functions; that is, those VMO functions whose mean oscillation over any cube is O(ρ(l(Q))) where l(Q) is the length of Q and ρ is a positive, non-decreasing function with ρ(0⁺) = 0.

We apply these results to obtain sufficient conditions for a Blaschke sequence to be the zeros of an analytic BMO(ρ) function on the unit disc.

A generalized Hausdorff dimension for functions and sets

Let E be a compact subset of the n-dimensional unit cube, 1_n, and let C be a collection of convex bodies, all of positive n-dimensional Lebesgue measure, such that C contains bodies with arbitrarily small measure. The dimension of E with respect to the covering class C is defined to be the number

d_C(E) = sup(β:H_{β, C}(E) > 0),

where H_{β, C} is the outer measure

inf(Ʃm(C_i)^β:UC_i Ↄ E, C_i ϵ C) .

Only the one and two-dimensional cases are studied. Moreover, the covering classes considered are those consisting of intervals and rectangles, parallel to the coordinate axes, and those closed under translations. A covering class is identified with a set of points in the left-open portion, 1’_n, of 1_n, whose closure intersects 1_n - 1’_n. For n = 2, the outer measure H_{β, C} is adopted in place of the usual:

Inf(Ʃ(diam. (C_i))^β: UC_i Ↄ E, C_i ϵ C),

for the purpose of studying the influence of the shape of the covering sets on the dimension d_C(E).

If E is a closed set in 1₁, let M(E) be the class of all non-decreasing functions μ(x), supported on E with μ(x) = 0, x ≤ 0 and μ(x) = 1, x ≥ 1. Define for each μ ϵ M(E),

d_C(μ) = lim/c → inf/0 log ∆μ(c)/log c , (c ϵ C)

where ∆μ(c) = v/x (μ(x+c) – μ(x)). It is shown that

d_C(E) = sup (d_C(μ):μ ϵ M(E)).

This notion of dimension is extended to a certain class Ӻ of sub-additive functions, and the problem of studying the behavior of d_C(E) as a function of the covering class C is reduced to the study of d_C(f) where f ϵ Ӻ. Specifically, the set of points in 1₁,

(*) {d_B(F), d_C(f)): f ϵ Ӻ}

is characterized by a comparison of the relative positions of the points of B and C. A region of the form (*) is always closed and doubly-starred with respect to the points (0, 0) and (1, 1). Conversely, given any closed region in 1₂, doubly-starred with respect to (0, 0) and (1, 1), there are covering classes B and C such that (*) is exactly that region. All of the results are shown to apply to the dimension of closed sets E. Similar results can be obtained when a finite number of covering classes are considered.

In two dimensions, the notion of dimension is extended to the class M, of functions f(x, y), non-decreasing in x and y, supported on 1₂ with f(x, y) = 0 for x · y = 0 and f(1, 1) = 1, by the formula

d_C(f) = lim/s · t → inf/0 log ∆f(s, t)/log s · t , (s, t) ϵ C

where

∆f(s, t) = V/x, y (f(x+s, y+t) – f(x+s, y) – f(x, y+t) + f(x, t)).

A characterization of the equivalence d_C1(f) = d_C2(f) for all f ϵ M, is given by comparison of the gaps in the sets of products s · t and quotients s/t, (s, t) ϵ C_i (I = 1, 2).

A hybrid-parallel framework for the nonlinear seismic analysis of very tall buildings

FRAME3D, a program for the nonlinear seismic analysis of steel structures, has previously been used to study the collapse mechanisms of steel buildings up to 20 stories tall. The present thesis is inspired by the need to conduct similar analysis for much taller structures. It improves FRAME3D in two primary ways.

First, FRAME3D is revised to address specific nonlinear situations involving large displacement/rotation increments, the backup-subdivide algorithm, element failure, and extremely narrow joint hysteresis. The revisions result in superior convergence capabilities when modeling earthquake-induced collapse. The material model of a steel fiber is also modified to allow for post-rupture compressive strength.

Second, a parallel FRAME3D (PFRAME3D) is developed. The serial code is optimized and then parallelized. A distributed-memory divide-and-conquer approach is used for both the global direct solver and element-state updates. The result is an implicit finite-element hybrid-parallel program that takes advantage of the narrow-band nature of very tall buildings and uses nearest-neighbor-only communication patterns.

Using three structures of varied sized, PFRAME3D is shown to compute reproducible results that agree with that of the optimized 1-core version (displacement time-history response root-mean-squared errors are ~〖10〗^(-5) m) with much less wall time (e.g., a dynamic time-history collapse simulation of a 60-story building is computed in 5.69 hrs with 128 cores—a speedup of 14.7 vs. the optimized 1-core version). The maximum speedups attained are shown to increase with building height (as the total number of cores used also increases), and the parallel framework can be expected to be suitable for buildings taller than the ones presented here.

PFRAME3D is used to analyze a hypothetical 60-story steel moment-frame tube building (fundamental period of 6.16 sec) designed according to the 1994 Uniform Building Code. Dynamic pushover and time-history analyses are conducted. Multi-story shear-band collapse mechanisms are observed around mid-height of the building. The use of closely-spaced columns and deep beams is found to contribute to the building's “somewhat brittle” behavior (ductility ratio ~2.0). Overall building strength is observed to be sensitive to whether a model is fracture-capable.