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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Serafino Cicerone
Formato:	article
Lenguaje:	EN
Publicado:	IEEE 2021
Materias:	Distributed algorithms mobile robots asynchrony pattern formation symmetry grid graphs Electrical engineering. Electronics. Nuclear engineering TK1-9971
Acceso en línea:	https://doaj.org/article/f0cedc8b802543eba4cbfa4d48a001e3
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:f0cedc8b802543eba4cbfa4d48a001e3
record_format	dspace
spelling	oai:doaj.org-article:f0cedc8b802543eba4cbfa4d48a001e32021-11-18T00:04:52ZBreaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study2169-353610.1109/ACCESS.2021.3123510https://doaj.org/article/f0cedc8b802543eba4cbfa4d48a001e32021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9590535/https://doaj.org/toc/2169-3536Concerning 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.Serafino CiceroneIEEEarticleDistributed algorithmsmobile robotsasynchronypattern formationsymmetrygrid graphsElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 147855-147873 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Distributed algorithms mobile robots asynchrony pattern formation symmetry grid graphs Electrical engineering. Electronics. Nuclear engineering TK1-9971
spellingShingle	Distributed algorithms mobile robots asynchrony pattern formation symmetry grid graphs Electrical engineering. Electronics. Nuclear engineering TK1-9971 Serafino Cicerone Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
description	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.
format	article
author	Serafino Cicerone
author_facet	Serafino Cicerone
author_sort	Serafino Cicerone
title	Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
title_short	Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
title_full	Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
title_fullStr	Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
title_full_unstemmed	Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study
title_sort	breaking symmetries on tessellation graphs via asynchronous robots: the line formation problem as a case study
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/f0cedc8b802543eba4cbfa4d48a001e3
work_keys_str_mv	AT serafinocicerone breakingsymmetriesontessellationgraphsviaasynchronousrobotsthelineformationproblemasacasestudy
_version_	1718425259608113152

Breaking Symmetries on Tessellation Graphs via Asynchronous Robots: The Line Formation Problem as a Case Study

Ejemplares similares