The problem of performing joint measurements recurs in many robotic applications, like constructing communication maps from signal strength samples gathered on the field. In spite of this, a theo ry supporting efficient algorithms has not been yet developed and ad hoc methods are usually employed. In this paper. we consider an environment represented by a metric graph and prove that the problem of Jointly performing measurements from given vertices is NP-hard when either the total traveled distance or the task comp letion time have to be minimized. Given the difficulty of finding optimal paths in an efficient way, we propose a greedy randomized approach able to cope with both the optimization objectives. In settings for which joint measurements must be taken for all pairs of vertices, we prove that a deterministic greedy algorithm achieves an O(m log n) approximation factor for the traveled distance object ive, where m is the number of robots and n the number of vertices, and an O(m2 log n) approximation factor for the completion time. Experiments in simulation show that our algorithms perform well in practice, also when compared to an ad hoc method taken from the literature.

A journey among pairs of vertices: Computing Robots' paths for performing joint measurements / A. Riva, J. Banfi, C. Fanton, N. Basilico, F. Amigoni (PROCEEDINGS OF THE INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS). - In: AAMAS '18 : Proceedings[s.l] : ACM, 2018. - ISBN 9781510868083. - pp. 229-237 (( Intervento presentato al 17. convegno International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 tenutosi a Stockholm nel 2018.

A journey among pairs of vertices: Computing Robots' paths for performing joint measurements

J. Banfi;N. Basilico;
2018

Abstract

The problem of performing joint measurements recurs in many robotic applications, like constructing communication maps from signal strength samples gathered on the field. In spite of this, a theo ry supporting efficient algorithms has not been yet developed and ad hoc methods are usually employed. In this paper. we consider an environment represented by a metric graph and prove that the problem of Jointly performing measurements from given vertices is NP-hard when either the total traveled distance or the task comp letion time have to be minimized. Given the difficulty of finding optimal paths in an efficient way, we propose a greedy randomized approach able to cope with both the optimization objectives. In settings for which joint measurements must be taken for all pairs of vertices, we prove that a deterministic greedy algorithm achieves an O(m log n) approximation factor for the traveled distance object ive, where m is the number of robots and n the number of vertices, and an O(m2 log n) approximation factor for the completion time. Experiments in simulation show that our algorithms perform well in practice, also when compared to an ad hoc method taken from the literature.
multirobot systems; joint measurements
Settore INF/01 - Informatica
Artificial Intelligence
Elsevier
et al.
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Nissan
NSF
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
p229-riva.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.59 MB
Formato Adobe PDF
1.59 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/2434/631698
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact