Gathering of asynchronous robots on circle with limited visibility using finite communication
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_ | 1866914022076448768 |
|---|---|
| author | Sharma, Avisek Ghosh, Satakshi Sau, Buddhadeb |
| author_facet | Sharma, Avisek Ghosh, Satakshi Sau, Buddhadeb |
| contents | This work addresses the gathering problem for a set of autonomous, anonymous, and homogeneous robots with limited visibility operating in a continuous circle. The robots are initially placed at distinct positions, forming a rotationally asymmetric configuration. The robots agree on the clockwise direction. In the $θ$-visibility model, a robot can only see those robots on the circle that are at an angular distance $<θ$ from it. Di Luna \textit{et. al.} [DISC'20] have shown that, in $π/2$ visibility, gathering is impossible. In addition, they provided an algorithm for robots with $π$ visibility, operating under a semi-synchronous scheduler. In the $π$ visibility model, only one point, the point at the angular distance $π$ is removed from the visibility. Ghosh \textit{et. al.} [SSS'23] provided a gathering algorithm for $π$ visibility model with robot having finite memory ($\mathcal{FSTA}$), operating under a special asynchronous scheduler.
If the robots can see all points on the circle, then the gathering can be done by electing a leader in the weakest robot model under a fully asynchronous scheduler. However, previous works have shown that even the removal of one point from the visibility makes gathering difficult. In both works, the robots had rigid movement. In this work, we propose an algorithm that solves the gathering problem under the $π$-visibility model for robots that have finite communication ability ($\mathcal{FCOM}$). In this work the robot movement is non-rigid and the robots work under a fully asynchronous scheduler. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04004 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gathering of asynchronous robots on circle with limited visibility using finite communication Sharma, Avisek Ghosh, Satakshi Sau, Buddhadeb Distributed, Parallel, and Cluster Computing This work addresses the gathering problem for a set of autonomous, anonymous, and homogeneous robots with limited visibility operating in a continuous circle. The robots are initially placed at distinct positions, forming a rotationally asymmetric configuration. The robots agree on the clockwise direction. In the $θ$-visibility model, a robot can only see those robots on the circle that are at an angular distance $<θ$ from it. Di Luna \textit{et. al.} [DISC'20] have shown that, in $π/2$ visibility, gathering is impossible. In addition, they provided an algorithm for robots with $π$ visibility, operating under a semi-synchronous scheduler. In the $π$ visibility model, only one point, the point at the angular distance $π$ is removed from the visibility. Ghosh \textit{et. al.} [SSS'23] provided a gathering algorithm for $π$ visibility model with robot having finite memory ($\mathcal{FSTA}$), operating under a special asynchronous scheduler. If the robots can see all points on the circle, then the gathering can be done by electing a leader in the weakest robot model under a fully asynchronous scheduler. However, previous works have shown that even the removal of one point from the visibility makes gathering difficult. In both works, the robots had rigid movement. In this work, we propose an algorithm that solves the gathering problem under the $π$-visibility model for robots that have finite communication ability ($\mathcal{FCOM}$). In this work the robot movement is non-rigid and the robots work under a fully asynchronous scheduler. |
| title | Gathering of asynchronous robots on circle with limited visibility using finite communication |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2509.04004 |