Multirobot exploration of communication-restricted environments

In the last two decades, research in mobile robotics has shown that exploiting a team of cooperative robots can provide a valid alternative to the employment of human operators in carrying out repetitive, difficult, and hazardous tasks. Possible applications include warehouse management, information gathering, search and rescue, and patrolling. Such teams of robots operating in the same environment to achieve common goals are customarily referred to as multirobot systems. From a general perspective, different challenges are present in the deployment of a multirobot system for a particular application. These range from the choice (or construction) of appropriate robotic platforms to deal with low-level tasks (sensing and actuation) to the development of decision-theoretic planning tools aimed at enabling the robots to accomplish the assigned tasks with the appropriate level of autonomy. In the context of mobile robotics, decisions happening at the highest levels of abstraction imply the definition of a navigation strategy. This specifies high-level directives for driving the robots in an environment to achieve some given goals, like visiting its most "interesting" locations. This thesis is concerned with the development of new navigation strategies for teams of autonomous mobile robots in the context of a particular kind of information gathering task, namely, the exploration of unknown environments. Throughout the years, several efforts have been devoted to study coordinated multirobot exploration strategies. Frequently, the proposed coordination mechanisms work under the assumption that communication between robots is possible between any two locations of the environment. However, real operational conditions may require to deploy robots equipped only with local limited-range communication modules: for instance, think of a search and rescue mission in a collapsed building, where the pre-existing WiFi infrastructure has been destroyed. The problem of developing multirobot systems for effective exploration in presence of communication constraints, despite its remarkable practical relevance, has not yet been addressed with efforts comparable to those devoted to its "ideal" counterpart. This thesis aims at improving the state-of-the-art in multirobot exploration of communication-restricted environments by providing methods for addressing some of the key challenges which, to the best of our knowledge, are still unsolved. In particular, we present the following original contributions. First, we provide a general framework for modeling multirobot exploration in presence of communication constraints. Here, we theoretically justify some common path planning assumptions by deriving new complexity results for a class of environment discretizations widely used in mobile robotics, i.e., grids. Second, we present an exploration strategy operating under what we call recurrent connectivity constraints to a fixed control station, which are often imposed in search and rescue settings. In short, our strategy enforces the robots to be connected with the constrol station each time they gather new information from the exploration frontiers (the boundaries between known and unknown portions of environment). This allows to obtain a good trade-off between classical exploration performance metrics (like the percentage of explored area within a given time) and situational awareness at the control station. Third, we study an approach to overcome the assumption, widespreadly adopted in the literature, of overly conservative or unrealistic priors on the robots' communication capabilities. In particular, we propose coordinated navigation strategies aimed at mapping the unknown communication features of a (fully or partially) known environment. These strategies work by collecting samples for building a Gaussian Process representing a map of the radio signal strength between any two locations of the environment. Such communication maps can then be used to infer the existence of communication links in a non-conservative, yet reliable, way. Finally, we propose an algorithmic framework for computing and handling the execution of backup plans aimed at dealing with the absence of mispredicted communication links in generic information gathering missions (hence including exploration as a particular case). In particular, we formalize what we call the multirobot reconnection problem, study its computational complexity, and provide optimal and heuristic algorithms for practical settings.

