1. Inicio
  2. Atrás
L
Título: Solving Multiagent Networks using Distributed Constraint Optimization
Autores: Pearce, Jonathan P.; JP Morgan Chase
Tambe, Milind; University of Southern California
Maheswaran, Rajiv; University of Southern California
Fecha: 2008-09-15
Publicador: Association for the Advancement of Artificial Intelligence
Fuente: Ver documento
Tipo: info:eu-repo/semantics/article
Peer-Reviewed Article
info:eu-repo/semantics/publishedVersion
Tema: Computer Science
7.1 Multi-Agent Systems; 15.2 Constraint Satisfaction
Descripción: In many cooperative multiagent domains, the effect of local interactions between agents can be compactly represented as a network structure. Given that agents are spread across such a network, agents directly interact only with a small group of neighbors. A distributed constraint optimization problem (DCOP) is a useful framework to reason about such networks of agents. Given agents’ inability to communicate and collaborate in large groups in such networks, we focus on an approach called k-optimality for solving DCOPs. In this approach, agents form groups of one or more agents until no group of k or fewer agents can possibly improve the DCOP solution; we define this type of local optimum, and any algorithm guaranteed to reach such a local optimum, as k-optimal. The article provides an overview of three key results related to koptimality. The first set of results gives worst-case guarantees on the solution quality of k-optima in a DCOP. These guarantees can help determine an appropriate k-optimal algorithm, or possibly an appropriate constraint graph structure, for agents to use in situations where the cost of coordination between agents must be weighed against the quality of the solution reached. The second set of results gives upper bounds on the number of k-optima that can exist in a DCOP. These results are useful in domains where a DCOP must generate a set of solutions rather than a single solution. Finally, we sketch algorithms for k-optimality and provide some experimental results for 1-, 2- and 3-optimal algorithms for several types of DCOPs.
Idioma: Inglés