Distributed We envision a scenario with robots moving on a terrain represented by a plane. A mobile robot, called explorer is connected by a communication chain to a stationary base camp. The chain is expected to pass communication messages between the explorer and the base camp. It is composed of simple, mobile robots, called relays. We are investigating strategies for organizing and maintaining the chain, so that the number of relays employed is minimized and nevertheless the distance between neighbored relays in the chain remains bounded. We are looking for local and distributed strategies employed by restricted relays that have to base their decision ("Where should I go?") solely on the relative positions of its neighbors in the chain. We present the Manhattan-Hopper and the Hopper strategy which improve the performance of all known solutions to this problem significantly. They are the first such strategies that are optimal in this setting, i.e., that allow the explorer to move with constant speed, independent of the length of the chain, and keep this length minimum up to a constant factor. In this paper we will deal with the question on how to organize a chain of relays connecting two points on a plane. One of the points, the base camp, is stationary while the other is mobile and is called explorer. We have no influence on the movement of the explorer; the strategies we design control movement of the relays. We design strategies for the relays that keep the chain short and maintain connectivity despite movement of the explorer. The main challenge lies in the restriction that the relays have to decide locally, basing their decisions only on very limited information. Up to now we have informally spoken of a chain of relays. Hereby we mean an ordered sequence of relays, denoted by v 1 , . . . , v n . For technical reasons we include the explorer and the base camp into the chain, as respectively its first and last element; v 0 describes the explorer and v n+1 the base camp. Elements of the chain will be referred to as stations, meaning either a relay, the explorer or the base camp. The main restriction on the chain is that we require the distance between stations neighbored in the chain not to exceed the transmission distance of 1. Thanks to this, the chain can forward communication messages between the base camp and the explorer. We want to design strategies for the relays which guide their movement on the plane. Each of the relays is assumed to execute its own copy of this strategy and is able to sense the environment. We will go deeper into detail on the computational and sensing abilities of relays when describing the relay model later. The greatest challenge for this problem is that we are looking for strategies which operate locally and with very simple logic. Therefore, we have to design a solution in which each relay computes its position on its own, where communication is not used at all, and relays possess no memory. We are interested to see whether one can design efficient strategies solving this problem within this simple model.
The Hopper and Manhattan Hopper strategies REF solve this problem in time O(n), in the Euclidean plane and on the grid, respectively, using robots with a constant number of states, a constant memory and the capability to communicate states to local neighbors (flags, lights).
Optimal strategies for maintaining a chain of relays between an explorer and a base camp
THEORETICAL COMPUTER SCIENCE
Mathematics Computer Science