EFFICIENT PARAMETRIC AND NON-PARAMETRICLOCALIZATION AND MAPPING IN ROBOTIC NETWORKS

Since the eighties localization and mapping problems have attracted the efforts of robotics researchers. However in the last decade, thanks to the increasing capabilities of the new electronic devices, many new related challenges have been posed, such as swarm robotics, aerial vehicles, autonomous cars and robotics networks. Efficiency, robustness and scalability play a key role in these scenarios. Efficiency is intended as an ability for an application to minimize the resources usage, in particular CPU time and memory space. In the aforementioned applications an underlying communication network is required so, for robustness we mean asynchronous algorithms resilient to delays and packet-losses. Finally scalability is the ability of an application to continue functioning without any dramatic performance degradation even if the number of devices involved keep increasing. In this thesis the interest is focused on parametric and non-parametric estimation algorithms ap- plied to localization and mapping in robotics. The main contribution can be summarized in the following four arguments: (i) Consensus-based localization We address the problem of optimal estimating the position of each agent in a network from relative noisy vectorial distances with its neighbors by means of only local communication and bounded complexity, independent of network size and topology. In particular we propose a consensus-based algorithm with the use of local memory variables which allows asynchronous implementation, has guaranteed exponential convergence to the optimal solution under simple deterministic and randomized communication protocols, and requires minimal packet transmission. In the randomized scenario, we then study the rate of convergence in expectation of the estimation error and we argue that it can be used to obtain upper and lower bound for the rate of converge in mean square. In particular, we show that for regular graphs, such as Cayley, Ramanujan, and complete graphs, the convergence rate in expectation has the same asymptotic degradation of memoryless asynchronous consensus algorithms in terms of network size. In addition, we show that the asynchronous implementation is also robust to delays and communication failures. We finally complement the analytical results with some numerical simulations, comparing the proposed strategy with other algorithms which have been recently proposed in the literature. (ii) Aerial Vehicles distributed localization: We study the problem of distributed multi- agent localization in presence of heterogeneous measurements and wireless communication. The proposed algorithm integrates low precision global sensors, like GPS and compasses, with more precise relative position (i.e., range plus bearing) sensors. Global sensors are used to reconstruct the absolute position and orientation, while relative sensors are used to retrieve the shape of the formation. A fast distributed and asynchronous linear least-squares algorithm is proposed to solve an approximated version of the non-linear Maximum Likelihood problem. The algorithm is provably shown to be robust to communication losses and random delays. The use of ACK-less broadcast-based communication protocols ensures an efficient and easy implementation in real world scenarios. If the relative measurement errors are sufficiently small, we show that the algorithm attains a solution which is very close to the maximum likelihood solution. The theoretical findings and the algorithm performances are extensively tested by means of Monte-Carlo simulations. (iii) Estimation and Coverage: We address the problem of optimal coverage of a region via multiple robots when the sensory field used to approximate the density of event appearance is not known in advance. We address this problem in the context of a client-server architecture in which the mobile robots can communicate with a base station via a possibly unreliable wireless network subject to packet losses. Based on Gaussian regression which allows to estimate the true sensory field with any arbitrary accuracy, we propose a randomised strategy in which the robots and the base station simultaneously estimate the true sensory distribution by collecting measurements and compute the corresponding optimal Voronoi partitions. This strategy is designed to promote exploration at the beginning and then smoothly transition to station the robots at the centroid of the estimated optimal Voronoi partitions. Under mild assumptions on the transmission failure probability, we prove that the proposed strategy guarantees the convergence of the estimated sensory field to the true field and that the corresponding Voronoi partitions asymptotically becomes arbitrarily close to an optimal Voronoi partition. Additionally, we also provide numerically efficient approximation that trade-off accuracy of the estimated map for reduced memory and CPU complexity. Finally, we provide a set of extensive simulations which confirm the effectiveness of the proposed approach. (iv) Non-parametric estimation of spatio-temporal fields: We address the problem of efficiently and optimally estimating an unknown time-varying function through the collection of noisy measurements. We cast our problem in the framework of non-parametric estimation and we assume that the unknown function is generated by a Gaussian process with a known covariance. Under mild assumptions on the kernel function, we propose a solution which links the standard Gaussian regression to the Kalman filtering thanks to the exploitation of a grid where measurements collection and estimation take place. This work show an efficient in time and space method to estimate time-varying function, which combine the advantages of the Gaussian regression, e.g. model-less, and of the Kalman filter, e.g. efficiency.

