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.
|Titolo:||A journey among pairs of vertices: Computing Robots' paths for performing joint measurements|
|Parole Chiave:||multirobot systems; joint measurements|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2018|
|Enti collegati al convegno:||Artificial Intelligence|
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|