A key component of transformers is the attention mechanism orchestrating how each token influences the propagation of every other token along the layers of a transformer. In this paper we provide a rigorous, mathematical analysis of the asymptotic properties of attention in transformers. Although we present several results based on different assumptions, all of them point to the same conclusion, all tokens asymptotically converge to each other, a phenomenon that has been empirically reported in the literature. Our findings are carefully compared with existing theoretical results and illustrated by simulations and experimental studies using the GPT-2 model.

Modern autopilot systems are prone to sensor attacks that can jeopardize flight safety. To mitigate this risk, we proposed a modular solution: the secure safety filter, which extends the well-established control barrier function (CBF)-based safety filter to account for, and mitigate, sensor attacks. This module consists of a secure state reconstructor (which generates plausible states) and a safety filter (which computes the safe control input that is closest to the nominal one). Differing from existing work focusing on linear, noise-free systems, the proposed secure safety filter handles bounded measurement noise and, by leveraging reduced-order model techniques, is applicable to the nonlinear dynamics of drones. Software-in-the-loop simulations and drone hardware experiments demonstrate the effectiveness of the secure safety filter in rendering the system safe in the presence of sensor attacks.

While most networks have long lifetimes, temporary network infrastructure is often useful for special events, pop-up retail, or disaster response. Aninstant IoTnetwork is one that is rapidly constructed, used for a few days, then dismantled. We consider the synthesis of instant IoT networks in urban settings. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quicklyscalingto large regions while producing cost-effective solutions. We explore two qualitatively different representations of the synthesis problems using satisfiability modulo convex optimization (SMC), and mixed-integer linear programming (MILP). The former is more expressive, for our problem, than the latter, but is less well-suited for solving optimization problems like ours. We show how to express our network synthesis in these frameworks. To scale to problem sizes beyond what these frameworks are capable of, we develop ahierarchical synthesistechnique that independently synthesizes networks in sub-regions of the deployment area, then combines these. We find that, while MILP outperforms SMC in some settings for smaller problem sizes, the fact that SMC's expressivity matches our problem ensures that it uniformly generates better quality solutions at larger problem sizes.

In this paper, we revisit the problem of learning a stabilizing controller from a finite number of demonstrations by an expert. By focusing on feedback linearizable systems, we show how to combine expert demonstrations into a stabilizing controller, provided that demonstrations are sufficiently long and there are at least$n+1$of them, where$n$is the number of states of the system being controlled. The results are experimentally demonstrated on a CrazyFlie 2.0 quadrotor.

In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, the meaningful structure is specified in some discrete space, leading to difficult nonconvex optimization problems. In this paper, we connect the model selection problem with structure-promoting regularizers to submodular function minimization with continuous and discrete arguments. In particular, we leverage the theory of submodular functions to identify a class of these problems that can be solved exactly and efficiently with an agnostic combination of discrete and continuous optimization routines. We show how simple continuous or discrete constraints can also be handled for certain problem classes and extend these ideas to a robust optimization framework. We also show how some problems outside of this class can be embedded into the class, further extending the class of problems our framework can accommodate. Finally, we numerically validate our theoretical results with several proof-of-concept examples with synthetic and real-world data, comparing against state-of-the-art algorithms.

While most approaches in formal methods address system correctness, ensuring robustness has remained a challenge. In this article, we present and study the logic rLTL, which provides a means to formally reason about both correctness and robustness in system design. Furthermore, we identify a large fragment of rLTL for which the verification problem can be efficiently solved, i.e., verification can be done by using an automaton, recognizing the behaviors described by the rLTL formula φ, of size at most O(3 |φ |), where |φ | is the length of φ. This result improves upon the previously known bound of O(5|φ |) for rLTL verification and is closer to the LTL bound of O(2|φ |). The usefulness of this fragment is demonstrated by a number of case studies showing its practical significance in terms of expressiveness, the ability to describe robustness, and the fine-grained information that rLTL brings to the process of system verification. Moreover, these advantages come at a low computational overhead with respect to LTL verification.

