Epigenetic cell memory allows distinct gene expression patterns to persist in different cell types despite a common genotype. Although different patterns can be maintained by the concerted action of transcription factors (TFs), it was proposed that long-term persistence hinges on chromatin state. Here, we study how the dynamics of chromatin state affect memory, and focus on a biologically motivated circuit motif, among histones and DNA modifications, that mediates the action of TFs on gene expression. Memory arises from time-scale separation among three circuit's constituent processes: basal erasure, auto and cross-catalysis, and recruited erasure of modifications. When the two latter processes are sufficiently faster than the former, the circuit exhibits bistability and hysteresis, allowing active and repressed gene states to coexist and persist after TF stimulus removal. The duration of memory is stochastic with a mean value that increases as time-scale separation increases, but more so for the repressed state. This asymmetry stems from the cross-catalysis between repressive histone modifications and DNA methylation and is enhanced by the relatively slower decay rate of the latter. Nevertheless, TF-mediated positive autoregulation can rebalance this asymmetry and even confers robustness of active states to repressive stimuli. More generally, by wiring positively autoregulated chromatin modification circuits under time scale separation, long-term distinct gene expression patterns arise, which are also robust to failure in the regulatory links.

Intracellular spatial heterogeneity is frequently observed in bacteria, where the chromosome occupies part of the cell's volume and a circuit's DNA often localizes within the cell. How this heterogeneity affects core processes and genetic circuits is still poorly understood. In fact, commonly used ordinary differential equation (ODE) models of genetic circuits assume a well-mixed ensemble of molecules and, as such, do not capture spatial aspects. Reaction-diffusion partial differential equation (PDE) models have been only occasionally used since they are difficult to integrate and do not provide mechanistic understanding of the effects of spatial heterogeneity. In this paper, we derive a reduced ODE model that captures spatial effects, yet has the same dimension as commonly used well-mixed models. In particular, the only difference with respect to a well-mixed ODE model is that the association rate constant of binding reactions is multiplied by a coefficient, which we refer to as the binding correction factor (BCF). The BCF depends on the size of interacting molecules and on their location when fixed in space and it is equal to unity in a well-mixed ODE model. The BCF can be used to investigate how spatial heterogeneity affects the behavior of core processes and genetic circuits. Specifically, our reduced model indicates that transcription and its regulation are more effective for genes located at the cell poles than for genes located on the chromosome. The extent of these effects depends on the value of the BCF, which we found to be close to unity. For translation, the value of the BCF is always greater than unity, it increases with mRNA size, and, with biologically relevant parameters, is substantially larger than unity. Our model has broad validity, has the same dimension as a well-mixed model, yet it incorporates spatial heterogeneity. This simple-to-use model can be used to both analyze and design genetic circuits while accounting for spatial intracellular effects.

The ability of cells to sense and respond to their environment is encoded in biomolecular reaction networks, in which information travels through processes such as production, modification, and removal of biomolecules. Recent advances in biotechnology have made it possible to reengineer these physical processes to the point where synthetic biomolecular circuits can be inserted into cells to program cell behavior for useful functionalities. These circuits are often designed in a bottom-up fashion with smaller components connected to form complex systems. In a bottom-up approach to design, it is highly desirable that circuit components behave modularly, that is, the input-output behavior of a module characterized in isolation remains unchanged when the context changes. Unfortunately, due to the physical processes by which information is communicated from one biomolecular circuit module to the other, the lack of modularity is often a problem. In fact, the input-output behavior of a module depends on both direct connectivity to other modules, due to loading effects, and indirect connectivity arising from loads applied to shared cellular resources. In this paper, we summarize the published work illustrating how the means of molecular communication lead to these problems. Specifically, we review the concept of retroactivity, which has been proposed to capture loading problems within a “signals and systems” framework, allowing for engineering solutions that restore modularity.

