Paper Info
Title
A Journey Among Pairs Of Vertices: Computing Robots' Paths For Performing Joint Measurements
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 theory 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 completion 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 objective, wherem is the number of robots and n the number of vertices, and an O(m(2) logn) 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.
Year
DOI
Venue
2018
10.5555/3237383.3237423
PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18)
Keywords
Field
DocType
multirobot systems, joint measurements
Binary logarithm,Graph,Vertex (geometry),Computer science,Algorithm,Greedy algorithm,Signal strength,Robot,Task completion,Multirobot systems,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Alessandro Riva133.09
Jacopo Banfi2158.04
Carlo Fanton300.34
Nicola Basilico436438.25
F. Amigoni552.12