The Gathering task by means of a swarm of robots disposed on the vertices of a graph requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting sufficient condition for the feasibility, applicable to any topology. We then consider dense and symmetric graphs like complete and complete bipartite graphs where asynchronous robots cannot solve much. In such topologies we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising by the general approach with specific techniques dictated by the considered topologies.

Gathering synchronous robots in graphs: from general properties to dense and symmetric topologies

Navarra A.
2019

Abstract

The Gathering task by means of a swarm of robots disposed on the vertices of a graph requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting sufficient condition for the feasibility, applicable to any topology. We then consider dense and symmetric graphs like complete and complete bipartite graphs where asynchronous robots cannot solve much. In such topologies we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising by the general approach with specific techniques dictated by the considered topologies.
2019
978-3-030-24921-2
978-3-030-24922-9
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1470442
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact