Invited Talks
Subhash Bhagat (Indian Association for the Cultivation of Science, India)
Title: The Mutual Visibility Problem for Autonomous Robots
Abstract: In this talk, we consider the mutual visibility problem for a set of autonomous, opaque robots under the obstructed visibility model. If three robots lie on a straight line, then the middle robot obstructs the vision of the two other robots. Thus, in a given initial robot configuration, all the robots may not be mutually visible to each other. The mutual visibility problem requires the robots to coordinate their movements to convert the current configuration into the one in which no three robots lie on a line. Under different computational models, a variety of solutions have been proposed in the literature both for oblivious robots and robots with constant amounts of persistent memory. While some results are on the feasibility of solutions in different computational models, the others considered the problem with different complexity measures and faults. The goal of this talk is to provide an overview of the problem and challenges to solve the problem under different computational models. The focus will be on the feasibility studies both for oblivious robots and robots with lights. We will also discuss some results on different complexity measures for the problem.
Stephane Devismes (Universite Grenoble Alpes, France)
Title: Exploring an Infinite Space using a few Weak Robots
Abstract: In this talk, we will review recent results about the infinite grid exploration by a small swarm of mobile robots with very weak capability. Indeed, these robots are myopic (they have a typically small visibility range), deaf-mute (they cannot explicitly communicate), opaque, and disoriented (they do not agree on a common North). However, they operate in synchronous Look-Compute-Move cycle and may be luminous, i.e., they may use lights with a constant number of colors that can be seen by other robots in their visibility range. Their light is actually their only permanent memory.
We will present several optimal solutions w.r.t. visibility range, number of colors, and number of robots. In particular, we will study the impact of the common chirality assumption (i.e., the fact that, when located on an axis of symmetry in its surroundings, a robot can or cannot distinguish its two sides, one from another) on the optimal bounds
George Giakkoupis (IRISA/INRIA, France)
Title: An Optimal Leader Election Population Protocol
Abstract: Population protocols are a popular model of distributed computing, where $n$ agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. In this talk we present the first leader election population protocol that is both time and space optimal, using $\Theta(\log\log n)$ states per agent, and electing a leader in $O(n\log n)$ interactions in expectation.
Link to the full version of the paper: https://hal.inria.fr/hal-02545348
Giuseppe Antonio Di Luna (University of Rome, Italy)
Abstract: Mobile agents are well known and popular. In this computational model a set of autonomous entities, the agents, move on top of a graph. The final purpose of this team is to coordinate in order to reach a target goal. The agents may either model intelligent messages circulating in a network (in this case is a software engineering paradigm) or a set of real robots inhabiting a discrete space (i.e., a fleet of autonomous trains on railways).
The ponderous literature on mobile agents has been almost entirely devoted to the study of agents on static graphs. Recently, several papers started the investigation of mobile agents in dynamic graphs, where the graph topology dynamically changes in a time-varying fashion. This setting effectively models real dynamic environments, as examples: a network of mobile sensors, where the dynamicity is introduced by the movement of the sensors and the unreliable wireless links; or roads in a metropolis, where the dynamicity is due to temporary traffic jams, construction works, etc.
The research of agents in dynamic graphs is mainly divided into two lines; one studies the centralized setting in which a single entity governs the movement of the entire team, the other studies the distributed setting. This talk is focussed on the distributed perspective: agents are fully-autonomous and they have to coordinate without central help.
In this setting, the feasibility and complexity of a certain task dramatically change according to the computational power of our entities. Example of computational assumptions are distinguishability of agents (i.e., whether they are anonymous or not), communication capabilities (e.g., face to face, whiteboards, wireless), synchronization of the system (e.g., fully synchronous, semi-synchronous, asynchronous), knowledge of the environment (e.g., topological knowledge, team size), etc.
This talk will survey recent results in the field, mainly focussing on the problems of exploration (the agents have to collectively explore the entire graph), gathering (the agents, initially scattered, have to meet in the same node) and blackhole search (the team has to identify a dangerous node able to destroy visiting agents). The talk will highlights how the computational landscape of the above problems changes depending on the capabilities of the agents.