Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913189324652544 |
|---|---|
| author | Bramas, Quentin Kakugawa, Hirotsugu Kamei, Sayaka Lamani, Anissa Ooshita, Fukuhito Shibata, Masahiro Tixeuil, Sébastien |
| author_facet | Bramas, Quentin Kakugawa, Hirotsugu Kamei, Sayaka Lamani, Anissa Ooshita, Fukuhito Shibata, Masahiro Tixeuil, Sébastien |
| contents | We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, SUIG can be solved in the fully synchronous model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_12698 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots Bramas, Quentin Kakugawa, Hirotsugu Kamei, Sayaka Lamani, Anissa Ooshita, Fukuhito Shibata, Masahiro Tixeuil, Sébastien Distributed, Parallel, and Cluster Computing We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, SUIG can be solved in the fully synchronous model. |
| title | Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2312.12698 |