Fin dagli anni ottanta i problemi di localizzazione e mapping sono stati argomenti molto stu- diati nell’ambito della robotica. Un’ulteriore spinta è avvenuta negli ultimi dieci anni grazie all’incremento delle capacità di calcolo dei dispositivi elettronici. Questo ha permesso di porre nuovi ambiziosi obbettivi, come il controllo di sciami robotici, UAVs, veicolo autonomi e reti robotiche. Efficienza, robustezza e scalabilità sono tre caratteristiche fondamentali che non possono mancare negli algoritmi di localizzazione e mapping. L’efficienza è la capacità di un algoritmo di mininizzare l’utilizzo di risorse, in particolare il tempo di utilizzo della CPU e la quantità di memoria utilizzata. Nella applicazioni sopra citate è richiesto l’utilizzo di un mezzo di comunicazione, per robustezza quindi intendiamo algoritmi asincroni capaci di funzionare anche in presenza di perdite di pacchetto e ritardi. Per finire con scalabilità intendiamo la capacità di un’algoritmo di funzionare senza drammatiche variazioni di prestazioni anche quando il numero di dispositivi coinvolti cresce. Questa tesi si pone l’obbiettivo di studiare metodi parametri e non parametrici applicati ai problemi di localizzazione e mapping nell’ambito della robotica. In particolare i principali contributi possono essere riassunti nei seguenti quattro argomenti: (i) Localizzazione tramite consensus: Il primo argomento affrontato è dato dal problema di stimare in modo ottimo le posizioni di un gruppo di agenti in una rete. Solamente gli agenti definiti come vicini nel grafo di comunicazione possono scambiarsi misure vettoriali rumorose di distanza. Questo requisito si traduce in una limitata complessità ed il vincolo della sola comunicazione locale, rendendo l’algoritmo indipendente dalla dimensione della rete e dalla sua topologia. Viene quindi proposto un algoritmo di consensus con memoria che ne per- mette l’implementazione asincrona. Di questo algoritmo è possibile provare la convergenza esponenziale ad una soluzione ottima, sotto le ipotesi di utilizzo di semplici protocolli di comunicazione deterministici o randomizzati e una richiesta minima di trasmissione di pacchetti. Nel caso di comunicazione randomizzata è inoltre presente uno studio della velocità di convergenza in aspettazione e tale risultato viene poi utilizzato per studiare la velocità di convergenza in media quadratica. In particolare viene mostrato che per grafi regolari, come i Cayley, i Ramanjuan ed i completi l’algoritmo proposto, e quello asincrono senza memoria, hanno il medesimo comportamento. Inoltre, l’implementazione asincrona è robusta a ritardi e perdite di pacchetto. Per finire l’analisi analitica è complementata con risultati numerici, comparando l’algoritmo proposto con altri algoritmi presenti in letteratura. (ii) Localizzazione distribuita di veicoli aerei: Successivamente viene studiato il problema della localizzazione distribuita multiagente in presenza di misure eterogenee e comunicazione wireless. L’algoritmo proposto integra misure assolute poco precise, come GPS e bussole, con misure relative più precise, come range e bearing. Le misure assolute sono usate per ricostruire la posizione e l’orientazione della formazione, mentre quelle relative sono usate per ricostruire le posizioni reciproche degli agenti. Viene proposto un algoritmo distribuito ed asincrono basato su minimi quadrati, che permette di risolvere una versione approssimata del problema di Massima Verosimiglianza non-lineare inizialmente presentato. Tale algoritmo è robusto a perdite di pacchetto e ritardi, inoltre l’uso di un protocollo ACK-less broadcast- based assicura un’efficiente e facile implementazione. Per finire se l’errore sulle misure relative è sufficientemente piccolo, viene mostrato come l’algoritmo raggiunge una soluzione molto vicina a quella del problema originale di massima verosimiglianza. I risultati teorici e le performance dell’algoritmo sono poi verificati attraverso numerose simulazioni Monte-Carlo. (iii) Stima e Coverage: Il terzo argomento studiato d`ato dal problema di coverage ottimo di una regione attraverso più robot. Si assume non nota a propri la sensory function usata per approssimare la densità di apparizioni degli eventi. Il setup considerato è un’architettura client-server nella quale ogni robot può comunicare con la base-station attraverso una rete di comunicazione soggetta a perdita di pacchetti. Proponiamo un algoritmo di stima basato su regressione Gaussiana che permette di stimare la sensory function con un’accuratezza arbi- traria. Per risolvere il problema di coverage è presentata una strategia randomica attraverso la quale i robot mobili e la base-station simultaneamente stimano la distribuzione della density function collezionando misure rumorose e computando le partizioni di Voronoi. Questa strategia è progettata per prima promuovere l’esplorazione e solo successivamente incentivare i robot a spostarsi nel centroide della partizioni di Voronoi stimate. Sotto deboli ipotesi sulla probabilità di errata trasmissione, proviamo che la strategia proposta garantisce la convergenza della density function stimata a quella vera e che le corrispondenti partizioni di Voronoi convergono asintoticamente andando arbitrariamente vicine a quella di Voronoi ottime. Viene anche proposta un’approssimazione numericamente efficiente che trova un compromesso tra la qualità della stima della mappa e le risorse computazionali utilizzate, e.g. memoria e CPU. Per finire, tramite svariate simulazioni, mostriamo l’efficacia dell’approccio proposto. (iv) Stima non parametrica di campi spazio-temporali: Affrontiamo per finire il problema della stima efficiente e ottima di una funzione sconosciuta e tempo variante attraverso la collezione di misure rumorose. Inquadriamo il problema nel framework della stima non parametrica e assumiamo che la funzione sia generata da un processo Gaussiano con covarianza nota. Sotto deboli ipotesi sul kernel del processo Gaussiano, viene proposta una soluzione che collega la classica regressione Gaussiana con il filtro di Kalman grazie all’utilizzo di una griglia su cui vengono prese le misure. Come risultato principale proponiamo un algoritmo ef- ficiente per stimare funzioni tempo e spazio varianti e che combina i vantaggi della regressione Gaussiana, e.g. l’assenza di modelli, con quelle del filtro di Kalman, e.g. l’efficienza.