Diagnosis of Multi-Robot Coordination Failures Using Distributed CSP Algorithms

Meir Kalech, Gal A. Kaminka, Amnon Meisels, Yehuda ElmaliachAAAI 2006

Abstract

Traditional multi-robot coordination failure diagnosis relies on centralized models, which are prone to single points of failure and high bandwidth requirements. This paper proposes a distributed approach by modeling robot interactions as a Distributed Constraint Satisfaction Problem (DisCSP). Through evaluations on physical robots and simulations, we demonstrate that Asynchronous Backtracking (ABT) provides a robust and efficient mechanism for self-diagnosis, outperforming common local search methods in both speed and reliability.

Introduction

In multi-robot systems, maintaining coordination is critical for mission success. A single robot failing to execute a command can jeopardize the entire team's objectives. Conventional diagnostic systems typically employ a centralized diagnoser. However, this architecture is fragile; if the central node fails or robots move out of communication range, the system loses its diagnostic capability. This research explores whether robots can autonomously diagnose coordination failures using only local communication and distributed algorithms.

Modeling Coordination as a Distributed CSP

The authors frame the coordination problem as a Distributed Constraint Satisfaction Problem (DisCSP). The team's desired behavior is represented by a constraint graph with two primary rule types:

  1. Concurrence (CCRN): Requirements for agents to perform specific actions simultaneously.
  2. Mutual-Exclusion (MUEX): Constraints preventing agents from performing conflicting actions together.

When coordination fails, the system state violates these constraints. The diagnostic goal is to identify a "minimal diagnosis"—the smallest set of robots whose state changes would restore system consistency. Four DisCSP algorithms were adapted for this task: Synchronous Backtracking (SBT) in both offline (SBT_OFF) and online (SBT_ON) modes, Asynchronous Backtracking (ABT), and Distributed Stochastic Search (DSA).

Experimental Methodology

The approach was validated using both physical and simulated environments:

  • Physical Implementation: A team of four Sony Aibo robots was tasked with a "space exploration" mission.
  • Simulation: The Player/Stage simulator enabled scaling the experiments to teams of 7 and 10 robots.
  • Failure Scenarios: Thirteen distinct failure cases were tested, ranging from simple sensor faults to complex multi-robot fault combinations.
Sony Aibo robots used in the physical experiments to test coordination failure diagnosis.

Key Results and Insights

The study revealed several critical advantages of backtracking algorithms in diagnostic contexts. While local search algorithms like DSA typically outperform backtracking in general DisCSP tasks, ABT proved superior for diagnosis. This is attributed to the "Close to Success" advantage: since robots are usually near a coordinated state before a failure, ABT can find a resolution in very few steps.

Efficiency and Scalability

Experimental data showed that ABT is significantly more efficient than the online version of SBT. As the number of agents increases, the communication overhead for SBT_ON grows exponentially, whereas ABT remains manageable.

Comparison of message counts across different algorithms and agent team sizes, highlighting ABT's efficiency.

Reliability

ABT consistently found a valid diagnosis whenever one existed. In contrast, DSA failed to find a diagnosis in 33% of cases and produced incorrect diagnoses at a much higher rate (46% compared to ABT’s 28%). While SBT_OFF was the fastest, its reliance on pre-computed solutions makes it unsuitable for dynamic environments where coordination rules may change.

Conclusion and Future Work

While ABT offers a robust distributed solution, several challenges remain. Currently, the "truth" of a diagnosis may only be known to a subset of agents, and robots may lack awareness of when the diagnostic process has fully terminated. Additionally, ABT finds a complete diagnosis but does not guarantee it is the minimal one. Future work will focus on ensuring team-wide consensus on diagnoses and refining algorithms to prioritize minimal explanations for failures.

Summary updated

BibTeX
@inproceedings{kalech2006diagnosis,
  author = {Meir Kalech and Gal A. Kaminka and Amnon Meisels and Yehuda Elmaliach},
  title = {{Diagnosis of Multi-Robot Coordination Failures Using Distributed CSP Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure