Scelta del candidato ottimo: un approccio basato sull'entropia

La scelta del candidato ottimo viene effettuata, per semplicità, in modo greedy, valutando cioè solo la posizione di esplorazione successiva, senza valutare se essa sia un ottimo globale. Tale scelta si è rilevata vincente dal punto di vista prestazionale, soffrendo tuttavia del problema dei minimi locali. In Figura 3.8 si può osservare come un punto di ottimo globale venga scartato a causa della maggiore informazione ottenibile al prossimo passo da un punto di ottimo locale. Quest'ultimo tuttavia non si rivela essere una buona scelta al passo successivo, poiché il robot si dirige verso una parete e dovrà necessariamente tornare indietro.

Figura 3.8: La metodo greedy porta alla scelta di ottimi locali

La scelta del candidato ottimo viene fatta, mediante stime probabilistiche, secondo il seguente criterio: sia $\Delta C$ il costo dovuto al movimento del robot per mappare completamente l'ambiente. La stima di tale valore, in condizioni ideali è data da:

$$E[\Delta C] = P - a$$

dove $P$ indica il perimetro stimato dell'ambiente e $a$ la lunghezza copribile con una singola misurazione. Se $P \approx a$, allora il robot non deve muoversi per completare il processo di mapping ( $E[\Delta C] \approx 0$), se invece $P \gg a$, allora il robot dovrà muoversi ancora per tutto il perimetro $P$ ( $E[\Delta C] \approx P$).

La misura dell'informazione ottenibile a partire da una posizione candidata si basa sul concetto di entropia relativa [13], [48]:

$$H_f = -\int f(X) \ln \frac{f(X)}{f_0(X)} dX$$

dove $X$ è il vettore contenente i parametri di posizione dei punti della mappa, $f$ è la funzione di densità di probabilità (PDF) dei valori di $X$ e $f_0(X)$ è la PDF non-informativa, assunta come uniforme [52].

Ciò a cui siamo interessati è un calcolo a priori della variazione entropica a seguito di una misurazione.

Data l'informazione corrente che abbiamo sull'ambiente, descritta dalla distribuzione a priori $f(X)$ e da quella a posteriori $f'(X)$, l'incremento atteso di entropia relativa sarà dato da:

