In distributed computing, many tasks have been studied involving mobile entities - also called robots - with weak capabilities. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires a snapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Compute phase), and finally moves toward a desired destination, if any (Move phase). In this context, we consider robots that have to visit a partially ordered set of locations. A solution to the problem is the assignment to each robot of a trajectory to follow in order to visit the required locations. The resolution of the task is subject to two main constraints. Robots have to minimize the energy spent to accomplish an assigned trajectory, and they have to avoid collisions among each other. The minimization of the energy is expressed in terms of the number of turns a robot has to perform in between two different locations. This equals the number of bends the assigned trajectory contains in between such locations. In general, the problem is known to require Ω(n) bends per connection, with n being the number of locations, even if considering just two robots involved. We study the case where the locations that a single robot has to visit are represented as colored points in the Euclidean plane, and only two colors are provided. This means the partial order among the locations is just based on two colors per robot. In this case, we provide a constructive solution for two robots with five bends per connection.

Energy saving and collision-free motion planning for oblivious robots

Cacciagrano, D. R.
2018-01-01

Abstract

In distributed computing, many tasks have been studied involving mobile entities - also called robots - with weak capabilities. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) cycles. During each cycle, a robot acquires a snapshot of the surrounding environment (Look phase), then executes an appropriate algorithm by using the obtained snapshot as input (Compute phase), and finally moves toward a desired destination, if any (Move phase). In this context, we consider robots that have to visit a partially ordered set of locations. A solution to the problem is the assignment to each robot of a trajectory to follow in order to visit the required locations. The resolution of the task is subject to two main constraints. Robots have to minimize the energy spent to accomplish an assigned trajectory, and they have to avoid collisions among each other. The minimization of the energy is expressed in terms of the number of turns a robot has to perform in between two different locations. This equals the number of bends the assigned trajectory contains in between such locations. In general, the problem is known to require Ω(n) bends per connection, with n being the number of locations, even if considering just two robots involved. We study the case where the locations that a single robot has to visit are represented as colored points in the Euclidean plane, and only two colors are provided. This means the partial order among the locations is just based on two colors per robot. In this case, we provide a constructive solution for two robots with five bends per connection.
2018
978-153865394-4
273
File in questo prodotto:
File Dimensione Formato  
CACCIAGRANO 2018.pdf

solo gestori di archivio

Tipologia: Versione Editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 206.41 kB
Formato Adobe PDF
206.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11581/443161
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact