Search

The paper proposes a method for the correct by design coordination of autonomous driving systems (ADS). It builds on previous results on collision avoidance policies and the modeling of ADS by combining descriptions of their static environment in the form of maps, and the dynamic behavior of their vehicles. An ADS is modeled as a dynamic system involving a set of vehicles coordinated by a Runtime that based on vehicle positions on a map and their kinetic attributes, computes free spaces for each vehicle. Vehicles are bounded to move within the corresponding allocated free spaces. We provide a correct by design safe control policy for an ADS, if its vehicles and the Runtime respect corresponding assume-guarantee contracts. The result is established by showing that the composition of assume-guarantee contracts is an inductive invariant that entails ADS safety. We show that it is practically possible to define speed control policies for vehicles that comply with their contracts. Furthermore, we show that traffic rules can be specified in a linear-time temporal logic as a class of formulas that constrain vehicle speeds. The main result is that, given a set of traffic rules, it is possible to derive free-space policies of the Runtime such that the resulting system behavior is safe by design with respect to the rules. [ABSTRACT FROM AUTHOR]

We study a sound verification method for parametric component-based systems. The method uses a resource logic, a new formal specification language for distributed systems consisting of a finite yet unbounded number of components. The logic allows the description of architecture configurations coordinating instances of a finite number of types of components, by means of inductive definitions similar to the ones used to describe algebraic data types or recursive data structures. For parametric systems specified in this logic, we show that decision problems such as reaching deadlock or violating critical section are undecidable, in general. Despite this negative result, we provide for these decision problems practical semi-algorithms relying on the automatic synthesis of structural invariants allowing the proof of general safety properties. The invariants are defined using the WS κ S fragment of the monadic second order logic, known to be decidable by a classical automata-logic connection, thus reducing a verification problem to checking satisfiability of a WS κ S formula. • We introduce a logic-based language for describing sets of configurations of parameterized distributed systems. • The language uses predicate symbols to hierarchically decompose the system architecture into specific patterns. • We address a parametric safety problem i.e., checking that reachable configurations stay clear of error configurations. • We show that deadlock freedom and critical section violation problems are undecidable, even for simple architectures. • We develop a verification method that synthesizes parametric invariants described using a decidable fragment of MSO. [ABSTRACT FROM AUTHOR]

We provide an algebraic formalization of connectors in the BIP component framework. A connector relates a set of typed ports. Types are used to describe different modes of synchronization, in particular, rendezvous and broadcast. Connectors on a set of ports P are modeled as terms of the algebra AC(P), generated from P by using a binary fusion operator and a unary typing operator. Typing associates with terms (ports or connectors) synchronization types—trigger or synchron—that determine modes of synchronization. Broadcast interactions are initiated by triggers. Rendezvous is a maximal interaction of a connector that includes only synchrons. The semantics of AC(P) associates with a connector the set of its interactions. It induces on connectors an equivalence relation which is not a congruence as it is not stable for fusion. We provide a number of properties of AC(P) used to symbolically simplify and handle connectors. We provide examples illustrating applications of AC(P), including a general component model encompassing methods for incremental model decomposition and efficient implementation by using symbolic techniques. [ABSTRACT FROM AUTHOR]

The article discusses the need for a rigorous approach to embedded systems design. Challenges abound. The heterogeneity of embedded systems components introduces several issues. Abstract design considerations must be reduced to practical details capable of being implemented. Systems must be robust, capable of withstanding a variety of perturbations. Education in computer science and electrical engineering will require better integration to meet these challenges. In addition, Industry needs to better respond to the emerging demands of embedded system design, and government policymakers should increase research funding.

Abstract: We propose a framework for component-based modeling using an abstract layered model for components. A component is the superposition of two models: a behavior model and an interaction model. Interaction models describe architectural constraints induced by connectors between components. We propose and analyze general requirements for component composition that motivated and guided the development of the framework. We define an associative and commutative composition operator on components encompassing heterogeneous interaction. As a particular instance of the proposed framework, we consider components where behavior models are transition systems and interaction models are described by priority relations on interactions. This leads to a concept of “flexible” composition different from usual composition in that it preserves deadlock-freedom and is appropriate for correctness by construction. Nevertheless, flexible composition is a partial operation. Product systems should be interaction safe in the sense that they do not violate constraints of the interaction model. We propose results ensuring correctness by construction of a system from properties of its interaction model and of its components. The properties considered include global deadlock-freedom, individual deadlock-freedom of components, and interaction safety. [Copyright &y& Elsevier]

