Development and analysis of algorithms for information-gathering in autonomous mobile robotics

The gathering of information is a problem that implicitly appears in a large number of autonomous mobile robotics tasks. Some examples are exploration, coverage, and surveillance, in which the abstract concept of information assumes different meanings, e.g., representation of parts of an unknown environment or the presence of entities or objects. In recent years, applications involving information gathering have received growing attention from both public institutions and private organizations. The development of proper algorithmic solutions, however, is still particularly challenging, being most of the problems involved computationally hard. In practice, several autonomous mobile robots adopt a layered architecture. Bottom levels include sensing and actuation, while the finding of a global plan to follow is demanded to higher levels. When a task requires to gather information by means of one or more autonomous mobile robots, the high-level plan often consists of a navigation plan, i.e., a sequence of locations (or poses) to orderly reach, where information is gathered. A navigation plan is usually computed on a high-level representation of the environment, in which most of the geometrical features and the robot dynamics are neglected, and that is commonly based on grids or graphs. On this abstract model, the information-gathering tasks can be formulated as optimization problems, in which an objective has to be minimized (e.g., the completion time or the energy consumption) and some application-dependent constraints must be satisfied. Unfortunately, most of the so-formulated problems are NP-hard and an effort has been made in the literature aimed at finding efficient sub-optimal algorithmic solutions. Although the approaches implemented can be broadly grouped in some standard classes (e.g., heuristics, greedy algorithms, linear programs relaxations), little is known about the quality of the navigation plans found. A typical tool to assess the performance of sub-optimal approaches is the analysis based on the approximation factor, that is, the ratio between the objective value of a sub-optimal solution and that of an optimal one. In this thesis, we address two different topics related to the gathering of information by means of one or more autonomous mobile robots. The tasks addressed in these two contexts are here formalized as high-level optimization problems, for which offline algorithmic solutions are developed and analyzed. The first topic is that of coverage of a known environment using tools mounted on the robots. In their classic formulation, coverage models assume that the tools are operated by independent actions of the robots (e.g., the sensing of the surrounding environment). However, the concept of coverage can be extended to encompass a larger number of tasks, in which actions may require the joint operations of two or more robots to cover some features of the environment. A first notable example is that of the measurement of the signal strength among pairs of locations. In this broader coverage framework, we address two problems of practical interest. (a) A robot that has to cover with a finite-range tool (e.g., a sensor or a brush) all the points of the free space of a given known environment. (b) A team of robots that has to jointly perform a given set of pairwise measurements in a given known environment. The second topic we consider is that of planning robot paths to reach given target locations. Differently from the typical path planning settings, we consider two scenarios in which communication constraints are imposed by practical application-dependent needs. These problems can arise in a number of information-gathering tasks, as robots deal with finite storage capabilities and it may be needed to flush data through a networked infrastructure, especially in long-term mission scenarios. Another critical aspect, emerging in multirobot tasks, is that of keeping robots connected in order to exchange information to enhance the decisions taken online. In this framework, the specific problems we address are the following. (c) A robot, moving from a start to a goal location, is required to gather data along its path (e.g., a video feed in a monitoring scenario). The robot has at its disposal only a limited amount of memory and hence gathered data has to be periodically delivered to a base station using transmission zones spread within the environment. (d) A team of robots moving in an environment must plan a set of start-goal joint paths which ensures global connectivity at each (discrete) time step, under some communication model. We assess the hardness of all the above problems by reduction from well-known hard problems. Once we have given strong evidence that optimal solutions are (in general) out of reach, we develop sub-optimal algorithmic solutions with particular attention to their efficiency, e.g., polynomial-time complexity. In some cases, an approximation factor guarantee is also devised. Finally, all the algorithms developed in the thesis are tested in simulation to provide an empirical evaluation of their performance. The results contained in this document can be considered a significant contribution to the field, as we provide the formalization of novel problems of practical interest, original analyses of the problems and their attribution to the proper complexity classes, polynomial-time algorithmic solutions, approximation factor results, and experiments in simulation. In a broader view, our achievements can provide useful insights for future analyses of similar (or related) problems, as well as be useful in the implementation and the deployment of efficient autonomous mobile robotics systems for specific applications.

