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:
- 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.
- 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.
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.
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