We propose a method for the implementation and analysis of real-time systems, based on the compilation of specifications into extended automata. Such a method has been already adopted for the so called "synchronous" real-time programming languages. The method is illustrated for a simple specification language that can be viewed as the, extension of a language for the description of systems of communicating processes, by adding timeout and watchdog constructs. An operational semantics is defined for arbitrary time domains. The main result is that such a language can be compiled into timed automata, extended automata with timers. Timers are special state variables that can be set to zero by transitions, and whose values measure the tithe elapsed since their last reset. Compared to extended automata generated by compilers of synchronous languages, timed automata do not make any assumption about the nature of time and adopt an event-driven execution mode, rather than a step-by-step one. Furthermore, their complexity does not depend on the values of the parameters of timeouts and watchdogs used in specifications. These features allow the application on timed automata of efficient code generation and analysis techniques. In particular, we show how symbolic model-checking of real-time properties can be directly applied to this model. [ABSTRACT FROM AUTHOR]

Modern systems evolve in unpredictable environments and have to continuously adapt their behaviour to changing conditions. The "DReAM" (Dynamic Reconfigurable Architecture Modelling) framework has been designed for modelling reconfigurable dynamic systems. It provides a rule-based language, inspired from Interaction Logic, which is expressive and easy to use encompassing all aspects of dynamicity including parametric multi-modal coordination with creation/deletion of components as well as mobility. Additionally, it allows the description of both endogenous/modular and exogenous/centralized coordination styles and sound transformations from one style to the other. The DReAM framework is implemented in the form of a Java API bundled with an execution engine. It allows us to develop runnable systems combining the expressiveness of the rule-based notation together with the flexibility of this widespread programming language. [ABSTRACT FROM AUTHOR]

The potential benefits of autonomous systems are obvious. However, there are still major issues to be dealt with before developing such systems becomes a commonplace engineering practice, with accepted and trustworthy deliverables. We argue that a solid, evolving, publicly available, community-controlled foundation for developing next-generation autonomous systems is a must, and term the desired foundation "autonomics". We focus on three main challenges: 1) how to specify autonomous system behavior in the face of unpredictability; 2) how to carry out faithful analysis of system behavior with respect to rich environments that include humans, physical artifacts, and other systems; and 3) how to build such systems by combining executable modeling techniques from software engineering with artificial intelligence and machine learning. [ABSTRACT FROM AUTHOR]

Cyber-physical systems have developed into a very active research field, with a broad range of challenges and research directions going from requirements, to implementation and simulation, as well as validation and verification to guarantee essential properties. In this survey paper, we focus exclusively on the following fundamental issue: how to link physicality and computation, continuous time-space dynamics with discrete untimed ones? We consider that cyber-physical system design flow involves the following three main steps: (1) cyber-physical systems modeling; (2) discretization for executability; and (3) simulation and implementation. We review—and strive to provide insight into possible approaches for addressing—the key issues, for each of these three steps. [ABSTRACT FROM AUTHOR]

There is growing recognition that regionalization of bacterial colonization and immunity along the intestinal tract has an important role in health and disease. Yet, the mechanisms underlying intestinal regionalization and its dysregulation in disease are not well understood. This study found that regional epithelial expression of the transcription factor GATA4 controls bacterial colonization and inflammatory tissue immunity in the proximal small intestine by regulating retinol metabolism and luminal IgA. Furthermore, in mice without jejunal GATA4 expression, the commensal segmented filamentous bacteria promoted pathogenic inflammatory immune responses that disrupted barrier function and increased mortality upon Citrobacter rodentium infection. In celiac disease patients, low GATA4 expression was associated with metabolic alterations, mucosal Actinobacillus, and increased IL-17 immunity. Taken together, these results reveal broad impacts of GATA4-regulated intestinal regionalization on bacterial colonization and tissue immunity, highlighting an elaborate interdependence of intestinal metabolism, immunity, and microbiota in homeostasis and disease. [Display omitted] • GATA4 prevents small intestinal inflammation by restricting bacterial colonization • GATA4 regulates bacterial colonization in part by regulating IgA and retinol metabolism • GATA4 deficiency, SFB, and Citrobacter rodentium synergize to drive immunopathology • Th17 immunity is found in celiac patients with GATA4 deficiency and Actinobacillus Regulators of intestinal regionalization are vital, yet poorly understood. Here, Earley et al. demonstrate how the transcription factor GATA4 regulates metabolic pathways and luminal IgA to control adherent bacteria colonization. Proper gut regionalization and commensal colonization is critical in preventing dysregulated Th17 responses and immunopathology in humans and mice. [ABSTRACT FROM AUTHOR]

