List of presentations

Noa Agmon, BarIlan University, Israel
Strategic path planning for robots in adversarial environments

Spyros Angelopoulos, LIP6, CNRS, Univ. Pierre et Marie Curie, Paris, France
Further connections between ray searching and contract scheduling problems
In this presentation we address connections between two classes of different, yet interrelated optimization problems. The first class of problems involves a searcher that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We discuss several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and faulttolerance issues, randomized strategies, and tradeoffs between performance and preemptions. For many of these problems we present the first known results that apply to multiray and multiproblem domains. Our objective is to demonstrate that several wellmotivated settings can be addressed using the same underlying approach.

Anthony Bonato, Ryerson University, Toronto, Canada
The game of Zombies and Survivors on graphs
We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is strictly greater than 1/2. We present asymptotic results for the zombie numbers of several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and Cartesian and toroidal grids.
 Jérémie Chalopin, LIF, CNRS, Univ. Aix Marseille, France
Anonymous Graph Exploration with Binoculars
We investigate the exploration of networks by a mobile agent. It is long known that, without global information about the graph, it is not possible to make the agent halts after the exploration except if the graph is a tree. We therefore endow the agent with binoculars, a sensing device that enables the agent to see the graph induced by its neighbors.
We show that, with binoculars, it is possible to explore and halt in a large class of nontree networks. We give a complete characterization of the class of networks that can be explored using binoculars using standard notions of discrete topology. This class is much larger than the class of trees: it contains in particular chordal graphs, plane triangulations and triangulations of the projective plane. Our characterization is constructive: we present an Exploration algorithm that is universal; this algorithm explores any network explorable with binoculars, and never halts in nonexplorable networks.

Sruti Gan Chaudhuri,Jadavpur University, Kolkata, West Bengal, India
Gathering of Asynchronous Oblivious Mobile Agents in a Tree
The talk will address the problem of gathering (collecting) a group of autonomous, identical, mobile agents (known as robots) placed arbitrarily in the nodes of an anonymous, unoriented tree. The robots operate in LookComputeMove cycles; Cycles are performed asynchronously for each robot. The robots
can’t remember computational results in the previous cycle. In this talk, we will
discuss some of possible ways to perform gathering under various limitations on robots capabilities.

Jurek Czyzowicz, Université du Québec en Outaouais, Canada
Patrolling by faulty robot
Mobile robots collaborate in order to solve efficiently the central problems in algorithmics of distributed computing like searching/exploration, rendezvous or pattern formation. Patrolling is a perpetual traversal of an environment by a collection of mobile robots. The standard measure of efficiency of a patrolling algorithm is defined by its idleness – the minimal time interval during which every point of the environment is always visited by at least one robot. Boundary patrolling and fence patrolling were fundamental problems investigated by the robotics community in the last decade.
We sketch briefly previous results concerning the algorithms for the boundary and fencepatrolling problem. When some (unknown) robots of the collection cannot perform their duties, the fence patrolling algorithms become surprisingly unnatural. In more details we discuss a new algorithm for patrolling by unreliable robots. We show that the presented algorithm achieves the idleness, which is the best possible.
 Shantanu Das, LIF, Univ. Aix Marseille, France.
Distributed Tasks for Mobile Robots with Energy Constraints
We consider distributed tasks for mobile robots moving on graph. Each robot has a constraint on its energy consumption which limits the number of edges it can traverse. Under such constraints, a team of robots need to perform a distributed task while sharing the work among them. In this model, even simple problems like delivering an object from source node to a target, becomes difficult to solve. We look at some recent results for energy constrained robots and discuss some open problems.
 Dariusz Dereniowski, Gdansk University of Technology, Poland