Phenotypical variability in the absence of genetic variation often reflects complex energetic landscapes associated with underlying gene regulatory networks (GRNs). In this view, different phenotypes are associated with alternative states of complex nonlinear systems: stable attractors in deterministic models or modes of stationary distributions in stochastic descriptions. We provide theoretical and practical characterizations of these landscapes, specifically focusing on stochastic Slow Promoter Kinetics (SPK), a time scale relevant when transcription factor binding and unbinding are affected by epigenetic processes like DNA methylation and chromatin remodeling. In this case, largely unexplored except for numerical simulations, adiabatic approximations of promoter kinetics are not appropriate. In contrast to the existing literature, we provide rigorous analytic characterizations of multiple modes. A general formal approach gives insight into the influence of parameters and the prediction of how changes in GRN wiring, for example through mutations or artificial interventions, impact the possible number, location, and likelihood of alternative states. We adapt tools from the mathematical field of singular perturbation theory to represent stationary distributions of Chemical Master Equations for GRNs as mixtures of Poisson distributions and obtain explicit formulas for the locations and probabilities of metastable states as a function of the parameters describing the system. As illustrations, the theory is used to tease out the role of cooperative binding in stochastic models in comparison to deterministic models, and applications are given to various model systems, such as toggle switches in isolation or in communicating populations, a synthetic oscillator, and a trans-differentiation network.

Duckietown is an open, inexpensive and flexible platform for autonomy education and research. The platform comprises small autonomous vehicles (“Duckiebots”) built from off-the-shelf components, and cities (“Duckietowns”) complete with roads, signage, traffic lights, obstacles, and citizens (duckies) in need of transportation. The Duckietown platform offers a wide range of functionalities at a low cost. Duckiebots sense the world with only one monocular camera and perform all processing onboard with a Raspberry Pi 2, yet are able to: follow lanes while avoiding obstacles, pedestrians (duckies) and other Duckiebots, localize within a global map, navigate a city, and coordinate with other Duckiebots to avoid collisions. Duckietown is a useful tool since educators and researchers can save money and time by not having to develop all of the necessary supporting infrastructure and capabilities. All materials are available as open source, and the hope is that others in the community will adopt the platform for education and research.

In this paper, we design a supervisor to prevent vehicle collisions at intersections. An intersection is modeled as an area containing multiple conflict points where vehicle paths cross in the future. At every time step, the supervisor determines whether there will be more than one vehicle in the vicinity of a conflict point at the same time. If there is, then an impending collision is detected, and the supervisor overrides the drivers to avoid collision. A major challenge in the design of a supervisor as opposed to an autonomous vehicle controller is to verify whether future collisions will occur based on the current drivers choices. This verification problem is particularly hard due to the large number of vehicles often involved in intersection collision, to the multitude of conflict points, and to the vehicles dynamics. In order to solve the verification problem, we translate the problem to a job-shop scheduling problem that yields equivalent answers. The job-shop scheduling problem can, in turn, be transformed into a mixed-integer linear program when the vehicle dynamics are first-order dynamics, and can thus be solved by using a commercial solver.

In this paper, we consider the problem of designing in-vehicle driver-assist systems that warn or override the driver to prevent collisions with a guaranteed probability. The probabilistic nature of the problem naturally arises from many sources of uncertainty, among which the behavior of the surrounding vehicles and the response of the driver to on-board warnings. We formulate this problem as a control problem for uncertain systems under probabilistic safety specifications and leverage the structure of the application domain to reach computationally efficient implementations. Simulations using a naturalistic data set show that the empirical probability of safety is always within 5% of the theoretical value in the case of direct driver override. In the case of on-board warnings, the empirical value is more conservative due primarily to drivers decelerating more strongly than requested. However, the empirical value is greater than or equal to the theoretical value, demonstrating a clear safety benefit.

This paper describes the implementation of a multi-vehicle supervisor to prevent collisions at intersections. The experiments are performed on an intersection testbed consisting of three RC cars. Here, we account for uncertainty in car dynamics and state measurement, and the presence of an uncontrolled car, which is human-driven. The supervisor overrides the controlled cars only when necessary to avoid a possible future collision. From the experiments, we demonstrate that intersection collisions are averted, that is, the cars continuously and safely run on the paths without stopping 92.8% of the times.

