Min-Max Gathering on Infinite Grid
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910652132491264 |
|---|---|
| author | Chakraborty, Abhinav Goswami, Pritam Ghosh, Satakshi |
| author_facet | Chakraborty, Abhinav Goswami, Pritam Ghosh, Satakshi |
| contents | Gathering is a fundamental coordination problem in swarm robotics, where the objective is to bring robots together at a point not known to them at the beginning. While most research focuses on continuous domains, some studies also examine the discrete domain. This paper addresses the optimal gathering problem on an infinite grid, aiming to improve the energy efficiency by minimizing the maximum distance any robot must travel. The robots are autonomous, anonymous, homogeneous, identical, and oblivious. We identify all initial configurations where the optimal gathering problem is unsolvable. For the remaining configurations, we introduce a deterministic distributed algorithm that effectively gathers $n$ robots ($n\ge 9$). The algorithm ensures that the robots gathers at one of the designated min-max nodes in the grid. Additionally, we provide a comprehensive characterization of the subgraph formed by the min-max nodes in this infinite grid model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11966 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Min-Max Gathering on Infinite Grid Chakraborty, Abhinav Goswami, Pritam Ghosh, Satakshi Distributed, Parallel, and Cluster Computing Gathering is a fundamental coordination problem in swarm robotics, where the objective is to bring robots together at a point not known to them at the beginning. While most research focuses on continuous domains, some studies also examine the discrete domain. This paper addresses the optimal gathering problem on an infinite grid, aiming to improve the energy efficiency by minimizing the maximum distance any robot must travel. The robots are autonomous, anonymous, homogeneous, identical, and oblivious. We identify all initial configurations where the optimal gathering problem is unsolvable. For the remaining configurations, we introduce a deterministic distributed algorithm that effectively gathers $n$ robots ($n\ge 9$). The algorithm ensures that the robots gathers at one of the designated min-max nodes in the grid. Additionally, we provide a comprehensive characterization of the subgraph formed by the min-max nodes in this infinite grid model. |
| title | Min-Max Gathering on Infinite Grid |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2410.11966 |