Offline and Online Learning of Signal Temporal Logic Formulae Using Decision Trees

In this article, we focus on inferring high-level descriptions of a system from its execution traces. Specifically, we consider a classification problem where system behaviors are described using formulae of Signal Temporal Logic (STL). Given a finite set of pairs of system traces and labels, where each label indicates whether the corresponding trace exhibits some system property, we devised a decision-tree-based framework that outputs an STL formula that can distinguish the traces. We also extend this approach to the online learning scenario. In this setting, it is assumed that new signals may arrive over time and the previously inferred formula should be updated to accommodate the new data. The proposed approach presents some advantages over traditional machine learning classifiers. In particular, the produced formulae are interpretable and can be used in other phases of the system’s operation, such as monitoring and control. We present two case studies to illustrate the effectiveness of the proposed algorithms: (1) a fault detection problem in an automotive system and (2) an anomaly detection problem in a maritime environment.

How Retroactivity Affects the Behavior of Incoherent Feedforward Loops

An incoherent feedforward loop (IFFL) is a network motif known for its ability to accelerate responses and generate pulses. It remains an open question to understand the behavior of IFFLs in contexts with high levels of retroactivity, where an upstream transcription factor binds to numerous downstream binding sites. Here we study the behavior of IFFLs by simulating and comparing ODE models with different levels of retroactivity. We find that increasing retroactivity in an IFFL can increase, decrease, or keep the network's response time and pulse amplitude constant. This suggests that increasing retroactivity, traditionally considered an impediment to designing robust synthetic systems, could be exploited to improve the performance of IFFLs. In contrast, we find that increasing retroactivity in a negative autoregulated circuit can only slow the response. The ability of an IFFL to flexibly handle retroactivity may have contributed to its significant abundance in both bacterial and eukaryotic regulatory networks.

Distributed and consistent multi-image feature matching via QuickMatch

In this work, we consider the multi-image object matching problem in distributed networks of robots. Multi-image feature matching is a keystone of many applications, including Simultaneous Localization and Mapping, homography, object detection, and Structure from Motion. We first review the QuickMatch algorithm for multi-image feature matching. We then present NetMatch, an algorithm for distributing sets of features across computational units (agents) that largely preserves feature match quality and minimizes communication between agents (avoiding, in particular, the need to flood all data to all agents). Finally, we present an experimental application of both QuickMatch and NetMatch on an object matching test with low-quality images. The QuickMatch and NetMatch algorithms are compared with other standard matching algorithms in terms of preservation of match consistency. Our experiments show that QuickMatch and Netmatch can scale to larger numbers of images and features, and match more accurately than standard techniques.

Reactive sampling-based path planning with temporal logic specifications

We develop a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The mission specification has two parts: (1) a global specification given as a linear temporal logic (LTL) formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula; and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The off-line algorithm has four main features. First, it is incremental, in the sense that the procedure for finding a satisfying path at each iteration scales only with the number of new samples generated at that iteration. Second, the underlying graph is sparse, which implies low complexity for the overall method. Third, it is probabilistically complete. Fourth, under some mild assumptions, it has the best possible complexity bound. The on-line algorithm leverages ideas from LTL monitoring and potential functions to ensure progress towards the satisfaction of the global specification while servicing locally sensed requests. Examples and experimental trials illustrating the usefulness and the performance of the framework are included.

A formal methods approach to interpretable reinforcement learning for robotic planning

Growing interest in reinforcement learning approaches to robotic planning and control raises concerns of predictability and safety of robot behaviors realized solely through learned control policies. In addition, formally defining reward functions for complex tasks is challenging, and faulty rewards are prone to exploitation by the learning agent. Here, we propose a formal methods approach to reinforcement learning that (i) provides a formal specification language that integrates high-level, rich, task specifications with a priori, domain-specific knowledge; (ii) makes the reward generation process easily interpretable; (iii) guides the policy generation process according to the specification; and (iv) guarantees the satisfaction of the (critical) safety component of the specification. The main ingredients of our computational framework are a predicate temporal logic specifically tailored for robotic tasks and an automaton-guided, safe reinforcement learning algorithm based on control barrier functions. Although the proposed framework is quite general, we motivate it and illustrate it experimentally for a robotic cooking task, in which two manipulators worked together to make hot dogs.

