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, 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