Multi-Robot Task Allocation Using Global Games with Negative Feedback: The Colony Maintenance Problem

Logan E. BeaverAAAI 2025 · DOI

Abstract

This paper presents a decentralized multi-robot task allocation (MRTA) framework based on Global Games modified with negative feedback. Traditional global games often rely on positive feedback, which can lead to catastrophic system failure if a subset of robots is removed. By implementing a utility function where tasks become less attractive as more robots participate, the system achieves natural self-regulation and resilience. Simulations of a "Colony Maintenance Problem" demonstrate that the system can maintain energy levels even after a 50% reduction in the robot workforce, while maintaining a computational efficiency of $O(N)$.

Introduction

Multi-Robot Task Allocation (MRTA) is a fundamental challenge in robotics, particularly for autonomous colonies that must forage for resources to maintain a central base. Traditional solutions typically fall into two categories: centralized optimization and consensus-based communication. Centralized methods are computationally intensive and represent a single point of failure, while consensus-based methods require significant communication bandwidth.

A more elegant alternative is the Global Game, where robots observe a global signal (such as colony energy levels) to make independent decisions. However, existing global game models often utilize positive feedback—where a task becomes more attractive as more robots join. This creates a brittle system: if several robots are removed, the "social proof" for the task vanishes, potentially causing the remaining robots to abandon the task and leading to system collapse.

Methodology

The proposed framework addresses these vulnerabilities by introducing negative feedback into the global game structure for the "Colony Maintenance Problem."

The Utility Function and Negative Feedback

Each robot calculates its utility for foraging, $\pi(n, \theta)$, based on the colony's energy urgency ($\theta$) and the number of robots currently foraging ($n$). Unlike positive-feedback models, the utility here decreases as $n$ increases. This ensures that robots only volunteer for a task if there is a genuine vacancy, preventing over-allocation and creating a self-regulating equilibrium.

The utility function $\pi(n, \theta)$ showing how the decision space changes as the number of foragers ($n$) increases.

Mixed Nash Equilibrium and Hysteresis

Robots employ a probabilistic strategy to reach a stable Mixed Nash Equilibrium. Instead of a binary threshold, they calculate a probability of foraging that stabilizes the expected number of workers. To prevent "chattering" (rapid switching between states), a hysteresis rule is implemented: once a robot commits to foraging, it must complete its cycle before reconsidering its strategy. Low-level safety and collision avoidance are managed via Linear Control Barrier Functions (CBFs), ensuring high-level decision-making remains decoupled from physical navigation.

Key Results

The system was evaluated in a MATLAB simulation featuring 12 robots and 6 energy sources. The primary objective was to maintain the "Nest Energy" above critical levels.

Resilience and Adaptation

A critical test of the system occurred at $t=900$ seconds, when 6 of the 12 robots were abruptly removed from the simulation. Because of the negative feedback loop, the marginal utility for the remaining idle robots immediately increased as $n$ dropped. The remaining robots automatically increased their foraging frequency to compensate for the loss.

Energy levels over time, demonstrating the system's ability to maintain nest energy after losing 50% of the workforce at $t=900$s.

As shown in the results, the system successfully maintained energy levels despite the 50% reduction in workforce. Furthermore, the reduction in robot density actually improved individual efficiency by reducing physical congestion around the central charging hub.

Discussion and Future Work

The negative feedback approach provides a robust, $O(N)$ linear-time solution for MRTA that is naturally resilient to external interference. By making tasks less attractive as they become crowded, the system avoids the "all-or-nothing" failures typical of positive-feedback systems.

Future research will focus on automating the tuning of utility function parameters (currently hand-tuned) using machine learning. Additionally, the model could be expanded to handle multiple global signals for colonies with competing needs, such as simultaneous repair, defense, and foraging tasks. Exploring the parallels between this mathematical framework and biological systems, such as honeybee site selection, remains a promising avenue for decentralized logic design.

Summary updated

BibTeX
@inproceedings{beaver2025multi,
  author = {Logan E. Beaver},
  title = {{Multi-Robot Task Allocation Using Global Games with Negative Feedback: The Colony Maintenance Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33485},
}
Figure