Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
Concerning the coordination of autonomous mobile robots, the main focus has been on the important class of <italic>Pattern Formation</italic> problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied...
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | article |
| Langue: | EN |
| Publié: |
IEEE
2021
|
| Sujets: | |
| Accès en ligne: | https://doaj.org/article/f0cedc8b802543eba4cbfa4d48a001e3 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| Résumé: | Concerning the coordination of autonomous mobile robots, the main focus has been on the important class of <italic>Pattern Formation</italic> problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied in the continuous environment (e.g., the Euclidean plane), whereas few results exist when robots move in a discretization of the plane, like infinite grids. In this environment, to form any pattern, the problem of breaking symmetries emerges. Breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. It may even happen that before obtaining the requested asymmetric configuration, most of the robots must be moved. Due to the asynchrony of robots, this fact greatly increases the difficulty of the problem. We assume very weak robots moving on any regular tessellation graph as a discretization of the Euclidean plane, and we devise an algorithm <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{break}}$ </tex-math></inline-formula> able to solve the <italic>Symmetry Breaking</italic> problem on both the square and triangular grids. It is important to note that <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{break}}$ </tex-math></inline-formula> is proposed so that it can be used as a module for solving more general problems. As a case study, we use <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{break}}$ </tex-math></inline-formula> to deal with the <italic>Line Formation</italic> problem, where <inline-formula> <tex-math notation="LaTeX">$n\ge 3$ </tex-math></inline-formula> robots must arrange themselves to occupy <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> contiguous vertices along a grid line. In this respect, we first provide an algorithm <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{LF}^{-}}$ </tex-math></inline-formula> able to partially solve this problem (it works with configurations in which it is not necessary to break symmetries), and then we show how <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{break}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{LF}^{-}}$ </tex-math></inline-formula> can be combined to form <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{LF}}$ </tex-math></inline-formula>. We provide a complete characterization of the solvability of the <italic>Line Formation</italic> problem on the considered topologies by showing that <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}_{{LF}}$ </tex-math></inline-formula> solves the problem in each configuration where this is possible. |
|---|