Spatial allocation in swarm robotics

This thesis proposes three distributed methods to achieve the allocation of a homogeneous swarm of robots to spatially distributed collective activities. Such tasks require the simultaneous presence of multiple robots to be successfully performed. Several approaches to solve the problem have been proposed in the scientific literature, both centralized and decentralized (relying either on implicit or explicit coordination), but, to the best of our knowledge, none of these works has focused on an instance of the problem with a scarce number of agents (i.e. inferior to the number of available task), using robots and tasks both embodied. The problem has first been formally analyzed and specified, using a novel approach based on UML diagrams. Then, the methods have been developed in the form of probabilistic finite state machines (PFSM), a microscopic level, behavior-based approach in swarm robotics. The first method (Naive) simply consists of a greedy allocation of the robots to available tasks in the environment, as soon as they have been localized. The second one (Probabilistic) improves the Naive one with probabilistic rules to avoid allocation conflicts and achieve a more uniform allocation. The third (Informed) is built upon the Probabilistic one, using odometry to avoid the redundant exploration of already visited clusters. The methods have been simulated on three different scenarios: Uniform, Biased and Corridor. We characterize the methods according to their allocation uniformity and allocation speed. We show that there exists a trade-off between uniformity and speed for the developed methods. We also find that the positioning of the clusters has a strong impact on the performances of the methods. We conclude that the Informed method has the best performances on the proposed scenarios.

Lo scopo di questo studio é lo sviluppo di un metodo distribuito per l’allocazione di uno sciame di robot omogenei ad un’insieme di attivitá collettive aventi una precisa distribuzione nello spazio. Tali attività richiedono la presenza simultanea di molteplici robot per poter essere eseguite con successo. Nella letteratura scientifica sono stati proposti diversi approcci, sia centralizzati che decentralizzati (basati in parte sulla coordinazione implicita, in parte su quella esplicita), ma, sulla base delle informazioni in nostro possesso, nessuno di questi lavori ha affrontato un’istanza del problema in cui il numero degli agenti é scarso (ossia inferiore al numero delle attivitá disponibili), utilizzando sia robot che attività rappresentati concretamente. Il primo passo del nostro lavoro é stata l’analisi e la produzione di una specifica formale del problema, utilizzando un approccio innovativo basato sui diagrammi UML. Successivamente, sono stati sviluppati tre metodi, sotto forma di automi a stati finiti probabilistici (PFSM), un approccio utilizzato nella swarm robotics al fine di definire il comportamento dei singoli agenti (i.e. a livello microscopico). Il primo metodo (Naive), consiste semplicemente nell’allocazione diretta dei robot alle attività disponibili nell’ambiente, non appena esse vengano localizzate. Il secondo (Probabilistic) migliora il metodo Naive introducendo alcune regole probabilistiche al fine di evitare conflitti in fase di allocazione ed ottenere una distribuzione uniforme dei robot. Il terzo (Informed) costituisce un’estensione del metodo Probabilistic, introducendo l’uso dell’odometria al fine di evitare l’esplorazione ridondante di cluster giá visitati. Gli algoritmi sopraccitati sono stati simulati su tre scenari dalle caratteristiche differenti: Uniform, Biased and Corridor, al fine di caratterizzare i metodi secondo la velocità nell’allocazione e l’uniformità nella distribuzione dei robot sui diversi cluster. Attraverso gli esperimenti, siamo riusciti a dimostrare l’esistenza di un trade-off tra l’uniformità della distribuzione e la velocità di allocazione dei diversi metodi. Abbiamo inoltre constatato che il posizionamento dei cluster influenza in modo non trascurabile le prestazioni del metodo. Considerati tutti i risultati, possiamo concludere che il metodo Informed é in grado di ottenere le migliori prestazioni su tutti gli scenari proposti.