DR-BIP is an extension of the BIP component framework intended for programming reconfigurable systems encompassing various aspects of dynamism. It relies on architectural motifs to structure the architecture of a system and to coordinate its reconfiguration at runtime. An architectural motif defines a set of interacting components that evolve according to reconfiguration rules. With DR-BIP, the dynamism can be captured as the inter-play of dynamic changes in three independent directions: (1) the organization of interactions between instances of components in a given configuration; (2) the reconfiguration mechanisms allowing creation/deletion of components and management of their interaction according to a given architectural motif; and (3) the migration of components between predefined architectural motifs which characterizes dynamic execution environments. The paper lays down the formal foundation of DR-BIP, illustrates its expressiveness on few examples and discusses avenues for dynamic reconfigurable system design. [ABSTRACT FROM AUTHOR]

Neuroepithelial crosstalk is critical for gut physiology. However, the mechanisms by which sensory neurons communicate with epithelial cells to mediate gut barrier protection at homeostasis and during inflammation are not well understood. Here, we find that Nav1.8+CGRP+ nociceptor neurons are juxtaposed with and signal to intestinal goblet cells to drive mucus secretion and gut protection. Nociceptor ablation led to decreased mucus thickness and dysbiosis, while chemogenetic nociceptor activation or capsaicin treatment induced mucus growth. Mouse and human goblet cells expressed Ramp1, receptor for the neuropeptide CGRP. Nociceptors signal via the CGRP-Ramp1 pathway to induce rapid goblet cell emptying and mucus secretion. Notably, commensal microbes activated nociceptors to control homeostatic CGRP release. In the absence of nociceptors or epithelial Ramp1, mice showed increased epithelial stress and susceptibility to colitis. Conversely, CGRP administration protected nociceptor-ablated mice against colitis. Our findings demonstrate a neuron-goblet cell axis that orchestrates gut mucosal barrier protection. [Display omitted] • Nav1.8+CGRP+ nociceptors neighbor goblet cells and induce rapid mucus secretion • Commensals trigger CGRP release, which signals to Ramp1 expressed by goblet cells • Nociceptor or Ramp1 ablation leads to decreased mucus levels and microbial dysbiosis • Neuron-goblet cell signaling via a CGRP-Ramp1 axis protects against colitis Pain sensory neurons induce mucus release from nearby intestinal goblet cells via a CGRP-Ramp1 axis in response to commensal and dietary cues to orchestrate gut mucosal protection. [ABSTRACT FROM AUTHOR]

We propose invariant-based techniques for the efficient verification of safety and deadlock-freedom properties of component-based systems. Components and their interactions are described in the BIP language. Global invariants of composite components are obtained by combining local invariants of their constituent components with interaction invariants that take interactions into account. We study new techniques for computing interaction invariants. Some of these techniques are incremental, i.e., interaction invariants of a composite hierarchically structured component are computed by reusing invariants of its constituents. We formalize incremental construction of components in the BIP language as the process of building progressively complex components by adding interactions (synchronization constraints) to atomic components. We provide sufficient conditions ensuring preservation of invariants when new interactions are added. When these conditions are not satisfied, we propose methods for generating new invariants in an incremental manner by reusing existing invariants from the constituents in the incremental construction. The reuse of existing invariants reduces considerably the overall verification effort. The techniques have been implemented in the D-Finder toolset. Among the experiments conducted, we have been capable of verifying safety properties and deadlock-freedom of sub-systems of the functional level of the DALA autonomous robot. This work goes far beyond the capacity of existing monolithic verification tools. [ABSTRACT FROM AUTHOR]

