Series in
Distributed Computing
edited by Roger Wattenhofer
Vol. 21
Jara Uitto
Collaboration in Multi-Agent Systems:
Adaptivity and Active Learning
1st edition / 1. Aufl. 2015. XII, 136 pages/Seiten,
€ 64,00.
ISBN 978-3-86628-549-1
Communication is a powerful tool that
enables the operation of a variety of old and new systems, such as mobile
networks, trade, and human relationships to name a few. Such systems consist of
many actors that, in one way or another, communicate with each other to reach a
common goal. In this dissertation, we study two rather different examples of
such multi-agent systems, namely, we explore the realm of recommendation
algorithms and networks of primitive models of computation.
In the case of recommendation algorithms,
the agents are able to share their preferences on some items via a centralized
entity that keeps track of the sharing history. The goal is to utilize the
sharing history so that the agents can learn which items they could potentially
like. In the case that the agents have many preferences in common, learning the
preferences can be helpful in finding good items for the agents. However, if
the agents do not have any preferences in common, it is hard to utilize the
sharing information. With this in mind, we propose a new scheme for competitive
analysis of recommendation algorithms, where we compare our online algorithms
to offline algorithms, that have limited information
about the input. In addition, we propose an online algorithm that finds a good
item for every agent in the system that has, up to a polylogarithmic
factor, an optimal competitive ratio in terms of our new scheme.
In the second part of the dissertation, we
focus on the Stone Age model of computation, where the agents are modeled by finite
state machines. First, we study the computation of a maximal independent set
(MIS) motivated by observations from biology, where cells are known to solve
this problem. We extend the study to
arbitrary networks, where the nodes are subject to crash failures. We propose a
distributed algorithm that is, on top of solving the MIS problem in the
presence of failures, able to contain the effects of the failures from the
nodes of the network that are not directly connected to the failed nodes.
Second, we study the Ants Nearby Treasure Search
(ANTS) problem in a similar model, where the agents are mobile. Our problem
setting is motivated by the foraging behavior of real world ants and the goal
of our agents is to locate a treasure hidden in an infinite grid. The agents
are faced by two different challenges in the environment. One of the challenges
is unexpected deaths (failures) of the agents, which requires the agents to
replace the dead agents to ensure that the treasure is eventually discovered.
The other challenge considers obstructions, that is, the agents have to adapt
to arbitrary obstacles in the environment. We show that by means of
cooperation, the agents are able to deal with both challenges and only require
a small overhead in the time complexity or in the number of agents required to
solve the task.
About
the Author
Jara
Uitto received his M.Sc. in 2011 from the Department
of Computer Science at the University of Helsinki. His doctoral studies took
place from 2011 to 2015 in the Distributed Computing Group at ETH Zürich
supervised by Prof. Dr. Roger Wattenhofer. He
received his PhD degree from ETH Zürich in August 2015. His research interests
include algorithms, distributed computing, and graph theory.
Keywords:
Collaboration, Distributed Systems, robots, ants,
matchings, Price of Anarchy (PoA), Price of Stability
(PoS)
Direkt bestellen
bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in
http://www.hartung-gorre.de
Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Hartung-Gorre Verlag / D-78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de