$$E[\Delta H] = E[H_{f'}] - H_f = - \int \hspace{-2mm} \int f'(X\vert Z) \ln \frac{f'(X\vert Z)}{f_0(X)} dX dZ + \int f(X) \ln \frac{f(X)}{f_0(X)} dX$$

Il valore atteso è dovuto al fatto che il valore reale di $H_{f'}$ dipende dal risultato della misura $Z$, ignota a priori.

Considero la misurazione di un punto nella posizione di partenza del robot. In questo caso la posizione di osservazione non è affetta da incertezza. Supponendo di lavorare con distribuzioni gaussiane e ipotizzando che gli errori delle misurazioni fatte in punti diversi dell'ambiente siano incorrelati, il valore atteso della variazione di entropia sarà data da:

$$E[\Delta H] \approx \sum_i \ln \frac{\sigma}{\sigma_{p,i}}$$

dove $\sigma_{p,i}$ è la deviazione standard della misurazione a priori rilevata in $i$. Se considero l'insieme $\mathcal N$ dei punti nuovi rilevati con una scansione, con $N = \vert\mathcal N\vert$, allora il valore atteso di $\Delta H$ nella posizione di partenza verrà dato dalla formula:

$$E[\Delta H] = \sum_{i \in \mathcal N} \ln \frac{\sigma}{P} = N \ln \frac{\sigma}{P}$$

Nelle posizioni diverse da quella di partenza, anche la posa del robot sarà affetta da incertezza. Se esiste un insieme $\mathcal A \neq \emptyset$, di punti già rilevati, l'incertezza della posizione influisce sull'incertezza a posteriori sia dei punti precedentemente rilevati $\mathcal A$, che di quelli nuovi $\mathcal N$.

I contributi di errore dovuti all'incertezza sulla posizione del robot in diversi punti di rilevazione sono correlati, per cui non si può sostituire semplicemente $\sigma$ con $\sqrt{\sigma^2 +\sigma_{unc,i}^2}$, dove con $\sigma_{unc,i}$ si intende l'incertezza con cui si misura il punto $i$, dovuta ad errori odometrici. Quando il robot si sposta in una nuova posizione infatti, viene commesso un errore nel calcolo dello spostamento effettuato (errore odometrico) che dipende dall'entità dello spostamento stesso e che si ripercuote sulla misurazione che verrà effettuata nella nuova posizione. Nel nostro caso, poichè il riferimento della mappa globale è centrato sul laser, l'errore odometrico influirà sul calcolo della rototraslazione del sistema di riferimento globale nella nuova posizione di esplorazione rispetto alla posizione precedentemente occupata dal robot.

La proprietà di additività dell'entropia relativa [48] permette di ottenere una formula che tenga conto di tutti i contributi. Suppongo che l'insieme dei possibili valori di $X$ possa essere diviso in sottoinsiemi distinti. L'entropia verrà quindi calcolata come somma del contributo associato ai diversi sottoinsiemi ( $-\sum_j P_j \ln P_j$, dove $P_j$ è la probabilità che il valore della variabile considerata appartenga al $j$-esimo sottoinsieme) e della somma pesata delle entropie all'interno dei sottoinsiemi in esame:

$$H_f = -\int f(X) \ln \frac{f(X)}{f_0(X)} dX = -\sum_j P_j \ln P_j + \sum_j P_j \bigg(\int f(X\vert j) \ln \frac{f(X\vert j)}{f_0(X)} dX \bigg)$$

Supponendo che $\sigma_{unc} \gg \sigma$ possiamo suddividere l'insieme dei possibili valori di misurazione in range di ampiezza $\sigma$ (corrispondente all'accuratezza del laser) e assumere che range differenti siano associati a sottoinsiemi disgiunti di possibili posizioni del robot. In questo caso l'entropia relativa totale è dovuta a due contributi, quello relativo all'entropia associata ai diversi range e alla somma pesata delle entropie delle misure in ciascun range. Assumendo che range diversi abbiano probabilità uniforme $\sigma/\sigma_{unc}$, il primo termine sarà dato da $-\ln(\sigma/\sigma_{unc})$, ma dato che $\sigma_{unc,i}$ non è costante per i diversi punti misurati, tale contributo dovrà essere pesato sui tutti i punti divenendo:

$$\frac{1}{N+A} \sum_i \ln \frac{\sigma_{unc,i}}{\sigma}$$

Per il calcolo totale del valore atteso della variazione di entropia abbiamo quindi ottenuto l'espressione:

$$E[\Delta H] \approx \frac{1}{A+N} \sum_{i \in \mathcal{A} \cup \m... ...\ln \frac{\sigma}{P} + \sum_{i \in \mathcal{A}} \ln \frac{\sigma}{\sigma_{p,i}}$$

dove $A = \vert{\mathcal A}\vert$ è il numero di punti rimisurati nella posizione considerata, $N$ è il numero di punti nuovi, $\sigma_{unc,i}$ è l'incertezza con cui si misura il punto $i$ dovuta all'errore odometrico, che dipende dalla posizione relativa del punto rispetto al robot e $\sigma_{p,i}$ rappresenta la deviazione standard a priori del punto $i$ già misurato in precedenza. I termini dell'equazione precedente esprimono rispettivamente l'incertezza dovuta agli errori di posizione del robot, l'incertezza dovuta ai nuovi punti e quella dovuta ai punti già misurati in precedenza.

Nelle prove sperimentali, data una posizione di osservazione $q$, i parametri descritti nella formula precedente sono stati calcolati come segue:

• ${\mathcal A}$ è l'insieme di punti di $M_{k}$ che cadono nel range dello scanner laser quando il robot rileva le quattro scansioni nella posizione $q$, costruendo la mappa parziale $m_k$.
• $N$ viene calcolato come $N_k - A$, dove $N_k$ è il numero di punti che compone $m_k$. In questo caso viene fatta un'assunzione sulla regolarità dell'ambiente: mappe parziali diverse hanno approssimativamente lo stesso numero di punti.
• $\sigma_{unc,i} = V_{\theta}\cdot d^2 + V_{xy}$, dove $V_{\theta}$ rappresenta la componente rotazionale dell'errore di posizione del robot in $q$, $d$ indica la distanza tra la posizione corrente del robot e $q$, $V_{xy}$ è la componente traslazionale dell'errore di posizione del robot in $q$.
• $\sigma = 0.0001$.
• $P = 20$ metri.
• $\sigma_{p,i}$ viene posta a $2\sigma$, assumendo che l'algoritmo di riallineamento esegua un match senza errori.

In condizioni ideali la distanza totale percorsa dal robot durante l'esplorazione è data da:

$$\overline{\Delta C} = P - a$$

equivalente alla lunghezza della mappa a cui viene tolta la misurazione effettuata nella posizione di partenza, mentre l'informazione acquisita risulta essere:

$$\overline{\Delta H} = N \ln \frac{\sigma}{P}$$

con $N = P/s$ ($s$ = distanza di campionamento).
Assumendo $s \approx \sigma$, allora posso esprimere $\overline{\Delta H}$ come:

$$\overline{\Delta H} = \frac{P}{\sigma} \ln \frac{\sigma}{P} = - \frac{P}{\sigma} \ln \frac{P}{\sigma}$$

Sostituendo $P = \overline{\Delta C} + a$, l'espressione di $\overline{\Delta H}$ diventa:

$$\overline{\Delta H} = - \frac{\overline{\Delta C} + a}{\sigma} \ln \frac{\overline{\Delta C} + a}{\sigma}$$

La cifra di merito per la scelta del candidato rappresenta lo scostamento tra il valore atteso $E[\Delta H]$ e il valore calcolato $\Delta H = - (\Delta C + a)/\sigma \ln (\Delta C + a)/\sigma$ dove $\Delta C$ indica la distanza che separa la posizione corrente dal candidato e $a$ la distanza coperta da una singola misurazione. La formula finale per la scelta del candidato ottimo risulta quindi essere:

$$J = E[\Delta H] + \frac{\Delta C + a}{\sigma} \ln \frac{\Delta C + a}{\sigma}$$

Il parametro J viene calcolato per ogni candidato e il candidato selezionato è quello a cui corrisponde $J$ minimo.