GRASTA-MAC 2015

joint workshops
7th workshop on GRAph Searching, Theory and Applications
5th workshop on Moving And Computing

October 19-23rd, 2015, Montréal, Canada

Merci à Christelle pour la photo

• Home
• Practical information
• Registration
• List of Participants
  
• List of talks
  
• Program
  
• About Graph Searching
• Previous GRASTA and MAC
• Contact

List of presentations

• Noa Agmon, Bar-Ilan 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 fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated 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 non-tree 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 non-explorable 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 Look-Compute-Move 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, rendez-vous 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 fence-patrolling 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 n-1$) of possible locations of guards (fixed in advance and guaranteed to give complete coverage), we present several upper and lower bounds on the worst-case 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
  
• Klaus-Tycho 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 Hegselmann-Krause 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 (man-made) 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 Hegselmann-Krause (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 EXPTIME-complete.
• 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 finite-state 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 non-negative integer function f that maps the set of non-negative 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 self-stabilizing 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 NP-hard to find the search ratio of a graph. Finding the randomized search ratio is equivalent to solving a zero-sum 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 non-terminating 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 Mesh-Networks, 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 two-hops distance.
• Alfredo Navarra, Univ. of Perugia, Italy
  Gathering on meeting-points: 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 Look-Compute-Move model. Anonymous and uniform robots are in fact required to gather only at some predetermined points in the plane, referred to as meeting-points. During a Look-Compute-Move cycle, a robot perceives the current configuration in terms of robots’ positions and meeting-points (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 meeting-points 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 cop-number 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 n-node 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 bounded-energy 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 bounded-energy agents always achieve rendezvous with detection in bounded-size 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 bounded-energy 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 bounded-energy agents (in bounded-size 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 torus-shaped 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 2-dimensional 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 look-compute-move 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 look-compute-move cycle the most common models are the fully synchronous (FSYNC), the semi-synchronous (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., path-planning 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 bio-relevant pattern-matching operations. The Ants operate on the medium in which the patterns are detected.
  - One can use use Cellular ANTomata as discrete models of feedback-heavy 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 NP-complete 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 self-organizing programmable matter
  Consider programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized 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 local-control 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 long-standing 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 n-gon not agreed upon in advance, even if the robots are asynchronous, disoriented, non-rigid, and have no chirality. As a by-product 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