Swarm resiliency in collective decision making

A swarm is a self-organised group of agents that locally interact with each other and with the environment to perform a common task. Individual agents are typically simple, with limited capabilities and partial knowledge. Numerous studies investigated the problem of collective decision making in swarms which consists in the process of how a swarm reaches an agreement. However, little attention has been devoted to studying swarm resiliency. Resiliency from a swarm point of view is the ability of the swarm to achieve its goal under disturbance. In this study disturbance is considered as an attack characterised by malicious agents introduced in the swarm. In this thesis we analysed swarm resiliency in collective decision making processes. We focused on best-of-n decisions defined as the task of finding a collective agreement over the most favourable option among a set of alternatives. We investigated the resilience of four different behaviours taken from the literature through computational analysis. We focused on how different kinds of attacks affect the performance of the four behaviours. To do so, we implemented DeMaMAS, a novel multi-agent simulator for comparison of decentralised decision making strategies. DeMaMAS is modular and allowed us to quickly re-implement the studied literature behaviours through the composition of a sequence of reusable unitary modules. In fact, we described all the investigated behaviours through a common structure which consists in a sequence of phases. All behaviours are composed by the same phases which can have different implementations. A specific implementation of a phase is what we call module. Thanks to its modular architecture DeMaMAS allowed us to compare and quantify the resiliency provided by each module. A further advantage of DeMaMAS's modular architecture is the possibility to implement malicious agents by changing just a few modules. To test the resiliency, our tool is able to simulate heterogeneous swarms, in which agents composing the swarm can have different behaviours. We decided to implement three types of malicious agents called wishy washy, sect, and contrarian, respectively performing denial of service, slow down, and wrong addressing. We analysed the performance on the four selected literature behaviours exposed to the three investigated attacks in different conditions varying the number of options, the difficulty of the decision problem, and the percentage of attackers in the swarm. Our first result showed that in simple decision problems, characterised by a low number of options and easily distinguishable alternatives, listening less is the best strategy for being more resilient. However, this strategy does not work to make more difficult collective decisions. Our results also revealed the importance of two modules to increase the swarm resiliency: the majority module, in which an agent picks the most frequent option from its neighbourhood, and the cross-inhibition, a module inspired by the nest-site selection process in honeybees that allows the swarm to break decision-deadlocks in complex best-of-n problems. Thanks to the modularity of DeMaMAS, once we identified the most resilient module, we created a new behaviour combining them. The new behaviour showed the best resiliency performance in terms of both speed and accuracy. Finally, we validated the performance of the novel behaviour through a set of experiments on physical devices. We implemented and tested two behaviours under a slow down attack in a swarm of 50 simple robots called Kilobots. The results from the robot experiments qualitatively matches the simulation results and confirms the benefits of the proposed behaviour. The outcomes of this thesis have been useful to support the analyses of a few research projects whose results will be disseminated through the following manuscript: swarm resiliency in collective decision making (F. Canciani, M.S. Talamali, J.A.R. Marshall, A. Reina) in preparation for the ICRA 2019 Workshop on Resilient Robot Teams, Montreal, Canada, May 20-24, 2019. Additionally, DeMaMAS, which I designed and implemented, is currently used for other research studies of which I will be acknowledged as a co-author.

Uno sciame è identificato come un gruppo di agenti auto-organizzati che interagiscono con l'ambiente e localmente l'uno con l'altro per conseguire un obiettivo comune. Gli agenti sono solitamente semplici, caratterizzati da capacità limitate e da una conoscenza parziale. Numerosi studi hanno esaminato il problema relativo al processo collettivo decisionale negli sciami, tuttavia sono stati fatti pochi studi riguardo la resilienza negli sciami, ossia l'abilità dello sciame di raggiungere il proprio obiettivo sotto l'influenza di un disturbo. In questo studio il disturbo viene considerato come un attacco caratterizzato da un agente (o più agenti) malevolo introdotto nello sciame. In questa tesi analizziamo la resilienza dello sciame in processi decisionali collettivi. La nostra attenzione si concentra nell'area riguardante il best-of-n definito come il compito di scegliere l'opzione migliore tra n alternative. Abbiamo studiato attraverso l'analisi computazionale la resilienza di quattro comportamenti proposti in letteratura. La nostra attenzione si è focalizzata su come diversi tipi di attacchi influenzano le prestazioni dei quattro comportamenti. Per far ciò abbiamo implementato DeMaMAS, un nuovo simulatore multi-agente per la comparazione di strategie di decisione collettiva decentralizzate. DeMaMAS è modulare e ci ha permesso di re-implementare velocemente i comportamenti studiati tramite la composizione di una sequenza riutilizzabile di moduli unitari. I comportamenti presi in considerazione possono essere descritti tramite una struttura comune, che consiste in una sequenza di fasi. Tutti i comportamenti selezionati sono composti dalle stesse fasi, che possono avere diverse implementazioni, chiamate moduli. Grazie alla sua architettura modulare DeMaMAS ci ha permesso di comparare e quantificare la resilienza fornita da ciascun modulo. Un altro importante vantaggio della struttura modulare di DeMaMAS è la possibilità di implementare agenti malevoli solamente cambiando alcuni moduli. Per testare la resilienza, la nostra applicazione è capace di simulare sciami eterogenei, in cui gli agenti che compongono lo sciame possono avere diversi comportamenti. Abbiamo implementato tre diversi tipi di agenti malevoli chiamati wishy washy, contrarian e sect che eseguono rispettivamente denial of service, slow down e wrong addressing. Abbiamo analizzato le prestazioni dei quattro comportamenti scelti sotto l'influenza dei tre attaccanti in condizioni differenti, variando il numero delle opzioni, la difficoltà del processo decisionale e la percentuale di attaccanti nello sciame. Il nostro primo risultato ha mostrato che nei problemi decisionali semplici, caratterizzati da un basso numero di opzioni e alternative facilmente distinguibili, ascoltare meno è la strategia migliore per essere più resilienti. Tuttavia questa strategia non è più utilizzabile in problemi decisionali complessi. I nostri risultati hanno rivelato l'importanza di due moduli che incrementano la resilienza: il primo detto majority, in cui un agente sceglie l'opzione più frequente dal suo vicinato; il secondo detto cross-inhibition, ispirato dal processo di selezione di un nuovo sito per il nido dalle api, permette allo sciame di rompere le decisioni soggette a dead-lock in problemi best-of-n complessi. Grazie alla modularità di DeMaMAS, una volta identificati i moduli più resilienti, tramite l'utilizzo di questi ultimi abbiamo creato un nuovo comportamento, il quale ha migliorato la resilienza sia in velocità di decisione che accuratezza. Infine, abbiamo validato le prestazioni del nuovo comportamento per mezzo di un insieme di esperimenti su dispositivi fisici. Abbiamo implementato e testato due diversi comportamenti sotto l'effetto di un attacco slow down in uno sciame di 50 robot semplici, chiamati Kilobots. Il risultato degli esperimenti sui robot combacia qualitativamente con i risultati delle simulazioni e conferma i benefici del comportamento proposto. L'esito della tesi è stato utile per il supporto di analisi di alcuni progetti di ricerca, che verranno diffusi tramite il seguente articolo: Swarm resiliency in collective decision making (F. Canciani, M.S. Talamali, J.A.R. Marshall, A. Reina) in preparazione per ICRA 2019 Workshop on Resilient Robot Teams, Montreal, Canada, Maggio 20-24, 2019. In aggiunta, DeMaMAS, è correntemente usato per altri studi in cui verrò riconosciuto come co-autore.