Abstract
This paper provides a comprehensive 20-year retrospective on Model-Based Diagnosis (MBD) specifically tailored for Multi-Agent Systems (MAS). It introduces a taxonomy to classify diagnostic algorithms based on their objectives (planning vs. coordination), architecture (centralized vs. distributed), and temporal nature. The survey highlights critical open challenges, including privacy concerns and the integration of machine learning into diagnostic frameworks.
Introduction
As Multi-Agent Systems (MAS)—such as autonomous warehouse robots, drone swarms, and self-driving car networks—become increasingly prevalent, the complexity of identifying failures grows exponentially. Determining the root cause of a system-wide halt—whether it stems from a hardware fault, a coordination disagreement, or a temporal ripple effect—requires sophisticated diagnostic tools.
Standard Model-Based Diagnosis (MBD) operates by comparing a "digital twin" or model of a system against real-world observations. If the two disagree, the algorithm deduces which components are likely failing. However, MAS present unique hurdles: they are massive, dynamic, often partially observable, and involve "social" interactions between agents that traditional MBD wasn't designed to handle. This survey explores how researchers have adapted MBD to meet these multi-agent challenges.
Methods
The authors categorize two decades of research using three primary attributes of MAS diagnosis:
- Objective (Plan vs. Coordination):
- Plan-Related Faults: Focus on identifying faulty execution steps, such as an agent failing to reach a destination.
- Coordination-Related Faults: Focus on "social diagnosis"—identifying why agents disagree on joint tasks or fail to maintain consistent interactions (e.g., communication breakdowns).
- Architecture (Centralized vs. Distributed):
- Centralized: A single "omniscient" diagnoser observes the entire system.
- Distributed: Each agent possesses a partial model and communicates with others to reach a global consensus on failures.
- Temporal vs. Non-Temporal:
- This attribute distinguishes whether an algorithm analyzes a single snapshot in time or a sequence of events to trace how a fault propagates over time.
The paper also reviews specific algorithmic approaches, such as representing coordination as a Constraint Satisfaction Problem (CSP) or using SAT solvers to assign "health values" to agents based on observed resource usage.
Key Insights
- Social Diagnosis: A significant shift in MAS diagnosis is moving from diagnosing individual components to diagnosing relationships. A system can fail even if every individual agent is "healthy" if their coordination logic is inconsistent.
- Scalability through Distribution: Centralized diagnosers represent single points of failure and lack scalability. There is a clear trend toward distributed diagnosis, where agents perform local diagnosis and merge findings, which is more robust but introduces communication overhead.
- Temporal Propagation: Faults in MAS are rarely static. A minor delay by one agent can propagate through a Multi-Agent Plan (MAP), making root cause isolation difficult without temporal reasoning.
- Model-Free vs. Model-Based: While focusing on MBD, the paper notes "Spectrum-based Fault Localization," which tracks agent participation in successful vs. failed tasks to build models on the fly for complex systems where a full model is hard to define.
Results
The primary result of this survey is a taxonomy that maps the landscape of MAS diagnosis research.
The analysis reveals that plan-related diagnosis is predominantly temporal and often distributed. In contrast, coordination-related diagnosis has historically been more centralized and non-temporal, though recent work (e.g., Natan and Kalech 2020) is pushing into distributed, temporal territory. A significant gap identified is the lack of research combining MBD with Machine Learning for MAS diagnosis, despite the explosion of ML in other diagnostic fields.
Conclusion and Future Work
The survey identifies several "frontier" problems that remain unsolved:
- Privacy: In competitive environments, agents may be reluctant to share internal states, complicating global diagnosis.
- Uncertain/Noisy Observations: Developing algorithms that can handle imperfect sensor data is a major hurdle.
- Online Replanning: Diagnosis must be coupled with automatic "re-planning" once a failure is identified.
- Intermittent Faults: Current models struggle with agents that fail inconsistently rather than being strictly "broken" or "healthy."
Summary updated