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.