Distributed misbehavior monitors for socially organized autonomous systems

In systems in which many heterogeneous agents operate autonomously, with competing goals and without a centralized planner or global information repository, safety and performance can only be guaranteed by "social" rules imposed on the behavior of individual agents. Social laws are structured in a way that they can be verified just by using local information made available to an agent by a small number of its neighbors. Automobile mobility with traffic rules and logistics robots in warehouses are canonical examples of such "regulated autonomy", but many other fairly-competing autonomous systems are to be expected shortly. In these systems, detecting whether an agent is not abiding by the rules is crucial for raising an alert and taking appropriate countermeasures. However, the limited visibility due to the local nature of the information makes the problem of misbehavior detection hard for any single agent, and only an exchange of information between agents can provide sufficient clues to arrive at a decision. This paper attacks the misbehavior detection problem for a class of socially organized autonomous systems, where the behavior of agents depends on the presence or absence of other neighbors. We propose a solution involving a "local monitor", which runs on each agent and includes a hybrid observer and a set-valued consensus node. Based on whatever visibility is available, it reconstructs a set-valued occupancy estimate of nearby regions and combines it with communicating neighbors to reach a shared view and a mismatch discovery. We provide a formal framework for describing social rules that unify many different applications and a tool to generate code automatically for local monitors. The technique is demonstrated in various systems, including self-driving cars, autonomous forklifts, and distributed power plants.