Architectures depict design principles: paradigms that can be understood by all, allow thinking on a higher plane and avoiding low-level mistakes. They provide means for ensuring correctness by construction by enforcing global properties characterizing the coordination between components. An architecture can be considered as an operator A that, applied to a set of components $${\mathcal{B}}$$ , builds a composite component $${A(\mathcal{B})}$$ meeting a characteristic property $${\Phi}$$ . Architecture composability is a basic and common problem faced by system designers. In this paper, we propose a formal and general framework for architecture composability based on an associative, commutative and idempotent architecture composition operator $${\oplus}$$ . The main result is that if two architectures A and A enforce respectively safety properties $${\Phi_{1}}$$ and $${\Phi_{2}}$$ , the architecture $${A_{1} \oplus A_{2}}$$ enforces the property $${\Phi_{1} \land \Phi_{2}}$$ , that is both properties are preserved by architecture composition. We also establish preservation of liveness properties by architecture composition. The presented results are illustrated by a running example and a case study. [ABSTRACT FROM AUTHOR]

We design and experimentally evaluate a hybrid safe-by-construction longitudinal collision avoidance controller for autonomous vehicles. The controller combines into a single architecture the respective advantages of a model predictive controller and a discrete safe controller. The model predictive controller is used to achieve optimal efficiency in nominal conditions. The safe controller avoids collision by applying two different policies, for nominal and out-of-nominal conditions, respectively. We present design principles for both controllers and show how each one can contribute in the hybrid architecture to improve performance, road occupancy and passenger comfort while preserving safety. The experimental results confirm the feasibility of the approach and the practical relevance of hybrid controllers for safe and efficient driving. [ABSTRACT FROM AUTHOR]

Using high level coordination primitives allows enhanced expressiveness of component-based frameworks to cope with the inherent complexity of present-day systems designs. Nonetheless, their distributed implementation raises multiple issues, regarding both the correctness and the runtime performance of the final implementation. We propose a novel approach for distributed implementation of multiparty interactions subject to scheduling constraints expressed by priorities. We rely on a new composition operator named Restriction, whose semantics dynamically restricts the set of interactions allowed for execution, depending on the current state. We show that this operator provides a natural encoding for priorities. We provide a knowledge-based optimization that modifies the Restriction operator to avoid superfluous communication in the final implementation. We complete our framework through an enhanced conflict resolution protocol that natively implements Restriction. A prototype implementation allows us to compare performances of different optimizations. [ABSTRACT FROM AUTHOR]

Although distributed systems are widely used nowadays, their implementation and deployment are still time-consuming, error-prone, and hardly predictable tasks. In this paper, we propose a method for producing automatically efficient and correct-by-construction distributed implementations from a model of the application software in Behavior, Interaction, Priority (BIP). BIP is a well-founded component-based framework encompassing high-level multi-party interactions for synchronizing components (e.g., rendezvous and broadcast) and dynamic priorities for scheduling between interactions. Our method transforms an arbitrary BIP model into a Send/Receive BIP model that is directly implementable on distributed execution platforms. The transformation consists in (1) breaking the atomicity of actions in components by replacing synchronous multiparty interactions with asynchronous Send/Receive interactions; (2) inserting distributed controllers that coordinate the execution of interactions according to a user-defined partition of interactions, and (3) adding a distributed algorithm for handling conflicts between controllers. The obtained Send/Receive BIP model is proven observationally equivalent to its corresponding initial model. Hence, all functional properties of the initial BIP model are preserved by construction in the implementation. Moreover, the obtained Send/Receive BIP model can be used to automatically derive distributed executable code. The proposed method is fully implemented. Currently, it is possible to generate C++ implementations for (1) TCP sockets for conventional distributed communication, (2) MPI for multi-processor platforms, and (3) POSIX threads for deployment on multi-core platforms. We present four case studies and report experimental results for different design choices including partition of interactions and choice of algorithm for distributed conflict resolution. [ABSTRACT FROM AUTHOR]

Rigorous system design requires the use of a single powerful component framework allowing the representation of the designed system at different detail levels, from application software to its implementation. A single framework allows the maintenance of the overall coherency and correctness by comparing different architectural solutions and their properties. The authors present the BIP (behavior, interaction, priority) component framework, which encompasses an expressive notion of composition for heterogeneous components by combining interactions and priorities. This allows description at different abstraction levels from application software to mixed hardware/software systems. A rigorous design flow that uses BIP as a unifying semantic model derives a correct implementation from an application software, a model of the target architecture, and a mapping. Implementation correctness is ensured by applying source-to-source transformations that preserve correctness of essential design properties. The design is fully automated and supported by a toolset including a compiler, the D-Finder verification tool, and model transformers. The authors present an autonomous robot case study to illustrate BIP's use as a modeling formalism as well as crucial aspects of the design flow for ensuring correctness. [ABSTRACT FROM AUTHOR]