Computing multirobot paths for joint measurement gathering

Multirobot systems represent a major sub-field of mobile robotics whose challenges have received a growing attention from researchers in the last few years. Specifically, the problem of performing joint measurements recurs in many robotic applications, like in constructing communication maps from signal strength samples gathered on the field, and in localization and positioning systems. In this work, we consider an environment represented by a metric graph where a team of robots has to perform a given pre-specified set of joint measurements, which represent the locations where information gathering is needed. The aim of this thesis is to solve one fundamental problem emerging from this scenario: seeking joint paths for the robots to perform all the required measurements at minimum cost. We 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 has 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. Extensive experiments show that our algorithms perform well in practice, also when compared to an ad hoc method taken from the literature.

I sistemi multirobot rappresentano un'importante area di ricerca nel campo della robotica, e stanno ricevendo sempre maggiore attenzione dai ricercatori. In particolare, il problema di eseguire misurazioni congiunte ricorre in molte applicazioni, come nella costruzione di mappe di comunicazione derivanti dal rilevamento di campioni di potenza del segnale, oppure nei sistemi di localizzazione e posizionamento. In questo lavoro, consideriamo un ambiente rappresentato da un grafo metrico in cui una squadra di robot deve eseguire un insieme pre-specificato di misurazioni congiunte, rappresentate dai punti fra i quali è richiesta l'acquisizione di informazioni. Lo scopo di questa tesi è risolvere uno dei problemi fondamentali che emergono da questo scenario: trovare percorsi congiunti per permettere ai robot di eseguire le misurazioni richieste a costo minimo. Proviamo che il problema di eseguire congiuntamente misurazioni su insiemi di vertici dati è NP-difficile quando dobbiamo minimizzare il totale della distanza percorsa oppure il tempo di completamento. Data la difficoltà di trovare percorsi ottimali in maniera efficiente, proponiamo un approccio greedy randomizzato capace di far fronte alla minimizzazione di entrambi gli obiettivi. Numerosi esperimenti dimostrano che i nostri algoritmi hanno buone prestazioni, anche quando confrontati con metodi ad hoc proposti in letteratura.