Learning to Coordinate without Sharing Information

Sandip Sen, Mahendra Sekaran, John HaleAAAI 1994

Introduction

This foundational 1994 paper from the AAAI proceedings explores how autonomous agents can achieve coordination without explicit communication or complex internal models of their peers. At the time, Distributed Artificial Intelligence (DAI) largely assumed that coordination required either message passing or pre-defined models of other agents' capabilities. This research challenges that assumption, demonstrating that global coordination can emerge from purely local, reinforcement-based learning.

Problem Statement

The authors identify three primary drawbacks to traditional communication-heavy coordination:

  1. Communication Overhead: Real-time messaging consumes significant time and bandwidth.
  2. System Fragility: Centralized or interdependent systems often collapse if a "key agent" fails.
  3. Trust Issues: In non-cooperative or competitive environments, shared information may be unreliable.

The central question is whether agents can learn to work together while remaining "blind" to each other, reacting only to environmental changes.

Methodology: The Block Pushing Task

The researchers utilized a Block Pushing Problem as a testbed. Two independent agents, $a_1$ and $a_2$, are tasked with moving a block along a specific 2D path toward a goal.

The block pushing task setup, showing the field of play, agents, and the ideal versus potential paths.

Technical Implementation

  • Q-Learning: Each agent employs the Watkins Q-learning algorithm, maintaining a policy matrix of states and actions updated via environmental rewards.
  • State and Action Space: The state is simplified to the block's lateral distance from the target path ($\Delta x$). Actions consist of choosing a force magnitude and one of 11 discretized angles.
  • Reward Function: Agents receive scalar feedback based on the block's proximity to the path after an action. Crucially, agents are unaware that another agent is contributing to the block's movement.
  • Exploration Strategy: Q-values are initialized to high positive numbers (optimistic initialization) to ensure agents explore a wide range of actions before converging on a policy.

Key Insights: Emergent Complementarity

The most significant finding is the emergence of functional complementarity. The agents do not learn identical behaviors; instead, they learn to compensate for one another. If Agent A's policy tends to push the block slightly off-course to the left, Agent B naturally learns a policy that pushes slightly to the right. Without any direct knowledge of each other, the agents evolve into a single functional unit.

Results and Analysis

The system demonstrated high reliability, with agents successfully reaching the goal in 100% of trials given sufficient state granularity. Convergence typically occurred between 115 and 800 trials.

Graphs showing the average distance from the optimal path over trials for different learning rates (beta) and the variation of steps to convergence.

A key technical contribution is the analysis of the learning rate ($\beta$). The authors derived a mathematical model to predict how $\beta$ influences convergence speed. As shown in the experimental data, higher learning rates generally lead to faster convergence, but the relationship is constrained by the granularity of the state space. Furthermore, the researchers demonstrated transfer learning: agents trained on one goal could adapt to a shifted goal with a 10% improvement in learning speed.

Limitations and Future Work

While successful, the approach has limitations:

  • Local Optima: The use of deterministic action selection often led to sub-optimal (though functional) policies.
  • Scalability and Complexity: The study focused on two agents in a simple environment. Future work is needed to assess performance in larger swarms or noisier, more complex environments.
  • Proposed Improvements: The authors suggest incorporating Boltzmann selection for better exploration and world models to improve predictive capabilities.

Summary updated

BibTeX
@inproceedings{sen1994learning,
  author = {Sandip Sen and Mahendra Sekaran and John Hale},
  title = {{Learning to Coordinate without Sharing Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure