Sue Ann Hong

Distributed Market-Based Algorithms for Multi-Agent Planning with Shared Resources Degree Type: Ph.D. in Computer Science
Advisor(s): Geoffrey Gordon
Graduated: May 2013

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 in fact 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. For example, satisfying collision-avoidance constraints is equivalent to assigning to a limited number of agents the right to claim a particular space at a particular time.

Market-based algorithms have become popular in collaborative multi-agent planning, particularly for task allocation, 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 main drawbacks: 1. it is somewhat of 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 presents a solution to address the drawbacks by providing mechanisms that automatically and optimally price the resources as well as simple, optimal bidding strategies for the agents.

We formulate multi-agent planning as factored mathematical programs that are optimized in a distributed fashion. Like other market-based planning algorithms, our methods allow for the optimization of each agent's local planning problem at the agent with limited communication; however, they are able to deal with more complex constraints than those usually used in market-based planning settings. 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, a distributed method for optimizing linear programs, with a cutting-plane algorithm. Second, we relax the framework with Lagrangian relaxation, for more efficient, convex optimization. Lagrangian relaxation yields an approximation to the original MILP, but we give a simple yet effective randomized rounding algorithm whose chance of failure can be bounded, and the result is a near-optimal approximation algorithm for problems with a very large number of agents contending for the resources. 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.

We evaluate our algorithms on domains ranging from task allocation and path planning to supply chain management, and demonstrate the power of wielding complex shared constraints in distributed planning, which we hope will continue to be studied in a wide range of domains.

Thesis Committee:
Geoffrey J. Gordon (Chair)
M. Bernardine Dias
Carlos Guestrin
Jeff Schneider
Amy Greenwald (Brown University)

Frank Pfenning, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Distributed multi-agent planning, planning under uncertainty, distributed optimization, Lagrangian relaxation, stochastic programming, traffic management, supply-chain management