Supervision of a nominal controller, to enforce safety, is concerned with appropriately modifying the generated control inputs, if needed, in order to keep a control system within a set of safe states. An integral component in supervision is a controlled invariant set contained in the set of safe states. In this paper, we build on recent results on the computation of polytopic controlled invariant sets to present a supervision framework that computes the corrected inputs analytically and, hence, suitable for real-time control. The framework is validated on the task of quadrotor obstacle avoidance by forcing the vehicle to navigate within controlled invariant sets of the obstacle-free space. The results are experimentally demonstrated on a Crazyflie 2.0 quadrotor.

Runtime monitoring is commonly used to detect the violation of desired properties in safety critical cyber-physical systems by observing its executions. Bauer et al. introduced an influential framework for monitoring Linear Temporal Logic (LTL) properties based on a three-valued semantics for a finite execution: the formula is already satisfied by the given execution, it is already violated, or it is still undetermined, i.e., it can still be satisfied and violated by appropriate extensions of the given execution. However, a wide range of formulas are not monitorable under this approach, meaning that there are executions for which satisfaction and violation will always remain undetermined no matter how it is extended. In particular, Bauer et al. report that 44% of the formulas they consider in their experiments fall into this category. Recently, a robust semantics for LTL was introduced to capture different degrees by which a property can be violated. In this paper we introduce a robust semantics for finite strings and show its potential in monitoring: every formula considered by Bauer et al. is monitorable under our approach. Furthermore, we discuss which properties that come naturally in LTL monitoring-such as the realizability of all truth values-can be transferred to the robust setting. We show that LTL formulas with robust semantics can be monitored by deterministic automata, and provide tight bounds on the size of the constructed automaton. Lastly, we report on a prototype implementation and compare it to the LTL monitor of Bauer et al. on a sample of examples.

Fully autonomous vehicles need the ability to localize without external help, for instance by using visual sensors together with a pre-loaded map of landmarks. In this paper we connect self-localization using landmarks with coding theory. This connection enables to translate Hamming distance properties to probabilistic localization guarantees given a certain number of errors in landmark identification; it also enables to leverage existing polynomial time decoding algorithms for localization. We present promising numerical evaluation results by simulating vehicle traveling paths along a road network generated from real data of a region in Washington D.C.

In this paper we revisit the problem of computing controlled invariant sets for controllable discrete-time linear systems and present a novel hierarchy for their computation. The key insight is to lift the problem to a higher dimensional space where the maximal controlled invariant set can be computed exactly and in closed-form for the lifted system. By projecting this set into the original space we obtain a controlled invariant set that is a subset of the maximal controlled invariant set for the original system. Building upon this insight we describe in this paper a hierarchy of spaces where the original problem can be lifted into so as to obtain a sequence of increasing controlled invariant sets. The algorithm that results from the proposed hierarchy does not rely on iterative computations. We illustrate the performance of the proposed method on a variety of scenarios exemplifying its appeal.

Runtime monitoring is commonly used to detect the violation of desired properties in safety critical cyber-physical systems by observing its executions. Bauer et al. introduced an influential framework for monitoring Linear Temporal Logic (LTL) properties based on a three-valued semantics: the formula is already satisfied by the given prefix, it is already violated, or it is still undetermined, i.e., it can still be satisfied and violated by appropriate extensions. However, a wide range of formulas are not monitorable under this approach, meaning that they have a prefix for which satisfaction and violation will always remain undetermined no matter how it is extended. In particular, Bauer et al. report that 44% of the formulas they consider in their experiments fall into this category.

Advances in optimization and constraint satisfaction techniques, together with the availability of elastic computing resources, have spurred interest in large-scale network verification and synthesis. Motivated by this, we consider the top-down synthesis of ad-hoc IoT networks for disaster response and search and rescue operations. This synthesis problem must satisfy complex and competing constraints: sensor coverage, line-of-sight visibility, and network connectivity. The central challenge in our synthesis problem is quickly scaling to large regions while producing cost-effective solutions. We explore a representation of the synthesis problems using a novel constraint satisfaction paradigm, satisfiability modulo convex optimization (SMC). We choose SMC because it matches the expressivity needs for our network synthesis. To scale to large problem sizes, we develop a hierarchical synthesis technique that independently synthesizes networks in sub-regions of the deployment area, then combines these. Our experiments show that SMC consistently generates better quality solutions than a baseline synthesis approach based on Mixed Integer Linear Programming (MILP).

