Optimal Distributed Market-Based Planning for Multi-Agent Systems with Shared Resources

Sue Ann Hong, Geoffrey J. GordonAISTATS 2011 · OpenReview

Abstract

Collaborative multi-agent systems require efficient planning for shared, scarce resources. While market-based algorithms are popular, they often lack optimality guarantees and require manual price tuning. This paper presents a "price-and-cut" (PC) algorithm that leverages Dantzig-Wolfe decomposition and Gomory cuts to provide a distributed, optimal framework for complex planning tasks. Evaluation on large-scale SAT problems and UAV task allocation demonstrates that the proposed method significantly outperforms centralized industrial solvers.

Introduction

In multi-agent environments, such as robotic fleets, agents must coordinate to utilize shared resources effectively. Centralized planning for such systems is computationally prohibitive as complexity scales exponentially with the number of agents. Market-based approaches, where agents bid on resources, offer a decentralized alternative but typically suffer from three limitations: the need for expert-tuned pricing heuristics, a lack of optimality guarantees, and difficulty handling coupling constraints like collision avoidance.

Methodology: The Price-and-Cut Algorithm

The authors formulate the multi-agent planning problem as a Mixed Integer Linear Program (MILP). To solve this optimally in a distributed manner, they introduce the Price-and-Cut algorithm, which combines two fundamental optimization techniques:

  1. Dantzig-Wolfe (D-W) Decomposition: This decomposes the global problem into a "Master Program" (acting as an auctioneer) and several "Subproblems" (representing individual agents). The Master Program sets prices for shared resources based on aggregate demand, and agents optimize their local plans accordingly.
  2. Gomory Cuts: While D-W decomposition is effective for continuous variables, planning often involves discrete decisions. The authors incorporate Gomory cuts—mathematical constraints added to the Master Program—to eliminate fractional solutions and ensure integer optimality.

A significant conceptual innovation is the interpretation of these cuts as "derivative resources." These represent specific combinations of actions or resource usages that require unique pricing to resolve conflicts, effectively automating the market design process.

Experimental Evaluation

The algorithm was tested on two distinct domains:

  • Factored 3SAT Problems: A set of 4,713 randomly generated problems with 2–10 subproblems and up to 900 clauses, designed to challenge general-purpose solvers.
  • Multi-UAV Task Allocation: A simulation involving three Unmanned Aerial Vehicles (UAVs) navigating a map to visit targets while avoiding collisions.
UAV task allocation scenario and performance comparison on the benchmark map.

Results and Discussion

The Price-and-Cut algorithm demonstrated substantial performance gains over the industry-standard CPLEX solver.

Computational Efficiency

The centralized PC algorithm outperformed CPLEX on 92.38% of instances that required more than one second to solve. The distributed version (DPC) further improved these results, outperforming the centralized version in 96.12% of cases. This suggests that the benefits of parallelizing subproblem solving significantly outweigh the communication overhead between agents and the auctioneer.

Performance metrics across SAT instances, showing iteration counts and runtime comparisons between PC, DPC, and CPLEX.

Domain-Specific Performance

In the UAV task allocation benchmark, the PC algorithm reached the optimal solution in 31 seconds, compared to 166 seconds for CPLEX. Furthermore, the "market" stabilized rapidly; most problems achieved optimality in fewer than 10 iterations, as shown in the iteration distribution.

Conclusion and Future Work

The Price-and-Cut framework provides a principled, automated, and optimal approach to distributed multi-agent planning. By interpreting mathematical cuts as resource prices, it bridges the gap between formal optimization and market-based heuristics. Future research will focus on extending the framework to handle stochastic environments, decentralizing the auctioneer role, and exploring the impact of using approximate local solvers for increased speed.

Summary updated

BibTeX
@inproceedings{hong2011optimal,
  author = {Sue Ann Hong and Geoffrey J. Gordon},
  title = {{Optimal Distributed Market-Based Planning for Multi-Agent Systems with Shared Resources}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=xQstr3hKPU},
}
Figure