Automated Design of Pluripotent Stem Cell Self-Organization

Human pluripotent stem cells (hPSCs) have the intrinsic ability to self-organize into complex multicellular organoids that recapitulate many aspects of tissue development. However, robustly directing morphogenesis of hPSC-derived organoids requires novel approaches to accurately control self-directed pattern formation. Here, we combined genetic engineering with computational modeling, machine learning, and mathematical pattern optimization to create a data-driven approach to control hPSC self-organization by knock down of genes previously shown to affect stem cell colony organization, CDH1 and ROCK1. Computational replication of the in vitro system in silico using an extended cellular Potts model enabled machine learning-driven optimization of parameters that yielded emergence of desired patterns. Furthermore, in vitro the predicted experimental parameters quantitatively recapitulated the in silico patterns. These results demonstrate that morphogenic dynamics can be accurately predicted through model-driven exploration of hPSC behaviors via machine learning, thereby enabling spatial control of multicellular patterning to engineer human organoids and tissues. A record of this paper's Transparent Peer Review process is included in the Supplemental Information.

Control in belief space with temporal logic specifications using vision-based localization

We present a solution for operating a vehicle without global positioning infrastructure while satisfying constraints on its temporal behavior, and on the uncertainty of its position estimate. The proposed solution is an end-to-end framework for mapping an unknown environment using aerial vehicles, synthesizing a control policy for a ground vehicle in that environment, and using a quadrotor to localize the ground vehicle within the map while it executes its control policy. This vision-based localization is noisy, necessitating planning in the belief space of the ground robot. The ground robot’s mission is given using a language called Gaussian Distribution Temporal Logic (GDTL), an extension of Boolean logic that incorporates temporal evolution and noise mitigation directly into the task specifications. We use a sampling-based algorithm to generate a transition system in the belief space and use local feedback controllers to break the curse of history associated with belief space planning. To localize the vehicle, we build a high-resolution map of the environment by flying a team of aerial vehicles in formation with sensor information provided by their onboard cameras. The control policy for the ground robot is synthesized under temporal and uncertainty constraints given the semantically labeled map. Then the ground robot can execute the control policy given pose estimates from a dedicated aerial robot that tracks and localizes the ground robot. The proposed method is validated using two quadrotors to build a map, followed by a two-wheeled ground robot and a quadrotor with a camera for ten successful experimental trials.

Modeling Genetic Circuit Behavior in Transiently Transfected Mammalian Cells

Binning cells by plasmid copy number is a common practice for analyzing transient transfection data. In many kinetic models of transfected cells, protein production rates are assumed to be proportional to plasmid copy number. The validity of this assumption in transiently transfected mammalian cells is not clear; models based on this assumption appear unable to reproduce experimental flow cytometry data robustly. We hypothesize that protein saturation at high plasmid copy number is a reason previous models break down and validate our hypothesis by comparing experimental data and a stochastic chemical kinetics model. The model demonstrates that there are multiple distinct physical mechanisms that can cause saturation. On the basis of these observations, we develop a novel minimal bin-dependent ODE model that assumes different parameters for protein production in cells with low versus high numbers of plasmids. Compared to a traditional Hill-function-based model, the bin-dependent model requires only one additional parameter, but fits flow cytometry input-output data for individual modules up to twice as accurately. By composing together models of individually fit modules, we use the bin-dependent model to predict the behavior of six cascades and three feed-forward circuits. The bin-dependent models are shown to provide more accurate predictions on average than corresponding (composed) Hill-function-based models and predictions of comparable accuracy to EQuIP, while still providing a minimal ODE-based model that should be easy to integrate as a subcomponent within larger differential equation circuit models. Our analysis also demonstrates that accounting for batch effects is important in developing accurate composed models.

Computational Techniques for Analysis of Genetic Network Dynamics