The searchlight problem for road networks
We consider the problem of searching for a mobile intruder
hiding in a road network given as the union of two or more lines, or two
or more line segments, in the plane. Some of the intersections of the road
network are occupied by stationary guards equipped with a number of
searchlights,
each of which can emit a single ray of light in any direction along the
lines (or line segments) it is on. The goal is to detect the intruder,
that is, to illuminate its location. Guards may alter the direction in
which they
aim a searchlight, but need to switch it off for some finite time interval
to effect the change. In contrast, the intruder may move with arbitrary
speed along the network (but cannot pass guards) and exploit this time
interval to recontaminate previously illuminated sections of the network.
For various classes of road networks characterized by the number $n$ of
lines (or line segments) comprising it and the number $g$ ($\leq n1$) of
possible locations of guards (fixed in advance and guaranteed to give
complete coverage), we present several upper and lower bounds on the
worstcase number of searchlights, each placed at one of the guard
positions, required to successfully search a given road network.

Fedor V. Fomin, Univ. Bergen, Norway
Tutorial on Graph Searching

KlausTycho Förster, Department Electrical Engineering, ETH, Zürich, Switzerland
Lower and Upper bounds for Online Directed Graph Exploration
This talk addresses the problem of exploring all nodes of an unknown directed graph in an online fashion. A searcher has to construct a tour that visits all nodes, but only has information about the parts of the graph it already visited. Analogously to the (offline) travelling salesman problem, the goal is to minimize the cost of such a tour. While online undirected graph exploration allows for constant to logarithmic multiplicative overhead, depending on the model used, directed graphs make the problem significantly harder for a searcher. In this talk, we will show that even supplying the searcher in a planar euclidean graph with the nodes’ coordinates does not help: Essentially, exploring a directed graph has a multiplicative overhead linear in the number of nodes.

Pierre Fraigniaud, LIAFA, CNRS, Univ. Paris Diderot, France
Decidability Classes for Mobile Agents Computing
 Matthias Fugger, Vienna University of Technology, Austria
Influence systems: the HegselmannKrause systems
Influence systems are distributed systems with dynamical communication
graphs that depend on the agents' states.
While such a dependency is unusual in the classical study of distributed
algorithms for artificial (manmade) systems, dynamic behaviors
of natural distributed systems in biology, physics, or opinion
dynamics can be modeled as influence systems.
In this talk we discuss a prominent example, the HegselmannKrause
(HK) system, which was originally designed to model opinion
dynamics.
Although its update rules are deceptively simple, many fundamental
questions are still open today.
We will give an overview on the state of the art about HK, as well as
the structure of proofs used.
We will then present variants of the original HK system, and discuss
the differences to the original model.
The talk concludes with a list of open problems.

Paul Hunter, Univ. Libre de Bruxelles, Belgium
Quantitative Sabotage Games
We study a generalisation of sabotage games, a model of dynamic network games introduced by van Benthem. The original definition of the game is inherently finite and therefore does not allow one to model infinite processes. We propose an extension of the sabotage games in which the first player (Runner) traverses an arena with dynamic weights determined by the second player (Saboteur). In our model of quantitative sabotage games, Saboteur is now given a budget that he can distribute amongst the edges of the graph, whilst Runner attempts to minimise the quantity of budget witnessed while completing his task. We show that for most of the classical cost functions considered in the literature, the problem of determining if Runner has a strategy to ensure a cost below some threshold is EXPTIMEcomplete.
 Anissa Lamani, Kyushu University, Japan
Synchronization and oscillations in population protocols
The population protocol (PP) model was introduced by Angluin at
al. to model passive distributed systems in which a collection of finitestate agents interact with each other in order to accomplish a common
task. The agents are assumed to be identical and uniform i.e., they are
not identified and all execute the same protocol. The computations
are performed through pairwise interactions i.e., when two agents in
teract, they exchange their local information and update their state
according to a common protocol. In addition, the interaction pattern
is unpredictable i.e., the agents have no control on the agents they will
interact with.
Many investigations have been made on the PP model addressing
different problems as computing a function, electing a leader, counting,
coloring and naming. Most of these problems are concerned with the
convergence to a specific configuration that contains the answer to the
problem that is considered. These problems are hence said to be static.
Only few investigations have considered dynamic problems as the token
circulation problem and the mutual exclusion problem.
We also consider a dynamic problem. More precisely, our aim is
to represent any periodic nonnegative integer function f that maps
the set of nonnegative integers N to itself, by a PP with a state set
Q and a subset S Q, such that, for any initial configuration C0,
with probability 1, there are a time instant t0 and a constant d 2 N
satisfying f(t + d) = S(Ct) for all t t0, where S(C) is the number
of agents with a state in S in a configuration C. We investigate for
this both the selfstabilizing synchronization problem and also the self
stabilizing oscillation problem.

