Multi-Agent Coordination: DCOPs and Beyond
Publication Type:
Conference PaperSource:
Twenty-Second International Joint Conference on Artificial Intelligence, AAAI Press, Volume 3, Barcelona, p.2838-2839 (2011)ISBN:
978-1-57735-515-1URL:
http://ijcai.org/papers11/contents.phpAbstract:
Distributed constraint optimization problems (DCOPs) are a model for representing multi-agent systems in which agents cooperate to optimize a global objective. The DCOP model has two main advantages: it can represent a wide range of problem domains, and it supports the development of generic algorithms to solve them. Firstly, this paper presents some advances in both complete and approximate DCOP algorithms. Secondly, it explains that the DCOP model makes a number of unrealistic assumptions that severely limit its range of application. Finally, it points out hints on how to tackle such limitations.
Improving function filtering for computationally demanding DCOPs
Publication Type:
Conference PaperSource:
Workshop on Distributed Constraint Reasoning at IJCAI 2011, Barcelona, p.99-111 (2011)Abstract:
In this paper we focus on solving DCOPs in computationally demanding scenarios. GDL optimally solves DCOPs, but requires exponentially large cost functions, being impractical in such settings. Function filtering is a technique that reduces the size of cost functions. We improve the effectiveness of function filtering to reduce the amount of resources required to optimally solve DCOPs. As a result, we enlarge the range of problems solvable by algorithms employing function filtering.
Divide-and-Coordinate by Egalitarian Utilities: turning DCOPs into egalitarian worlds
Egalitarian Utilities Divide-and-Coordinate: Stop arguing about decisions, let's share rewards!
Divide and Coordinate: solving DCOPs by agreement
Publication Type:
Conference PaperSource:
Proc. of the 9th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'10), IFAAMAS, Canada, p.149-156 (2010)Keywords:
DCOP; Multi-agent Optimization; Divide and Coordinate; DaCSA; approximate algorithms; boundsAbstract:
In this paper we investigate an approach to provide approximate, anytime algorithms for DCOPs that can provide quality guaran- tees. At this aim, we propose the divide-and-coordinate (DaC) ap- proach. Such approach amounts to solving a DCOP by iterating (1) a divide stage in which agents divide the DCOP into a set of simpler local subproblems and solve them; and (2) a coordinate stage in which agents exchange local information that brings them closer to an agreement. Next, we formulate a novel algorithm, the Divide and Coordinate Subgradient Algorithm (DaCSA), a computational realization of DaC based on Lagrangian decompositions and the dual subgradient method. By relying on the DaC approach, DaCSA provides bounded approximate solutions. We empirically evaluate DaCSA showing that it is competitive with other state-of- the-art DCOP approximate algorithms and can eventually outperform them while providing useful quality guarantees.
Constructing a unifying theory of dynamic programming DCOP algorithms via the Generalized Distributive Law