In this paper we propose modeling and analysis techniques for genetic networks that provide biologists with insight into the dynamics of such systems. Central to our modeling approach is the framework of hybrid systems and our analysis tools are derived from formal analysis of such systems. Given a set of states characterizing a property of biological interest P , we present the Multi-Affine Rectangular Partition (MARP) algorithm for the construction of a set of infeasible states I that will never reach P and the Rapidly Exploring Random Forest of Trees (RRFT) algorithm for the construction of a set of feasible states F that will reach P. These techniques are scalable to high dimensions and can incorporate uncertainty (partial knowledge of kinetic parameters and state uncertainty).We apply these methods to understand the genetic interactions involved in the phenomenon of luminescence production in the marine bacterium V. fischeri.

Receding horizon temporal logic control in dynamic environments

We present a receding horizon method for controlling an autonomous vehicle that must satisfy a rich mission specification over service requests occurring at the regions of a partitioned environment. The overall mission specification consists of a temporal logic statement over a set of static, a priori known requests, a regular expression over a set of dynamic requests that can be sensed only locally, and a servicing priority order over these dynamic requests. Our approach is based on two main steps. First, we construct an abstraction for the motion of the vehicle in the environment by using input–output linearization and assignment of vector fields to the regions in the partition. Second, a receding horizon controller computes local plans within the sensing range of the vehicle such that both local and global mission specifications are satisfied. We implement and evaluate our method through experiments and simulations consisting of a quadrotor performing a persistent surveillance task over a planar grid environment.

Incremental controller synthesis in probabilistic environments with temporal logic constraints

In this paper, we consider automatic computation of optimal control strategies for a robot interacting with a set of independent uncontrollable agents in a graph-like environment. The mission specification is given as a syntactically co-safe Linear Temporal Logic formula over some properties that hold at the vertices of the environment. The robot is assumed to be a deterministic transition system, while the agents are probabilistic Markov models. The goal is to control the robot such that the probability of satisfying the mission specification is maximized. We propose a computationally efficient incremental algorithm based on the fact that temporal logic verification is computationally cheaper than synthesis. We present several case studies where we compare our approach to the classical non-incremental approach in terms of computation time and memory usage.

Control of noisy differential-drive vehicles from time-bounded temporal logic specifications

We address the problem of controlling a noisy differential drive mobile robot such that the probability of satisfying a specification given as a bounded linear temporal logic formula over a set of properties at the regions in the environment is maximized. We assume that the vehicle can determine its precise initial position in a known map of the environment. However, motivated by practical limitations, we assume that the vehicle is equipped with noisy actuators and, during its motion in the environment, it can only measure the angular velocity of its wheels using limited accuracy incremental encoders. Assuming the duration of the motion is finite, we map the measurements to a Markov decision process (MDP). We use recent results in statistical model checking to obtain an MDP control policy that maximizes the probability of satisfaction. We translate this policy to a vehicle feedback control strategy and show that the probability that the vehicle satisfies the specification in the environment is bounded from below by the probability of satisfying the specification on the MDP. We illustrate our method with simulations and experimental results.

Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints

In this paper we present a method for automatic planning of optimal paths for a group of robots that satisfy a common high-level mission specification. The motion of each robot is modeled as a weighted transition system, and the mission is given as a linear temporal logic (LTL) formula over a set of propositions satisfied at the regions of the environment. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize a cost function that captures the maximum time between successive satisfactions of the optimizing proposition while guaranteeing that the formula is satisfied. When the robots can follow a given trajectory exactly, our method computes a set of optimal satisfying paths that minimize the cost function and satisfy the LTL formula. However, if the traveling times of the robots are uncertain, then the robots may not be able to follow a given trajectory exactly, possibly violating the LTL formula during deployment. We handle such cases by leveraging the communication capabilities of the robots to guarantee correctness during deployment and provide bounds on the deviation from the optimal values. We implement and experimentally evaluate our method for various persistent surveillance tasks in a road network environment.

Temporal logic robot control based on automata learning of environmental dynamics

