| The Distributed Constraint Optimization Problem (DCOP) framework is a recent approach to coordination, reasoning, and teamwork within a multi-agent system (MAS). DCOP extends from the traditional AI approach of constraint satisfaction. DCOP supports aspects of privacy, autonomy, robustness, and distribution of computation and observation for MAS that are unavailable in centralized solutions. Recently several algorithms have been proposed to solve general DCOPs, generating both complete, optimal solutions (ADOPT, DPOP) and approximate solutions (DBA, DSA, and LS-DPOP). In addition, many problem domains have been mapped into the DCOP formalization, including distributed sensor networks, resource allocation/scheduling, plan coordination, and joint policy coordination. Unfortunately, the complexity of current DCOP algorithms severely limits their applicability to interesting, large-scale problems. In addition, many real-world problems cannot be represented under the current DCOP model because it requires deterministic constraint outcomes.;This dissertation work improves and extends the DCOP framework for complex MAS domains. This work contributes to three main areas: scalable DCOP for large problems, uncertainty reasoning using DCOP, and application of DCOP to real-world problems. This work contributes new algorithms, new problem domain mappings, new representation models, novel integrated solutions to real-world problems, as well as challenges for future applications of MAS coordination techniques. |