Negli ultimi due decenni, la ricerca nel campo della robotica mobile autonoma ha mostrato come l'impiego di un team cooperativo di robot possa fornire una valida alternativa all'utilizzo di operatori umani nel portare a termine compiti difficili, ripetitivi e pericolosi. Le possibili applicazioni includono la gestione di magazzini, la raccolta di informazioni, le operazioni di ricerca e soccorso e quelle di pattugliamento. Tali team di robot operanti nel medesimo ambiente per raggiungere un obiettivo comune sono solitamente chiamati sistemi multirobot. Da un punto di vista generale, lo sviluppo di un sistema multirobot per una particolare applicazione presenta diverse sfide. Tra esse troviamo la scelta (o costruzione) di una piattaforma robotica appropriata per affrontare compiti di basso livello (percezione e attuazione) e lo sviluppo di strumenti di pianificazione delle decisioni per permettere ai robot di portare a termine i propri compiti con un appropriato livello di autonomia. Nel contesto della robotica mobile, le decisioni che avvengono ai livelli di maggiore astrazione implicano la definizione di una strategia di navigazione: essa specifica direttive di alto livello per muovere i robot in un ambiente in modo da raggiungere dei dati obiettivi, come visitare delle posizioni particolarmente "interessanti". Questa tesi riguarda lo sviluppo di nuove strategie di navigazione per team di robot mobili autonomi nel contesto di una particolare applicazione nell'ambito della raccolta di informazioni: l'esplorazione di ambienti ignoti. Nel corso degli anni, diversi sforzi sono stati profusi nello studio di strategie coordinate di esplorazione per sistemi multirobot. Spesso, i meccanismi di coordinamento proposti si basano sull'assunzione che la comunicazione tra due robot sia possibile tra qualsiasi coppia di punti dell'ambiente. Tuttavia, in uno scenario reale, potrebbe essere richiesto il dispiegamento di robot equipaggiati solamente con moduli di comunicazione locali con range limitato: si pensi, ad esempio, a una missione di ricerca e soccorso in un edificio collassato, in cui la preesistente infrastruttura WiFi è andata distrutta. Il problema dello sviluppo di sistemi multirobot in grado di ottenere un'efficace esplorazione in presenza di vincoli dettati dalla comunicazione, a dispetto della sua notevole rilevanza pratica, non è ancora stato affrontato con un impegno paragonabile a quello della sua controparte "ideale". L'obiettivo di questa tesi è migliorare lo stato dell'arte nell'esplorazione multirobot di ambienti in presenza di comunicazione limitata, fornendo metodi per affrontare alcune sfide chiave che, a quanto ci risulta, rimangono a oggi ancora aperte. In particolare, presentiamo i seguenti contributi originali. Per prima cosa, forniamo un framework generale in cui modellare l'esplorazione multirobot in presenza di vincoli di comunicazione. Alcune comuni assunzioni relative al problema della pianificazione del percorso sono qui giustificate derivando nuovi risultati di complessità computazionale per una classe di discretizzazione di ambienti ampiamente usata in robotica mobile, ossia le griglie. In seguito, presentiamo una strategia di esplorazione operante sotto quelli che chiamiamo vincoli di connettività ricorrente a una stazione di controllo fissa, i quali sono particolarmente adatti a uno scenario di ricerca e soccorso. In breve, la nostra strategia impone ai robot di essere connessi con la stazione di controllo ogni volta che essi raccolgono nuova informazione dalle frontiere dell'esplorazione (i confini tra ambiente noto e ignoto). Questo permette di ottenere un buon bilanciamento tra classiche misure di performance (come ad esempio la percentuale di area mappata in un dato tempo) e la possibilità di ottenere aggiornamenti tempestivi alla stazione di controllo. Successivamente, studiamo un approccio per superare l'assunzione, largamente adottata in letteratura, di conoscenze a priori riguardo le capacità di comunicazione dei robot troppo conservative o irrealistiche. In particolare, proponiamo strategie di navigazione coordinate aventi lo scopo di mappare delle caratteristiche sconosciute riguardanti la comunicazione di un ambiente noto (interamente o parzialmente). Queste strategie si basano sul collezionamento di campioni atti a costruire un Processo Gaussiano rappresentante la mappa della potenza del segnale radio tra ogni coppia di punti dell'ambiente. Tali mappe di comunicazione possono essere poi usate per inferire la presenza di link di comunicazione in modo non conservativo e tuttavia affidabile. Infine, proponiamo un framework algoritmico per calcolare e gestire l'esecuzione di piani di riserva in grado di gestire l'assenza di link di comunicazione erroneamente predetti in generiche missioni di raccolta informazioni (includendo quindi anche l'esplorazione come caso particolare). In particolare, formalizziamo quello che chiamiamo problema della riconnessione multirobot, studiamo la sua complessità computazionale e forniamo algoritmi ottimi e euristici adatti a situazioni reali.