Abstract
This paper introduces two reinforcement learning algorithms, ACE (Action Estimation) and AGE (Action Group Estimation), designed to facilitate coordination among reactive agents in Multi-Agent Systems (MAS). By adapting the "bucket brigade" learning model, the research demonstrates how agents can overcome conflicting goals and limited local visibility to solve complex tasks. Experimental results in a Blocks World environment show that while both methods outperform random baselines, the synergistic approach of AGE significantly improves performance by accounting for the context of concurrent actions.
Introduction
In the early development of Multi-Agent Systems, achieving effective coordination without centralized control was a primary hurdle. Agents in these systems typically face two significant challenges:
- The Incompatibility Constraint: Multiple agents may attempt actions that physically conflict, such as two robots trying to manipulate the same object simultaneously.
- The Local Information Constraint: Agents often have a restricted view of their environment. This partial visibility can lead to the "Sussman anomaly," where an agent cannot distinguish between states where an action is helpful versus when it is redundant or harmful.
Gerhard Weiß addresses these issues by investigating how agents can collectively learn which actions to perform through a decentralized reinforcement mechanism.
Methods: ACE and AGE
The paper proposes two algorithms based on an action-oriented version of the bucket brigade learning model, originally developed for classifier systems. In this framework, agents "bid" for the right to execute actions based on their estimated value.
- ACE (Action Estimation): This individualistic approach has each agent estimate the "goal relevance" of its own possible actions. The highest bidders execute their actions, provided they do not conflict with other winning bids.
- AGE (Action Group Estimation): This synergistic approach estimates the relevance of sets of concurrent actions (activity contexts). This accounts for the fact that an action's value often depends on what other agents are doing at the same time.
Credit Assignment: Both algorithms use a reinforcement mechanism where a reward is paid out upon task completion. In a "bucket brigade" fashion, agents that acted in the final step pay a portion of their reward to those that acted in the previous step. This creates a chain of value that reinforces the entire sequence of coordinated actions leading to the goal.
Experimental Setup: The Blocks World
The algorithms were benchmarked using a simulated Blocks World environment.
The setup involved five agents ($A_1$ through $A_5$), each with specialized capabilities (e.g., Agent 1 can only move block A). The task was to transform a specific "Start Configuration" into a "Goal Configuration" within a strict limit of four cycles. To simulate realistic constraints, agents had limited sensors; for example, Agent 1 only perceived information directly related to block A.
Results and Key Insights
The primary insight from the experiments is that context is king. An action's value is frequently dependent on the simultaneous moves of other agents. This is why AGE, which evaluates groups of actions, consistently outperformed the individualistic ACE.
Key results include:
- Learning Curve: Both ACE and AGE reached their maximum performance level after approximately 250 trials.
- Performance Gap: AGE achieved a significantly higher reward rate (approx. 800/1000) compared to ACE (approx. 600/1000).
- Stability: Once the agents learned a successful sequence, performance remained stable, proving the bucket brigade effectively "locks in" coordinated behaviors.
However, neither algorithm reached the theoretical maximum reward of 1000. This ceiling is attributed to the local information constraint; without broader sensors or communication, agents eventually hit a functional limit due to state ambiguity.
Discussion and Future Work
While AGE is more effective, it is computationally more expensive, as its cost scales combinatorially with the number of agents. Future research directions suggested by the author include moving beyond simple reactive agents toward those capable of reasoning about others' intentions or using internal memory to overcome partial visibility. Additionally, hierarchical organization is proposed as a potential solution for managing more complex multi-agent societies.
Summary updated