DISTRIBUTED ON-LINE MULTI-AGENT OPTIMIZATION UNDER UNCERTAINTY: BALANCING EXPLORATION AND EXPLOITATION

Matthew E. Taylor (), Manish Jain (), Prateek Tandon (), Makoto Yokoo () and Milind Tambe ()
Additional contact information
Matthew E. Taylor: Computer Science Department, Lafayette College, Easton, PA 1804, USA
Manish Jain: Computer Science Department, The University of Southern California, Los Angeles, CA 90089, USA
Prateek Tandon: Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Makoto Yokoo: Department of Informatics, Kyushu University, Fukuoka, 819-0395, Japan
Milind Tambe: Computer Science Department, The University of Southern California, Los Angeles, CA 90089, USA

Advances in Complex Systems (ACS), 2011, vol. 14, issue 03, 471-528

Abstract: A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems; DCOP agents must have complete and accurate knowledge about the reward function at plan time.We extend the DCOP framework, defining theDistributed Coordination of Exploration and Exploitation(DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation.Two classes of algorithms are introduced:static estimationalgorithms perform simple calculations that allow agents to either stay or explore, andbalanced explorationalgorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms maylowerteam performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon theteam uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty.

Keywords: Cooperative multi-agent systems; exploration; optimization; Distributed Constraint Optimization (DCOP); Distributed Coordination of Exploration and Exploitation (DCEE) (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525911003104
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:14:y:2011:i:03:n:s0219525911003104

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525911003104

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().