Optimally Gathering Two Robots - Sorbonne Université Access content directly
Reports (Research Report) Year : 2017

Optimally Gathering Two Robots


We present an algorithm that ensures in finite time the gathering of two robots in the non-rigid ASYNC model. To circumvent established impossibility results, we assume robots are equipped with 2-colors lights and are able to measure distances between one another. Aside from its light, a robot has no memory of its past actions, and its protocol is deterministic. Since, in the same model, gathering is impossible when lights have a single color, our solution is optimal with respect to the number of used colors.
Fichier principal
Vignette du fichier
gathering_tr.pdf (879.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01575451 , version 1 (20-08-2017)


Attribution - NonCommercial - NoDerivatives



Adam Heriban, Xavier Défago, Sébastien Tixeuil. Optimally Gathering Two Robots. [Research Report] UPMC Sorbonne Universités. 2017. ⟨hal-01575451⟩
517 View
147 Download



Gmail Facebook X LinkedIn More