Auction Mechanism Design for Multi-Robot Coordination

Curt A. Bererton, Geoffrey J. Gordon, Sebastian ThrunNeurIPS 2003 · OpenReview

Overview

This paper introduces a decentralized algorithm that automatically designs a market architecture to coordinate multi-robot systems. By decomposing complex, "loosely coupled" Markov Decision Processes (MDPs) into individual robot tasks linked by resource "prices," the authors achieve the coordination quality of a centralized planner with the scalability of a decentralized system.

The Curse of Dimensionality in Multi-Robot Planning

Planning for multiple robots is notoriously difficult due to the curse of dimensionality. While we can model a single robot’s decisions using a Markov Decision Process (MDP), scaling this to $N$ robots causes the state and action spaces to explode exponentially. A joint MDP for a fleet of robots quickly becomes mathematically intractable.

Existing solutions usually fall into two camps:

  1. Centralized MDPs: Theoretically optimal but computationally impossible for more than a few robots.
  2. Market Architectures: Heuristic-based systems where robots "bid" on tasks. These are scalable and intuitive but often lack a formal connection to optimal planning theory.

The authors aim to bridge this gap by creating a mathematically rigorous way to decompose a large multi-robot MDP into smaller, manageable pieces that can be solved independently while still accounting for robot interactions.

Methods: From Global Planning to Distributed Auctions

The core of the paper is a technique to turn a global planning problem into a distributed auction.

  • Loosely Coupled MDPs: The authors define a class of problems where robots mostly act independently but interact through "fictitious resources." These resources can be physical (like fuel) or logical (like the right to occupy a specific square or the right to be towed).
  • Constraint Relaxation: The key "trick" is relaxing the resource constraints. Instead of requiring resources to balance perfectly at every single millisecond, the algorithm requires them to balance in expectation over time.
  • Dantzig-Wolfe Decomposition: This mathematical engine splits the global Linear Program (LP) into two parts:
  • A Master Agent: Sets "prices" for resources based on global supply and demand.
  • Slave Agents (Robots): Each robot runs its own local MDP planner, treating the prices as costs or rewards.
  • Iterative Auction: The master agent suggests prices, robots submit their preferred plans (expected resource usage), and the master adjusts prices until the system converges to a consistent global policy.

Simulations

The paper evaluates the algorithm using three custom simulation environments rather than standard static datasets:

  1. Multi-Robot Towing: A 300x300 grid where robots can break down and must be towed to a repair zone by teammates.
  2. Path Planning with Fuel Constraints: A synthetic maze where 15 robots must reach 10 goals while minimizing a quadratic penalty on total fuel (path length).
Path planning maze environment
  1. Multi-Robot Paintball: A complex tactical simulator where teams coordinate attacks and repairs.

Key Insights and Results

  • Prices as Dual Variables: The authors show that the "prices" in their market are actually the dual variables of the resource constraints in the global optimization problem. This provides a formal economic justification for using auctions in robotics.
  • Automatic Mechanism Design: Unlike traditional market-based robotics where humans decide what to bid on, this algorithm automatically determines what the resources are and how they should be priced based on the underlying MDP physics.
  • Convergence: In the fuel-constrained path planning task, the decentralized auction rapidly converged to the optimal policy, successfully trading off goal quality against distance.
Auction convergence over iterations
  • Tactical Superiority: In the paintball simulation, the coordinated planner (using the auction mechanism) won 48 out of 50 games against a standard "attack nearest enemy" baseline. An uncoordinated version of the same planner only won 42 out of 50.
  • Scalability: The system successfully coordinated 9 robots in a large grid environment, a task that would be computationally impossible for a standard joint MDP.

Limitations and Future Work

  • Overoptimism: Because the constraints only hold "in expectation," the robots can occasionally be overoptimistic. For example, two robots might both plan to be towed by each other at the same time because, on average, the "towing resource" balances out.
  • Hand-Specified Policies: In the paintball example, the underlying robot behaviors (like "attack" or "tow") were hand-specified. The authors suggest that future work should involve using policy search methods to learn these base behaviors automatically.
  • Communication Overhead: While the computation is decentralized, the Dantzig-Wolfe decomposition requires iterative communication between the master and the robots, which might be a bottleneck in high-latency environments.

Summary updated

Abstract

The design of cooperative multi-robot systems is a highly active research area in robotics. Two lines of research in particular have generated inter- est: the solution of large, weakly coupled MDPs, and the design and im- plementation of market architectures. We propose a new algorithm which joins together these two lines of research. For a class of coupled MDPs, our algorithm automatically designs a market architecture which causes a decentralized multi-robot system to converge to a consistent policy. We can show that this policy is the same as the one which would be produced by a particular centralized planning algorithm. We demonstrate the new algorithm on three simulation examples: multi-robot towing, multi-robot path planning with a limited fuel resource, and coordinating behaviors in a game of paint ball.
BibTeX
@inproceedings{bererton2003auction,
  author = {Curt A. Bererton and Geoffrey J. Gordon and Sebastian Thrun},
  title = {{Auction Mechanism Design for Multi-Robot Coordination}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2003},
  url = {https://openreview.net/forum?id=H1Nj-OZObB},
}
Figure