Applications such as reconstructing cell lineage trees (represented as phylogenetic trees) from single-cell sequencing data require reconstructing a [Formula: see text]-matrix that has many errors and missing entries. We introduce Sempervirens, a very fast matrix reconstruction algorithm for noisy and incomplete matrix representations of phylogenetic trees. Sempervirens uses an iterative maximum-likelihood approach to determine the topology tree represented by the corrupted data. We show that Sempervirens is at least three orders of magnitude faster than other methods on thousand by thousand matrices, with the speed gap widening with larger matrices. We also show that Sempervirens matches state-of-the-art methods in reconstruction accuracy. The speed of Sempervirens enables it to be tractably applied to reconstructing much larger matrices than those that other methods can reconstruct. In addition to experimental results, we justify the algorithm with a mathematical treatment of its subprocedures. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This work was supported by the Office of Science of the Department of Energy [Contract DE-AC02-05CH11231]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0373 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0373 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Tight coupling between computation, communication, and control pervades the design and application of cyber-physical systems (CPSs). Due to the complexity of these systems, advanced design procedures that account for these tight interconnections are paramount to ensure the safe and reliable operation of control algorithms under computational constraints. This paper presents the Simulator for Hardware Architecture and Real-time Control (Sharc) to assist in the co-design of control algorithms and the computational hardware on which they are run. Sharc simulates the execution of a user-specified control algorithm on a given processor microarchitecture configuration, evaluating how computational constraints affect the dynamical properties of the closed-loop system. We illustrate the power of Sharc by examples of MPC applied to adaptive cruise control and the stabilization of an inverted pendulum. Sharc can be found at github.com/pwintz/sharc.

Neural network controllers have become popular in control tasks thanks to their flexibility and expressivity. Stability is a crucial property for safety-critical dynamical systems, while stabilization of partially observed systems, in many cases, requires controllers to retain and process long-term memories of the past. We consider the important class of recurrent neural networks (RNN) as dynamic controllers for nonlinear uncertain partially-observed systems, and derive convex stability conditions based on integral quadratic constraints, S-lemma and sequential convexification. To ensure stability during the learning and control process, we propose a projected policy gradient method that iteratively enforces the stability conditions in the reparametrized space taking advantage of mild additional information on system dynamics. Numerical experiments show that our method learns stabilizing controllers with fewer samples and achieves higher final performance compared with policy gradient.

Reachability analysis is a critical tool for the formal verification of dynamical systems and the synthesis of controllers for them. Due to their computational complexity, many reachability analysis methods are restricted to systems with relatively small dimensions. One significant reason for such limitation is that those approaches, and their implementations, are not designed to leverage parallelism. They use algorithms that are designed to run serially within one compute unit and they can not utilize widely-available high-performance computing (HPC) platforms such as many-core CPUs, GPUs and Cloud-computing services. This paper presents PIRK , a tool to efficiently compute reachable sets for general nonlinear systems of extremely high dimensions. PIRK can utilize HPC platforms for computing reachable sets for general high-dimensional non-linear systems. PIRK has been tested on several systems, with state dimensions up to 4 billion. The scalability of PIRK ’s parallel implementations is found to be highly favorable.

Successfully synthesizing controllers for complex dynamical systems and specifications often requires leveraging domain knowledge as well as making difficult computational or mathematical tradeoffs. This paper presents a flexible and extensible framework for constructing robust control synthesis algorithms and applies this to the traditional abstraction-based control synthesis pipeline. It is grounded in the theory of relational interfaces and provides a principled methodology to seamlessly combine different techniques (such as dynamic precision grids, refining abstractions while synthesizing, or decomposed control predecessors) or create custom procedures to exploit an application’s intrinsic structural properties. A Dubins vehicle is used as a motivating example to showcase memory and runtime improvements.

This paper presents TIRA, a Matlab library gathering several methods for the computation of interval over-approximations of the reachable sets for both continuous- and discrete-time nonlinear systems. Unlike other existing tools, the main strength of interval-based reachability analysis is its simplicity and scalability, rather than the accuracy of the over-approximations. The current implementation of TIRA contains four reachability methods covering wide classes of nonlinear systems, handled with recent results relying on contraction/growth bounds and monotonicity concepts. TIRA's architecture features a central function working as a hub between the user-defined reachability problem and the library of available reachability methods. This design choice offers increased extensibility of the library, where users can define their own method in a separate function and add the function call in the hub function.