Predicting the dynamic behavior of a large network from that of the composing modules is a central problem in systems and synthetic biology. Yet, this predictive ability is still largely missing because modules display context-dependent behavior. One cause of context-dependence is retroactivity, a phenomenon similar to loading that influences in non-trivial ways the dynamic performance of a module upon connection to other modules. Here, we establish an analysis framework for gene transcription networks that explicitly accounts for retroactivity. Specifically, a module's key properties are encoded by three retroactivity matrices: internal, scaling, and mixing retroactivity. All of them have a physical interpretation and can be computed from macroscopic parameters (dissociation constants and promoter concentrations) and from the modules' topology. The internal retroactivity quantifies the effect of intramodular connections on an isolated module's dynamics. The scaling and mixing retroactivity establish how intermodular connections change the dynamics of connected modules. Based on these matrices and on the dynamics of modules in isolation, we can accurately predict how loading will affect the behavior of an arbitrary interconnection of modules. We illustrate implications of internal, scaling, and mixing retroactivity on the performance of recurrent network motifs, including negative autoregulation, combinatorial regulation, two-gene clocks, the toggle switch, and the single-input motif. We further provide a quantitative metric that determines how robust the dynamic behavior of a module is to interconnection with other modules. This metric can be employed both to evaluate the extent of modularity of natural networks and to establish concrete design guidelines to minimize retroactivity between modules in synthetic systems.

In this paper, we leverage vehicle-to-vehicle (V2V) communication technology to implement computationally efficient decentralized algorithms for two-vehicle cooperative collision avoidance at intersections. Our algorithms employ formal control theoretic methods to guarantee a collision-free (safe) system, whereas overrides are only applied when necessary to prevent a crash. Model uncertainty and communication delays are explicitly accounted for by the model and by the state estimation algorithm. The main contribution of this work is to provide an experimental validation of our method on two instrumented vehicles engaged in an intersection collision avoidance scenario in a test track.

We consider the problem of synthesising the least restrictive controller for collision avoidance of multiple vehicles at an intersection. The largest set of states for which there exists a control that avoids collisions is known as the maximal controlled invariant set. Exploiting results from the scheduling literature we prove that, for a general model of vehicle dynamics at an intersection, the problem of checking membership in the maximal controlled invariant set is NP-hard. We then describe an algorithm that solves this problem approximately and with provable error bounds. The approximate solution is used to design a supervisor for collision avoidance whose complexity scales polynomially with the number of vehicles. The supervisor is based on a hybrid algorithm that employs a dynamic model of the vehicles and periodically solves a scheduling problem.

In this paper, we show how to design a provably safe robotic roundabout system comprised of three vehicles. This is accomplished by combining two-vehicle collision avoidance primitives, which are each computationally light given the natural partial order structure on which the system evolves. We show how to design the system parameters in order to prevent conflicts among the control primitives, and to thus ensure the safety and liveness of the system as a whole. We implement our design on a multi-vehicle test-bed involving three vehicles continuously running on three intersecting roundabouts, and provide experimental results demonstrating the system is collision free and live.

As in several engineering applications, biomolecular systems present impedance-like effects at interconnections called retroactivity. This phenomenon presents a challenge for modular design in synthetic biology. An insulation device is a biological module that enables attenuation of retroactivity at interconnections. In this paper, we propose the design of an insulation device by exploiting the naturally existing time-scale separation of phosphotranspher systems.

In this paper, we employ partial order techniques to develop linear complexity algorithms for guaranteed collision avoidance between vehicles at highway and roundabout mergings. These techniques can be employed by virtue of the rich structure offered by such traffic systems, which constrain vehicles to advance unidirectionally along a path. The algorithms are safe by construction while maintaining the liveness of the system. The proposed algorithms are on-line implemented in a decentralized fashion on an experimental testbed composed of two in-scale communicating vehicles continuously running on an autonomous roundabout system.

The rules that govern decision making in systems controlled by humans are often simple to describe. However, deriving these rules from the actions of a group can be very difficult, making human behavior hard to predict. We develop an algorithm to determine the rules implemented by drivers at a traffic intersection by observing the trajectories of their cars. We apply such algorithm to a traffic intersection scenario reproduced in the Caltech multi-vehicle lab, with human subjects remotely driving kinematic robots. The results obtained on these data suggest that this kind of human behavior is to some extent predictable on our data set, and different subjects implement similar rules.