We propose a distributed approach to achieve spatially targeted communication that does not rely on external tracking infrastructure or dedicated hardware. The core idea of our approach is to leverage existing situated communication modalities to establish ad-hoc spatially targeted communication links (henceforth "STC links") between robots that want to communicate to one another. Our approach assumes a situated communication modality capable of detecting and sending at least three distinguishable situated signals that are broadcast within a limited communication range. The proposed approach is based around an iterative elimination process that results in a dedicated communication link between the robot initiating communication (henceforth the "initiator robot") and the desired communication target (henceforth the "target robot"). In this process, the initiator robot iteratively eliminates robots within communication range (henceforth the "potential recipient robots") it does not wish to communicate with until only the target robot is left. Further communication links to robots neighboring the target robot (henceforth the "target group") can be established through an iterative growth process. Our approach has a number of positive features. Firstly, it can use standard, low-cost components. In our experimentation, we use off-the-shelf cameras and LEDs of three different colors to generate the three situated signals. Secondly, the proposed approach scales well with the number of potential recipient robots: the elimination process at the heart of our approach scales logarithmically while the growth process scales linearly. Finally, our approach also has the benefit that it can be accurately represented by Markov chain models. We present separate models for the elimination process and the growth process and confirm the scalability of our approach. We present repeated real-world experiments with a heterogeneous robotic system, composed of up to 10 ground-based robots and one aerial robot. The initiator robot in our experiments is the flying AR.Drone robot [1]. The potential recipients are the ground-based marXbots [2]. Our experiments show that our method can be successfully implemented on real robotic hardware, and that it enables spatial coordination between robots not initially designed to communicate with each other.

Our heterogeneous multirobot testbed is composed of an AR.Drone 1.0 and up to ten marXbots. For safety reasons, we use a colorless, transparent plexiglass platform installed at 40cm height from the ground to shield the marXbots from the the AR.Drone (see Fig. 1a). The camera feed from the AR.Drone is shown in the inset. The inset's border color is used to visualize the signals sent by the AR.Drone via wireless Ethernet broadcast. The color white represents the freeze signal. The marXbots use their LEDs to transmit situated signals by displaying a color from the set >C:={red,blue,green}. These signals can be received by any robot, i.e., an AR.Drone or another marXbot, in the vicinity using the downward-pointing camera or the omnidirectional camera, respectively. A simple blob detection technique is applied to locate robots emitting a signal using their LEDs. Studies that require larger number of robots are conducted in a physics-based simulator [3] developed for multirobot simulation (see Fig. 1b). In simulation, we use the LEDs mounted on the aerial robot to visualize the signals transmitted to the marXbots. Additionally, in simulation-based experiments we use up to seven signals C:={red,blue,green,magenta,cyan,yellow,orange}.

(a)	(b)

Fig. 1: (a) The experimental setup showing the AR.Drone sending the signal blue, six marXbots responding with either blue or green color signals, the plexiglass platform, and a light source representing the object of interest. (b) A snapshot from simulation showing the aerial robot emitting the green signal, 100 marXbots responding using either the signal blue or green, and a cylinder placed on the ground representing the object of interest.

An STC link is established between an initiator and a target robot by the means of an iterative elimination process. We assume a set C:={c1,...,c_s: s >= 3} of distinct signals. The set C consists of signal c1, used to initialize and terminate the elimination process, and of the subset C_s:={c_2, ...,c_s} that contains the signals used in the iterative elimination process. In the heterogeneous multirobot system considered in the study, RGB colors are used to define the sets as C:={red,blue, green} and C_s:={blue, green}. The initiator robot initializes the elimination process by emitting the signal c1. The robots that perceive the c1 signal enter the elimination process by acknowledging with c2. Then, the initiator robot starts the elimination process by emitting a matching handshake signal c2. At each iteration, robots still in the process individually choose a signal to emit from the set C_s. The initiator robot responds by matching the signal emitted by the target robot. At the end of the iteration, only those robots whose signal match that of the initiator robot remain in the process. The other (non-matching) robots no longer emit any signal, and thus take take no further part in the selection process. The elimination process continues until the target robot is the only robot remaining. At this point, the initiator robot indicates the termination of the elimination process by repeating c1. The target robot acknowledges the termination by signaling c1. The initiator robot has now established an STC link to the target robot.

In multirobot systems, spatially targeted messages often need to be conveyed to groups of robots. In this section, we present an extension to our protocol that allows an initiator robot (the AR.Drone in our case) to expand an existing one-to-one STC link to a one-to-many link. To communicate with a group of co-located robots, the initiator first establishes a one-to-one STC link to a favorably located robot and then iteratively expands the link to include more neighbors. Note that we are not interested in which individual robots are in the target group, but only in the size of the group and its spatial cohesiveness. We validate the model using simulation-based studies and extensive experimentation on real robots. We present the results of our scalability studies. Finally, we present an experiment exemplifying the usefulness of one-to-many STC in real world tasks.

Given a set C:={c1,c2,c3} of distinct signals, a one-to-one STC link between an initiator and a target robot can be expanded into a one-to-many STC link through an iterative growth process. At the start of the process, the target robot is the only member of the target group. At each iteration, the initiator robot may emit the signal c3 to request a growth of the target group. From the robots that perceive this signal, those that have a target group member within perception range respond with signal c2. We refer to these robots as candidate robots. Next, each candidate robot determines if any other robot is located between itself and the closest target group member, and if so, leaves the process. We refer to the remaining candidate robots as closest candidate robots. This exclusion mechanism amongst the candidate robots ensures the spatial cohesiveness of the target group. The closest candidate robots communicate their candidacies to the initiator robot by emitting c3. If the number of the closest candidate robots plus the number of current group members (hereafter referred to as the "potential target group size") exceeds target group size, the initiator robot issues the signal c2 to request the closest candidate robots to relinquish their candidacies probabilistically. The c2 signal is issued until the potential target group size is smaller or equal to the target group size. Otherwise, if the potential target group size does not exceed the target group size, the initiator robots grants group membership to the closest candidate robots by emitting c1. Hence, the initiator robot may halt the growth process at an intermediate group size that is smaller than the target group size. If the intermediate group size is smaller than the target group size, the initiator robot restarts the growth process around the intermediate group. This incremental growth is repeated until the target group size is reached.