Persistent surveillance with aerial vehicles (drones) subject to connectivity and power constraints is a relatively uncharted domain of research. To reduce the complexity of multi-drone motion planning, most state-of-the-art solutions ignore network connectivity and assume unlimited battery power. Motivated by this and advances in optimization and constraint satisfaction techniques, we introduce a new persistent surveillance motion planning problem for multiple drones that incorporates connectivity and power consumption constraints. We use a recently developed constrained optimization tool (Satisfiability Modulo Convex Optimization (SMC)) that has the expressivity needed for this problem. We show how to express the new persistent surveillance problem in the SMC framework. Our analysis of the formulation based on a set of simulation experiments illustrates that we can generate the desired motion planning solution within a couple of minutes for small teams of drones (up to 5) confined to a 7 × 7 × 1 grid-space.

Robust Linear Temporal Logic (rLTL) was crafted to incorporate the notion of robustness into Linear-time Temporal Logic (LTL) specifications. Technically, robustness was formalized in the logic rLTL via 5 different truth values and it led to an increase in the time complexity of the associated model checking problem. In general, model checking an rLTL formula relies on constructing a generalized Büchi automaton of size 5 | φ | where | φ | denotes the length of an rLTL formula φ. It was recently shown that the size of this automaton can be reduced to 3 | φ | (and even smaller) when the formulas to be model checked come from a fragment of rLTL. In this paper, we introduce Evrostos, the first tool for model checking formulas in this fragment. We also present several empirical studies, based on models and LTL formulas reported in the literature, confirming that rLTL model checking for the aforementioned fragment incurs in a time overhead that makes the verification of rLTL practical.

The vision of an Internet-of-Things calls for combining the increasing connectivity of devices at the edge with the ability to compute either at the edge or on more powerful servers in the network. There is great interest in exploring the feasibility of these ideas when devices such as quadcopters or ground robots at the edge are controlled over the cloud, i.e., by leveraging computational power available elsewhere in the network. One of the main difficulties, especially in the context of the Internet-of-Battlefield- Things is the need to keep the data private. In this paper we propose a solution to this problem by extending previous results by the authors from a single system controlled over the cloud to networks of systems that are controlled and coordinated over the cloud. We propose a noncryptographic lightweight encoding scheme that ensures the privacy of the data exchanged by all the participating parties.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

The design of cyber-physical systems (CPSs) requires methods and tools that can efficiently reason about the interaction between discrete models, e.g., representing the behaviors of “cyber” components, and continuous models of physical processes. Boolean methods such as satisfiability (SAT) solving are successful in tackling large combinatorial search problems for the design and verification of hardware and software components. On the other hand, problems in control, communications, signal processing, and machine learning often rely on convex programming as a powerful solution engine. However, despite their strengths, neither approach would work in isolation for CPSs. In this paper, we present a new satisfiability modulo convex programming (SMC) framework that integrates SAT solving and convex optimization to efficiently reason about Boolean and convex constraints at the same time. We exploit the properties of a class of logic formulas over Boolean and nonlinear real predicates, termed monotone satisfiability modulo convex formulas, whose satisfiability can be checked via a finite number of convex programs. Following the lazy satisfiability modulo theory (SMT) paradigm, we develop a new decision procedure for monotone SMC formulas, which coordinates SAT solving and convex programming to provide a satisfying assignment or determine that the formula is unsatisfiable. A key step in our coordination scheme is the efficient generation of succinct infeasibility proofs for inconsistent constraints that can support conflict-driven learning and accelerate the search. We demonstrate our approach on different CPS design problems, including spacecraft docking mission control, robotic motion planning, and secure state estimation. We show that SMC can handle more complex problem instances than state-of-the-art alternative techniques based on SMT solving and mixed integer convex programming.

This paper develops a control approach with correctness guarantees for the simultaneous operation of lane keeping and adaptive cruise control. The safety specifications for these driver assistance modules are expressed in terms of set invariance. Control barrier functions (CBFs) are used to design a family of control solutions that guarantee the forward invariance of a set, which implies satisfaction of the safety specifications. The CBFs are synthesized through a combination of sum-of-squares program and physics-based modeling and optimization. A real-time quadratic program is posed to combine the CBFs with the performance-based controllers, which can be either expressed as control Lyapunov function conditions or as black-box legacy controllers. In both cases, the resulting feedback control guarantees the safety of the composed driver assistance modules in a formally correct manner. Importantly, the quadratic program admits a closed-form solution that can be easily implemented. The effectiveness of the control approach is demonstrated by simulations in the industry-standard vehicle simulator Carsim.

