Prestazioni e accuratezza dell'algoritmo proposto

Nelle prove sperimentali effettuate è stato possibile testare la correttezza e l'efficienza del metodo proposto. In particolare è stato possibile notare che la perdita di velocità nell'esecuzione del programma, dovuta all'aumentare della dimensione della mappa globale è stata ridotta drasticamente dall'impiego della procedura di clustering. Si è potuto notare infatti come sul tempo di esecuzione abbiano pesato in maniera maggiore le attese dei dati odometrici, inviati dai sensori sulla porta seriale, rispetto al costo di esecuzione degli algoritmi di riallineamento e di NBV.

Nelle prove effettuate il tempo medio impiegato per la costruzione di una mappa parziale è stato di circa 180 secondi; di questi circa 112 secondi (il 62%) sono stati impiegati nelle 4 rotazioni di 90 gradi e nelle attese dei dati odometrici sulla porta seriale. Cinque iterazioni successive dell'algoritmo di riallineamento applicato alle scansioni componenti la mappa parziale hanno richiesto dai 2 ai 5 secondi. Tale valore dipende dal numero di punti comuni tra le scansioni rilevate dal laser: maggiore è il numero di punti in comune tra le scansioni in esame e maggiore sarà il tempo necessario per il loro riallineamento.

Il tempo richiesto per la scelta del candidato ottimo dipende sia dal numero di candidati che vengono scartati perchè non raggiungibili dal robot sia dal numero di punti presenti nella mappa globale. Il calcolo dei parametri di scelta di ogni candidato richiede circa 0.08 secondi per una mappa globale composta da 423 punti; quindi se tutti i 40 candidati generati sono raggiungibili, la scelta del candidato ottimo richiede circa 3.2 secondi. Prima dell'introduzione degli algoritmi di riallineamento e clustering la dimensione media delle mappe globali (quattro passi di esplorazione) ottenute con il metodo di esplorazione proposto era di circa 2600 punti, mentre ora le mappe globali costruite effettuando quattro passi di esplorazione hanno una dimensione di circa 680 punti (Figura 4.3).

Figura 4.3: La mappa A è stata ottenuta senza l'uso degli algoritmi di riallineamento e clustering ed è composta da 2595 punti; la mappa B, ottenuta con il metodo qui proposto, contiene 678 punti. Entrambe rappresentano l'atrio del Dipartimento di Elettronica e Informazione (primo ambiente di prova).

A B

Dato che per il calcolo dei parametri di scelta del candidato ottimo è necessario calcolare il numero di punti precedentemente misurati che ci si aspetta siano rilevati nuovamente nella posizione candidata, per ogni candidato in esame dovrà essere calcolata la distanza da ciascun punto della mappa globale; se essa è minore del range del laser allora il punto della mappa sarà visibile dal candidato, altrimenti esso non verrà rilevato. In questo modo si dovranno effettuare un numero di calcoli di distanza candidato-punto mappa uguale al numero di punti della mappa globale costruita fino a quel momento e moltiplicato per il numero dei candidati in esame. Considerando le mappe globali prese come esempio (680 punti utilizzando l'algoritmo proposto e 2600 punti senza l'uso delle procedure di riallineamento e clustering), il tempo necessario al calcolo dei parametri di scelta di ciascun candidato viene ridotto del 75% circa grazie all'introduzione delle procedure di riallineamento e semplificazione. Tale valore è stato ottenuto facendo una proporzione tra il tempo impiegato per il calcolo dei parametri di scelta in una mappa composta da 680 punti e quello che occorre per gli stessi calcoli in una mappa formata da 2600 punti.

Nelle prove sperimentali è stato anche misurato il tempo di semplificazione di una mappa parziale prima che essa venga fusa con la mappa globale. Il processo di clustering impiega circa 3 secondi per ridurre una mappa parziale formata da 1343 punti in una costituita da 665 punti. In Tabella 4.1 sono riassunti i tempi di esecuzione dell'algoritmo di esplorazione proposto.

Tabella 4.1: Tempi di esecuzione dell'algoritmo di esplorazione

Processo	Tempo di esecuzione
Costruzione mappa globale (4 passi)	$14min$ circa
Costruzione mappa parziale	$180s$ circa
4 rotazioni di 90 gradi e attesa dati odometrici	$4 \times 28s = 112s$
Valutazione parametri di scelta candidato	$0.08s$ per ogni candidato
	(mappa globale di 423 punti)
Riallineamento tra due scansioni successive	$0.4-1s$ (per ogni riallineamento)
Clustering della mappa parziale	$3s$ circa

L'introduzione delle procedure di riallineamento e clustering ha permesso inoltre di ottenere mappe più accurate, minimizzando le sovrapposizioni dei punti comuni tra le mappe. In Figura 4.4 vengono confrontate due mappe parziali prima e dopo l'implementazione delle procedure di riallineamento e clustering. Si osservi come il problema dei punti appartenenti a mappe parziali diverse che si sovrappongono affligge in modo significativo solo l'implementazione del metodo di esplorazione che non fa uso delle procedure che riallineano e semplificano le mappe parziali.

Figura 4.4: La mappa A è stata ottenuta senza far uso delle procedure di riallineamento e clustering, mentre la mappa B é stata costruita impiegando tali procedure.

A B