An official website of the United States government
This paper introduces inter-triggering hybrid automata, a formalism to represent multi-agent systems where each agent is represented as a hybrid automaton and agents interact by triggering discrete transitions (jumps and resets) on their “neighboring" agents. Using this formalism, we define responsibility-sensitive safety as respecting one another’s invariances while triggering jumps and resets. This allows us to make a formal connection between responsibility and robust controlled invariant sets for individual agents, therefore leading to a compositional verification framework for the safety of the overall multi-agent system. We discuss several advantages of this viewpoint and illustrate it on a highway driving example.
more »
« less
Compositional safety rules for inter-triggering hybrid automata
In this paper, we present a compositional condition for ensuring safety of a collection of interacting systems modeled by inter-triggering hybrid automata (ITHA). ITHA is a modeling formalism for representing multi-agent systems in which each agent is governed by individual dynamics but can also interact with other agents through triggering actions. These triggering actions result in a jump/reset in the state of other agents according to a global resolution function. A sufficient condition for safety of the collection, inspired by responsibility-sensitive safety, is developed in two parts: self-safety relating to the individual dynamics, and responsibility relating to the triggering actions. The condition relies on having an over-approximation method for the resolution function. We further show how such over-approximations can be obtained and improved via communication. We use two examples, a job scheduling task on parallel processors and a highway driving example, throughout the paper to illustrate the concepts. Finally, we provide a comprehensive evaluation on how the proposed condition can be leveraged for several multi-agent control and supervision examples.
more »
« less
- Award ID(s):
- 1918123
- PAR ID:
- 10296574
- Date Published:
- Journal Name:
- Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control
- Page Range / eLocation ID:
- 1 to 11
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Summary This paper introduces a new class of feedback‐based data‐driven extremum seeking algorithms for the solution of model‐free optimization problems in smooth continuous‐time dynamical systems. The novelty of the algorithms lies on the incorporation of memory to store recorded data that enables the use of information‐rich datasets during the optimization process, and allows to dispense with the time‐varying dither excitation signal needed by standard extremum seeking algorithms that rely on a persistence of excitation (PE) condition. The model‐free optimization dynamics are developed for single‐agent systems, as well as for multi‐agent systems with communication graphs that allow agents to share their state information while preserving the privacy of their individual data. In both cases, sufficient richness conditions on the recorded data, as well as suitable optimization dynamics modeled by ordinary differential equations are characterized in order to guarantee convergence to a neighborhood of the solution of the extremum seeking problems. The performance of the algorithms is illustrated via different numerical examples in the context of source‐seeking problems in multivehicle systems.more » « less
-
null (Ed.)Modeling is a significant piece of the puzzle in achieving safety certificates for distributed IoT and cyberphysical systems. From smart home devices to connected and autonomous vehicles, several modeling challenges like dynamic membership of participants and complex interaction patterns, span across application domains. Modeling multiple interacting vehicles can become unwieldy and impractical as vehicles change relative positions and lanes. In this paper, we present an egocentric abstraction for succinctly modeling local interactions among an arbitrary number of agents around an ego agent. These models abstract away the detailed behavior of the other agents and ignore present but physically distant agents. We show that this approach can capture interesting scenarios considered in the responsibility sensitive safety (RSS) framework for autonomous vehicles. As an illustration of how the framework can be useful for analysis, we prove safety of several highway driving scenarios using egocentric models. The proof technique also brings to the forefront the power of a classical verification approach, namely, inductive invariant assertions. We discuss possible generalizations of the analysis to other scenarios and applications.more » « less
-
Connected Autonomous Vehicles (CAVs) are expected to enable reliable and efficient transportation systems. Most motion planning algorithms for multi-agent systems are not completely safe because they implicitly assume that all vehicles/agents will execute the expected plan with a small error. This assumption, however, is hard to keep for CAVs since they may have to slow down (e.g., to yield to a jaywalker) or are forced to stop (e.g. break down), sometimes even without a notice. Responsibility-Sensitive Safety (RSS) defines a set of safety rules for each driving scenario to ensure that a vehicle will not cause an accident irrespective of other vehicles' behavior. RSS rules, however, are hard to evaluate for merge, intersection, and unstructured road scenarios. In addition, deadlock situations can happen that are not considered by the RSS. In this paper, we propose a generic version of RSS rules for CAVs that can be applied to any driving scenario. We integrate the proposed RSS rules with the CAV's motion planning algorithm to enable cooperative driving of CAVs. Our approach can also detect and resolve deadlocks in a decentralized manner. We have conducted experiments to verify that a CAV does not cause an accident no matter when other CAVs slow down or stop. We also showcase our deadlock detection and resolution mechanism. Finally, we compare the average velocity and fuel consumption of vehicles when they drive autonomously but not connected with the case that they are connected.more » « less
-
In this paper we develop a state transition function for partially observable multi-agent epistemic domains and implement it using Answer Set Programming (ASP). The transition function computes the next state upon an occurrence of a single action. Thus it can be used as a module in epistemic planners. Our transition function incorporates ontic, sensing and announcement actions and allows for arbitrary nested belief formulae and general common knowledge. A novel feature of our model is that upon an action occurrence, an observing agent corrects his (possibly wrong) initial beliefs about action precondition and his observability. By examples, we show that this step is necessary for robust state transition. We establish some properties of our state transition function regarding its soundness in updating beliefs of agents consistent with their observability.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3447928.3456659