We introduce a scalable observer architecture, which can efficiently estimate the states of a discrete-time linear-time-invariant system whose sensors are manipulated by an attacker, and is robust to measurement noise. Given an upper bound on the number of attacked sensors, we build on previous results on necessary and sufficient conditions for state estimation, and propose a novel Multi-Modal Luenberger (MML) observer based on efficient Satisfiability Modulo Theory (SMT) solving. We present two techniques to reduce the complexity of the estimation problem. As a first strategy, instead of a bank of distinct observers, we use a family of filters sharing a single dynamical equation for the states, but different output equations, to generate estimates corresponding to different subsets of sensors. Such an architecture can reduce the memory usage of the observer from an exponential to a linear function of the number of sensors. We then develop an efficient SMT-based decision procedure that is able to reason about the estimates of the MML observer to detect at runtime which sets of sensors are attack-free, and use them to obtain a correct state estimate. Finally, we discuss two optimization-based algorithms that can efficiently select the observer parameters with the goal of minimizing the sensitivity of the estimates with respect to sensor noise. We provide proofs of convergence for our estimation algorithm and report simulation results to compare its runtime performance with alternative techniques. We show that our algorithm scales well for large systems (including up to 5,000 sensors) for which many previously proposed algorithms are not implementable due to excessive memory and time requirements. Finally, we illustrate the effectiveness of our approach, both in terms of resiliency to attacks and robustness to noise, on the design of large-scale power distribution networks.

Evaluation of industrial embedded control system designs is a time-consuming and imperfect process. While an ideal process would apply a formal verification technique such as model checking or theorem proving, these techniques do not scale to industrial design problems, and it is often difficult to use these techniques to verify performance aspects of control system designs, such as stability or convergence. For industrial designs, engineers rely on testing processes to identify critical or unexpected behaviors. We propose a novel framework called Underminer to improve the testing process; this is an automated technique to identify nonconverging behaviors in embedded control system designs. Underminer treats the system as a black box and lets the designer indicate the model parameters, inputs, and outputs that are of interest. It differentiates convergent from nonconvergent behaviors using Convergence Classifier Functions (CCFs). The tool can be applied in the context of testing models created late in the controller development stage, where it assumes that the given model displays mostly convergent behavior and learns a CCF in an unsupervised fashion from such convergent model behaviors. This CCF is then used to guide a thorough exploration of the model with the help of optimization-guided techniques or adaptive sampling techniques, with the goal of identifying rare nonconvergent model behaviors. Underminer can also be used early in the development stage, where models may have some significant nonconvergent behaviors. Here, the framework permits designers to indicate their mental model for convergence by labeling behaviors as convergent/nonconvergent and then constructs a CCF using a supervised learning technique. In this use case, the goal is to use the CCF to test an improved design for the model. Underminer supports a number of convergence-like notions, such as those based on Lyapunov analysis and temporal logic, and also CCFs learned directly from labeled output behaviors using machine-learning techniques such as support vector machines and neural networks. We demonstrate the efficacy of Underminer by evaluating its performance on several academic as well as industrial examples.

We address the problem of determining the satisfiability of a Boolean combination of convex constraints over the real numbers, which is common in the context of hybrid system verification and control. We first show that a special type of logic formulas, termed monotone Satisfiability Modulo Convex (SMC) formulas, is the most general class of formulas over Boolean and nonlinear real predicates that reduce to convex programs for any satisfying assignment of the Boolean variables. For this class of formulas, we develop a new satisfiability modulo convex optimization procedure that uses a lazy combination of SAT solving and convex programming to provide a satisfying assignment or determine that the formula is unsatisfiable. Our approach can then leverage the efficiency and the formal guarantees of state-of-the-art algorithms in both the Boolean and convex analysis domains. A key step in lazy satisfiability solving is the generation of succinct infeasibility proofs that can support conflict-driven learning and decrease the number of iterations between the SAT and the theory solver. For this purpose, we propose a suite of algorithms that can trade complexity with the minimality of the generated infeasibility certificates. Remarkably, we show that a minimal infeasibility certificate can be generated by simply solving one convex program for a sub-class of SMC formulas, namely ordered positive unate SMC formulas, that have additional monotonicity properties. Perhaps surprisingly, ordered positive unate formulas appear themselves very frequently in a variety of practical applications. By exploiting the properties of monotone SMC formulas, we can then build and demonstrate effective and scalable decision procedures for problems in hybrid system verification and control, including secure state estimation and robotic motion planning.

This demo abstract presents PrOLoc, a localization system that combines partially homomorphic encryption with a new way of structuring the localization problem to enable efficient and accurate computation of a target's location while preserving the privacy of the observers.

Aided by advances in sensors and algorithms, systems for localizing and tracking target objects or events have become ubiquitous in recent years. Most of these systems operate on the principle of fusing measurements of distance and/or direction to the target made by a set of spatially distributed observers using sensors that measure signals such as RF, acoustic, or optical. The computation of the target's location is done using multilateration and multiangulation algorithms, typically running at an aggregation node that, in addition to the distance/direction measurements, also needs to know the observers' locations. This presents a privacy risk for an observer that does not trust the aggregation node or other observers and could in turn lead to lack of participation. For example, consider a crowd-sourced sensing system where citizens are required to report security threats, or a smart car, stranded with a malfunctioning GPS, sending out localization requests to neighboring cars - in both cases, observer (i.e., citizens and cars respectively) participation can be increased by keeping their location private. This paper presents PrOLoc, a localization system that combines partially homomorphic encryption with a new way of structuring the localization problem to enable efficient and accurate computation of a target's location without requiring observers to make public their locations or measurements. Moreover, and unlike previously proposed perturbation based techniques, PrOLoc is also resilient to malicious active false data injection attacks. We present two realizations of our approach, provide rigorous theoretical guarantees, and also compare the performance of each against traditional methods. Our experiments on real hardware demonstrate that PrOLoc yields location estimates that are accurate while being at least 500x faster than state-of-art secure function evaluation techniques.

Although it is widely accepted that every system should be robust, in the sense that "small" violations of environment assumptions should lead to "small" violations of system guarantees, it is less clear how to make this intuitive notion of robustness mathematically precise. In this paper, we address this problem by developing a robust version of Linear Temporal Logic (LTL), which we call robust LTL and denote by rLTL. Formulas in rLTL are syntactically identical to LTL formulas but are endowed with a many-valued semantics that encodes robustness. In particular, the semantics of the rLTL formula $φ\Rightarrow ψ$ is such that a "small" violation of the environment assumption $φ$ is guaranteed to only produce a "small" violation of the system guarantee $ψ$. In addition to introducing rLTL, we study the verification and synthesis problems for this logic: similarly to LTL, we show that both problems are decidable, that the verification problem can be solved in time exponential in the number of subformulas of the rLTL formula at hand, and that the synthesis problem can be solved in doubly exponential time.

Evaluation of industrial embedded control system designs is a time-consuming and imperfect process. While an ideal process would apply a formal verification technique such as model checking or theorem proving, these techniques do not scale to industrial design problems, and it is often difficult to use these techniques to verify performance aspects of control system designs, such as stability or convergence. For industrial designs, engineers rely on testing processes to identify critical or unexpected behaviors. We propose a novel framework called Underminer to improve the testing process; this is an automated technique to identify non-converging behaviors in embedded control system designs. Underminer treats the system as a black box, and lets the designer indicate the model parameters, inputs and outputs that are of interest. It supports a multiplicity of convergence-like notions, such as those based on Lyapunov analysis and those based on temporal logic formulae. Underminer can be applied in the context of testing models created in the controller-design phase, and can also be applied in a scenario such as hardware-in-the-loop testing. We demonstrate the efficacy of Underminer by evaluating its performance on several examples.

