EFFICIENT PARAMETRIC AND NON-PARAMETRICLOCALIZATION AND MAPPING IN ROBOTIC NETWORKS

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.