Diagnosing resource usage failures in multi-agent systems

In the not-so-far future, autonomous vehicles will be ubiquitous and, consequently, need to be coordinated to avoid traffic jams and car accidents. A failure in one or more autonomous vehicles may break this coordination, resulting in reduced efficiency (due to traffic load) or even bodily harm (due to accidents). The challenge we address in this paper is to identify the root cause of such failures. Identifying the faulty vehicles in such cases is crucial in order to know which vehicles to repair to avoid future failures as well as for determining accountability (e.g., for legal purposes). More generally, this paper discusses multi-agent systems (MAS) in which the agents use a shared pool of resources and they coordinate to avoid resource contention by agreeing on a temporal resource allocation. The problem we address, called the Temporal Multi-Agent Resource Allocation (TMARA) diagnosis problem (TMARA-Diag), is to find the root cause of failures in such MAS that are caused by malfunctioning agents that use resources not allocated to them. As in the autonomous vehicles example, such failures may cause the MAS to perform suboptimally or even fail, potentially causing a chain reaction of failures, and we aim to identify the root cause of such failures, i.e., which agents did not follow the planned resource allocation. We show how to formalize TMARA-Diag as a model-based diagnosis problem and how to compile it to a set of logical constraints that can be compiled to Boolean satisfiability (SAT) and solved efficiently with modern SAT solvers. Importantly, the proposed solution does not require the agents to share their actual plans, only the agreed upon temporal resource allocation and the resources used at the time of failure. Such solutions are key in the development and success of intelligent, large, and security-aware MAS.