Property:Abstract
From Murray Wiki
Jump to navigationJump to search
This is a property of type Text.
S
We present a synthesis method for communication protocols for active safety applications that satisfy certain formal specifications on quality of service requirements. The protocols are developed to provide reliable communication services for automobile active safety applications. The synthesis method transforms a specification into a distributed implementation of senders and receivers that together satisfy the quality of service requirements by transmitting messages over an unreliable medium. We develop a specification language and an execution model for the implementations, and demonstrate the viability of our method by developing a protocol for a traffic scenario in which a car runs a red light at a busy intersection. +
C
We present a theory of contracts that is centered around reacting to failures and explore it from a general assume-guarantee perspective as well as from a concrete context of automated synthesis from linear temporal logic (LTL) specifications, all of which are compliant with a contract metatheory introduced by Benveniste et al. We also show how to obtain an automated procedure for synthesizing reactive assume-guarantee contracts and implementations that capture ideas like optimality and robustness based on assume-guarantee lattices computed from antitone Galois connection fixpoints. Lastly, we provide an example of a “reactive GR(1)” contract and a simulation of its implementation. +
D
We present an approach that allows mission and contingency management to be achieved in a distributed and dynamic manner without any central control over multiple software modules. This approach comprises two key elements---a mission management subsystem and a Canonical Software Architecture (CSA) for a planning subsystem. The mission management subsystem works in conjunction with the planning subsystem to dynamically replan in reaction to contingencies. The CSA ensures the consistency of the states of all the software modules in the planning subsystem. System faults are identified and replanning strategies are performed distributedly in the planning and the mission management subsystems through the CSA. The approach has been implemented and tested on Alice, an autonomous vehicle developed by the California Institute of Technology for the 2007 DARPA Urban Challenge. +
A
An automated model reduction tool to guide the design and analysis of synthetic biological circuits +
We present an automated model reduction algorithm that uses quasi-steady state approximation based reduction to minimize the error between the desired outputs. Additionally, the algorithm minimizes the sensitivity of the error with respect to parameters to ensure robust performance of the reduced model in the presence of parametric uncertainties. We develop the theory for this model reduction algorithm and present the implementation of the algorithm that can be used to perform model reduction of given SBML models. To demonstrate the utility of this algorithm, we consider the design of a synthetic biological circuit to control the population density and composition of a consortium consisting of two different cell strains. We show how the model reduction algorithm can be used to guide the design and analysis of this circuit. +
We present an identification framework for biochemical systems that allows multiple candidate models to be compared. This framework is designed to select a model that fits the data while maintaining model simplicity. The model identification task is divided into a parameter estimation stage and a model comparison stage. Model selection is based on calculating Akaike's Information Criterion, which is a systematic method for determining the model that best represents a set of experimental data. Two case studies are presented: a simulated transcriptional control circuit and a system of oscillators that has been built and characterized in vitro. In both examples the multi-model framework is able to discriminate between model candidates to select the one that best describes the data. +
U
We present the results from a flight experiment demonstrating two significant advances in software enabled
control: optimization-based control using real-time trajectory generation and logical programming environments for
formal analysis of control software. Our demonstration platform consisted of a human-piloted F-15 jet flying together
with an autonomous T-33 jet. We describe the behavior of the system in two scenarios. In the first, nominal state
communications were present and the autonomous aircraft maintained formation as the human pilot flew maneuvers. In
the second, we imposed the loss of high-rate communications and demonstrated an autonomous safe âlost wingmanâ
procedure to increase separation and re-acquire contact. The flight demonstration included both a nominal formation
flight component and an execution of the lost wingman scenario. +
C
We propose a compositional stability analysis methodology for verifying properties of systems that are interconnections of multiple subsystems. The proposed method assembles stability certificates for the interconnected system based on the certificates for the input-output properties of the subsystems. The hierarchy in the analysis is achieved by utilizing dual decomposition ideas in optimization. Decoupled subproblems establish subsystem level input-output properties whereas the ``master'' problem imposes and updates the conditions on the subproblems toward ensuring interconnected system level stability properties. Both global stabilityanalysis and region-of-attraction analysis are discussed. +
R
Reverse Engineering Combination Therapies for Evolutionary Dynamics of Disease: An Hinfty Approach +
We propose a general algorithm for the systematic design of feedback strategies to stabilize the evolutionary dynamics of a generic disease model using an H1 approach. We show that designing antibody concentrations can be cast as an H1 state feedback synthesis problem, where the feedback gain is constrained to not only be strictly diagonal, but also that its diagonal elements satisfy an overdetermined set of linear equations. Leveraging recent results in positive systems, we additionally show that our algorithm always converges to a stabilizing controller. +
H
We propose a method for eliminating variables from component specifications during the decomposition of GR(1) properties into contracts. The variables that can be eliminated are identified by parameterizing the communication architecture to investigate the dependence of realizability on the availability of information. We prove that the selected variables can be hidden from other components, while still expressing the resulting specification as a game with full information with respect to the remaining variables. The values of other variables need not be known all the time, so we hide them for part of the time, thus reducing the amount of information that needs to be communicated between components. We improve on our previous results on algorithmic decomposition of GR(1) properties, and prove existence of decompositions in the full information case. We use semantic methods of computation based on binary decision diagrams. To recover the constructed specifications so that humans can read them, we implement exact symbolic minimal covering over the lattice of integer orthotopes, thus deriving minimal formulae in disjunctive normal form over integer variable intervals. +
S
Strategy-Driven Partitioning into Switching Modes for Piecewise-Affine Systems with Continuous Environments +
We propose a methodology for abstracting discrete-time piecewise-affine systems influenced by additive continuous environment variables, to synthesize correct-by-construction controllers from linear temporal logic specifications. The proposed algorithm partitions the environment domain into polytopes, considered as modes controlled by the environment. In each mode the environment variable is treated as a bounded disturbance for the system. Mode polytopes are iteratively enlarged while a strategy isomorphism between successive system partitions can be constructed. Isomorphisms are obtained by solving the stable marriage problem after proving that our case admits a unique solution. This leads to mapping high-level symbolic variables to equivalence classes of polytopes, instead of single polytopes as in other works. We thus avoid the need to merge partitions, which can create sliver polytopes, causing numerical problems during reachability computations. The approach enables using the same strategy over partitions that have an isomorphic subgraph relevant to the strategy. Reachability checks between neighboring partitions are used to reduce non-determinism introduced by switching and allow continuous restoration of discrete state. If bifurca- tions occur that prevent strategy reuse, then switched system game synthesis is performed, and a logic modeling formalism proposed that avoids trivial cyclic counterexamples. +
A
We propose a methodology for automatic synthesis of embedded control software that accounts for exogenous disturbances. The resulting system is guaranteed, by construction, to satisfy a given specification expressed in linear temporal logic. The embedded control software consists of three components: a goal generator, a trajectory planner, and a continuous controller. We demonstrate the effectiveness of the proposed technique through an example of an autonomous vehicle navigating an urban environment. This example also illustrates that the system is not only robust with respect to exogenous disturbances but also capable of handling violation of the environment assumptions. +
M
We propose a model for planar carangiform swimming based on conservative equations for
the interaction of a rigid body and an incompressible fluid. We account for the generation
of thrust due to vortex shedding through controlled coupling terms. We investigate the
correct form of this coupling experimentally with a robotic propulsor, comparing its
observed behavior with that predicted by unsteady hydrodynamics. Our analysis of thrust
generation by an oscillating hydrofoil allows us to characterize and evaluate certain
families of gaits. Our final swimming model takes the form of a control-affine nonlinear
system. +
N
We propose a negative feedback architecture that regulates activity of artificial genes, or "genelets", to meet their output downstream demand, achieving robustness with respect to uncertain open-loop output production rates. In particular, we consider the case where the outputs of two genelets interact to form a single assembled product. We show with analysis and experiments that negative autoregulation matches the production and demand of the outputs: the magnitude of the regulatory signal is proportional to the error between the circuit output concentration and its actual demand. This two-device system is experimentally implemented using in vitro transcriptional networks, where reactions are systematically designed by optimizing nucleic acid sequences with publicly available software packages. We build a predictive ordinary differential equation (ODE) model that captures the dynamics of the system, and can be used to numerically assess the scalability of this architecture to larger sets of interconnected genes. Finally, with numerical simulations we contrast our negative autoregulation scheme with a cross-activation architecture, which is less scalable and results in slower response times. +
L
We propose a new abstraction refinement procedure based on machine learning to improve the performance of nonlinear constraint solving algorithms on large-scale problems. The proposed approach decomposes the original set of constraints into smaller subsets, and uses learning algorithms to propose sequences of abstractions that take the form of conjunctions of classifiers. The core procedure is a refinement loop that keeps improving the learned results based on counterexamples that are obtained from partial constraints that are easy to solve. Experiments show that the proposed techniques significantly improve the performance of state-of-the-art constraint solvers on many challenging benchmarks. The mechanism is capable of producing intermediate symbolic abstractions that are also important for many applications and for understanding the internal structures of hard constraint solving problems. +
M
We propose a planar model for the swimming
of certain marine animals based on
reduced Euler-Lagrange equations for the interaction of a rigid body and
an incompressible fluid.
This model assumes the form of a control-affine nonlinear system with drift;
preliminary accessibility analysis suggests its utility in predicting
efficacious gaits for piscimimetic robots.
We account for the generation of thrust due to
vortex shedding through controlled coupling terms. At the
heart of this coupling is an abstraction from hydrofoil theory;
we investigate its applicability to real
swimming using an articulated robotic caudal fin. We compare the
observed behavior of our experimental apparatus to that predicted
numerically by steady hydrodynamic theory. +
S
We propose a procedure for the synthesis of con- trol protocols for systems governed by nonlinear differential equations and constrained by temporal logic specifications. This procedure relies on a particular finite-state abstraction of the un- derlying continuous dynamics and a discrete representation of the external environmental signals. A two-player game formulation provides computationally efficient means to construct a discrete strategy based on the finite-state model. We focus on systems with differentially flat outputs, which, in a straightforward manner, allows the construction of continuous control signals from the discrete transitions dictated by the discrete strategy. The resulting continuous-time output trajectories are provably guaranteed to robustly satisfy the original specifications. +
B
Barrier-Based Test Synthesis for Safety-Critical Systems Subject to Timed Reach-Avoid Specifications +
We propose an adversarial, time-varying test-synthesis procedure for safety-critical systems without requiring specific knowledge of the underlying controller steering the system. From a broader test and evaluation context, determination of difficult tests of system behavior is important as these tests would elucidate problematic system phenomena before these mistakes can engender problematic outcomes, e.g. loss of human life in autonomous cars, costly failures for airplane systems, etc. Our approach builds on existing, simulation-based work in the test and evaluation literature by offering a controller-agnostic test-synthesis procedure that provides a series of benchmark tests with which to determine controller reliability. To achieve this, our approach codifies the system objective as a timed reach-avoid specification. Then, by coupling control barrier functions with this class of specifications, we construct an instantaneous difficulty metric whose minimizer corresponds to the most difficult test at that system state. We use this instantaneous difficulty metric in a game-theoretic fashion, to produce an adversarial, time-varying test-synthesis procedure that does not require specific knowledge of the system's controller, but can still provably identify realizable and maximally difficult tests of system behavior. Finally, we develop this test-synthesis procedure for both continuous and discrete-time systems and showcase our test-synthesis procedure on simulated and hardware examples. +
S
We propose formal means for synthesizing switching protocols that determine the sequence in which the modes of a switched system are activated to satisfy certain high-level specifications in linear temporal logic (LTL). The synthesized protocols are robust against exogenous disturbances on the continuous dynamics and can react to possibly adversarial events (both external and internal). Finite-state approximations that abstract the behavior of the underlying continuous dynamics are defined using finite transition systems. Such approximations allow us to transform the continuous switching synthesis problem into a discrete synthesis problem in the form of a two-player game between the system and the environment, where the winning conditions represent the high-level temporal logic specifications. Restricting to an expressive subclass of LTL formulas, these temporal logic games are amenable to solutions with polynomial-time complexity. By construction, existence of a discrete switching strategy for the discrete synthesis problem guarantees the existence of a switching protocol that can be implemented at the continuous level to ensure the correctness of the nonlinear switched system and to react to the environment at run time. +
We propose formal means for synthesizing switching protocols that determine the sequence in which the modes of a switched system are activated to satisfy certain high-level specifications in linear temporal logic. The synthesized protocols are robust against exogenous disturbances on the continuous dynamics. Two types of finite tran- sition systems, namely (deterministic) under-approximations and over-approximations (potentially with nondeterministic transitions), that abstract the behavior of the underlying continuous dynamics are defined. In particular, we show that the discrete synthesis problem for an under-approximation can be formulated as a model checking problem, whereas that for an over-approximation can be transformed into a two-player game. Both of these formulations are amenable to efficient, off-the-shelf software tools. By construction, existence of a discrete switching strategy for the discrete synthesis problem guarantees the existence of a continuous switching protocol for the continuous synthesis problem, which can be implemented at the continuous level to ensure the correctness of the nonlinear switched system. Moreover, the proposed framework can be straightforwardly extended to accommodate specifications that require reacting to possibly adversarial external events. +
F
We provide a new perspective on using formal methods to model specifications and synthesize implementations for the design of biological circuits. In synthetic biology, design objectives are rarely described formally. We present an assume-guarantee contract framework to describe biological circuit design objectives as formal specifications. In our approach, these formal specifications are implemented by circuits modeled by ordinary differential equations, yielding a design framework that can be used to design complex synthetic biological circuits at scale. We describe our approach using the design of a biological AND gate as a motivating, running example. +
