University of Illinois Urbana-Champaign

A Unified Framework for Multi-Agent Agreement

Lakkaraju, Kiran; Gasser, Les

Content Files
A Unified Framework for Multi-Agent Agreement.pdf

Permalink

https://hdl.handle.net/2142/11280

Description

Title
A Unified Framework for Multi-Agent Agreement
Author(s)
  • Lakkaraju, Kiran
  • Gasser, Les
Issue Date
2006-12
Keyword(s)
computer science
Date of Ingest
2009-04-21T19:27:32Z
Abstract
Multi-Agent Agreement problems (MAP) - the ability of a population of agents to search out and converge on a common state - are central issues in many multi-agent settings, from distributed sensor networks, to meeting scheduling, to development of norms, conventions, and language. While much work has been done on particular agreement problems, no unifying framework exists for comparing MAPs that vary in, e.g., strategy space complexity, inter-agent accessibility, and solution type, and understanding their relative complexities. We present such a unification, the Distributed Optimal Agreement Framework, and show how it captures a wide variety of agreement problems. To demonstrate DOA and its power, we apply it to two well-known MAPs: convention evolution and language convergence. We demonstrate the insights DOA provides toward improving known approaches to these problems. Using a careful comparative analysis of a range of MAPs and solution approaches via the DOA framework, we identify a single critical differentiating factor: how accurately an agent can discern other agent.s states. To demonstrate how variance in this factor influences solution tractability and complexity we show its effect on the convergence time and quality of Particle Swarm Optimization approach to a generalized MAP.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11280
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY