Pattern Formation for Fat Robots with Memory
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917960246886400 |
|---|---|
| author | Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André |
| author_facet | Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André |
| contents | Given a set of $n\geq 1$ autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane, we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small $O(1)$-sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in $O(n) + O(q \log n)$ rounds with probability at least $1 - n^{-q}$. The algorithms are collision-free and do not require the knowledge of the number of robots. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_14649 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Pattern Formation for Fat Robots with Memory Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André Computational Geometry Given a set of $n\geq 1$ autonomous, anonymous, indistinguishable, silent, and possibly disoriented mobile unit disk (i.e., fat) robots operating following Look-Compute-Move cycles in the Euclidean plane, we consider the Pattern Formation problem: from arbitrary starting positions, the robots must reposition themselves to form a given target pattern. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between the two robots. We assume that a robot's movement cannot be interrupted by an adversary and that robots have a small $O(1)$-sized memory that they can use to store information, but that cannot be communicated to the other robots. To solve this problem, we present an algorithm that works in three steps. First it establishes mutual visibility, then it elects one robot to be the leader, and finally it forms the required pattern. The whole algorithm runs in $O(n) + O(q \log n)$ rounds with probability at least $1 - n^{-q}$. The algorithms are collision-free and do not require the knowledge of the number of robots. |
| title | Pattern Formation for Fat Robots with Memory |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2309.14649 |