On the impact of unlimited computational power in OBLOT: consequences for synchronous robots on graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918135849811968 |
|---|---|
| author | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| author_facet | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| contents | The OBLOT model has been extensively studied in theoretical swarm robotics. It assumes weak capabilities for the involved mobile robots, such as they are anonymous, disoriented, no memory of past events (oblivious), and silent. Their only means of (implicit) communication is transferred to their positioning, i.e., stigmergic information. These limited capabilities make the design of distributed algorithms a challenging task. Over the last two decades, numerous research papers have addressed the question of which tasks can be accomplished within this model. Nevertheless, as it usually happens in distributed computing, also in OBLOT the computational power available to the robots is neglected as the main cost measures for the designed algorithms refer to the number of movements or the number of rounds required. In this paper, we prove that for synchronous robots moving on finite graphs, the unlimited computational power (other than finite time) has a significant impact. In fact, by exploiting it, we provide a definitive resolution algorithm that applies to a wide class of problems while guaranteeing the minimum number of moves and rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the impact of unlimited computational power in OBLOT: consequences for synchronous robots on graphs Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo Distributed, Parallel, and Cluster Computing The OBLOT model has been extensively studied in theoretical swarm robotics. It assumes weak capabilities for the involved mobile robots, such as they are anonymous, disoriented, no memory of past events (oblivious), and silent. Their only means of (implicit) communication is transferred to their positioning, i.e., stigmergic information. These limited capabilities make the design of distributed algorithms a challenging task. Over the last two decades, numerous research papers have addressed the question of which tasks can be accomplished within this model. Nevertheless, as it usually happens in distributed computing, also in OBLOT the computational power available to the robots is neglected as the main cost measures for the designed algorithms refer to the number of movements or the number of rounds required. In this paper, we prove that for synchronous robots moving on finite graphs, the unlimited computational power (other than finite time) has a significant impact. In fact, by exploiting it, we provide a definitive resolution algorithm that applies to a wide class of problems while guaranteeing the minimum number of moves and rounds. |
| title | On the impact of unlimited computational power in OBLOT: consequences for synchronous robots on graphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2509.04383 |