Decision making on robotic networks with hybrid performance metrics for planetary exploration applications

This thesis is about distributed consensus on robotic networks for planetary exploration. The advantages of distributed architectures for space exploration have long been studied; furthermore, multiagent architectures are extremely ad- vantageous on small solar system bodies, whose low gravity and uncertain dy- namic environment make traditional mobility paradigms unapplicable. Rel- ativistic delays make autonomy paramount for all probes operating beyond Earth orbit. Yet no energy-efficient procedures for autonomous consensus on robotic networks exist: current algorithms are either optimized for ground- based applications or largely inefficient. The purpose of this thesis is to design efficient algorithms to reach an agreement between cooperative stationary or slow-moving robotic agents. We explore metrics describing time performance, power consumption and ro- bustness; we propose time-optimal and energy-optimal algorithms and show how optimality with respect to one parameter typically leads to very bad performance with respect to other metrics. We then design a novel hybrid algorithm that scales from time-optimal to message-optimal behavior, trading time performance and robustness for energy efficiency, according to an user-defined tuning parameter. Worst- case performance of the algorithm is investigated analytically; real-world performance on a simplified space exploration scenario is explored through numerical simulations with satisfactory results. Future research directions will include extension of our work to fast- moving robotic networks such as swarms of planetary hoppers, optimization with respect to legacy omnidirectional (broadcast) communication protocols and application to problems such as UAV deployment for patrolling and ATC conflict resolution.

Questa tesi studia come prendere decisioni in modo efficiente e decentralizzato su reti robotiche per l'esplorazione di corpi del Sistema Solare. Le architetture multiagente per l'esplorazione spaziale promettono di offrire maggiore robustezza e migliore efficienza rispetto ai paradigmi monolitici oggi dominanti. Un'architettura multiagente è inoltre particolarmente adatta all'esplorazione dei piccoli corpi del Sistema Solare. Comete, asteroidi e piccole lune presentano morfologie e composizioni geologiche complesse che rendono necessaria l'esplorazione di regioni estese; d'altra parte, la microgravità rende impossibile o sconsigliabile l'applicazione di sistemi di mobilità tradizionali. Più agenti stazionari ancorati alla superficie permetterebbero di esplorare ampie regioni senza incorrere negli svantaggi inerenti in nuovi sistemi di mobilità non ancora testati; una rete di agenti mobili, d'altra parte, permetterebbe di rilassare i requisiti di mobilità richiesti ad ogni singolo veicolo, concedendo di testare con gradualità tecnologie innovative e garantendo il raggiungimento degli obiettivi scientifici anche a fronte di guasti catastrofici di uno o più agenti. L'autonomia è necessaria nell'esplorazione spaziale: i ritardi dovuti alle distanze interplanetarie e la congestione del Deep Space Network non permettono di controllare direttamente i veicoli se non per periodi di tempo molto brevi. La letteratura scientifica presenta molti algoritmi per prendere decisioni collaborative in modo decentralizzato: questi algoritmi, tuttavia, sono tipicamente ottimizzati per applicazioni terrestri e, in particolare, non tengono conto del consumo energetico dovuto alle comunicazioni tra agenti. Lo scopo di questa tesi è presentare algoritmi che permettano ad agenti robotici di prendere decisioni in modo efficiente rispetto a metriche rilevanti per l'esplorazione robotica del Sistema Solare. Dopo aver evidenziato i limiti delle soluzioni esistenti nella letteratura, presentiamo delle metriche che caratterizzano il comportamento temporale, il consumo energetico e la robustezza degli algoritmi di consenso distribuito. Esploriamo quindi i limiti fondamentali del problema del consenso rispetto a queste metriche e mostriamo come due algoritmi esistenti permettano di minimizzare rispettivamente il tempo necessario e il numero di bytes scambiati (quindi il consumo energetico) per raggiungere una decisione in modo decentralizzato. Questa soluzione, tuttavia, non è soddisfacente: prestazioni ottimali nel tempo comportano forti compromessi in termini di consumo energetico, mentre la minimizzazione del consumo energetico rende l'algoritmo lento e fragile rispetto a guasti dei canali di comunicazione. Progettiamo quindi un algoritmo ibrido e regolabile che permette di ottenere compromessi tra tempo di convergenza, consumo energetico e robustezza. Le prestazioni dell'algoritmo sono esplorate analiticamente nel caso peggiore e su alcune semplici topologie di rete; simulazioni numeriche permettono quindi di valutare il comportamento dell'algoritmo in uno scenario realistico di esplorazione di un piccolo corpo del Sistema Solare. I risultati sono soddisfacenti. Nel prossimo futuro, la ricerca si concentrerà sull'estensione dei nostri risultati a reti di agenti in rapido movimento e alla ricerca di algoritmi ottimali per reti broadcast. Le applicazioni del nostro algoritmo vanno oltre l'esplorazione spaziale e includono problemi di interesse aerospaziale come il controllo di gruppi di pattugliatori aerei senza pilota e la risoluzione di conflitti nel controllo del traffico aereo.