Decentralized Coordination in Multi-Agent Systems
Ph.D. thesis abstract
Mihail Mihaylov
ai.vub.ac.be/members/mike
Promotor: Prof.dr. Ann Nowé (VUB)
Copromotor: Prof.dr. Karl Tuyls (UM)
Date of defense: July 3, 2012
Many computer systems are comprised of multiple entities (or agents) with common objectives. Though these systems can be made intelligent, using artificial intelligence techniques, individual agents are often restricted in their capabilities and have only limited knowledge of their environment. However, the group as a whole is capable of executing more complex tasks than a single agent can perform. Individual agents, therefore, need to coordinate their activities in order to meet the design objectives of the entire system. Implementing a centralized control for distributed computer systems is an expensive task due to the high computational costs, the communication overhead, the curse of dimensionality and the single point of failure problem. The complexity of centralized control can be reduced by addressing the problem from a multi-agent perspective. Moreover, many real-world problems are inherently decentralized, where individual agents are simply unable to fulfill their design objectives on their own. In multi-agent systems with no central control, agents need to efficiently coordinate their behavior in a decentralized and self-organizing way in order to achieve their common, but complex design objectives. Therefore it is the task of the system designer to implement efficient mechanisms that enable the decentralized coordination between highly constrained agents. In this thesis we take the role of designers of decentralized systems and investigate the following problem, which motivates our research:
Problem statement: How can the designer of a decentralized system, imposing minimal system requirements and overhead, enable the efficient coordination of highly constrained agents, based only on local interactions and incomplete knowledge?
Our research on decentralized coordination is inspired by the challenging domain of wireless sensor networks (WSNs). The WSN problem requires resource-constrained sensor nodes to coordinate their actions, in order to improve message throughput, and at the same time to anti-coordinate, in order to reduce communication interference. Throughout this thesis we analyze this (anti-)coordination problem by studying its two building blocks separately so that we form a solid basis for understanding the more complex task of (anti-)coordination. We study pure coordination in the problem of convention emergence and pure anti-coordination in dispersion games. We then study the full problem of (anti-)coordination in time, as seen in the WSN domain. Thus the above problem statement gives rise to three research questions, which we answer in separate chapters:
RQ 1: How can conventions emerge in a decentralized manner in pure coordination games?
RQ 2: How can agents achieve pure anti-coordination in a decentralized manner in dispersion games?
RQ 3: How can highly constrained sensor nodes organize their communication schedules in a decentralized manner in a wireless sensor network?
Our main contribution is to propose a simple decentralized reinforcement learning approach, called Win-Stay Lose-probabilistic-Shift (WSLpS), that allows highly constrained agents to efficiently coordinate their behavior imposing minimal system requirements and overhead. We demonstrate that global coordination can emerge from simple and local interactions without the need of central control or any form of explicit coordination. Despite its simplicity, WSLpS quickly achieves efficient collective behavior both in pure coordination games (in chapter 3) and in pure anti-coordination games (in chapter 4). We use our approach in the design of an adaptive low-cost communication protocol, called DESYDE, which achieves efficient wake-up scheduling in wireless sensor networks (in chapter 5). In this way we demonstrate how a simple and versatile approach achieves efficient decentralized coordination in real-world multi-agent systems.
