Distributed Constraint Optimization of Multi-Agent Systems

Abstract:

To coordinate effectively, multiple agents must reason and communicate about the interactions between their individual local decisions. Distributed planning, distributed scheduling, distributed resource allocation and distributed task allocation are some examples of multiagent problems where such reasoning is required. In order to represent these types of automated reasoning problems, researchers in Multiagent Systems have proposed distributed constraints as a key paradigm. Previous research in Artificial Intelligence and Constraint Programming has shown that constraints are a convenient yet powerful way to represent automated reasoning problems. This dissertation advances the state-of-the-art in Multiagent Systems and Constraint Programming through three key innovations. First, this dissertation introduces a novel algorithm for Distributed Constraint Optimization Problems (DCOP). DCOP significantly generalizes existing satisfaction-based constraint representations to allow optimization. We present Adopt, the first algorithm for DCOP that allows asynchronous concurrent execution and is guaranteed to terminate with the globally optimal solution. The key idea is to perform systematic distributed optimization based on conservative solution quality estimates rather than exact knowledge of global solution quality. This method is empirically shown to yield orders of magnitude speedups over existing synchronous methods and is shown to be robust to lost messages. Second, this dissertation introduces bounded-error approximation as a flexible method whereby agents can find global solutions that may not be optimal but are guaranteed to be within a given distance from optimal. This method is useful for time-limited domains because it decreases solution time and communication overhead. Bounded-error approximation is a significant departure from existing incomplete local methods, which rely exclusively on local information to obtain a decrease in solution time but at the cost of abandoning all theoretical guarantees on solution quality. Third, this dissertation presents generalized mapping strategies that allow a significant class of distributed resource allocation problem to be automatically represented via distributed constraints. These mapping strategies are signficant because they illustrate the utility of the distributed constraint representation. These mapping strategies are useful because they provide multiagent researchers with a general, reusable methodology for understanding, representing and solving their own distributed resource allocation problems. Our theoretical results show the correctness of the mappings.