We consider evacuation of a group of $n \geq 2$ autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed $1$ in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio ($CR$) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio $CR=3+2 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [3,5.681319]$. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.

Abstract A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $${\mathbb {Z}} \times {\mathbb {Z}}$$ Z × Z . Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the shape , is initially connected. The (Manhattan) distance between the furthest cells of the shape is called its span . The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest . That is, the robot has to move all bricks in such a way that the span of the resulting shape be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected shape, in time $$O(sn)$$ O ( s n ) , where s is the span of the initial shape and $$n$$ n is the number of bricks. We show that this complexity is optimal.

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $\mathbb{Z} \times \mathbb{Z}$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time $O(sz)$, where $s$ is the span of the initial field and $z$ is the number of bricks. We show that this complexity is optimal.

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time.

We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and "measuring instruments'' of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most $$\sqrt{17}+4\approx 8.123$$ times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

Two anonymous robots placed at different positions on an infinite line need to rendezvous. Each robot possesses a clock which it uses to time its movement. However, the robot's individual parameters in the form of their walking speed and time unit may or may not be the same for both robots. We study the feasibility of rendezvous in different scenarios, in which some subsets of these parameters are not the same. As the robots are anonymous, they execute the same algorithm and when both parameters are identical the rendezvous is infeasible. We propose a universal algorithm, such that the robots are assured of meeting in finite time, in any case when at least one of the parameters is not equal for both robots.

Abstract. A fence, represented by a unit interval is to be patrolled collectively by n robots. At any moment a robot may move in one of the two possible states: walking or patrolling. Each state is associated with a maximal moving speed which cannot be exceeded. A robot may have a unique pair of speeds, but its patrolling speed is always smaller than its walking speed. Each robot is allowed to patrol while moving only in one of the two directions (not necessarily the same for all robots). We want to schedule the perpetual movements of the robots so as to minimize the idleness, defined as the smallest time interval within which every point is always visited by some robot. First, we give a centralized algorithm constructing schedules with optimal idleness, and subsequently we show a nice application to a transportation problem concerning Scheduling with Regular Delivery. Our main contribution is the study of distributed, dynamical schedules for patrolling robots with only primitive capabilities. Surprisingly we are able to design a dynamic schedule for very weak collections of two robots (silent, oblivious, passively mobile), achieving the optimal idleness. Our algorithm defines a dynamical system of memoryless robots moving back and forth in an interval. In general, analysis of the system dynamics is very complex. Part of our contribution is a very technical analysis of the dynamics of special families of dynamical systems of n robots that we call regular. For such systems we also propose a highly non-trivial O(n2) algorithm to decide whether or not robots converge to a stable configuration thus verifying if the dynamic schedule is optimal. It turns out that a very natural family of

We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

We consider the problem of searching on a line using n mobile robots, of which at most f are faulty, and the remaining are reliable. The robots start at the same location and move in parallel along the line with the same speed. There is a target placed on the line at a location unknown to the robots. Reliable robots can find the target when they reach its location, but faulty robots cannot detect the target. Our goal is to design a parallel algorithm minimizing the competitive ratio, represented by the worst case ratio between the time of arrival of the first reliable robot at the target, and the distance from the source to the target.

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their uniform maximum speeds. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness.

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and 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. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with k memory bits, we show that optimal rendezvous time is Θ(n+n2/k) in n-node trees. More precisely, if k ≥ c log n, for some constant c, we design agents accomplishing rendezvous in arbitrary trees of unknown size n in time O(n+n2/k), starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time o(n+n2/k), even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a n-node line.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(log2n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log2n).

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. Intuitively, the rendezvous problem is more difficult than exploration, as it reduces to the latter, if one of the agents is inert. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically.

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting -- agents can, indeed, meet almost everywhere -- we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other.

No abstract available.

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family.In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family.In particular, we give O(n log n) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments.We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices.In general, finding a line transversal for a family of n objects takes fl(n log n) time.This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.