Euristiche di semplificazione delle mappe a punti

Data una mappa a punti risulta spesso necessaria una semplificazione atta a rendere più rapide le operazioni da svolgere sulla mappa stessa. L'obiettivo primario è quello ottenere un sottoinsieme $Q$ di $m$ punti da un insieme $P$ formato da $n$ punti di partenza (con $m$ $\le$ $n$). In [16] vengono proposte diverse soluzioni che operano su mappe a punti, partizionabili in due classi principali:

1. Algoritmi che partono da una soluzione generata in modo casuale e che applicano regole iterative per procedere alla semplificazione.
2. Algoritmi di clustering che partizionano l'insieme di partenza e scelgono un punto rappresentativo per ogni partizione creata.

Algoritmi iterativi:
Questa classe di algoritmi procede in modo iterativo trovando diverse soluzioni al problema della semplificazione e scegliendo la migliore. La differenza primaria tra le diverse tecniche risiede nel modo in cui il sottoinsieme $Q$ viene generato.

Scelta del miglior elemento tra $k$ sottoinsiemi generati in modo casuale:
Consideriamo $k$ sottoinsiemi generati in modo casuale $Q_1,\dots,Q_k$ dall'insieme $P$, calcoliamo l'errore di approssimazione per ognuno [16] e scegliamo il sottoinsieme che genera l'errore di approssimazione minore. In questo approccio, maggiore è il numero $k$ dei sottoinsiemi generati in modo casuale, migliore risulta l'approssimazione dell'insieme di partenza.

Simulated annealing:
Questa tecnica di semplificazione [32] inizia con una soluzione casuale e cerca di convergere alla soluzione ottima introducendo dei cambiamenti nel sottoinsieme in esame, anch'essi generati in modo casuale. Un cambiamento viene mantenuto se migliora la soluzione (il sottoinsieme $Q$) corrente oppure se viene incontrata una condizione di fine. Un cambiamento casuale consiste, ad esempio, nello scegliere un punto in $Q$ e sostituirlo con un punto in $P/Q$, generando il sottoinsieme $Q'$. La generazione casuale della sostituzione avviene nel modo seguente: durante la $i$-esima iterazione, il sottoinsieme $Q$ viene rimpiazzato con il sottoinsieme $Q'$ con la probabilità $Pr$, espressa in (2.1):

$$Pr = e^{\frac{\Delta(Q,P) - \Delta(Q',P)}{T_i}}$$ (2.1)

dove $T_i$ è un parametro di valore $T_i = (k-i)/k$, $k$ è il numero totale di iterazioni dell'algoritmo e $\Delta(Q,P)$ e $\Delta(Q',P)$ rappresentano gli errori di approssimazione di $Q$ e $Q'$ rispetto a $P$, definiti in [16] nel modo seguente:

$$\Delta_R (Q,P) = max_{ r \in R} \mid~\mid r \cap P \mid - (n/m) \cdot \mid r \cap Q \mid ~\mid$$ (2.2)

con $R$, famiglia di range considerati (porzioni dell'insieme considerato) e $r$, particolare range in esame. $n$ e $m$ sono rispettivamente il numero di punti degli insiemi $P$ e $Q$.

Swapping:
Dapprima otteniamo un'approssimazione di $P$ considerando un sottoinsieme $Q$ di grandezza $m$ generato in modo casuale e quindi tentiamo di migliorarlo nel seguente modo: calcoliamo un range $r_{pos}$ con il maggiore errore casuale positivo e un range $r_{neg}$ con il maggiore errore casuale negativo.

Il calcolo degli errori casuali positivo e negativo si ottiene a partire da (2.2) senza applicare il valore assoluto alla differenza. In questo modo un errore positivo indicherà che il valore di $\mid r \cap P \mid$ è superiore a quello di $(n/m) ~\cdot\mid r \cap Q \mid$ e viceversa in caso di errore negativo.

Da $Q$ togliamo un insieme casuale di punti in $Q \cup r_{neg}$ e aggiungiamo un insieme casuale di punti in $(P/Q) \cup r_{pos}$. Questa euristica è fortemente dipendente dall'avere una buona configurazione di partenza. Se ciò non accade si rischia di ottenere un minimo locale senza speranza di ulteriori miglioramenti.

Swapping con restart:
Questa è una variante della tecnica precedente che ricomincia con un insieme $Q$ random se 10 iterazioni consecutive della tecnica di Swapping falliscono nel migliorare la soluzione.

Swapping con il 10% di perturbazione:
Se 10 iterazioni consecutive di Swapping non migliorano la soluzione, vengono rimossi $\lceil m/10 \rceil$ punti in modo casuale e vengono sostituiti con $\lceil m/10 \rceil$ punti di $P/Q$.

Algoritmi di Clustering:
Le tecniche di clustering agiscono partizionando (implicitamente o esplicitamente) l'insieme $P$ di partenza in $m$ gruppi e scegliendo per ogni gruppo uno o più campioni rappresentativi.

Righe e Colonne:
Questa euristica produce un sottoinsieme $Q$ con $m = r \times s$ elementi ordinando gli $n$ punti dell'insieme di partenza secondo valori crescenti delle ascisse e raggruppandoli in colonne, ognuna contenente $n/r$ punti. I punti all'interno di ogni colonna vengono quindi ordinati e raggruppati in righe di $n/m$ elementi. Otterremo quindi un partizionamento del piano in $m$ celle rettangolari, ognuna contenente $n/m$ punti. Per formare l'insieme $Q$ viene preso un campione per ogni cella.

Quadtree:
Questa tecnica è basata sulla struttura dati a quadtree. Sia $S$ un quadrato orientato secondo gli assi contenente l'insieme $P$ di partenza. Partizioniamo $S$ in modo ricorsivo nella maniera seguente: se $S$ contiene meno di $4 \delta$ punti (con $\delta = n/m$, rapporto tra il numero di punti dell'insieme di partenza e dell'insieme semplificato) non viene fatto nulla, altrimenti $S$ viene partizionato in 4 quadrati e ogni quadrato viene ripartizionato in modo ricorsivo.

Una volta calcolata questa partizione, scegliamo un campione per ogni quadrato. Se il quadrato contiene $k$ punti di P, allora scegliamo un insieme di elementi pari a $\lfloor k/\delta + 1/2 \rfloor$ da quel particolare quadrato.

Dobkin-Tal:
Il metodo, originariamente proposto da Dobkin e Tal in [18] funziona nel modo seguente:

• Considero un insieme P di punti di una mappa
• La mappa viene semplificata accoppiando un punto della mappa con quello a lui più vicino all'interno della mappa stessa.
• Una volta trovate le coppie si rimpiazzano i due punti accoppiati con il punto medio, generando l'insieme Q che rappresenta la nuova mappa.

Il metodo gode delle seguenti caratteristiche, che lo hanno portato ad essere scelto nella presente tesi, al fine di semplificare le mappe a punti:

• Non necessita di un ordinamento dei punti, al contrario di altri metodi.
• Le operazioni da effettuare sono semplici e quindi vengono eseguite velocemente.
• Il metodo funziona bene con punti uniformemente distribuiti, come nel caso di scansioni di pareti od oggetti rilevati mediante scansioni laser.

In Figura 2.4 si può notare come il metodo implementato snellisca la mappa dell'ambiente, riducendo il numero dei punti da 643 a 327 senza tuttavia perdita significativa di informazione.

Figura 2.4: Clustering di una mappa al fine di ridurne il numero di punti