Tecniche che non fanno uso di odometria

In letteratura si possono trovare anche alcuni tentativi che mirano a risolvere il problema della localizzazione e della costruzione di una mappa geometrica senza ricorrere alle informazioni odometriche.

Per esempio, Einsele in [19] ha sviluppato un approccio al problema avvalendosi di tecniche di programmazione dinamica (DP, Dynamic Programming), opportunamente adattate al contesto dello scan matching. Attraverso un processo incrementale, a ogni acquisizione sensoriale la nuova mappa acquisita viene confrontata con una mappa di riferimento, scelta nell'insieme delle mappe precedentemente acquisite, e l'informazione ottenuta viene utilizzata per la localizzazione del robot. La nuova mappa viene poi aggiunta a una particolare struttura dati ad albero al fine di ottenere una descrizione topologica dell'ambiente.

Il sensore di acquisizione utilizzato a tale scopo è uno scanner panoramico, capace di acquisire una scansione a 360 gradi. Ad ogni scansione il sensore restituisce una mappa costituita da una lista di punti ordinata secondo il senso di scansione. La mappa così ottenuta viene pre-elaborata nel modo seguente. Inizialmente viene applicato un filtro di segmentazione in grado di generare una mappa a segmenti con un algoritmo simile a quanto proposto in [65]. Considerando la mappa a punti come una lista ordinata secondo l'ordine di scansione del sensore, vengono presi due punti qualsiasi della mappa e uniti con un segmento e viene poi calcolata la distanza da tale segmento di tutti i punti compresi tra i due estremi del segmento stesso; se il punto più distante ha distanza maggiore di una soglia predefinita, il segmento viene diviso in due utilizzando quel punto come estremo comune dei due nuovi segmenti e si applica ricorsivamente il metodo ai due segmenti generati.

Nella seconda fase, i segmenti ottenuti in precedenza vengono raffinati attraverso il metodo dei minimi quadrati rispetto ai punti che li hanno generati. Infine i segmenti vengono descritti attraverso la rappresentazione normale di Hesse nella quaterna $\left( \alpha, d, \varphi_{s}, \varphi_{e} \right)$, dove $d$ è la distanza del segmento rispetto all'origine, calcolata rispetto alla retta di appartenenza di angolo $\alpha$, mentre $\varphi_{s}$ e $\varphi_{e}$ sono gli angoli sotto i quali sono visti l'estremo iniziale e finale del segmento.

Per lo scan matching viene utilizzata una tecnica di programmazione dinamica [6] che consiste nel confronto tramite pattern matching degli insiemi di segmenti della mappa appena acquisita $M_{T}$ e di una mappa di riferimento $M_{R}$, scelta tra quelle acquisite in precedenza. Dati in ingresso due insiemi di segmenti, l'algoritmo DP restituisce una associazione tra i vari segmenti e una misura che ne rappresenta la similarità.

La misura di similarità tiene conto delle differenze tra i parametri di distanza $d$ e di angolo $\alpha$ dei due segmenti, restituendo come valore massimo 1 se i due segmenti sono perfettamente sovrapposti e valori compresi nell'intervallo $\left( 0, 1 \right)$ per gli altri casi. Sulla base delle associazioni ottenute, viene determinata la trasformazione che permette l'allineamento ottimo delle mappe in termini di traslazione $\left( \Delta x, \Delta y \right)$ e di rotazione $\Delta \theta$. Per il calcolo della traslazione, per ogni coppia di segmenti associati viene richiesto che lo spostamento copra la distanza che separa i due segmenti, risolvendo la seguente equazione:

$$r_{i} \cos \alpha _{iR} \cdot \Delta x + r_{i} \sin \alpha _{iR} \cdot \Delta y = r_{i} \left( {d_{R} - d_{T} } \right)$$ (2.7)

dove $\alpha _{iR}$ è l'angolo dell'$i$-esimo segmento della mappa di riferimento $M_{R}$, $d_{R}$ e $d_{T}$ sono le distanze dei due segmenti confrontati, rispettivamente appartenenti alla mappa $M_{R}$ e alla mappa $M_{T}$, e $r_{i}$ è un coefficiente che tiene conto del numero di punti che hanno concorso alla formazione del segmento rispetto al numero totale di punti nella mappa. Mettendo assieme tutte le equazioni relative a ogni coppia di segmenti si ottiene un sistema (sovradimensionato) nelle variabili $\Delta x$ e $\Delta y$ che viene risolto con il metodo dei minimi quadrati, determinando così la traslazione.

Per quanto riguarda la rotazione, l'angolo $\Delta \theta$ viene calcolato come la media di tutte le differenze angolari di ciascuna coppia:

$$\Delta \theta = \sum\limits_{i = 1}^n {r_{i} \left[ {\left( {\alpha _{iR} - \alpha _{iL} } \right)} \right]}$$ (2.8)

Dopo aver ottenuto la localizzazione del robot, la nuova mappa viene memorizzata in una struttura dati ad albero dove ogni nodo contiene la mappa a segmenti ottenuta e la posizione in cui è stata percepita mentre gli archi congiungenti i nodi determinano le relazioni di vicinanza tra le varie mappe.

I principali limiti del metodo proposto risultano essere i seguenti: questa soluzione può essere usata principalmente in ambienti di tipo poligonale; inoltre il sistema si basa implicitamente sull'assunzione di brevi spostamenti del robot tra una scansione e l'altra. Nella prova sperimentale proposta, su una distanza percorsa di 8 metri sono state effettuate $53$ scansioni, quindi con uno spostamento medio inferiore ai $15$ centimetri.