The correctness of control software in many safety-critical applications such as autonomous vehicles is very crucial. One approach to achieve this goal is through “symbolic control”, where complex physical systems are approximated by finite-state abstractions. Then, using those abstractions, provably-correct digital controllers are algorithmically synthesized for concrete systems, satisfying some complex high-level requirements. Unfortunately, the complexity of constructing such abstractions and synthesizing their controllers grows exponentially in the number of state variables in the system. This limits its applicability to simple physical systems. This paper presents a unified approach that utilizes sparsity of the interconnection structure in dynamical systems for both construction of finite abstractions and synthesis of symbolic controllers. In addition, parallel algorithms are proposed to target high-performance computing (HPC) platforms and Cloud-computing services. The results show remarkable reductions in computation times. In particular, we demonstrate the effectiveness of the proposed approach on a 7-dimensional model of a BMW 320i car by designing a controller to keep the car in the travel lane unless it is blocked.

No abstract available.

This paper tackles the problem of constructing finite abstractions for formal controller synthesis with high dimensional systems. We develop a theory of abstraction for discrete time nonlinear systems that are equipped with variables acting as interfaces for other systems. Systems interact via an interconnection map which constrains the value of system interface variables. An abstraction of a high dimensional interconnected system is obtained by composing subsystem abstractions with an abstraction of the interconnection. System abstractions are modular in the sense that they can be rearranged, substituted, or reused in configurations that were unknown during the time of abstraction. Constructing the abstraction of the interconnection map can become computationally infeasible when there are many systems. We introduce intermediate variables which break the interconnection and the abstraction procedure apart into smaller problems. Examples showcase the abstraction of a 24-dimensional system through the composition of 24 individual systems, and the synthesis of a controller for a 6-dimensional system with a consensus objective.

We present a method of generating spatial maps of kinetic parameters from dynamic sequences of images collected in hyperpolarized carbon-13 magnetic resonance imaging (MRI) experiments. The technique exploits spatial correlations in the dynamic traces via regularization in the space of parameter maps. Similar techniques have proven successful in other dynamic imaging problems, such as dynamic contrast enhanced MRI. In this paper, we apply these techniques for the first time to hyperpolarized MRI problems, which are particularly challenging due to limited signal-to-noise ratio (SNR). We formulate the reconstruction as an optimization problem and present an efficient iterative algorithm for solving it based on the alternation direction method of multipliers. We demonstrate that this technique improves the qualitative appearance of parameter maps estimated from low SNR dynamic image sequences, first in simulation then on a number of data sets collected in vivo. The improvement this method provides is particularly pronounced at low SNR levels.

The problem of verifying properties of large, networked cyber-physical systems (CPS) is beyond the reach of most computational tools today. Two common "divide-and-conquer" techniques for CPS verification are assume-guarantee contracts from the formal methods literature and input-output properties from the control theory literature. Combining these two approaches, we first introduce the notion of a parametric assume-guarantee contract, which lets reason about system behavior abstractly in a parameter domain. We next show how a finite gain property can be encoded in this form and provide a generalized small-gain theorem for parametric assume-guarantee contracts. This theorem recovers the classical small gain theorem as a special case and its derivation highlights the connection between assume-guarantee reasoning and small-gain results. This new small-gain theorem applies to behaviors beyond bounded deviation from a nominal point to include a fragment of linear temporal logic with parametrized predicates that can encode safety, recurrence, and liveness properties. Our results are validated with an example which certifies that the interconnection of two freeway segments experiences intermittent congestion.

Given a dynamical system and a specification, assumption mining is the problem of identifying the set of admissible disturbance signals and initial states that generate trajectories satisfying the specification. We first introduce the notion of a directed specification, which describes either upper or lower sets in a partially ordered signal space, and show that this notion encompasses an expressive temporal logic fragment. We next show that the order preserving nature of monotone dynamical systems makes them amenable to a systematic form of assumption mining that checks numerical simulations of system trajectories against directed specifications. The assumption set is then located with a multidimensional bisection method that converges to the boundary from above and below. Typical objectives in vehicular traffic control, such as avoiding or clearing congestion, are directed specifications. In an application to a freeway flow model with monotone dynamics, we identify the set of vehicular demand profiles that satisfy a specification that congestion be intermittent.

