Abstract
In large-scale multiagent systems, such as autonomous warehouse robots, coordinating actions without overwhelming communication channels is a critical challenge. This paper introduces a hierarchical protocol that enables agents to coordinate by exchanging "behavior abstractions" rather than exhaustive plans. By iteratively refining these abstractions only when potential conflicts are detected, agents can efficiently identify relevant peers and resolve interactions. Experimental results using the MICE testbed demonstrate that this approach effectively balances communication costs with plan quality, particularly in environments where computational resources are constrained.
Introduction
As autonomous systems become more prevalent, the need for efficient coordination among numerous active agents grows. Traditional coordination methods often require agents to broadcast detailed plans to all others, leading to "swamped" communication lines and excessive CPU usage for analyzing irrelevant data. The central problem addressed here is how agents can identify and resolve potential interferences without sharing every detail of their intended actions. This paper proposes a decentralized, flexible protocol that allows agents to "feel each other out" at varying levels of abstraction.
Methodology: The Behavior Hierarchy
The core of the proposed protocol is the Behavior Hierarchy, a multi-dimensional representation that extends beyond simple goal or plan structures. A behavior is defined across six key dimensions: Who, What, When, Where, How, and Why.
The coordination protocol follows an iterative "dialogue" process:
- Abstract Broadcast: Each agent initially broadcasts its most abstract behavior (e.g., "Robot A is cleaning Floor 1 today").
- Conflict Detection: Agents map received abstractions into their own spatial and temporal contexts. If behaviors overlap or are proximal, a potential interaction is flagged.
- Refinement or Modification: Upon detecting a potential conflict, an agent can either modify its behavior (e.g., changing the time or location) or refine it by moving down a level in the hierarchy to exchange more specific details (e.g., specifying a particular wing and time slot).
- Convergence: The process continues until all conflicts are resolved or proven non-existent through detailed inspection.
Experimental Evaluation
The protocol was evaluated using the Michigan Intelligent Coordination Experiment (MICE) testbed. The researchers simulated environments with varying numbers of robots and spatial constraints to test the protocol's robustness.
Two primary environments were used:
- Environment A: Two robots in two rooms connected by two narrow doorways.
- Environment B: Three robots in two rooms connected by a single narrow doorway.
Key Results and Insights
The study conducted 36 experiments, varying the environment, the level of resolution (Abstract, Intermediate, Detailed), and the computational cost.
- Collision Avoidance: The protocol successfully prevented collisions that occurred perpetually in simulations without coordination.
- Efficiency vs. Overhead: A clear trade-off exists between communication cost and plan quality. Abstract resolution proved superior when computation was "expensive," as it reached "good enough" solutions quickly. Conversely, detailed resolution was more effective when computation was "cheap," allowing for higher parallelism (e.g., robots passing closely) that outweighed negotiation time.
- Spatial vs. Temporal Resolution: Resolving conflicts by altering spatial paths (where) was generally more efficient than temporal serialization (waiting), as it avoided creating bottlenecks.
- Organizational Mapping: The dimensions of the behavior hierarchy (Who, What, How) align with human organizational structures, such as personnel, product, and functional hierarchies, suggesting a natural framework for multiagent systems.
Conclusion and Future Work
The hierarchical protocol provides a scalable way for agents to coordinate by focusing communication on potential conflicts. While effective, the current implementation relies on a fixed "pecking order" for conflict resolution. Future work should explore more flexible negotiation strategies, handle dynamic agent entry and exit, and investigate multi-dimensional trade-offs during the refinement process.
Summary updated