Optimally Gathering Two Robots

Abstract : 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.
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

http://hal.upmc.fr/hal-01575451
Contributeur : Sébastien Tixeuil <>
Soumis le : dimanche 20 août 2017 - 11:55:28
Dernière modification le : jeudi 11 janvier 2018 - 06:26:29

Fichiers

gathering_tr.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Pas de modification 4.0 International License

Identifiants

  • HAL Id : hal-01575451, version 1
  • ARXIV : 1708.06183

Collections

Citation

Adam Heriban, Xavier Défago, Sébastien Tixeuil. Optimally Gathering Two Robots. [Research Report] UPMC Sorbonne Universités. 2017. 〈hal-01575451〉

Partager

Métriques

Consultations de la notice

212

Téléchargements de fichiers

20