La raccolta d'informazioni è un problema ricorrente in molte applicazione della robotica autonoma mobile. Alcuni esempi sono l'esplorazione di ambienti sconosciuti, la sorveglianza e l'ispezione di edifici o proprietà. In queste applicazioni il concetto astratto d'informazione assume diverse forme, e.g., porzioni di mappa sconosciute o la presenza di oggetti ed entità. Grazie alla crescente attenzione da parte di organizzazioni pubbliche e private, lo sviluppo di sistemi robotici per la raccolta d'informazioni ha ricevuto una spinta notevole. Tuttavia, la progettazione di soluzioni algoritmiche adeguate resta uno degli aspetti più importanti per la realizzazione dei sistemi. Nella pratica, la maggior parte dei sistemi robotici adottano un'architettura multi-livello. I livelli più bassi si occupano della gestione dei sensori e degli attuatori, mentre la pianificazione necessaria per raggiungere un determinato obiettivo viene demandata a quelli più alti. Quando il sistema ha come obiettivo quello di raccogliere informazioni, la pianificazione di alto livello si concentra spesso solo sulla navigazione del robot. I piani di navigazione vengono solitamente calcolati mediante rappresentazioni di alto livello dell'ambiente, come grafi o griglie, che astraggono in larga parte dalla geometria e della dinamica del robot. Su questo modelli, la raccolta d'informazione viene formulata come problema di ottimizzazione. Sfortunatamente, la maggior parte dei problemi d'interesse pratico risultano essere NP-difficili e gli sforzi fatti fin'ora in letteratura mirano a trovare efficienti soluzioni sub-ottime. Nonostante gli approcci seguiti siano piuttosto comuni e ricorrenti, poco si sa riguardo alla qualità dei piani trovati in questo modo. Un metodo diffuso per attestare le prestazioni di un approccio sub-ottimo è quello del fattore di approssimazione, ovverosia, del rapporto tra il valore della soluzione trovata e il valore della soluzione ottima. In questa tesi, affrontiamo due diversi argomenti legati alla raccolta d'informazioni tramite uno o più robot autonomi mobili. Il primo è quello del Coverage, in cui il robot, equipaggiato con un sensore, deve pianificare un percorso che gli permetta di coprire una determinata caratteristica dell'ambiente in cui si trova. I problemi considerati, nello specifico, saranno due: (a) Il robot deve coprire, tramite uno strumento con portata limitata (e.g., un sensore), tutti i punti nello spazio libero dell'ambiente. (b) Una squadra di robot deve effettuare delle misurazioni a coppie (e.g., la potenza di un segnale) fra diverse paia di punti nello spazio. Il secondo argomento è quello del Path planning con vincoli di comunicazione. Anche in questo caso i problemi considerati saranno due, uno single-robot e uno multiple-robot: (c) Il robot, muovendosi da un punto all'altro nello spazio, è soggetto alla raccolta continua d'informazioni (e.g., una registrazione video di sorveglianza). Avendo a sua disposizione una memoria limitata, il robot deve periodicamente consegnare i dati raccolti tramite una delle zone di trasmissione presenti nell'ambiente. (d) Una squadra di robot deve pianificare un insieme di percorsi che li portino dalle loro posizioni iniziali a un dato insieme di posizioni obiettivo. In aggiunta, dato un modello di comunicazione arbitrario, i robot devono rimanere in connessi fra loro durante il percorso. Verranno forniti risultati teorici sulla difficoltà computazionale di tutti e quattro i problemi considerati. Verranno inoltre proposti degli efficienti algoritmi sub-ottimi e, in alcuni casi, verrà fornita un'analisi del loro fattore di approssimazione. Infine, tutti gli algoritmi della tesi verranno valutati sperimentalmente in simulazione, fornendo, quando possibile, confronti diretti con lo stato dell'arte.