Thomas Lidbetter, London School of Economics, UK
The expanding search ratio of a graph
Suppose a stationary Hider is located at an unknown vertex of a rooted graph with weighted edges. An expanding search of the graph is a sequence of edges starting at the root, each of which is incident to a vertex already searched. The search ratio, or competitive ratio of an expanding search is defined as the maximum value over all vertices of the ratio of the cost of reaching that vertex and the shortest path to the vertex from the root. The search ratio of a graph is the minimum search ratio of any expanding search and the randomized search ratio is the minimum expected search ratio of any randomized expanding search. It is NPhard to find the search ratio of a graph. Finding the randomized search ratio is equivalent to solving a zerosum game. We discuss search algorithms for finding the search ratio and randomized search ratio for various classes of graphs. For other classes we give algorithms that approximate these parameters within a constant factor. This is joint work with Spyros Angelopoulos and Christoph Dürr.

Marcello Mamino, LIX, Ecole Polytechnique, Palaiseau, France
On strategy recovery and mean payoff games
For nonterminating games, the tasks of evaluating every
position and finding an optimal strategy are not necessarily
equivalent. We will discuss the problem of finding an optimal strategy
given the value of all positions for (stochastic) mean payoff games.

Euripides Markou, University of Thessaly, Lamia, Greece
Mobile Agents Rendezvous in MeshNetworks, in spite of a Malicious Agent
We study the problem of mobile agents rendezvous in a mesh network, in presence of a powerful malicious mobile agent. The ‘honest’ mobile agents are asynchronous and anonymous finite automata and they need to gather at a node. They have no knowledge about the network, apart from its topology, and they can communicate only when they meet at a node. The malicious mobile agent is able to prevent the agents from reaching the node it occupies, while it is arbitrarily fast, has full knowledge of the network and it cannot be exterminated by the honest agents.
We prove that the problem can be solved when the honest agents initially form a connected configuration without ‘holes’ if and only if they can determine which are the occupied nodes within a twohops distance.

Alfredo Navarra, Univ. of Perugia, Italy
Gathering on meetingpoints: feasibility and optimality
We consider a new and challenging variant of the gathering problem of oblivious and asynchronous robots moving in the Euclidian plane under the standard LookComputeMove model.
Anonymous and uniform robots are in fact required to gather only at some predetermined points in the plane, referred to as meetingpoints. During a LookComputeMove cycle, a robot perceives the current configuration in terms of robots’ positions and meetingpoints (Look) according to its own coordinate system, decides whether to move toward some direction (Compute), and in the positive case it moves (Move).
In this talk we survey on recent results characterizing when gathering on meetingpoints can be accomplished and introducing optimization issues. In fact, we have also approached the problem with respect to two natural objective functions: 1) minimization of the total distance travelled by all robots; 2) minimization of the maximal distance travelled by a single robot.

Nicolas Nisse, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France
Tutorial on Cops and Robber Games
Given a graph G, the seminal cops and robber game involves two players [Nowakowski and Winkler, Quilliot, 1983]. Player 1 first places its cops on vertices of G, then Player 2 places its Robber on one node. Then, turn by turn, Player 1 moves its cops to neighboring nodes and then Player 2 does as well with its robber (cops and robber may stay idle). This is a full information game in the sense that cops and robber are always visible to each other. The Cops win if eventually one cop occupies the same node as the robber, and the Robber wins otherwise. The copnumber of a graph G is the smallest number of cops that ensures that the robber will eventually be captured in G. In particular, Meyniel conjectured that O(n^{1/2}) cops are sufficient to capture a robber in any nnode graph (1985).
While still open in general graphs, this conjecture has been proved in many graph classes (bounded genus, graph exclusing fixed minor, etc.). In this talk, we survey the main variants of these games, the results and open problems in this area.