We develop a technique to automatically generate a control policy for a robot moving in an environment that includes elements with unknown, randomly changing behavior. The robot is required to achieve a surveillance mission, in which a certain request needs to be serviced repeatedly, while the expected time inbetween consecutive services is minimized and additional temporal logic constraints are satisfied. We define a fragment of linear temporal logic to describe such a mission and formulate the problem as a temporal logic game. Our approach is based on two main ideas. First, we extend results in automata learning to detect patterns of the unknown behavior of the elements in the environment. Second, we employ an automata–theoretic method to generate the control policy. We show that the obtained control policy converges to an optimal one when the partially unknown behavior patterns are fully learned. In addition, we illustrate the method in an experimental setup, in which an unmanned ground vehicle, with the help of a cooperating unmanned aerial vehicle (UAV), satisfies a temporal logic requirement in a partitioned environment whose regions are controlled by barriers with unknown behavior.

Controlling the outcome of the Toll-like receptor signaling pathways

The Toll-Like Receptors (TLRs) are proteins involved in the immune system that increase cytokine levels when triggered. While cytokines coordinate the response to infection, they appear to be detrimental to the host when reaching too high levels. Several studies have shown that the deletion of specific TLRs was beneficial for the host, as cytokine levels were decreased consequently. It is not clear, however, how targeting other components of the TLR pathways can improve the responses to infections. We applied the concept of Minimal Cut Sets (MCS) to the ihsTLR v1.0 model of the TLR pathways to determine sets of reactions whose knockouts disrupt these pathways. We decomposed the TLR network into 34 modules and determined signatures for each MCS, i.e. the list of targeted modules. We uncovered 2,669 MCS organized in 68 signatures. Very few MCS targeted directly the TLRs, indicating that they may not be efficient targets for controlling these pathways. We mapped the species of the TLR network to genes in human and mouse, and determined more than 10,000 Essential Gene Sets (EGS). Each EGS provides genes whose deletion suppresses the network's outputs.

Optimal path planning for surveillance with temporal-logic constraints

In this paper we present a method for automatically generating optimal robot paths satisfying high-level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by an arbitrary linear temporal-logic (LTL) formula over propositions satisfied at the regions of a partitioned environment. The mission specification contains an optimizing proposition, which must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot path that minimizes the cost function. The problem is motivated by applications in robotic monitoring and data-gathering. In this setting, the optimizing proposition is satisfied at all locations where data can be uploaded, and the LTL formula specifies a complex data-collection mission. Our method utilizes Büchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal-logic specification. We then present a graph algorithm that computes a run corresponding to the optimal robot path. We present an implementation for a robot performing data collection in a road-network platform.

An application of monotone functions decomposition to the reconstruction of gene regulatory networks

We describe the reconstruction of a gene regulatory network involved with the Toll-like Receptor signaling pathways. By applying our recent identification algorithm to a time series gene expression dataset, we identify regulatory interactions between genes and construct discrete-time piece-wise affine regulatory functions. Our validation shows that our model predicts the expression levels of the genes involved in the network with good accuracy.

Deep epistasis in human metabolism

We extend and apply a method that we have developed for deriving high-order epistatic relationships in large biochemical networks to a published genome-scale model of human metabolism. In our analysis we compute 33,328 reaction sets whose knockout synergistically disables one or more of 43 important metabolic functions. We also design minimal knockouts that remove flux through fumarase, an enzyme that has previously been shown to play an important role in human cancer. Most of these knockout sets employ more than eight mutually buffering reactions, spanning multiple cellular compartments and metabolic subsystems. These reaction sets suggest that human metabolic pathways possess a striking degree of parallelism, inducing "deep" epistasis between diversely annotated genes. Our results prompt specific chemical and genetic perturbation follow-up experiments that could be used to query in vivo pathway redundancy. They also suggest directions for future statistical studies of epistasis in genetic variation data sets.

Exploiting the pathway structure of metabolism to reveal high-order epistasis

BACKGROUND

Biological robustness results from redundant pathways that achieve an essential objective, e.g. the production of biomass. As a consequence, the biological roles of many genes can only be revealed through multiple knockouts that identify a set of genes as essential for a given function. The identification of such "epistatic" essential relationships between network components is critical for the understanding and eventual manipulation of robust systems-level phenotypes.

