A Journey Among Pairs of Vertices: Computing Robots' Paths for Performing Joint Measurements
Alessandro Riva, Jacopo Banfi, C. Fanton, Nicola Basilico, Francesco Amigoni · 2018
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, where m is the number of robots and n the number of vertices, and an O ( m 2 log n ) approximation factor for the completion time. Experiments in simulation show that our algorithms perform well in practice, also