Collaboration in Multi-Agent Systems: Adaptivity and Active Learning
1st Edition
Published on 12. October 2015
Book
Paperback/Softback
XII, 136 pages
978-3-86628-549-1 (ISBN)
Description
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.
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.