RESULTS

We introduce and apply a network-based approach for genome-scale metabolic knockout design. We apply this method to uncover over 11,000 minimal knockouts for biomass production in an in silico genome-scale model of E. coli. A large majority of these "essential sets" contain 5 or more reactions, and thus represent complex epistatic relationships between components of the E. coli metabolic network.

CONCLUSION

The complex minimal biomass knockouts discovered with our approach illuminate robust essential systems-level roles for reactions in the E. coli metabolic network. Unlike previous approaches, our method yields results regarding high-order epistatic relationships and is applicable at the genome-scale.

Robustness analysis and tuning of synthetic gene networks

MOTIVATION

The goal of synthetic biology is to design and construct biological systems that present a desired behavior. The construction of synthetic gene networks implementing simple functions has demonstrated the feasibility of this approach. However, the design of these networks is difficult, notably because existing techniques and tools are not adapted to deal with uncertainties on molecular concentrations and parameter values.

RESULTS

We propose an approach for the analysis of a class of uncertain piecewise-multiaffine differential equation models. This modeling framework is well adapted to the experimental data currently available. Moreover, these models present interesting mathematical properties that allow the development of efficient algorithms for solving robustness analyses and tuning problems. These algorithms are implemented in the tool RoVerGeNe, and their practical applicability and biological relevance are demonstrated on the analysis of the tuning of a synthetic transcriptional cascade built in Escherichia coli.

AVAILABILITY

RoVerGeNe and the transcriptional cascade model are available at http://iasi.bu.edu/%7Ebatt/rovergene/rovergene.htm.

Analysis of lactose metabolism in E.coli using reachability analysis of hybrid systems

We propose an abstraction method for medium-scale biomolecular networks, based on hybrid dynamical systems with continuous multi-affine dynamics. This abstraction method follows naturally from the notion of approximating nonlinear rate laws with continuous piecewise linear functions and can be easily automated. An efficient reachability algorithm is possible for the resulting class of hybrid systems. An efficient reachability algorithm is possible for the resulting class of hybrid systems. An approximation for an ordinary differential equation model of the lac operon is constructed, and it is shown that the abstraction passes the same experimental tests as were used to validate the original model. The well studied biological system exhibits bistability and switching behaviour, arising from positive feedback in the expression mechanism of the lac operon. The switching property of the lac system is an example of the major qualitative features that are the building blocks of higher level, more coarse-grained descriptions. The present approach is useful in helping to correctly identify such properties and in connecting them to the underlying molecular dynamical details. Reachability analysis together with the knowledge of the steady-state structure are used to identify ranges of parameter values for which the system maintains the bistable switching property.

Systematic analysis of conservation relations in Escherichia coli genome-scale metabolic network reveals novel growth media

A biochemical species is called producible in a constraints-based metabolic model if a feasible steady-state flux configuration exists that sustains its nonzero concentration during growth. Extreme semipositive conservation relations (ESCRs) are the simplest semipositive linear combinations of species concentrations that are invariant to all metabolic flux configurations. In this article, we outline a fundamental relationship between the ESCRs of a metabolic network and the producibility of a biochemical species under a nutrient media. We exploit this relationship in an algorithm that systematically enumerates all minimal nutrient sets that render an objective species weakly producible (i.e., producible in the absence of thermodynamic constraints) through a simple traversal of ESCRs. We apply our results to a recent genome scale model of Escherichia coli metabolism, in which we traverse the 51 anhydrous ESCRs of the metabolic network to determine all 928 minimal aqueous nutrient media that render biomass weakly producible. Applying irreversibility constraints, we find 287 of these 928 nutrient sets to be thermodynamically feasible. We also find that an additional 365 of these nutrient sets are thermodynamically feasible in the presence of oxygen. Since biomass producibility is commonly used as a surrogate for growth in genome scale metabolic models, our results represent testable hypotheses of alternate growth media derived from in silico analysis of the E. coli genome scale metabolic network.