Hyperpolarized carbon-13 magnetic resonance imaging has enabled the real-time observation of perfusion and metabolism in vivo. These experiments typically aim to distinguish between healthy and diseased tissues based on the rate at which they metabolize an injected substrate. However, existing approaches to optimizing flip angle sequences for these experiments have focused on indirect metrics of the reliability of metabolic rate estimates, such as signal variation and signal-to-noise ratio. In this paper we present an optimization procedure that focuses on maximizing the Fisher information about the metabolic rate. We demonstrate through numerical simulation experiments that flip angles optimized based on the Fisher information lead to lower variance in metabolic rate estimates than previous flip angle sequences. In particular, we demonstrate a 20% decrease in metabolic rate uncertainty when compared with the best competing sequence. We then demonstrate appropriateness of the mathematical model used in the simulation experiments with in vivo experiments in a prostate cancer mouse model. While there is no ground truth against which to compare the parameter estimates generated in the in vivo experiments, we demonstrate that our model used can reproduce consistent parameter estimates for a number of flip angle sequences.

We present an efficient computational procedure for finite abstraction of discrete-time mixed monotone systems by considering a rectangular partition of the state space. Mixed monotone systems are decomposable into increasing and decreasing components, and significantly generalize the well known class of monotone systems. We tightly overapproximate the one-step reachable set from a box of initial conditions by computing a decomposition function at only two points, regardless of the dimension of the state space. We apply our results to verify the dynamical behavior of a model for insect population dynamics and to synthesize a signaling strategy for a traffic network.

Efforts to engineer synthetic gene networks that spontaneously produce patterning in multicellular ensembles have focused on Turing's original model and the "activator-inhibitor" models of Meinhardt and Gierer. Systems based on this model are notoriously difficult to engineer. We present the first demonstration that Turing pattern formation can arise in a new family of oscillator-driven gene network topologies, specifically when a second feedback loop is introduced which quenches oscillations and incorporates a diffusible molecule. We provide an analysis of the system that predicts the range of kinetic parameters over which patterning should emerge and demonstrate the system's viability using stochastic simulations of a field of cells using realistic parameters. The primary goal of this paper is to provide a circuit architecture which can be implemented with relative ease by practitioners and which could serve as a model system for pattern generation in synthetic multicellular systems. Given the wide range of oscillatory circuits in natural systems, our system supports the tantalizing possibility that Turing pattern formation in natural multicellular systems can arise from oscillator-driven mechanisms.

We study power control in multicell CDMA wireless networks as a team optimization problem where each mobile attains its individual fixed target SIR level by transmitting with minimum possible power level. We derive conditions under which the power control problem admits a unique feasible solution. Using a Lagrangian relaxation approach similar to F. Kelly et al. (1998) we obtain two decentralized dynamic power control algorithms: primal and dual power update, and establish their global stability utilizing both classical Lyapunov theory and the passivity framework [J.T. Wen and M. Arcak, February 2004]. We show that the robustness results of passivity studies [(X. Fan et al., July 2004), (X. Fan et al., 2004)] as well as most of the stability and robustness analyses of F. Kelly et al. (1998) in the literature are applicable to the power control problem considered. In addition, some of the basic principles of call admission control are investigated from the perspective of the model adopted in this paper. We illustrate the proposed power control schemes through simulations.

Network flow control regulates the traffic between sources and links based on congestion, and plays a critical role in ensuring satisfactory performance. In recent studies, global stability has been shown for several flow control schemes. By using a passivity approach, this paper presents a unifying framework which encompasses these stability results as special cases. In addition, the new approach significantly expands the current classes of stable flow controllers by augmenting the source and link update laws with passive dynamic systems. This generality offers the possibility of optimizing the controllers, for example, to improve robustness and performance with respect to time delay, unmodeled flows, and capacity variation.