Bipedal robots are prime examples of complex cyber-physical systems (CPS). They exhibit many of the features that make the design and verification of CPS so difficult: hybrid dynamics, large continuous dynamics in each mode (e.g., 10 or more state variables), and nontrivial specifications involving nonlinear constraints on the state variables. In this paper, we propose a two-step approach to formally synthesize control software for bipedal robots so as to enforce specifications by design and thereby generate physically realizable stable walking. In the first step, we design outputs and classical controllers driving these outputs to zero. The resulting controlled system evolves on a lower dimensional manifold and is described by the hybrid zero dynamics governing the remaining degrees of freedom. In the second step, we construct an abstraction of the hybrid zero dynamics that is used to synthesize a controller enforcing the desired specifications to be satisfied on the full order model. Our two step approach is a systematic way to mitigate the curse of dimensionality that hampers the applicability of formal synthesis techniques to complex CPS. Our results are illustrated with simulations showing how the synthesized controller enforces all the desired specifications and offers improved performance with respect to a controller that was utilized to obtain walking experimentally on the bipedal robot AMBER 2.

Motivated by the need to secure cyber-physical systems against attacks, we consider the problem of estimating the state of a noisy linear dynamical system when a subset of sensors is arbitrarily corrupted by an adversary. We propose a secure state estimation algorithm and derive (optimal) bounds on the achievable state estimation error. In addition, as a result of independent interest, we give a coding theoretic interpretation for prior work on secure state estimation against sensor attacks in a noiseless dynamical system.

According to the IEEE standard glossary of software engineering, robustness is the degree to which a system or component can function correctly in the presence of invalid inputs or stressful environment conditions. In this paper we present a design methodology for robust cyber-physical systems (CPS) based on a notion of robustness for CPS termed input-output dynamical stability. It captures two intuitive aims of a robust design: bounded disturbances have bounded consequences and the effect of sporadic disturbances disappears as time progresses. Our framework to synthesize robust CPS is based on an abstraction and refinement procedure, where the robust CPS is obtain through the refinement of a design for an abstraction of the concrete CPS. The soundness of the approach is ensured through the use of several novel notions of simulation relation introduced in this paper.

Wide deployment of wireless sensor and actuator networks in cyber-physical systems requires systematic design tools to enable dynamic tradeoff of network resources and control performance. In this paper, we consider three recently proposed aperiodic control algorithms which have the potential to address this problem. By showing how these controllers can be implemented over the IEEE 802.15.4 standard, a practical wireless control system architecture with guaranteed closed-loop performance is detailed. Event-based predictive and hybrid sensor and actuator communication schemes are compared with respect to their capabilities and implementation complexity. A two double-tank laboratory experimental setup, mimicking some typical industrial process control loops, is used to demonstrate the applicability of the proposed approach. Experimental results show how the sensor communication adapts to the changing demands of the control loops and the network resources, allowing for lower energy consumption and efficient bandwidth utilization.

In this paper we present and analyze a novel algorithm to synthesize controllers enforcing linear temporal logic specifications on discrete-time linear systems. The central step within this approach is the computation of the maximal controlled invariant set contained in a possibly non-convex safe set. Although it is known how to compute approximations of maximal controlled invariant sets, its exact computation remains an open problem. We provide an algorithm which computes a controlled invariant set that is guaranteed to be an under-approximation of the maximal controlled invariant set. Moreover, we guarantee that our approximation is at least as good as any invariant set whose distance to the boundary of the safe set is lower bounded. The proposed algorithm is founded on the notion of sets adapted to the dynamics and binary decision diagrams. Contrary to most controller synthesis schemes enforcing temporal logic specifications, we do not compute a discrete abstraction of the continuous dynamics. Instead, we abstract only the part of the continuous dynamics that is relevant for the computation of the maximal controlled invariant set. For this reason we call our approach specification guided. We describe the theoretical foundations and technical underpinnings of a preliminary implementation and report on several experiments including the synthesis of an automatic cruise controller. Our preliminary implementation handles up to five continuous dimensions and specifications containing up to 160 predicates defined as polytopes in about 30 minutes with less than 1 GB memory.

A key property for systems subject to uncertainty in their operating environment is robustness : ensuring that unmodeled but bounded disturbances have only a proportionally bounded effect upon the behaviors of the system. Inspired by ideas from robust control and dissipative systems theory, we present a formal definition of robustness as well as algorithmic tools for the design of optimally robust controllers for ω-regular properties on discrete transition systems. Formally, we define metric automata —automata equipped with a metric on states—and strategies on metric automata which guarantee robustness for ω-regular properties. We present fixed-point algorithms to construct optimally robust strategies in polynomial time. In contrast to strategies computed by classical graph theoretic approaches, the strategies computed by our algorithm ensure that the behaviors of the controlled system gracefully degrade under the action of disturbances; the degree of degradation is parameterized by the magnitude of the disturbance. We show an application of our theory to the design of controllers that tolerate infinitely many transient errors provided they occur infrequently enough.

