Distributed Market-Based Algorithms for Multi-Agent Planning with Shared Resources
Abstract
We propose a new family of market-based distributed planning algorithms for collaborative multi-agent systems with complex shared constraints. Such constraints tightly couple the agents together, and appear in problems ranging from task or resource allocation to collision avoidance. While it is not immediately obvious, a wide variety of constraints can be reduced to generalized resource allocation problems; the translation is straightforward for task or resource allocation problems, and for general problems any shared constraint between agents can be considered a resource. Market-based algorithms have become popular in collaborative multi-agent planning due to their intuitive and simple distributed paradigm as well as their success in domains such as robotics and software agent systems. However, they suffer from several drawbacks: (1) it is an art to create a reasonable pricing in each domain, requiring a human designer and parameter tuning; (2) they rarely guarantee optimality; (3) they do not often have a natural way to incorporate uncertainty in planning; and (4) most existing algorithms require a central trusted auctioneer. This thesis addresses these drawbacks by providing mechanisms that automatically and optimally price the resources. It also provides simple, optimal bidding strategies for the agents. We consider three different settings and give algorithms for each that compute resource prices automatically, and do so to guarantee (near-)optimality. First, we formalize factored mixed integer linear programs (MILPs), and give a novel distributed optimization algorithm by combining Dantzig-Wolfe decomposition with a cutting-plane algorithm. Second, we relax the framework with Lagrangian relaxation for more efficient, convex optimization. Finally, we study planning under uncertainty in the Lagrangian relaxation framework via stochastic programming, and give efficient algorithms for representing and optimizing uncertainty in factored Markov decision processes.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 2013
- Accession Number
- ADA582823
Entities
People
- Sue A. Hong
Organizations
- Carnegie Mellon University