Andrzej Pelc, Université du Québec en Outaouais, Canada
Rendezvous of communicating agents
Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round.
We want to achieve a more demanding goal, called {\em rendezvous with detection}: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the {\em beeping model}, introduced in \cite{CK}. In each round an agent can either listen or beep. In the {\em local beeping model}, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the {\em global beeping model},
an agent hears a {\em loud} beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a {\em soft} beep in a round if it listens in this round and if the other agent is at some other node and beeps.
We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if {\em boundedenergy agents}, i.e., agents that can make at most $c$ moves, for some integer $c$, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can boundedenergy agents always achieve rendezvous with detection in boundedsize networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of boundedenergy agents is {\em e
xponent
ially} larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for boundedenergy agents
(in boundedsize networks) as fast as for unrestricted agents.

Franck Petit, LIP6, Univ. Paris 6, France
Optimal Torus Exploration by Oblivious Mobile Robots
We consider autonomous robots that are endowed with motion actuators and visibility sensors. The robots we consider are weak, i.e., they are anonymous, uniform, unable to explicitly communicate, and oblivious (they do not remember any of their past actions). In this paper, we propose an optimal (w.r.t. the number of robots) solution for the terminating exploration of torusshaped networks by a team of k such robots in the SSYNC model.
In more details, we first show that it is impossible to explore any simple torus of arbitrary size with (strictly) less than four robots, even if the algorithm is probabilistic. If the algorithm is required to be deterministic, four robots are also insufficient. This negative result implies that the only way to obtain an optimal algorithm (w.r.t. the number of robots participating to the algorithm) is to make use of probabilities.
Then, we propose a probabilistic algorithm that uses four robots to explore all simple tori of size l*L (7<= l <= L). Hence, in such tori, four robots are necessary and sufficient to solve the (probabilistic) terminating exploration. As a torus can be seen as a 2dimensional ring, our result shows, perhaps surprisingly, that increasing the number of possible symmetries in the network (due to increasing dimensions) does not necessarily come at an extra cost w.r.t. the number of robots that are necessary to solve the problem.

Guiseppe Prencipe, Dipartimento di Informatica, Università di Pisa, Italy
The power of lights for autonomous mobile robots
In the last few years, a large amount of work has been devoted to the
study of models for autonomous mobile robots moving in a
lookcomputemove cycle, without explicit communication capabilities.
The main goal has been to understand the relationships between
capabilities of the robots and their power to solve common tasks. With
respect to their lookcomputemove cycle the most common models are
the fully synchronous (FSYNC), the semisynchronous (SSYNC), and the
asynchronous (ASYNC).
Recently, in the ASYNC model, the weakest of the three, a simple form
of direct and explicit communication has been introduced: each robot
is equipped with a light bulb that is visible to all other robots, and
that can display a constant numbers of different colors. In other
words, the robots are equipped with a constant number of visible (and
persistent) bits of memory.
In this talk we will show the impact of lights on the computational
power of a team of autonomous mobile robots.

Arnold Rosenberg, Northeastern University, Boston, USA
Cellular ANTomata: Principles, Problems, and Progress
A Cellular ANTomaton is a Cellular Automaton (CA) that has a team of mobile FSMs
(finite state machines) operating on it  with at most one mobile FSM per CA
cell. The mobile FSMs  which we call Ants can be quite different from the
(identical) FSMs that populate the cells of the CA; in the heterogeneous case, the
Ants may be quite different from one another. The exciting feature of Cellular
ANTomata is their combining distributed computing by the Ants with tightly
synchronized computing by the FSMs of the CA.
Cellular ANTomata find potential applications in a broad range of applications:
* In the domain of Robotics, Ants are robots that are controlled by a smart floor.
One envisages the CA as doing, e.g., pathplanning while the Ants manipulate
various objects that reside on the "floor" that hosts the CA.
* In the domain of Bioinformatics.
 One can use use the CA as a parallel computer that efficiently performs a variety
of biorelevant patternmatching operations. The Ants operate on the medium in
which the patterns are detected.
 One can use use Cellular ANTomata as discrete models of feedbackheavy biological
