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.
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.
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