Distributed Market-Based Algorithms for Multi-Agent Planning with Shared Resources
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Numerical Mathematics
- Operations Research