Multirobot coverage of modular environments

Multirobot systems for covering environments are increasingly used in applications like cleaning, industrial inspection, patrolling, and precision agriculture. The problem of covering a given environment using multiple robots can be naturally formulated and studied as a multi-Traveling Salesperson Problem (mTSP). In a mTSP, the environment is represented as a graph and the goal is to find tours (starting and ending at the same depot) for the robots in order to visit all the vertices with minimum global cost, which is typically calculated as the makespan, namely the length of the longest tour. The mTSP is an NP-hard problem for which several approximation algorithms have been proposed. These algorithms usually assume generic environments, but tighter approximation bounds can be reached focusing on specific environments. In this thesis, we address the case of modular environments, namely of environments composed of sub-parts, called modules, that can be reached from each other only through some linking structures. Examples are multi-floor buildings, in which the modules are the floors and the linking structures are the staircases or the elevators, and floors of large hotels or hospitals, in which the modules are the rooms and the linking structures are the corridors. Considering modular environments, we present an efficient (with polynomial worst-case time complexity) algorithm that finds a solution for the mTSP whose cost is within a bounded distance from the cost of the optimal solution. The main idea of our algorithm is to allocate disjoint "blocks" of adjacent modules to the robots, in such a way that each module is covered by only one robot. We experimentally compare our algorithm against some state-of-the-art algorithms for solving mTSPs in generic environments and show that it is able to provide solutions with lower makespan and spending a computing time several orders of magnitude shorter.

La copertura di ambienti è sempre più frequentemente effettuata tramite sistemi multi-robot in molte applicazioni, come la pulizia di superfici, ispezioni industriali, pattugliamento e agricoltura di precisione. Il problema della copertura di un certo ambiente utilizzando sistemi multi-robot può essere formulato come problema dei commessi viaggiatori multipli o mTSP (dall'inglese multi-Traveling Salesperson Problem). In un mTSP, l'ambiente è rappresentato come un grafo e l'obiettivo è trovare i percorsi (che inizino e terminino nello stesso vertice deposito) dei robot, tali che tutti i vertici del grafo vengano visitati almeno una volta minimizzando il costo globale, che è generalmente calcolato come il makespan, ovvero la lunghezza del percorso più lungo. L'mTSP è un problema NP-hard per il quale sono stati proposti molti algoritmi di approssimazione. Questi algoritmi solitamente lavorano su ambienti generici, ma è possibile ottenere fattori di approssimazione migliori concentrandosi su ambienti specifici. In questa tesi analizziamo il caso degli ambienti modulari, ovvero ambienti composti da sotto parti, i moduli, collegati tra loro attraverso una struttura di collegamento. Esempi di tali ambienti sono gli edifici con più piani, in cui i moduli sono i piani e la struttura di collegamento è la scala o l'ascensore, oppure i piani di grandi hotel od ospedali, in cui i moduli sono le singole stanze e la struttura di collegamento è rappresentata dai corridoi. Considerando gli ambienti modulari, presentiamo un algoritmo efficiente (con una complessità temporale polinomiale nel caso peggiore) che, dato un mTSP, fornisce una soluzione il cui costo è garantito essere ad una distanza limitata dal costo della soluzione ottimale. L'idea del nostro algoritmo è di allocare ai robot "blocchi" disgiunti di moduli adiacenti, in modo che ogni modulo sia coperto da uno ed un solo robot. In questa tesi, forniamo anche un confronto sperimentale del nostro algoritmo con altri algoritmi proposti in letteratura che risolvono un mTSP in ambienti generici. Mostriamo come il nostro algoritmo fornisca soluzioni con un makespan più piccolo e richieda un tempo di computazione più basso di molti ordini di grandezza.