Progetto logico della soluzione del problema

L'algoritmo proposto si pone l'obiettivo di trovare un percorso esplorativo ottimo, cercando passo dopo passo la posizione successiva ottima. Il metodo si avvale della mappa parziale del mondo in cui il robot è immerso per ricavare il valore atteso della quantità di informazione ottenibile a partire da una posizione candidata.

Il robot svolge il processo di mapping effettuando rilevamenti mediante lo scanner laser che vengono impiegati sia per costruire un modello dell'ambiente, sia per effettuare la localizzazione. Una scansione è composta da una lista di punti che rappresentano i contorni degli oggetti incontrati dal raggio del laser.

Ogni scansione rileva una sequenza di misurazioni equidistanziate, secondo direzioni separate da un angolo programmabile (un grado nelle prove effettuate), coprendo un angolo complessivo di 180 gradi. Ogni scansione restituisce quindi 180 punti. Dalla posizione corrente il robot effettua quattro scansioni successive con orientamenti distanziati di 90 gradi tra loro, effettuando un giro completo su se stesso e costruendo una mappa parziale. Per ogni scansione viene effettuato un controllo atto ad eliminare i valori di fondo scala. La mappa globale dell'ambiente viene ottenuta integrando le mappe parziali raccolte da diverse posizioni. Il modello risultante sarà composto quindi da un insieme di punti che descrivono gli oggetti presenti nell'ambiente in cui il robot è immerso.

Ogni punto viene descritto da una tripla $(x,y,\sigma_p)$, dove $x$ e $y$ sono le coordinate del punto e $\sigma_p$ è la deviazione standard che rappresenta l'incertezza di cui la misura è affetta, dovuta, in generale, sia all'accuratezza del sensore che all'incertezza sulla posizione del robot. Il sistema di riferimento usato è il centro dello scanner laser, quindi le coordinate dei punti che compongono la mappa vengono aggiornate ogni volta che il robot cambia la sua posizione. Ogni spostamento porta anche ad un aggiornamento di $\sigma_p$ di un fattore che dipende dalla grandezza dello spostamento effettuato. Dopo ogni movimento viene stimata la rototraslazione usando l'odometria e tale stima viene raffinata usando un algoritmo di scan matching, atto a diminuire l'incertezza sulla posizione dei punti della mappa globale.

La nuova posizione di esplorazione viene infine scelta generando una serie di candidati all'interno della porzione di ambiente esplorata fino a quel momento e pesandone il valore informativo con il costo dovuto al loro raggiungimento. I passi complessivi del processo di esplorazione possono essere riassunti nel modo seguente:

1. Dalla posizione corrente, occupata dal robot durante la $k$-esima iterazione viene costruita la mappa parziale $m_k$ dell'ambiente rilevando quattro scansioni consecutive $s_{i,k}$ ( $i=1,\dots,4$) distanziate di 90 gradi, in modo che il robot compia un giro completo su se stesso.

2. Le quattro scansioni vengono riferite allo stesso sistema di riferimento secondo la trasformazione $t_{o}$, fornita dal sistema odometrico, quindi riallineate mediante l'algoritmo di scan matching IDC e fuse, formando la mappa parziale $m_k$.

3. Ad $m_k$ viene applicato l'algoritmo di clustering di Dobkin-Tal atto a semplificare la mappa parziale limitando la perdita di informazione.

4. La mappa globale $M_k$ viene aggiornata mediante l'aggiunta del modello locale $m_k$, ottenendo $M_{k+1}$. L'aggiornamento viene preceduto dal riallineamento di $m_k$ e $M_k$ effettuato mediante l'algoritmo IDC. Il modello $m_{k}$ viene quindi aggiunto a $M_{k}$ mediante l'algoritmo di Dobkin-Tal, usato per inserire i punti di $m_{k}$ che non sono già presenti nella mappa globale.

5. Le posizioni candidate vengono generate all'interno di $M_{k+1}$, scartando quelle non raggiungibili.

6. Viene fatta la scelta del candidato ottimo e vengono calcolati i parametri di movimento del robot $\rho$ e $\theta$ per raggiungere la nuova posizione da cui continuare il processo di esplorazione.

7. Una volta raggiunta la nuova posizione viene calcolata la trasformazione $t_{k,o}$ mediante le informazioni odometriche rilevate durante lo spostamento e tramite queste vengono aggiornate le coordinate e l'incertezza $\sigma_p$ dei punti della mappa globale rispetto alla nuova posizione. L'esplorazione riprende dal passo 1.

8. L'esplorazione ha termine nei seguenti casi:
   1. Terminano i passi di esplorazione imposti all'avvio del processo di esplorazione.
   2. Il robot non ha spazio per ruotare durante la costruzione della mappa parziale.
   3. Non esistono ulteriori posizioni candidate raggiungibili.

Verranno ora dettagliati i passi di esplorazione dell'algoritmo: in particolare verrà illustrato come avviene il processo di costruzione della mappa parziale e l'integrazione di questa con la mappa globale. Verrà inoltre descritto in dettaglio il metodo di Next Best View proposto, per la scelta della posizione ottima di esplorazione.