Generazione della posizione di esplorazione successiva

Avendo a che fare con informazioni parziali e incomplete sull'ambiente, è necessario sviluppare delle euristiche di esplorazione in grado di risolvere il problema della scelta della prossima posizione del robot, da cui continuare il processo di esplorazione. Alle tecniche che risolvono questo problema viene dato il nome di metodi NBV, cioè Next Best View. Nella scelta della nuova posizione di osservazione occorre tenere in considerazione diversi fattori, come ad esempio il potenziale guadagno di informazione rispetto al tempo e alle risorse impiegate per il raggiungimento della nuova posizione e la possibile perdita di accuratezza nella stima della posizione del robot [25], [58].

Gonzáles-Baños, Latombe, Murali ed Efrat in [23] propongono un metodo di scelta basato sul concetto di ``spazio libero''. Alcuni punti candidati vengono generati in modo casuale vicino ai confini delle zone esplorate, in cui il robot non rischia collisioni. La scelta della migliore posizione viene effettuata in base alla porzione di area inesplorata che risulta visibile attraverso le free curve, cioè le parti di mappa in cui lo scanner laser non ha incontrato pareti od oggetti ma ha restituito il valore di fondo scala.

Sempre in [23] viene proposto un modello poligonale dell'ambiente costruito a partire dalle rilevazioni ottenute mediante scansioni laser. Un modello iniziale $M_0$ viene costruito nella posizione iniziale $q_0$ e successivamente espanso iterativamente. Ad ogni iterazione $k=1,2,\dots$ il pianificatore utilizza il modello $M_{k-1}=(P_{k-1},F_{k-1})$ per scegliere la prossima posizione $q_k$ in cui muoversi per continuare il processo di esplorazione dell'ambiente. $F_{k-1}$ sta ad indicare il safe space calcolato fino all'iterazione precedente, cioè lo spazio libero da ostacoli in cui il robot può muoversi senza rischio di collisioni e $P_{k-1}$ rappresenta l'insieme dei confini dell'ambiente esplorato che corrispondono a pareti o contorni di oggetti rilevati, che vengono detti solid edge. I confini ambientali che invece corrispondono ai valori di fondo scala del laser vengono detti free curve: questi sono i punti vicino a cui generare i candidati per la scelta della successiva posizione di esplorazione. Se non esistono più confini dell'ambiente che corrispondono a free curve, il processo di esplorazione termina.

Figura 2.9: Esempio di esplorazione: i solid edge corrispondono ai contorni dell'ambiente o agli oggetti presenti in esso, le free curve corrispondono ai valori di fondo scala del laser. Immagine tratta da [23].

Il criterio proposto sceglie la posizione ottima all'interno dello spazio libero $F_{k-1}$, tra una serie di candidati generati in modo casuale, eseguendo i seguenti passi:

1. $n$ posizioni vengono generate in modo casuale in $F_{k-1}$
2. Per ogni posizione $q$ viene calcolata la lunghezza dei solid edge (i contorni dell'ambiente corrispondenti a pareti od oggetti presenti in esso) visibili in $F_{k-1}$, tenendo in considerazione la portata del laser in uso e l'orientamento del robot. La posizione $q$ viene tenuta in considerazione solo se tale lunghezza è maggiore di una certa soglia. Questo controllo viene fatto per assicurare il corretto funzionamento dell'algoritmo di riallineamento usato.
3. Viene calcolata la quantità di nuova informazione ottenibile a partire dalla posizione $q$ generando dei raggi equispaziati di lunghezza $r$, uguale al range del laser, e calcolando la porzione del raggio che esce da $F_{k-1}$.
4. La somma di tutte le lunghezze calcolate diventa la quantità di nuova informazione ottenibile da $q$ (vedi Figura 2.10).

In [25] González-Baños e Latombe danno una definizione formale dei concetti espressi in [23] e forniscono una formula di scelta del candidato ottimo che tiene conto anche della distanza da percorrere per raggiungere la posizione scelta. Dati infatti un certo numero di candidati $\mathcal N_{sam}$, la posizione ottima $q$ viene scelta secondo la formula:

$$g(q) = A(q) \cdot exp(- \lambda \cdot L(q,q_k))$$ (2.9)

in cui $L(q,q_k)$ rappresenta la lunghezza del cammino minimo che connette la posizione corrente con quella del candidato $k$-esimo e $\lambda$ rappresenta un parametro settato sperimentalmente a 20 cm$^{-1}$. $A(q)$ è l'informazione ottenibile dalla posizione $q$ calcolata come spiegato in precedenza. Il candidato scelto come successiva posizione da cui effettuare nuove rilevazioni è quello che massimizza $g(q)$.

Figura 2.10: Area potenzialmente visibile attraverso le free curve da una posizione candidata. Immagine tratta da [25].

Osserviamo che per $\lambda = 0$ la posizione migliore viene scelta unicamente in base al vantaggio informativo che porta, mentre per $\lambda \rightarrow \infty$ la scelta viene fatta unicamente in base alla distanza da percorrere e verrà scelto il candidato più vicino al robot.

Nonostante le prove sperimentali proposte dagli autori assicurino la correttezza della formula proposta, questa non viene validata da un'altrettanto solida base teorica, che giustifichi la scelta della funzione esponenziale. Il metodo presentato in questa tesi, invece, pesa l'informazione ottenibile dalla posizione candidata con il costo di raggiungimento di quest'ultima sfruttando il noto concetto di entropia, usata per quantizzare il contributo informativo ottenibile da una posizione.

L'approccio proposto da Burgard, Fox, Moors, Simmons e Thrun in [12], considera il problema dell'esplorazione di un ambiente da parte di $n$ robot mobili. Il metodo proposto si pone l'obiettivo di minimizzare il tempo di esplorazione necessario a mappare completamente un ambiente, coordinando i robot in modo che essi esplorino contemporaneamente regioni diverse. Per raggiungere tale scopo viene impiegato un approccio probabilistico che tiene conto sia dell'informazione ottenibile da una posizione, sia del costo per il raggiungimento di quest'ultima.

Il metodo proposto dagli autori viene validato sia dalla teoria che dalle prove sperimentali, tuttavia tale criterio si adatta naturalmente alle mappe a griglia e non trova applicazione nelle mappe a punti, utilizzate invece nel metodo di esplorazione proposto in questa tesi.

Infine il metodo proposto da Sim e Dudek in [49] consiste in un algoritmo on-line che fa uso di una telecamera per esplorare un ambiente sconosciuto cercando di massimizzarne la copertura. L'approccio presentato è basato sul filtro di Kalman e ha come obiettivo primario la costruzione di una traiettoria di esplorazione sicura che permetta al robot di localizzarsi, basandosi sulla mappa costruita fino a quel momento. La sicurezza della navigazione viene garantita dall'uso di un sonar, atto a evitare le collisioni con gli oggetti presenti nell'ambiente. Tale approccio si differenzia da quello proposto in questa tesi in quanto non valuta solo la prossima posizione di esplorazione, ma un intero insieme di posizioni di osservazione lungo il cammino.