The gathering problem has been largely studied in the last years with respect to various basic graph topologies. The requirement is to move a team of robots initially placed at different vertices of the input graph towards a common vertex, and to let them remain at such a vertex. Robots move based on the so called Look-Compute-Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move towards one of its neighbors (Compute), and in the positive case it makes the computed move instantaneously (Move). All the phases are performed asynchronously for each robot. So far, the goal has been mainly to detect the minimal assumptions that allow to accomplish the gathering task, without taking care of any cost measure of the provided solutions. In this paper, we are interested in devising optimal algorithms in terms of total number of moves the robots have to perform in order to finalize the gathering. In particular, we consider infinite grids as input graphs, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.

### Optimal Gathering on Infinite Grids

#### Abstract

The gathering problem has been largely studied in the last years with respect to various basic graph topologies. The requirement is to move a team of robots initially placed at different vertices of the input graph towards a common vertex, and to let them remain at such a vertex. Robots move based on the so called Look-Compute-Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move towards one of its neighbors (Compute), and in the positive case it makes the computed move instantaneously (Move). All the phases are performed asynchronously for each robot. So far, the goal has been mainly to detect the minimal assumptions that allow to accomplish the gathering task, without taking care of any cost measure of the provided solutions. In this paper, we are interested in devising optimal algorithms in terms of total number of moves the robots have to perform in order to finalize the gathering. In particular, we consider infinite grids as input graphs, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.
##### Scheda breve Scheda completa Scheda completa (DC)
2014
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/1308498`
• ND
• 14
• 9