Thomas Durantel

Julie Coloigner

Olivier Commowick

A CONVOLUTIONAL WASSERSTEIN DISTANCE FOR TRACTOGRAPHY EVALUATION: COMPLEMENTARITY STUDY TO STATE-OF-THE-ART MEASURES

Evaluation and comparison of tractograms are crucial and open problems that need to be solved in order to evaluate the false positives rate and variability of tractography algorithms. In this context, a lot of measures have been developed and are typically used to judge the quality of a tractogram. They however do not rely on the same quantities extracted from the tractograms to compare and may thus not evaluate the same aspects of tractogram quality. To evaluate this aspect and the measures redundancy or complementarity, we perform a quantitative analysis of the most common ones, both on simulated data and in real circumstances. We also propose a new evaluation measure based on optimal transport theory. We show that, when used in conjunction, these measures can provide a more in depth comparison of tractograms and thus a more complete evaluation.

INTRODUCTION

Diffusion MRI and fiber tractography are promising methods for the evaluation of the brain nervous fiber pathways. Since the emergence of these techniques at the end of the previous century [START_REF] Basser | In vivo fiber tractography using DT-MRI data[END_REF], many new methods have appeared. The first ones were based on tensors, one of the simplest diffusion models [START_REF] Mori | Fiber tracking: principles and strategies -a technical review[END_REF]. Since then, numerous studies have shown the limitations of tensor-based tractography in complex fiber structures [START_REF] Gao | Validation of DTI tractography-based measures of primary motor area connectivity in the squirrel monkey brain[END_REF]. To overpass these limitations, new algorithms, using either other diffusion models (orientation distribution functions [START_REF] Descoteaux | Regularized, fast, and robust analytical q-ball imaging[END_REF] or multi-tensors [START_REF] Tuch | High angular resolution diffusion imaging reveals intravoxel white matter fiber heterogeneity[END_REF]) or new probabilistic tractography methods [START_REF] Stamm | Adaptive multi-modal particle filtering for probabilistic white matter tractography[END_REF]7], have been developed. These methods have allowed a better reconstruction of complex fiber bundles like the corticospinal tract (CST) or the corpus callosum (CC) [START_REF] Girard | On the cortical connectivity in the macaque brain: A comparison of diffusion tractography and histological tracing data[END_REF], but still do not reach an acceptable false positive rate to be used in a clinical context [START_REF] Maier-Hein | The challenge of mapping the human connectome based on diffusion tractography[END_REF].

The large number of existing techniques results in a lot of variability in the reconstruction of fiber bundles, which prevents, on one hand, clinicians from correctly interpreting the results, and on the other hand makes it difficult to evaluate and compare tractography algorithms [START_REF] Schilling | Tractography dissection variability: What happens when 42 groups dissect 14 white matter bundles on the same dataset?[END_REF]. Hence, many challenges [START_REF] Côté | Tractometer: Towards validation of tractography pipelines[END_REF][START_REF] Maffei | The irontract challenge: Validation and optimal tractography methods for the hcp diffusion acquisition scheme[END_REF] have been organized to 1-study the sources of this variability, 2-provide a general framework allowing to more easily compare tractography algorithms. In those chal-lenges, a few probabilistic methods [START_REF] Tournier | Improved probabilistic streamlines tractography by 2nd order integration over fibre orientation distributions[END_REF][START_REF] Smith | Anatomically-constrained tractography: Improved diffusion MRI streamlines tractography through effective use of anatomical information[END_REF][START_REF] Baran | Parallel transport tractography[END_REF] have shared the first place.

When organizing such challenges or evaluating an algorithm, the question of evaluation of tractograms becomes essential. While visual evaluations are crucial to quickly judge the quality of tractograms, they do not allow for an in-depth comparison and a quantitative performance analysis. Therefore, comparison being at the core of these challenges, measures have been developed to quantify and study differences between methods. First, measures such as the Dice score, its generalized version [START_REF] Crum | Generalized overlap measures for evaluation and validation in medical image analysis[END_REF] or density correlation [START_REF] Schilling | Tractography dissection variability: What happens when 42 groups dissect 14 white matter bundles on the same dataset?[END_REF] analyze tractograms as an image derived from the fiber bundles being compared. Second, the anatomical plausibility can be studied with topographic regularity [START_REF] Baran | Tracking and validation techniques for topographically organized tractography[END_REF] or, as in TractoMeter, the number of valid connections (VC, the percentage of streamlines that correctly connect both ends of a fiber bundle) and the number of valid streamlines (VS, the percentage of streamlines that are part of VC, and that respect the general shape of the bundle).

As mentioned above, tractograms evaluation measures are a crucial and actual problem that lacks of a general answer. Multiple measures are available in the literature. However, as they work on different objects or quantities derived from tractograms, it is probable that one measure does not explain fully tractograms variations and errors, nor that they expose the same kind of errors. This has however never been explored in the literature. We thus propose first to study and compare the behavior of the most common of these measures when the reference and tested tractograms diverge from each other. This is done using simulated data by applying linear and non linear transformations, and also comparing results of different tractography algorithms in real cases. We also define and evaluate a new tractogram evaluation measure based on optimal transport and demonstrate its interest in combination to other measures.

METHODOLOGY

We first present four measures, based either on streamlines or on images derived from streamlines, typically used in recent works [START_REF] Côté | Tractometer: Towards validation of tractography pipelines[END_REF][START_REF] Schilling | Tractography dissection variability: What happens when 42 groups dissect 14 white matter bundles on the same dataset?[END_REF] for evaluating tractogram quality: generalized Dice score, density correlation, valid connections and valid streamlines. We then introduce our new measure based on optimal transport.

Generalized Dice score

The Dice and generalized Dice scores measure overlap between a reference and a test image. There are several generalizations of the binary Dice score. We have chosen the one proposed in [START_REF] Crum | Generalized overlap measures for evaluation and validation in medical image analysis[END_REF]. Unlike the original Dice score, that assumes binary image inputs, the generalized Dice score handles weighted images. In the case of tractograms, these images are fiber density images (i.e. the weight of a voxel is the number of streamlines that pass through it). That property allows this measure to give more importance to the most dense regions.

Density correlation

The density correlation is also based on the use of fiber density images. It computes the cross-correlation coefficient between the reference density image and the test density image. It is given by:

ρ = i (A i -A)(B i -B) i (A i -A) 2 i (B i -B) 2 (1)
with ρ ∈ [-1, 1], A i and B i the value of the corresponding image at voxel i, and A and B the average voxel value of reference and test density images. One advantage of this measure over the generalized Dice score is that it can yield negative results, thus giving information about a negative correlation.

Valid Connections

In many cases, obtaining the ground truth of tractography is difficult. Some measures thus assume that we do not know the complete ground truth tractogram but rather only the start and end regions (start and end ROIs) at which the fibers should end. In this case, the evaluation measure can be defined by counting fibers of the evaluated tractogram that actually start and stop in these regions [START_REF] Côté | Tractometer: Towards validation of tractography pipelines[END_REF]. This percentage is named valid connections (VC) and was used in the TractoMeter challenge.

Valid Streamlines

Going one step further than VC, we can consider that, in addition to the start and end ROIs, we also know the envelope of the ground truth tractogram. If the full ground truth tractogram is available, this envelope can be extracted as a binary image highlighting voxels where at least one fiber passes through. The percentage of valid streamlines (VS) is then the percentage of all streamlines that are part of Valid Connections, and that do not leave the ground truth envelope. Hence the percentage of valid streamlines will always be lower than the percentage of valid connections.

Wasserstein distance

We propose in this paper a novel evaluation measure based on the computation of the Wasserstein distance, derived from optimal transport theory. First, we will introduce these concepts and then how to use them to evaluate tractograms.

Let µ 0 and µ 1 be, respectively, a source and a target distributions and π(x, y) a transport plan that describes the amount of mass transported from µ 0 at location x to µ 1 at location y. The 2-Wasserstein distance, simply called Wasserstein distance in the following, defines a distance that can be used to measure the discrepancy between two distributions. It is given by Eq. 2:

W 2 2,γ (µ 0 , µ 1 ) = inf π∈Π [ M ×M d(x, y) 2 π(x, y) dx dy -γH(π)]
(2) with d(x, y) the distance function between two elements x ∈ M and y ∈ M , and M a compact, connected Riemannian manifold.

The last term, γH(π), is an entropic regularization term which is used to smooth the function and thus to provide a unique solution to the problem. Many methods have been devised in the literature to obtain this solution [START_REF] Bonneel | Spot: Sliced partial optimal transport[END_REF][START_REF] Figalli | The optimal partial transport problem[END_REF]. The most common is the Sinkhorn algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]. However, this algorithm has two majors limitations. First, being an iterative algorithm, it can take a long time to converge. Second, when comparing two distributions of fibers (our tractograms), the distributions are made of individual Diracs at each point of each fiber. The number of distances to compute between the two distributions therefore becomes quickly overly large both in computation times and memory consumption (e.g. in our case, a normal fiber bundle can have 50000 points, so that 50000 2 distances need to be computed and stored to be computationally efficient).

Consequently, we have chosen to rely on a newly introduced and particularly efficient method: the convolutionnal Wasserstein distance algorithm proposed by Solomon et al. [START_REF] Solomon | Convolutional wasserstein distances: Efficient optimal transportation on geometric domains[END_REF]. It relies on the Varadhan's formula to replace the kernel of the Sinkhorn algorithm by a Gaussian kernel from the heat equation when dealing with distributions represented as 3D images. Considering the tractograms as 3D density images as above for the generalized Dice score, we can perform the Sinkhorn iterations through 3D Gaussian kernel convolutions, which are both very computation and memory efficient since we can perform them directly on the images and thus do not have to store the distance matrix explicitly.

EXPERIMENTS

To compare the behaviour of the evaluated measures and to test the Wasserstein distance (WD), two sets of experiments, one on simulated transformations and another one on real data, were performed.

In the first set of experiments, the 5 evaluation measures (Dice, correlation, VC, VS and WD) were computed on 4 controlled transformations cases, often found at least partially in real cases. The data used here is the Cortico-Spinal Tract (CST) of 5 subjects of the Human connectome Project (HCP). This ground truth data was obtained by Wasserthal et al. [START_REF]Tractseg -fast and accurate white matter tract segmentation[END_REF] by performing fiber tracking using Mrtrix and multiple times filtered, first by ROIs, then by an expert. The 4 experiments were designed as follows: Translation The reference track is translated along the X axis from 0 to 12.5 mm, in step of 0.0125 mm. Rotation The track is rotated around the Z axis (roughly the CST main axis) and the centre of gravity of the bundle by an angle from 0 to 360 degrees, with increments of 1 degree Deformation A stationary velocity field (SVF) [START_REF] Arsigny | A Log-Euclidean framework for statistics on diffeomorphisms[END_REF] is generated by randomly generating Gaussian weight functions inside the reference fiber bundle mask. To each weight function is associated an individual translation in a random direction, with a random magnitude. The SVF is the weighted combination of these translations using the Gaussian weight functions. In our case, we generated for each deformation from one to 75 Gaussian weight functions, with a random translation between 0 and 5 mm. This SVF is then integrated and applied to the tractograms. To characterize the global amplitude of each generated deformation, we compute the average vector norm at each voxel, inside the bundle envelope. Degradation The track is degraded by randomly removing fibers from 0 to 100 percent of the reference fiber bundle For each of these simulated datasets, cross-correlation coefficients were further computed between each pair of measure curves computed. This allowed to quantify the complementarity between these measures (the smaller the correlation the more complementary information).

The second set of experiments is based on data from the HCP and more particularly on 3 bundles, the CST, the Optic radiation (OR) and the first Superior longitudinal fascicle (SLF) tracked with the parallel transport frame algorithm [START_REF] Baran | Parallel transport tractography[END_REF], the Mrtrix3 iFOD2 [START_REF] Tournier | Improved probabilistic streamlines tractography by 2nd order integration over fibre orientation distributions[END_REF] and the DIPY Probabilistic PFT algorithm [START_REF] Smith | Anatomically-constrained tractography: Improved diffusion MRI streamlines tractography through effective use of anatomical information[END_REF]. For the 3 algorithms, only default parameters were used and 10000 streamlines were generated by running a whole brain tractography, then by filtering the results with the start and end ROIs, segmented with TractSeg. The evaluation was then performed between the ground truth tracks given by [START_REF]Tractseg -fast and accurate white matter tract segmentation[END_REF] and the resulting tractograms. For that experiment, we may note that the evaluation framework forces VC to be at 100%, thus only the other measures were computed. The purpose of these experiments is not, here, to compare these methods but to study the behavior of our measures in comparison with the state of the art methods.

RESULTS

We present in this section representative results obtained for the two sets of experiments. For translation, Fig. 1.a shows that all measures follow the same behavior, except for VC that seems to provide different information. All combinations have indeed a correlation coefficient above 0.95, except for ρ(Corr, V C) = 0.60, ρ(Dice, V C) = 0.63, ρ(W D, V C) = 0.70 and ρ(V C, V S) = 0.43. We have a maximum of 0.99 for ρ(Corr, Dice).

For rotation, Fig. 1.b shows the same result as the translation, even more pronounced. We found ρ(W D, Corr) = 0.41, ρ(W D, Dice) = 0.41, ρ(W D, V C) = 0.37 and, ρ(W D, V S) = 0.23. All other are above 0.90 and the maximum is ρ(Corr, Dice) = 0.99.

For the deformation (Fig. 1.c), linear regression (plus a 95% confidence interval, in transparent on the plot) were computed and plotted to study the correlation between each measure against deformation. VC were not plotted because the major part of the deformation did not occur on the ending parts of the streamlines. The R 2 of each regression are as follows: 0.64 for Dice score, 0.40 for the density correlation, 0.38 for VS and 0.03 for WD. The regression plots show that, the Density correlation, the Dice score and VS percentage (red, blue and black) appear to follow the expected trend: they decrease when the average norm increases. However, the relationship between these measures and the average norm may not be linear and the x-axis is probably to simplistic to really conclude here without further experiments.

For degradation (Fig. Results for the real data experiment are shown in Table 1. Fig. 2 presents the resulting tractograms on which measurements were made. We can see that, in first analysis, the measures describe well the overall quality of the tractograms.

DISCUSSION AND CONCLUSION

The cross correlation results for rotation and translation show that, for these transformations, the Dice score and the density correlation do not give complementary information. For translation, VC appears in each combination with the lowest coefficient, meaning that for this type of transformation, streamlines based measures can bring complementary information to image based measures. In the rotation case, the Wasserstein distance is the least correlated with the others, thus, that gives more information on tractogram quality in complement to other measures. The R 2 of the linear regressions for deformation plots show that these measures have difficulties to evaluate properly deformations in tractograms. However, this result should be taken with caution since, in this experiment, we tried to reflect local deformations with an average global information which may not be enough to capture the deformations variations. Designing more local evaluation of the deformation magnitude would be beneficial. Finally, for the degradation, all coefficients are relatively low, in particular the density correlation and the Dice score that are almost uncorrelated showing their complementarity.

For real data, results show that, globally, VC, Dice and the correlation follow the same trend. The Wasserstein distance seems to give slightly different information. A more in-depth real data study will bring more information on that aspect.

As shown above, the Wasserstein distance can, in certain cases, be used to deliver information that the other measures cannot. However, we would like to point out some of the actual limits of this distance and therefore some future works that could improve this measure. First, the measure computes a distance between all points of the two tractograms instead of matching fibers, which is not topologically right. A way to transport fibers from a tractogram to another should be looked into. Second, special attention must be given to the quantity of mass transported. Indeed, balanced (the same amount of mass on both sides) and unbalanced (different amounts of mass) optimal transport are two different problems, which require different solutions. In this work, balanced optimal transport is forced by normalising the tractograms densities. This can lead to unexpected situations, e.g. with the degradation experiment, where, for a high percentage of degradation, we force an entire tractogram to be transported onto a few fibers.

In conclusion, we have proposed, in this work, a comparative analysis, both on synthetic data (translation, rotation, deformation, degradation) and in real circumstance, of the behavior of a few typically used tractograms evaluation measures: the Dice score, the density correlation, the percentage of valid connections and valid streamlines. We then proposed a new measure, based on optimal transport and compared its behavior against the other measures. We show that, in most cases, it can be useful to use multiple measures in conjunction since they do not correlate and thus bring different kinds of information. We also show that, although still being in development, our new Wasserstein measure can be used to compare tractograms, bringing additional information.

Fig. 1 .

 1 Fig. 1. Results for simulated data.

  1.d), VC and VS, which by nature cannot measure a degradation (as the overall shape and the endings of the bundle are not affected), are not computed. Corr and WD are almost identical (except for the curves inversion). Dice follows a different trend, possibly leading to more information. In addition, ρ(W D, Corr) = 0.51 and

Fig. 2 .

 2 Fig. 2. Resulting tractograms for each algorithm. From left to right and top to bottom : the ground truth, Mrtrix IFOD2, Trekker and Dipy PFT. And from left to right in each case : the CST, the OR and the SLF

Table 1 .

 1 Results for real data experiment. Red text denotes results for IFOD2, blue for Trekker, black for Dipy PFT.

		Dice	Dens. corr.	WD	VS (%)
	CST 0.23/0.18/0.53 0.47/0.36/0.54 37/74/72 42/43/78
	OR	0.26/0.22/0.08 0.43/0.34/0.37 48/24/99 45/33/33
	SLF 0.29/0.15/0.04 0.55/0.20/0.38 27/16/74 50/38/24


Yoann Dieudonné

Shlomi Dolev

Franck Petit

Michael Segal

Deaf, Dumb, and Chatting Robots Enabling Distributed Computation and Fault-Tolerance Among Stigmergic Robot *

Keywords: Explicit Communication, Mobile Robot Networks, Stigmergy

We investigate ways for the exchange of information (explicit communication) among deaf and dumb mobile robots scattered in the plane. We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among the robots. We propose one-to-one deterministic movement protocols that implement explicit communication.

We first present protocols for synchronous robots. We begin with a very simple coding protocol for two robots. Based on on this protocol, we provide one-to-one communication for any system of n ≥ 2 robots equipped with observable IDs that agree on a common direction (sense of direction). We then propose two solutions enabling one-to-one communication among anonymous robots. Since the robots are devoid of observable IDs, both protocols build recognition mechanisms using the (weak) capabilities offered to the robots. The first protocol assumes that the robots agree on a common direction and a common handedness (chirality), while the second protocol assumes chirality only. Next, we show how the movements of robots can provide implicit acknowledgments in asynchronous systems. We use this result to design asynchronous one-to-one communication with two robots only. Finally, we combine this solution with the schemes developed in synchronous settings to fit the general case of asynchronous one-to-one communication among any number of robots.

Our protocols enable the use of distributing algorithms based on message exchanges among swarms of Stigmergic robots. Furthermore, they provides robots equipped with means of communication to overcome faults of their communication device.

Introduction

Research for achieving coordination among teams (or, swarms) of mobile robots is challenging and has a great scientific and practical implications. Swarms of mobile robots are used, and are planned to be even used more, in several critical situations. Swarms provide the ability to measure properties, collect information and act in a given (sometimes dangerous) physical environment. Numerous of potential applications exist for such multi-robot systems, to name only a very few: environmental monitoring, large-scale construction, risky area surrounding or surveillance, and exploration of awkward environments.

In a given environment, the ability for the swarm of robots to succeed in the accomplishment of the assigned task greatly depends on the capabilities the robots have, that is, their moving capacities and sensory organs. Existing technologies allow to consider robots equipped with sensor devices for vision (camera, radar, sonar, laser, etc.) and means of communication (wireless devices). Means of communication are even required to enable classical distributed algorithms and to achieve completion of some tasks like information relay, surveillance, or intelligence activities.

An interesting question is "What happens if the means of communication are lost or not exist?" In that case, the robots can observe the location of the robots but cannot communicate with them. Such robots are called deaf and dumb. There are numerous realistic scenarios where there is no mean to communicate. Such scenarios are easy to figure out, e.g.,

• wireless devices are faulty;

• the robots evolve in zones with blocked wireless communication, e.g., hostile environments where communication are scrambled or forbidden;

• physical constraints prevent to fit out any wireless device on the robots.

The latter can arise for instance when no space is available on the robots or the robots are too small with respect to the size of the wireless device. This would be the case with swarms of nano-robots. As a matter of fact, the question of solving distributed tasks with swarms of deaf and dumb robots is not a novel one. This question has been extensively carried in different fields of computed science such as artificial intelligence [START_REF] Matarić | Issues and approaches in the design of collective autonomous agents[END_REF], control theory [START_REF] Fukuda | Approach to the dynamically reconfigurable robotic sytem[END_REF][START_REF] Noreils | An architecture for cooperative and autonomous mobile robots[END_REF][START_REF] Kube | Task modelling in collective robotics[END_REF], and recently in the distributed computing field [START_REF] Suzuki | Distributed anonymous mobile robots -formation of geometric patterns[END_REF][START_REF] Prencipe | Distributed Coordination of a Set of Autonomous Mobile Robots[END_REF]. Some of these approaches are inspired of biology studies of the animal behavior, mainly the behavior of social insects [START_REF] Beckers | From local actions to global tasks: Stigmergy and collective robotics[END_REF]. Indeed, these social systems present an intelligent collective behavior although they are composed by simple individuals with extremely limited capabilities. Solutions to problems "naturally" emerge from the self-organization and indirect communication of these individuals. The capacity to communicate using such indirect communication (or, implicit communication) is referred to as stigmergy in the biological literature [START_REF] Grassé | La reconstruction du nid et les coordinations inter-individuelles chez bellicositermes natalensis et cubitermes sp. la theorie de la stigmergie: Essai dinterpretation des termites constructeurs[END_REF]. There are numerous examples of such indirect communication in nature, for instance from ants and termites communicating using pheromones or from bees, communicating performing waggle dances to find shortest paths between their nest and food sources. The question of whether the waggle of bees is a language or not is even an issue [START_REF] Wenner | Anatomy of a Controversy: the Question of a "Language" Among Bees[END_REF].

However, stigmergy allows to make a given task only. Communications are not consider as a task by itself. In other words, the stigmergic phenomenon provides indirect communication, a guidance for a specific work. Even if, sometime stigmergy allows insects to modify their physical environmentthis phenomenon is sometime referred to as sematectonic stigmergy [START_REF] Wilson | Sociobiology[END_REF]-stigmergy never provides a communication task by itself. In other words, stigmergy does not allow tasks as chatting, intelligence activities, or sending information which are not related with a given task.

In this paper, we investigate ways for the exchange of information among deaf and dumb mobile robots scattered in the plane. In the sequel, we refer to this task as explicit communicationsometime, also referred to as direct communication [START_REF] Matarić | Issues and approaches in the design of collective autonomous agents[END_REF]. Explicit communication enables the use of distributed algorithms among the robots. We study the possibility to solve this problem deterministically when robots are communicating only by moving with respect to certain capabilities, namely synchrony, identities, sense of orientation, and chirality.

Contribution. We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages between deaf and dumb robots. We propose six one-to-one deterministic protocols that implement explicit communication.

We first present four protocols for synchronous robots. We begin with a very simple protocol for two robots, showing how high-level information can be coded by simple moves. Based on this protocol, we provide one-to-one communication into any system of n ≥ 2 robots equipped with observable IDs that agree on a common direction (sense of direction). We then propose two solutions enabling one-to-one communication among anonymous robots. Since the robots are devoid of observable IDs, both protocols build recognition mechanisms using the (weak) capabilities offered to the robots. The third algorithm assumes that the robots have sense of direction and agree on a common handedness (chirality). The fourth protocol assumes chirality only.

In synchronous systems, since every robot is active at each time instant, there is no concern with the receipt of the messages. Indeed, every movement is seen by every robot. As a consequence, no message acknowledgment is required. By contrast, in asynchronous settings, in each computation steps, some robots can be inactive. Thus, few robot movements can be missed out, and as a consequence, some messages. We show how the robot movements can provide implicit acknowledgments in asynchronous settings. We use this result in the design of asynchronous one-to-one communication with two robots only. Finally, we combine this solution with the schemes developed in synchronous settings to fit the general case of asynchronous one-to-one communication among any number of robots.

Note that our protocols-either synchronous or asynchronous-can be easily adapted to implement efficiently one-to-many or one-to-all explicit communication. Also, in the context of robots (explicitely) communicating by means of communication (e.g., wireless), since our protocols allow robots to explicitly communicate even if their communication devices are faulty, in a very real sense, our solution can serve as a communication backup, i.e., it provides fault-tolerance by allowing the robots to communicate without means of communication (wireless device).

Related Work. The issue of handling swarms of robots using deterministic distributed algorithm was first studied in [START_REF] Suzuki | Agreement on a common x-y coordinate system by a group of mobile robots[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots -formation of geometric patterns[END_REF]. Beyond supplying formal correctness proofs, the main motivation is to understand the relationship between the capabilities of the robots and the solvability of given tasks. For instance, "Assuming that the robots agree on a common direction (having a compass), which tasks are they able to deterministically achieve?", or "What are the minimal condition to elect a leader deterministically?"

As a matter of fact, the motivation turns out to be the study of the minimal level of ability the robots are required to have in the accomplishment of some basic cooperative tasks in a deterministic way. Examples of such tasks are specific problems, so that pattern formation, line formation, gathering, spreading, and circle formation-refer for instance to [START_REF] Suzuki | Distributed anonymous mobile robots -formation of geometric patterns[END_REF][START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF][START_REF] Defago | Circle formation for oblivious anonymous mobile robots with no common sense of orientation[END_REF][START_REF] Prencipe | Distributed Coordination of a Set of Autonomous Mobile Robots[END_REF][START_REF] Cieliebak | Solving the robots gathering problem[END_REF][START_REF] Prencipe | Distributed algorithms for autonomous mobile robots[END_REF][START_REF] Dieudonné | Circle formation of weak mobile robots[END_REF][START_REF] Cohen | Local spreading algorithms for autonomous robot systems[END_REF] for this problems,-or more "classical" problems in the field of distributed systems, such that leader election [START_REF] Prencipe | Distributed Coordination of a Set of Autonomous Mobile Robots[END_REF][START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF][START_REF] Flocchini | Pattern formation by autonomous robots without chirality[END_REF][START_REF] Dieudonné | Deterministic leader election in anonymous sensor networks without common coodinated system[END_REF]. To the best of our knowledge, no previous work addresses the problem of enabling explicit communication in swarms of robots.

Roadmap. In the next section, we describe the model and the problem considered in this paper. The two following sections (Section 3 and 4) are devoted to synchronous and asynchronous settings, respectively. (Due to the lack of space, proofs are given in the appendix.) Finally, we make some concluding remarks in Section 5. In the same section, extensions and open problems are also discussed.

Preliminaries.

In this section, we first define the distributed system considered in this paper. We then state the problem to be solved.

Model. We adopt the model introduced in [START_REF] Suzuki | Agreement on a common x-y coordinate system by a group of mobile robots[END_REF], below referred to as Semi-Synchronous Model (SSM). The distributed system considered in this paper consists of n mobile robots (agents or sensors). Any robot can observe, compute and move with an infinite decimal precision. The robots are equipped with sensors enabling to detect the instantaneous position of the other robots in the plane. Viewed as points in the Euclidean plane, the robots are mobile and autonomous. There is no kind of explicit communication medium.

Each robot r has its own local x-y Cartesian coordinate system with its own unit measure. Given an x-y Cartesian coordinate system, the handedness is the way in which the orientation of the y axis (respectively, the x axis) is inferred according to the orientation of the x axis (resp., the y axis). The robots are assumed to have the ability of chirality, i.e., the n robots share the same handedness. We consider non-oblivious robots, i.e., every robot can remember its previous observations, computations, or motions made in any previous step.

We assume that the system is either identified or anonymous. In the former case, each robot r is assumed to have a visible (or, observable) identifier denoted id r such that, for every pair r, r ′ of distinct robots, id r = id r ′ . In the latter, no robot is assumed to have a visible identified. In this paper, we will also discuss whether the robots agree on the orientation of their y-axis or not. In the former case, the robots are said to have the sense of direction. (Note that since the robots have the ability of chirality, when the robots have the sense of direction, they also agree on their x-axis).

Time is represented as an infinite sequence of time instants t 0 , t 1 , . . . , t j , . . . Let P (t j ) be the set of the positions in the plane occupied by the n robots at time t j (j ≥ 0). For every t j , P (t j ) is called the configuration of the distributed system in t j . P (t j ) expressed in the local coordinate system of any robot r i is called a view. At each time instant t j (j ≥ 0), each robot r i is either active or inactive. The former means that, during the computation step (t j , t j+1 ), using a given algorithm, r i computes in its local coordinate system a position p i (t j+1 ) depending only on the system configuration at t j , and moves towards p i (t j+1 )-p i (t j+1 ) can be equal to p i (t j ), making the location of r i unchanged. In the latter case, r i does not perform any local computation and remains at the same position.

The concurrent activation of robots is modeled by the interleaving model in which the robot activations are driven by a uniform fair scheduler. In this paper, we discuss whether the system is synchronous or asynchronous. In the former case, every robot is active at each instant. The latter means that at least one robot is required to be active at each instant.

In every single activation, the distance traveled by any robot r is bounded by σ r . So, if the destination point computed by r is farther than σ r , then r moves toward a point of at most σ r . This distance may be different between two robots.

Problem. Indirect communication is the result of the observations of other robots. Using indirect communication, we aim to implement Direct communication, that is a purely communicative act, one with the sole purpose of transmitting messages [START_REF] Matarić | Issues and approaches in the design of collective autonomous agents[END_REF]. In this paper, we consider directed communication that aim at a particular receiver. Such communication are said to be one-to-one, specified as follows: (Emission) If a robot r wants to send a message m to a robot r ′ , then r eventually sends m to r ′ ; (Receipt) Every robot eventually receives every message which is meant to it. Note that the above specification induces that r is able to address r ′ . This implies that any protocol solving the above specification have to come up with (1) Routing mechanism and (2) Naming mechanism, the latter, in this context of anonymous robots.

The specification also induces that the robots are able to communicate explicit messages. So, any one-to-one communication protocol in our model has to be able (3) to code explicit messages with implicit communication, i.e., with (non-ambiguous) movements.

One-to-One Communications in Synchronous Settings

It is well-known that in synchronous systems, Emission and Receipt properties are easily verified. Thus, we focus on the three additional properties described above. We first present a solution working for two robots only that shows how explicit information can be easily coded making moves. The second protocol addresses Routing property. Combined with the simple coding mechanism, it provides one-to-one communication into any system of n ≥ 2 robots equipped with observable IDs and sense of direction. Our third and fourth solutions deal with anonymous networks. Since the robots are devoid of observable IDs, both protocols provide Naming mechanism, i.e., they build recognition mechanisms using the capabilities offered to the robots. The third algorithm assumes that the robots have sense of direction. The last one assumes robots with chirality only (no common sense of direction).

Coding With Two Robots

Each even step t i → t i+1 (i = 2p, p ≥ 0) is used by each robot to send a bit in {0, 1}. To send "0" ("1", respectively) to the other robot r ′ , a robot, r, moves on its right (left, resp.) with respect to the direction given by r ′ -refer to Figure1. To avoid that the robots do not go either too far or near of each other, each odd step t i+1 → t i+2 is used by the robots to come back to its first position. Note that this simple protocol is silent [START_REF] Dolev | Memory requirements for silent stabilization[END_REF] in the following sense: a robot eventually moves if it has some messages to transmit. Also, note that if each robot r knows the maximum distance σ r ′ that the other robot r ′ can cover in one step, then, the protocol can easily be adapted to reduce the number of moves made by the robots to send bytes. In that case, the total distance 2σ r ′ made by r ′ on its right and its left can be divided by the number of possible bytes send by the robots. Then, r ′ moves on its right or on its left of a distance corresponding to the byte sent.

Routing With Identified Robots Having Sense Of Direction

First, for each robot being a priori surrounded of several robots, our method requires to include a mechanism avoiding collisions. Next, it must include a technique allowing any robot to send messages to a specific robot. In order to deal with the collision avoidance, we use the following concept, Voronoi diagram, in the design of our method. Definition 3.1 (Voronoi diagram) [START_REF] Aurenhammer | Voronoi diagrams-a survey of a fundamental geometric data structure[END_REF] The Voronoi diagram of a set of points P = {p 1 , p 2 , • • • , p n } is a subdivision of the plane into n cells, one for each point in P . The cells have the property that a point q belongs to the Voronoi cell of point p i iff for any other point p j ∈ P , dist(q, p i ) < dist(q, p j ) where dist(p, q) is the Euclidean distance between p and q. In particular, the strict inequality means that points located on the boundary of the Voronoi diagram do not belong to any Voronoi cell.

Our protocol requires the two following preprocessing steps-executed at time t 0 :

1. Each robot computes the Voronoi Diagram, each Voronoi cell being centered on a robot position-refer to Case (a) in Figure 2, the plain line. Every robot is allowed to move into its Voronoi cell only. This ensures the collision avoidance.

2. For each associated Voronoi cell c r of robot r, each robot r computes the corresponding granular g r , the largest disc of radius R r centered on r and enclosed in c r -Case (a) in Figure 2, the dotted lines. Notice that the radii of different disks might be different. Each granular is sliced into 2n slices, i.e., the angle between two adjacent diameters is equal to π n . Each diameter is labeled from 0 to n -1, the diameter labeled by 0 being aligned on the North, the other are numbered in the natural order following the clockwise direction.

Note that since the robots share a common handedness (chirality), they all agree on the same clockwise direction. Having a common sense of direction, they all agree on the same granular and slice numbering. Once these two preprocessing steps are done, the protocol follows a similar scheme as the case with two robots: when a robot r wants to send a bit to any robot r ′ , to send 0 (resp., 1), r moves inside g r on the Northern/Eastern/North-Eastern (resp., Southern/Western/South-Western) side on the diameter labeled r ′ . Next, it comes back to its first position, i.e., the center of g r .

Naming With Anonymous Robots Having Sense Of Direction

It may seem difficult to send a message to a specific robot since no robot has an observable ID. However, it is shown in [START_REF] Flocchini | Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots[END_REF] that if the robots have sense of direction and chirality, then they can agree on a total order over the robots. This is simply obtained as follows: Each robot r labels every observed robot with its local xy coordinate in the local coordinate system of r. Even if the robots do not agree on their metric system, by sharing the same x-and y-axes, they agree on the same order.

Naming With Anonymous Robots Without Sense Of Direction

By contrast to the previous case, with the lack of sense of direction, the robots cannot deterministically agree on a common labeling of the cohort. For instance, in Figure 3, the symmetry of the configuration prevent the robots to decide on a common naming, even with the ability of chirality. We now describe our method in the design of a relative (w.r.t. each robot) naming allowing to implement one-to-one communication for anonymous robots having no common sense of direction. We refer to Figure 4 to explain our scheme.

Our method starts (at t 0 ) with the two preprocessing steps describe above. At the end we have the Voronoi Diagram and the sliced granulars-to avoid useless overload in the figure, the latter are omitted in Figure 4. Then, still at time t 0 , each robot r computes the smallest enclosing circle, denoted by SEC, of the robot positions. Note that since the robots have the ability of chirality, then they can agree on a common clockwise direction of SEC. Note that SEC is unique and can be computed in linear time [START_REF] Megiddo | Linear-time algorithms for linear programming in 3 and related problems[END_REF].

Next, r considers the "horizon line", denoted by H r , as the line passing through itself and O, the center of SEC. Given H r , r consider each radius of SEC passing through a robot. The robots are numbered in the growing order following the radii in the clockwise direction starting from H r . When several robots are located on the same radius, they are numbered in the growing order starting from O. Note that this means that r is not necessary labeled by 0 if some robots are located between itself and O on its radius. An example of this preprocessing phase is shown in Figure 4 for a given robot r.

The method to send messages to a given robot is the same as the previous case. Every robot r slices its granular according to H r , the diameter corresponding to H r being labeled by 0 and so on in the clockwise direction. The sending of bit is made following the same scheme as above, the Northern being given by the direction of H r and the Eastern following the clockwise direction. Each robot addresses bits according to its relative labeling. Note first that every robot observes the movements of all the robots. So, every robot is able to know all the messages sent in the system. This could provide fault-tolerance by redundancy, any robot being able to send any message again to its addressee. Also, note that by construction, the labelling is specific to each robot. However, every robot, r, is able to compute the labelling with respect to each robot of the system. Therefore, for by observing each movement made by any robot r ′ , r is able to know to whom a bit is addressed, and in particular, to itself. Every robot is able to compute the message address, each of them being able to compute the relative naming of all the robots.

One-to-One Communications in Asynchronous Settings

In synchronous systems, since every robot is active at each time instant, there is no concern with the receipt of the messages. Indeed, every robot motion is seen by every robot. As a consequence, no message acknowledgment is required. By contrast, in asynchronous settings, only fairness is assumed, i.e., in each computation steps, some robots can remain inactive. So, some robots motions can be lost, and by the way, some messages. Therefore, asynchronous settings require a synchronization mechanism ensuring the acknowledgment of each message sent.

In this section, we mainly focus on the both Emission and Receipt properties. We first state the two following results-due to the lack of space, the proof of Lemma 4.1 is given in this appendix: Lemma 4.1 Let r and r ′ be two robots. Assume that r always moves in the same direction each time it becomes active. If r observes that the position of r ′ has changed twice, then r ′ must have observed that the position of r has changed at least once.

Proof.

By contradiction, assume that at time t i , r notes that the position of r ′ has changed twice and r ′ has not observed that the position of r has changed at least once. Without loss of generality, we assume that t i is the first time for which r notes that the position of r ′ has changed twice. So at time t i , r knows three distinct positions of r ′ and t i ≥ 2. Let p j be the last (or the third) position of r ′ that r has observed, and t j the first time instant for which p j is occupied by r ′ . Obviously, t j < t i . Now we have two cases to consider :

• case 1 : t j = t i -1 . The fact that r knows three distinct positions of r ′ implies that r is become active and has moved at least twice between t = 0 and t = t i -1 and, thus at least once between t = 0 and t = t i -2. Consequently, at time t j = t i -1, r ′ would have noted that r's position has changed at least once. Contradiction.

• case 2 : t j ≤ t i -2. We have two cases to consider :

-case a : r ′ moves at least once between t j + 1 and t i -1. In that case, r notes that the position of r ′ has changed twice before time t i : that contradicts the fact that t i is the first time for which r notes that the position of r ′ has changed twice.

-case b : r ′ does not move between t j + 1 and t i -1. As mentioned above, the fact that r knows three distinct positions of r ′ implies that r is become active and has moved at least twice between t = 0 and t = t i -1. However, r ′ does not move between t j + 1 and t i -1. Hence, r has moved at least twice between t = 0 and t = t j and, thus at least once between t = 0 and t = t j -1. So, at time t j r ′ would have noted that r's position has changed at least once. Contradiction.

2

Corollary 4.2 Let r and r ′ be two robots. Assume that r always moves in the same direction on a line l as soon as it becomes active. If r observes that the position of r ′ has changed twice, then r ′ knows the line l and the direction toward which r moved.

One-to-One Communications With Two Asynchronous Robots

Both robots follow the same scheme, in the sequel referred to as Protocol Async 2 . Each time a robot, let us say r, becomes active, it moves in the opposite direction of the other robot, r ′ . Let us call this direction the N orth r . Robot r behaves like this while it has nothing to send to r ′ . As soon as r observes that the position of r ′ changed twice, by Corollary 4.2, r is guaranteed that r ′ knows the line H and the direction on which r has moved. Let us call the line H the horizon line. Note that since the two robots follow the same behavior, H is common to both of them and their respective North are oriented in the opposite direction. From this point on, r can start to send messages to r ′ . When r wants to send a bit "0" ("1", respectively) to r ′ , r moves along a line perpendicular to on the Est side (West side, resp.) of H with respect to N orth r . It then move in the same direction each time it becomes active until it observes that the position of r ′ has changed twice. At this moment on, from Lemma 4.1, r knows that r ′ has seen it in its Est side. Then, r comes back on H. Once r is located on H, it starts to move again toward the N orth r direction until it observes that r ′ has moved twice. In this way, if Robot r wants to communicate another bit (following the same scheme), it is allowed to move on its East or West side again. So, the new bit and the previous bit are well distinguished by Robot r ′ even if they have the same value. An example of our scheme is shown in Figure 5.

Note that by Lemma 4.1, Protocol Async 2 ensures the Receipt property provided the following condition: r observed that the position of r ′ changed twice before any direction change. We now show that Protocol Async 2 ensures this condition. Lemma 4.4 Let r and r ′ be two robots. In every execution of Protocol Async 2 , r observes that the position of r ′ changes infinitely often.

Proof.

Assume by contradiction that, there exists some executions of Protocol Async 2 such that, eventually, r observes that that position of r ′ remains unchanged. Consider the suffix of such an execution where r observes that the position of r ′ remains unchanged. Assume that r ′ is eventually motionless. By fairness and Remark 4.3, this case is impossible. So, r ′ moves infinitely often. Thus, each time that r observes r ′ , r ′ is at the same position. There are two cases to consider:

1. Robot r ′ eventually sends no bit. In that case, by executing Protocol Async 2 , r ′ moves infinitely often in the same direction on H. Which contradicts that each time that r observes r ′ , r ′ at the same position.

2. Robot r ′ sends bits infinitely often. Since r ′ is at the same position each time r observes it, r ′ goes in a direction and comes back at the same position infinitely often. So, from Protocol Async 2 , r ′ observed that the position of r changed twice infinitely often (each time r ′ changes its direction). By Lemma 4.1, each time r ′ observes that the position changed twice, r observes that the position of r ′ has changed at least once. A contradiction.

2

Lemmas 4.1 and 4.4 ensures that Protocol Async 2 ensures the Receipt property. Furthermore, Lemma 4.4 ensures that no robot is starved sending a bit (i.e., it can change its direction infinitely often). So, Property Emission is guaranteed by Protocol Async 2 . That leads to the following theorem: Theorem 4.5 Protocol Async 2 implements one-to-one explicit communication for two robots.

However, this scheme has the drawback of making the two robots moving away infinitely often of each other. To deal with this drawback, the two robots can alternate their direction on H each time they send a new bit. Lemmas 4.1 and 4.4 ensure that no bit would be missed. However, with this protocol, the robots can collide together. To avoid that the robots neither collide, they can divide the covered distance by x > 1 in each move. This introduces another drawback: the robots are required to be able to move an infinitesimally small distance. This is also the main drawback of the protocol of any number of robots in the next subsection.

One-to-One Communication For Any Number Of Anonymous Asynchronous Robots

We now combine the previous method with the one developed in Section 3. In the following, we describe our method assuming anonymous robots , devoid of sense of direction, i.e., the weakest assumptions made in Section 3. Obviously, our method is also compatible with extra assumptions, namely IDs or sense of direction. We assume that the robots knows P (t 0 ), i.e., the positions of the robots are known by every robot in t 0 or all the robots are awake in t 0 . Using P (t 0 ), when a robot wakes for the time (possibly after t 0 ), it computes all the preprocessing steps, including the computation of SEC. The only difference is that the granular is sliced in n + 1 slices-instead of n slices as in the synchronous case. Consider that the extra slice, corresponding to H r , the diameter being on radius of SEC passing through r) is not assigned to a particular robot. Let us call this slice κ. In our method, κ plays the role of the horizon line H as for the case with two robots-refer to Figure 6. That is, each robot moves on its respective κ to indicate that it has no bit to transmit. Thus, for every robot r, Protocol Async n works as follows:

1. If r wants to send a bit to a robot r ′ , then if r is not at the center of its granular then it comes back on this latter one. Then, r moves on the Northern/Estern/North-Estern (resp., Southern/Western/South-Western) side on the diameter labelled with r ′ . It then moves in the same direction on the diameter labelled r ′ each time it becomes active. To make sure that all the robots observed its movement, r moves in the same direction until it observes that the position of every robot changed twice. Next, r comes back to the center of its granular (i.e., its initial position in P (t 0 ) by moving along the same slice. Finally, it moves in the same direction on κ avoiding to reach the border of its granular before it observes that the position of every robot changed twice. In this way, it is now allowed to send a new bit by following the same scheme and we are sure that the new bit and the previous bit are well distinguished by Robot r ′ even if they have the same value.

2. If r does not want to send a bit, then while r does not want to send any bit, it moves in the same direction on κ avoiding to reach the border of its granular before it observes that the position of every robot changed twice. When the latter occurs, it moves on the opposite direction, and so on. If eventually, r wants to send a bit, then it comes back toward the center following the same rule as the first case.

Note that in both case, while a robot is moving toward a direction (on a slice), it must avoid to reach either the border or the center of the granular. In order to implement this constraint, it is required the robots divide the covered distance by x > 1 in each move. Also, as for the synchronous case, every robot is able to read every message sent by any robot r to any robot r ′ , enabling a kind of redundancy.

By applying the same reasoning as in Subsection 4.1 for every pair of robots, we can claim:

Theorem 4.6 Protocol Async n implements one-to-one explicit communication for two robots.

Concluding Remarks, Extensions, and Open Problems

In this work we proposed (deterministic) movement protocols that implement explicit communication, and therefore allow the application of (existing) distributed algorithms; distributing algorithms that use message exchanges. Movements-signals are introduced as a mean to transfer messages between deaf and dumb robots. The movement protocols can serve as a backup to other means of (e.g., wireless) communication.

In this paper we first presented protocols for synchronous robots. Some of them assume that the robots are equipped with observable IDs and that the robots agree on a common direction. We also proposed protocols enabling one-to-one communication among anonymous robots by building recognition mechanisms assuming the robots share a common handedness only. Note that the robots may decide to flock in a certain direction, subtracting the agreed upon global flocking movement in order to preserve the relative movements used for communication.

We have adapted the protocols developed in synchronous settings to fit the general case of asynchronous one-to-one communication among any number of robots.

Next, we list several notable extensions and open problems.

Silent, Finite Movements and Discrete Computation. We call the ability for a communication protocol to be silent when a robot eventually moves if it has some message to transmit. Note that this desirable property would help to save energy resources of the robots. The protocols proposed with synchronous settings (Section 3) are clearly silent. Our asynchronous solutions are not silent (Remark 4.3). The question of whether the design of silent asynchronous algorithms is possible or not is open. A related issue concerns the distance (eventually) covered by the robots. In this paper, we could not overcome either infinite growing distance or infinitely decreasing distance. As a matter of fact, we believe that the fact that an asynchronous robot that sequentially observes another robot at the same place, cannot determine whether the robot moved and returned to the same position or did not move at all, implies an impossibility for a communication by a finite number of moves.

Computations with an infinite decimal precision is different and, in a way, weaker assumption than infinitely small movements. Indeed, one can assume infinite decimal precision with the "reasonable" assumption of finite movements, i.e., with a minimal and maximal distance covered in one atomic step, or even step over a grid. In this paper, we assumed a maximal covered distance (σ r ), but not a minimal covered distance. This would be the case by assuming that the plane is either a grid or a hexagonal pavement [START_REF] Gordon | Discrete bee dance algorithms for pattern formation on a grid[END_REF]. For instance, with such assumption, the robots could be prone to make computation errors due to round off, and, therefore, face a situation where robots are not able to identify all of possible 2n directions obtained by slices inside of disks and are limited to recognize only a certain number of directions. This case could be solved by avoiding the use of 2n slices of granular by transmitting the index of the robot to whom the message intended following the message itself. For this we would need only k + 1, 1 ≤ k < 2n segments (or 2k + 1 slices). In particular, we would use one segment for message transmission (as in the case of two robots); using the other k segments the robot who wants to transmit a message allows to transmit the index of the robot to whom the message is designated. Definitely, such index can be represented by log n log k = log k n symbols. Notice, this strategy would slow down the algorithm and increase the number of steps required to transmit a message. More precisely, the number of steps required in this method to identify the designated robot is log k n. For example, by taking O(log n) slices instead of O(n), the number of steps to transmit a message would increase by O( log n log log n ).

Partial synchrony. In the continuity of the above discussion, an other important feature in the field of mobile robots is the weakness/strength of the model. For instance, in this paper, we used the semi-synchronous model (SSM). It would be interesting to achieve solutions by relaxing synchrony among the robots to achieve solutions into a fully asynchronous model (e.g., , CORDA [START_REF] Prencipe | Distributed Coordination of a Set of Autonomous Mobile Robots[END_REF]).

Visibility. Another issue would the visibility capability of the robots [START_REF] Flocchini | Gathering of autonomous mobile robots with limited visibility[END_REF]. For instance, the following question could be investigated: "Can one-to-one communication be achieved by a team of robots with limited visibility?" With the same approach, the problem of explicit communication could be addressed assuming that the amount of memory the robots are equipped with is bounded.

Stabilization. Stabilization [START_REF] Dolev | Self-Stabilization[END_REF] would be a very desirable property to enable. It seems that, in our case, stabilization can be achieved in the synchronous case by carefully adapting the protocols proposed in Section 3; say by assuming a global clock (using GPS input) returning to the initial location and (re)computing the prepossessing phase every round timestamp. The self-stabilization property for the asynchronous case requires further study.

Figure 1 :

 1 Figure 1: One-to-one communication for 2 synchronous robots.

  An example showing the system with 12 robots, viewed by each robot after the two preprocessing phases. Robot 9 sends either "0" or "1" to Robot 3.

Figure 2 :

 2 Figure 2: One-to-one communication with n identified robots having sense of direction.

Figure 3 :

 3 Figure3: A symmetric example where six robots are scattered in the plane in such a way that for every robot, there is another robot having the same view-the arrows show the local x-y coordinate system of the each robot. They are not able to agree on a common direction nor a common naming.

Figure 4 :

 4 Figure 4: An example showing how the relative naming is built with respect to Robot r.

Figure 5 :Remark 4 . 3

 543 Figure 5: Asynchronous one-to-one communication for 2 robots. Robot r sends "001 . . .", Robot r ′ sends "0 . . .".

Figure 6 :

 6 Figure 6: An example showing how the granular is sliced with respect to r.

The work of Shlomi Dolev and Michael Segal has been partially supported by US Air Force grant.