• LGV
• localizzazione basata su mappa
• scansione virtuale

La tesi rientra in un più ampio progetto che ha come obiettivo la navigazione autonoma di veicoli, senza l’ausilio di landmark artificiali. Grazie ad una conoscenza precisa dell’ambiente derivante da una scansione 3D effettuata a priori, la mappa di navigazione può considerarsi perfettamente nota.
Il veicolo dovrà quindi poter identificare la posizione in cui si trova relazionando in tempo reale una scansione laser 2D con la mappa nota.
A partire dalla mappa viene generata una scansione virtuale basandosi sulla posizione presunta proveniente dalla predizione di un filtro di Kalman. La scansione reale viene confrontata con quella virtuale per identificare la trasformazione di correzione. La tesi si concentra sullo sviluppo di algoritmi finalizzati alla creazione della scansione virtuale in grado di rispecchiare fedelmente le modalità di acquisizione e le caratteristiche di un laser scanner planare. Le tecniche studiate rientrano nel settore della grafica computazionale e sono state adattate allo scopo della tesi. Il primo algoritmo sviluppato è il Ray Casting e si basa sull'idea di considerare tutti i punti della mappa al fine di indirizzarli nei loro precisi settori e poi selezionare quelli interessati alla scansione. Successivamente si è optato per algoritmi con complessità computazionale indipendente dalla dimensione della mappa, che sfruttano operazioni di ricerca su griglia, noti con il nome di Ray Marching e Rasterizzazione.
Ogni impulso è simulato geometricamente, e il problema si riduce nell'individuazione delle intersezioni tra raggi e griglia. Ciò è finalizzato a determinare gli indici delle celle interessate che potrebbero potenzialmente contenere punti della mappa scanditi.
Varie procedure in grado di ricavare le intersezioni sono state sviluppate ponendo attenzione sui tempi di esecuzione. L'algoritmo più veloce tra quelli sviluppati è risultato essere il 4-Connected Bresenham, poichè accelera il processo di intersezione raggio-griglia implementando poche semplici operazioni matematiche. A partire da questa idea è nato un algoritmo che evita di emettere un beam virtuale alla volta, ma piuttosto realizza la scansione emettendo interi settori di beam, detti Superbeam. In tal modo si velocizza il processo di Ray Marching, qualora le geometrie della mappa presentassero pareti lunghe definite da numerosi punti adiacenti: la rasterizzazione di un intero settore, determina in pochi passi, quali siano i punti interessati alla scansione virtuale.
Un ulteriore aspetto ha considerato quale strategia multithreading potesse essere più adatta e in grado di parallelizzare l'esecuzione di ogni algoritmo, rendendola più veloce. Dopo aver individuato il numero di task all'interno degli algoritmi da eseguire come "flussi indipendenti" si è decisa la modalità di istanza e creazione dei thread. La scelta è ricaduta sulla creazione di un gruppo di thread (pool) all'avvio del processo, ai quali viene assegnato un lavoro quando richiesto. Questa strategia si contrappone alla creazione di un thread per ogni richiesta e il vantaggio che essa produce è la velocità di esecuzione. Infatti, servire la richiesta all'interno di un thread esistente è tipicamente più veloce che attendere la creazione di un thread.
Dai risultati simulativi, l’algoritmo Superbeam risulta essere il più veloce, capace di generare una scansione virtuale con tempi compatibili con la navigazione del veicolo, inferiori a 12ms.
Test in scenari realistici sono stati effettuati a conclusione del lavoro.