Robustness is the property that a system only exhibits small deviations from the nominal behavior upon the occurrence of small disturbances. While the importance of robustness in engineering design is well accepted, it is less clear how to verify and design discrete systems for robustness. We present a theory of input-output robustness for discrete systems inspired by existing notions of input-output stability (IO-stability) in continuous control theory. We show that IO-stability captures two intuitive goals of robustness: bounded disturbances lead to bounded deviations from nominal behavior, and the effect of a sporadic disturbance disappears in finitely many steps. We show that existing notions of robustness for discrete systems do not have these two properties. For systems modeled as finite-state transducers, we show that IO-stability can be verified and the synthesis problem can be solved in polynomial time. We illustrate our theory using a reference broadcast synchronization protocol for wireless networks.

Systems working in uncertain environments should possess a robustness property, which ensures that the behaviours of the system remain close to the original behaviours under the influence of unmodeled, but bounded, disturbances. We present a theory and algorithmic tools for the design of robust discrete controllers for π-regular properties on discrete transition systems. Formally, we define metric automata - automata equipped with a metric on states - and strategies on metric automata which guarantee robustness for π-regular properties. We present graph-theoretic algorithms to construct such strategies in polynomial time. In contrast to strategies computed by classical automata-theoretic algorithms, the strategies computed by our algorithm ensure that the behaviours of the controlled system under disturbances satisfy a related property which depends on the magnitude of the disturbance. We show an application of our theory to the design of controllers that tolerate infinitely many transient errors provided they occur infrequently enough.

We introduce PESSOA 2.0, a tool that automatically synthesizes controllers for cyber-physical systems based on correct-by-design methodology. PESSOA 2.0 accepts a cyber-physical system represented by a set of smooth differential equations and automata and a specification in a fragment of Linear Temporal Logic that is expressive enough to describe interesting properties but simple enough to avoid Safra's construction. It outputs, if possible, a controller for the system that enforces the specification up to an abstraction parameter. We report on examples illustrating the expressiveness of the fragment and the controllers synthesized by the tool.

Software implementations of controllers for physical subsystems form the core of many modern safety-critical systems such as aircraft flight control and automotive engine control. A fundamental property of such implementations is stability, the guarantee that the physical plant converges to a desired behavior under the actions of the controller. We present a methodology and a tool to perform automated static analysis of embedded controller code for stability of the controlled physical system.

Time-triggered periodic control implementations are over provisioned for many execution scenarios in which the states of the controlled plants are close to equilibrium. To address this inefficient use of computation resources, researchers have proposed self-triggered control approaches in which the control task computes its execution deadline at runtime based on the state and dynamical properties of the controlled plant. The potential advantages of this control approach cannot, however, be achieved without adequate online resource-management policies. This paper addresses scheduling of multiple self-triggered control tasks that execute on a uniprocessor platform, where the optimization objective is to find trade-offs between the control performance and CPU usage of all control tasks. Our experimental results show that efficiency in terms of control performance and reduced CPU usage can be achieved with the heuristic proposed in this paper.

A vast majority of control systems require the use of networks for the communication between the different agents: sensors, controllers, and actuators. The existing paradigm regards the messages, between sensors and controllers and between controllers and actuators, as periodic. Although this strategy facilitates the analysis and implementation, it leads to a conservative usage of the communication bandwidth. Based on previous work by the authors, an aperiodic strategy is proposed in this paper for the dynamic allocation of bandwidth according to the current state of the plants and the available resources. The case of control loops closed over Controller Area Networks (CANs) is discussed in detail and illustrated on a train car.

Formations of multi-agent systems, such as mobile robots, satellites and aircraft, require individual agents to satisfy their kinematic equations while constantly maintaining interagent constraints. In this paper, we develop a systematic framework for studying formation motion feasibility of multi-agent systems. In particular, we consider formations wherein all the agents cooperate to enforce the formation. We determine algebraic conditions that guarantee formation feasibility given the individual agent kinematics. Our framework also enables us to obtain lower dimensional control systems describing the group kinematics while maintaining all formation constraints.