systems that are both complex and continuous in nature. (The immune system in the
liver is a tempting candidate.)
* In the domain of Big data, Ants can be mobile processors that respond to
summonses relayed through the underlying CA, as it organizes massive amounts of
data. In this manner, Ants bring processing power to where it is needed within the
data.
We illustrate Cellular ANTomata solving some simple computational problems that
hint at their computational potential.

Elham Roshanbin, Dalhousie University, Halifax, Canada
On the complexity of the graph burning
Assume that we want to spread a message among all the users of a network. Knowing the structure of the network, we may consider how fast this can be done. Graph burning is a new graph process which is used as a model for the spread of social contagion. Burning number is the graph parameter associated with the burning process and measures the speed of contagion in the underlying graph of a social network. In this talk we show that the burning problem is NPcomplete for trees of maximum degree three and even for the spider graphs. We also provide some algorithms for finding the burning number of some specific graphs.
This is joint work with Anthony Bonato and Jeannette Janssen.

Nicola Santoro, Carleton University, Ottawa, Canada
Tutorial on Models for computational mobile entities

Christian Scheideler, University of Paderborn, Germany
Leader election and shape formation with selforganizing programmable matter
Consider programmable matter consisting of
simple computational elements, called particles, that can establish and
release bonds and can actively move in a selforganized way. I will present
first results concerning the feasibility of solving basic problems relevant for
such programmable matter. As a model, I will use a general form of the
amoebot model first proposed in SPAA 2014. Based on that model, efficient
localcontrol algorithms for leader election and path formation requiring only
particles with constant size memory will be presented, and the limitations of
solving these problems within the amoebot model will be discussed.

Wei Shi, University of Ontario Institute of Technology, Canada
Dynamically Spawned Black Hole search

Frédéric Simard, Laval University, Québec, Canada
A Generalized Model of Games of Cops and Robbers with Randomness
Since Nowakowski and Winkler's seminal 1983 paper, every variants of the Cop and Robber game have typically been studied independatly. Then, in 2014, Anthony Bonato and Gary MacGillivray proposed a model to generalise all cops and robbers games called deterministic, that is in which there are no elements of chance. This model is then solved with an extension of the classical quasiorder relation used for solving instances of cops and robbers games. Although this model is incredibly powerful, we feel the deterministic assumption is too restrictive. Indeed, in 2012 Pawel Pralat and Antonios Kehagias proposed the Cop and Drunk Robber game in which the robber is walking randomly on the graph. This game cannot be encapsulated in Bonato and MacGillivray's model because of the deterministic requirement. In a 2015 article presented at CP 2015, Cork, Ireland, the authors have showed how to solve the Cop and Drunk Robber game with another extension of the typical method for solving cops and robbers games in the form of a recursion. Thus, in this paper is presented a new framework to model Cops and Robbers games generalizing that of Bonato and MacGillivray to include games with stochastic elements and an extension of the CP 2015 recursion to solve this model.

Giovanni Viglietta, University of Ottawa, Canada
Distributed Computing by Mobile Robots: Solving the Uniform Circle Formation Problem
We discuss a recent breakthrough on a longstanding open problem on pattern formation by autonomous oblivious robots moving in the Euclidean plane. We will show how a swarm of n robots, starting from any initial configuration, can arrange itself on the vertices of a regular ngon not agreed upon in advance, even if the robots are asynchronous, disoriented, nonrigid, and have no chirality. As a byproduct we argue that, for pattern formation tasks, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are irrelevant.

Koichi Wada, Faculty of Science and Engineering, HOSEI University, Tokyo, Japan
A new model of mobile robots with lights and its computational power
We propose a new model for autonomous and anonymous mobile robots with
lights.
The model is extended of conventional mobile robots with lights such
that each robot has internal lights usable only for itself and/or
external ones usable only for other robots. We consider a gathering
problem of n mobile robots(n >= 3) and discuss its solvability in a
proposed model.

Yukiko Yamauchi, Kyushu University, Japan
Formation Problems for Synchronous Mobile Robots
in the Three Dimensional Euclidean Space