2.1Cennistorici 2Localizzazionespaziale

2

Localizzazione spaziale

2.1 Cenni storici

Il problema di avere una stima della propria posizione spaziale nelle mappe terrestri è sempre stato fondamentale per l'uomo. Si può ritenere che tale problema si è presentato per la prima volta nel momento in cui l'uomo si è discostato da

riferimenti prettamente visivi e legati alla topografia del terreno per esplorare ambienti in cui essi mancavano del tutto e di cui non si poteva nell'immediato tracciare una mappa topologica. Questi aspetti vennero affrontati seriamente nel momento in cui l'uomo cominciò a solcare le vastità degli spazi marittimi, per

raggiungere territori sempre più lontani che la semplice navigazione lungo costa non avrebbe potuto permettere.

I primi sistemi di orientamento erano praticamente legati a dei punti di riferimento che fossero sempre immutabili e onnipresenti come le stelle. Nacquero quindi strumenti atti a determinare la propria posizione rispetto ad astri di riferimento, tra questi possiamo citare l'ottante e il sestante [13] che insieme alla bussola [14] e ad un orologio costituiscono un accuratissimo sistema di localizzazione globale. La soluzione al problema della localizzazione coinvolgeva diverse branche della scienza come l'astronomia, la matematica e la geografia.

Nel '700 la navigazione oceanica era ancora condotta alla stima del parallelo, non molto differente da quanto iniziarono Portoghesi e Spagnoli tre secoli prima. L'astronomia di posizione permetteva solo un controllo in maniera diretta della latitudine e non della longitudine. L'altezza del sole, della stella polare o della croce del sud veniva misurata con astrolabi o quadranti, tutti strumenti, cioè a visione diretta, la cui precisione solo in condizioni più che ideali (calma piatta, cielo sereno, ottimo strumento), poteva avvicinarsi ad un terzo di grado. Onde ottenere la latitudine, tale misurazione veniva poi elaborata utilizzando apposite tavole.

Il principio su cui si basavano tali strumenti era la misura dell'angolo tra la stella polare e l'orizzonte che determina la latitudine. Funziona sempre perché la posizione della stella polare è invariante rispetto alla rotazione terrestre.

La longitudine è un po' più complessa da calcolare. Essa si basa sull'osservazione dei “Fenomeni Medicei” [15] ossia particolari fenomeni astronomici osservabili simultaneamente da qualsiasi località del globo terrestre. Se si calcola il tempo solare in cui si verifica un fenomeno mediceo in differenti località è possibile verificare che lo stesso fenomeno ha tempi solari differenti; convertendo le differenze di tempo in gradi è possibile stabilire sia la misura di longitudine di una località rispetto a Greenwich, dove passa il meridiano fondamentale, sia la differenza di longitudine tra le diverse località. Era il primo sistema di localizzazione assoluta al

mondo, l'equivalente del moderno GPS.

L'avvento dell'era tecnologica (seconda metà del '900), la diffusioni di sistemi di misura delle distanze sempre più raffinati, la necessità di automatismi industriali, la necessità di utilizzi in sistemi di riferimento sempre più circoscritti, hanno reso indispensabile lo studio e l'attuazione di metodologie sempre più sofisticate che non fossero legati a riferimenti assoluti come le mappe stellari o topografiche, fino a giungere ai moderni sistemi di controllo e automazione robotica.

2.2 Sistemi di localizzazione

Il problema fondamentale della localizzazione è quello di rendere una persona o un oggetto (ad esempio un robot) in grado di riconoscere la propria posizione nell'ambiente o come nel nostro caso di rendere un sistema domotico in grado di sapere in ogni istante la posizione e l'orientamento del tracked target (l'obiettivo tracciato o monitorato).

A secondo di come viene codificata la posizione del target e del metodo di misura della posizione utilizzato, possiamo identificare diverse categorie di LPS.

Una prima suddivisione, quindi, può essere così fatta:

● Localizzazione dipendente dalla codifica della posizione: ○ Localizzazione in coordinate cartesiane

○ Localizzazione su mappa topologica

● Localizzazione dipendente dal metodo di misura e\o calcolo della posizione:

■ Ricostruzione odometrica;

■ Navigazione inerziale;

○ Localizzazione Assoluta:

■ Landmark naturali/artificiali; ■ Boe attive/passive

■ Comparazione di mappe (Model Matching)

2.3 Localizzazione in coordinate cartesiane

Notazione usata in questo tipo di problemi:

● Of(xf,yf) sistema di riferimento fisso

● Gf(xr,yr) sistema di riferimento solidale al target

Il problema fondamentale di questo metodo diventa il calcolo della matrice di trasformazione Trftale che:

Gr=TrfGf

ovvero trovare quella particola matrice di traslazione/rotazione che permetta di mettere in relazione la posizione del target nel sistema di riferimento assoluto con quello solidale al target stesso.

2.4 Localizzazione su mappa topologica

In questa tipologia l'ambiente viene rappresentato mediante un grafo T composto da m nodi e n archi; i nodi raffigurano locazioni significative (ad esempio stanze, corridoi, porte) mentre gli archi identificano le relazioni di adiacenza tra i nodi. La posizione del target viene pertanto identificata come un nodo nel grafo.

2.5 Metodi di localizzazione relativa

Il sistemi di localizzazione relativi ci permettono di rispondere alla domanda “Dove sono rispetto a dove ero nel momento in cui comincio ad osservare la mia posizione”, presuppongono il calcolo di una direzione e una velocità del moto. La direzione e la velocità possono essere di per sé assoluti ( speedometri, compassi) o solidali (giroscopi, accelerometri). I sistemi relativi sono spesso molto più accurati nel breve termine ma soffrono di errori di accuratezza nel lungo termine.

● Sistemi odometrici ( misure di velocità, accelerazione, rotazione) ● Navigazione inerziale ( giroscopi, accelerometri).

Si tratta di metodi incrementali che misurano la nuova posizione del target basandosi su una posizione nota (o comunque stimata al passo precedente).

2.5.1 Ricostruzione odometrica ( gli encoders )

L'odometria, nonostante sia affetta da errori sistematici e non, è il metodo più usato per la localizzazione dei robot in quanto non ha alti costi di applicazione ed è facilmente integrabile con altri metodi di localizzazione che invece danno misure più accurate.

L'idea di base della ricostruzione odometrica è quello del calcolo della nuova posizione del target in base alla strada percorsa rispetto alla posizione precedente. Il calcolo avviene tramite l'integrazione nel tempo dell'informazione di movimento. Per ricavare i valori da integrare, l'odometria utilizza degli Encoder, attaccati agli assi delle ruote o all'armatura del motore che vanno a misurare la velocità di rotazione delle ruote e/o l'orientamento dello sterzo (basandosi sul principio che la rotazione compiuta da una ruota può essere tradotta in spostamento lineare). In particolare abbiamo bisogno di due tipi differenti di encoder (in robotica mobile esistono molti tipi diversi di encoder, ma i più usati son quelli ottici):

● Encoder ottici incrementali: misurano la velocità di rotazione delle

ruote e da essa ricavano direttamente la relativa posizione.

● Encoder ottici assoluti: misurano la posizione angolare delle ruote e da

essa ricavano la relativa velocità.

Il principio di base di entrambi è quello di avere un fascio di luce puntato su un fotorecettore, che viene periodicamente interrotto da una sequenza di segmenti opachi/trasparenti, posta su un disco rotante, solidale con l'albero motore. In particolare l'encoder ottico incrementale interrompe il raggio di luce producendo un'onda quadra con un certo numero di impulsi per ogni rotazione completa dell'albero motore.

Un esempio di encoder incrementale è il Tachometer Encoder fornito di un solo canale di riproduzione e che quindi gestisce solo le funzionalità di base appena

descritte. Per aumentare la risoluzione, quindi, bisogna aumentare il numero di impulsi, ma inevitabilmente anche il costo del dispositivo. Inoltre questo tipo di encoder non funziona bene in applicazioni a bassa velocità a causa di problemi dovuti agli errori di quantizzazione e soprattutto non sono in grado di rivelare la direzione di rotazione delle ruote, ovvero misurano la velocità in valore assoluto.

Per risolvere quest’ultimo problema al posto dei tachometers vengono usati i

Phase Quadrature Incremental Encoder che usano due canali di riproduzione, il

secondo dei quali è sfasato rispetto al primo di 90°. In questo modo questo tipo di encoder è in grado di identificare anche il verso di rotazione delle ruote, perché le posizioni intermedie dell'albero motore sono rappresentate da numeri binari che l'encoder può “contare” in avanti oppure indietro rispetto alla sua posizione di partenza (dalla tabella sottostante si vede come i codici delle posizioni intermedie dell'albero motore siano codificati con il codice Gray, dove ogni stato differisce dall'altro solo per un singolo bit).

In caso di applicazioni che coinvolgono rotazioni continue di 360°, molti encoders incorporano anche un terzo canale che si alza una sola volta per ogni rotazione completa dell'albero motore (vedi canale I della figura sopra) e che quindi indicano quante rotazioni complete sono state effettuate.

Negli encoder ottici assoluti non abbiamo più un solo fotorecettore che riceve uno stream di bit sequenziali, bensì vengono usati degli array di fotorecettori che ricevono i bit in parallelo.

Come si può notare nella figura precedente, l'encoder, posto sull'albero motore è composto da più tracce concentriche, in modo che, la successione di segmenti opachi/trasparenti, generi delle “parole” ovvero una stringa di bit in parallelo e non una sequenza. Ovviamente per ogni posizione del disco di ottengono dei codici che identificano in maniera univoca le varie posizioni angolari assolute dell'albero motore.

I codici più usati per questo tipo di applicazione sono o il codice Gray oppure il codice binario generico. Gli encoder ottici assoluti sono utilizzati soprattutto per applicazioni “lente”, che richiedono informazioni sulla posizione e che non ammettono la perdita di riferimento in seguito a interruzioni nell'alimentazione.

Come limiti di questi encoder, infine, si può citare il fatto che necessitano di un disco decisamente più grande per aumentare la risoluzione (ogni traccia aggiunta raddoppia la risoluzione), ciò ne aumenta considerevolmente il costo (ogni traccia quadruplica il costo); inoltre questi dispositivi sono molto meno robusti agli urti, alle

vibrazioni e alle temperature.

2.5.2 Navigazione inerziale

La navigazione inerziale per il calcolo della posizione utilizza invece giroscopi e accelerometri; i primi misurano la velocità di rotazione, i secondi invece l'accelerazione. La navigazione inerziale fornisce misure dinamiche e a breve termine, inoltre ha il vantaggio di non avere bisogno di informazioni esterne sulla dinamica del movimento perché i dati sono ricavati tramite misurazione dirette. Il grosso svantaggio della navigazione inerziale però è dovuto al fatto che per ottenere l'orientazione e la posizione bisogna integrare una volta e due volte, rispettivamente, la velocità di rotazione e l'accelerazione, generando quindi errori in posizione che crescono in modo integrale col tempo (deriva).

2.6 Metodi di localizzazione assoluta

Il sistemi di localizzazione assoluti ci permettono di rispondere alla domanda “Dove sono rispetto ad una limitata zona di osservazione o a tutto il resto del mondo”. Si tratta di metodi che calcolano la posizione assoluta del target nello spazio senza avere bisogno di una stima precedente.

2.6.1 Riconoscimento di Landmark

I landmark sono tratti distintivi dell'ambiente che l'LPS può riconoscere con il proprio sistema sensoriale. I landmark, generalmente, sono scelti in maniera tale da essere facilmente riconoscibili (ad es. contrastano con lo sfondo) e possono essere di due tipi [29]:

● naturali, ovvero segni o oggetti che già preesistono nell'ambiente come

porte, angoli, lunghe pareti, rilevabili ad esempio con sensori di prossimità (laser [24], ultrasonici [22]);

● artificiali, ovvero oggetti costruiti appositamente per la

navigazione-localizzazione, come lampade, luci sul soffitto, forme geometriche quali rettangoli, linee, cerchi (che possono anche contenere informazioni aggiuntive tipo codici a barre) nel caso di sensori visivi.

Compito fondamentale della localizzazione è quella di riconoscere i landmark, la cui posizione è fissa e nota a priori, e di calcolare la posizione in base a quelli riconosciuti dal sistema sensoriale. Per semplificare il problema si assume che posizione e orientamento siano noti con buona approssimazione, ad esempio tramite un sistema odometrico, in modo tale da diminuire lo spazio di ricerca.

Questo metodo di localizzazione essenzialmente può essere composto in quattro fasi come in figura:

Se si utilizzano i landmark naturali, il sistema di localizzazione è generalmente composto da:

● un sensore (di tipo visivo) che viene usato nella Fase 1 per l'acquisizione dei dati sensoriali e nella Fase 2 per riconoscere i landmark dallo sfondo;

● un metodo per trovare le corrispondenze (matching) tra i landmark

osservati e una mappa acquisita in fase di addestramento (training) dove sono segnati tutti i landmark

● un metodo per calcolare la posizione del target e stimare l'errore in

relazione alle corrispondenze trovate, usato in Fase 411

Il problema fondamentale con i landmark naturali è quello del riconoscimento. Utilizzando i landmark artificiali la fase di riconoscimento risulta molto più semplice, perché i landmark sono progettati appositamente per massimizzare il contrasto con lo sfondo e per avere una forma nota con precisione, inoltre i sensori di rilevamento dei landmark possono essere progettati ad-hoc per quella particolare applicazione.

2.7 Sistemi basati su boe

L'uso di sistemi di navigazione basato su boe è largamente utilizzato nella

11 Ad esempio usando i Filtri di Kalman o la localizzazione di Markov, che si descriveranno nel prossimo capitolo.

navigazione aerea e navale. Tale sistema permette di ottenere un'informazione di posizione con il minimo dispendio computazionale, fornendo al tempo stesso un alto grado di precisione, tuttavia conduce ad alti costi d'installazione e di manutenzione.

Questo metodo di localizzazione può essere identificato come un caso particolare di riconoscimento di landmark artificiali; le boe infatti sono dispositivi costruiti appositamente per la localizzazione e possono essere distinti in due topologie:

● boe passive: semplici specchi che riflettono un fascio di luce (laser);

● boe attive (active beacons): ovvero dispositivi che rispondono al fascio

di luce emesso dal target, ad esempio su un canale ad infrarossi, codificando l'angolo con cui sono stati colpiti da questo. Questi sono quelli di gran lunga più usati; unico svantaggio sono gli elevati costi di installazione e manutenzione (le boe devono essere posizionate con molta precisione). Ovviamente le boe devono essere posizionate in punti noti e per il calcolo della posizione si usano algoritmi di triangolazione, trilaterazione o multilaterazione.

2.7.1 Trilaterazione

La trilaterazione si basa sul calcolo della posizione a partire dalla misura della distanza esistente tra le boe. Tale metodo prevede l'uso di tre o più trasmettitori posizionati in punti noti dell'edificio e di un ricevitore montato ad esempio a bordo di un robot; tuttavia nulla vieta di effettuare l'operazione complementare, ossia montare i ricevitori sulle pareti di una stanza ed il trasmettitore sul tracking target. Usando il TOF (Time of Flight) del segnale emesso dai trasmettitori il sistema computa la distanza esistente tra ciascun trasmettitore ed il ricevitore o equivalentemente tra ciascun ricevitore ed il trasmettitore. Di fatto il GPS [30] (Global Positioning System) o le boe ultrasoniche sono un esempio tipico di applicazione della trilaterazione12_.

La soluzione del problema della trilaterazione passa dal calcolo del punto di intersezione di tre sfere. Uguagliando le equazioni delle tre sfere e imponendo come vincoli la posizione di ciascuna che risulta nota si determina il punto di intersezione

12 Applicazioni di tali sistemi verranno discusse nel capitolo successivo.

B. In formule: r₂2 _{= x−d }2_y2_z2 r₁2 = x2 y2 z2 r32 = x−i 2y−j2z2

il sistema di tre equazioni porta alla soluzione:

x = r12−r22d2 2d y = r1 2_−r 3 2_{x−i }2 2j  j 2 − r₁2_−r 2 2_d2_2 8d2 _j z =



dove x,y,z rappresentano le coordinate del punto cercato.

Poiché come è facile riscontrare sia matematicamente dalla soluzione della coordinata Z, sia graficamente dalla intersezione delle tre sfere, sono possibili 1, 2 o nessuna soluzione al problema, è facile immaginare che in presenza di segnali disturbati dal rumore si possano verificare problemi pratici, soprattutto nel caso in cui sia presente almeno una soluzione.

Nel caso si presentino 2 soluzioni ci sono diversi metodi per scartare una delle due soluzioni:

1. Metodo matematico: si può utilizzare una quarta sfera e determinare quale delle due superfici si trovi più vicina ad essa.

2. Metodo logico: ad esempio nei sistemi GPS [30] si assume che il punto

corretto sia quello che si trovi internamente alle orbite dei satelliti, sarebbe assurdo pensare che la persona sia nello spazio, all'esterno dell'orbita

satellitare.

Se si introduce anche la presenza dell'errore, che nella figura precedente dovremmo rappresentare come δr che si va a sommare al raggio di ciascuna sfera, il problema diventa ancora più complicato poiché, in questo caso, l'intersezione tra le sfere sarà costituita da un volume e non da un punto.

2.7.2 Triangolazione

In questo tipo di sistemi sono presenti tre o più trasmettitori attivi (di solito ad infrarossi) posizionati ad esempio come nella figura precedente in posizioni note S1, S2, S3. Un sensore rotante altamente direttivo, montato invece a bordo di un robot, registra gli angoli λ1, λ2, λ3, posizioni alle quali il ricevitore “vede” i trasmettitori

allineati con il sensore stesso, si parla in questo caso di AoA (Angle of Arrival). A partire da queste misure è possibile calcolare sia le coordinate cartesiane Xoe Yo sia

l'orientamento θ; per calcolare la posizione si usa generalmente il metodo di Snellius-Pothenot noto in topografia anche con il nome di intersezione inversa.

Per fissare le idee: R=(X0,Y0) ha coordinate incognite e detti S1, S2e S3tre punti

noti ed essendo noti gli angoli α= S1RS2 e β= S2RS3, si può dedurre la posizione di P

ed effettuare la verifica con i prodotti scalari dei versori diretti da R verso S1, S2e S3.

Il problema generale di Snellius-Pothenot, normalmente affrontato in topografia, consiste nel calcolare la posizione di un punto accessibile essendo note le posizioni di tre punti visibili ma inaccessibili (si pensi alle coordinate di tre vette di montagne o di tre campanili visibili da una posizione di cui si vuol calcolare la posizione geografica). Se ci si pone nel punto di coordinate incognite e, con un teodolite13_{, si misurano gli angoli tra le tre coppie di punti noti e il punto di}

osservazioni si può calcolare la posizione del punto noto a patto che i tre punti noti e il punto da calcolare non si trovino, per sfortunata circostanza, su uno stesso cerchio. [31,32].

Questo problema è di particolare interesse anche all'infuori del calcolo topografico. Se infatti si scatta una foto in cui vengono fotografate almeno due terne di punti equidistanziati (ma per minimizzare gli errori di misura e l'imprecisione dovuta alla dimensione dei pixel sarà opportuno inquadrare varie terne ovvero, ad esempio, un reticolo quadrato posto di sfondo) e di cui sono note le coordinate nello spazio e se si conosce la lunghezza focale dell'obbiettivo con cui è stata effettuata la foto è possibile calcolare la posizione e l'orientamento della fotocamera al momento del click, e ricavati questi dati è possibile determinare le posizioni angolari di tutti gli altri punti inquadrati dalla foto ovvero le direzioni assolute (nel sistema di riferimento usato) di tutte le rette passanti per il fuoco e per ciascun pixel della foto. Effettuando pertanto varie foto da punti diversi della stessa scena, ma a patto sempre di inquadrare almeno due terne di punti equidistanziati ed allineati e di coordinate note, è possibile arrivare ad effettuare la ricostruzione tridimensionale dell'intera scena [31].

Esistono però delle configurazioni che non permettono di avere soluzioni uniche. In particolare, nel caso in cui le tre boe sono allineate (figura 16) e nel caso in cui il robot si trovi sulla circonferenza che unisce le tre boe (figura 17).

13 Il teodolite è uno strumento ottico a cannocchiale per la misurazione degli angoli azimutali e zenitali, usato per rilievi geodetici e topografici.

In quest’ultimo caso infatti è possibile identificare l’orientazione, ma non la posizione perché gli angoli alla circonferenza sono tutti uguali per ogni punto della circonferenza.

L'unico problema di questi sistemi è che la potenza dei trasmettitore, a parità di area di controllo, deve essere di gran lunga superiore per assicurare una trasmissione omnidirezionale ed essere sempre visibile. Per ovviare a tale problema spesso si ricorre a trasmettitori direzionali che operano all'interno di un cono di direttività. Naturalmente limitare il raggio di azione della trasmissione produce inevitabilmente degli errori nel calcolo della posizione nel momento in cui il ricevitore si trovi ad operare all'esterno di tale cono per almeno un trasmettitore, infatti per il calcolo della posizione occorrono tutti e tre gli angoli menzionati.

Figura 16: Boe allineate

Si possono distinguere due tipi di triangolazione in base alla tecnica di implementazione:

1. Trasmettitore/Ricevitore rotante, Riflettori Stazionari. In questa implementazione c'è un solo laser rotante a bordo del veicolo e tre specchi riflettenti montati in posizioni fisse e note.

2. Trasmettitore rotante, Ricevitori stazionari. Qui il trasmettitore, di solito un emettitore laser, si trova a bordo del veicolo, mentre tre o più ricevitori sono montati sulle pareti dell'edificio, i ricevitori rivelano l'incidenza del laser e ricavano l'angolo di incidenza da informazioni sull'angolo codificate dal trasmettitore.

2.7.3 Multilaterazione

La Multilaterazione, conosciuta anche come Posizionamento Iperbolico permette di determinare accuratamente la posizione di un oggetto calcolando il cosìddetto TDOA (Time Difference of Arrival) di un segnale trasmesso da un trasmettitore verso tre o più ricevitori; è possibile eseguire anche qui l'operazione complementare ossia calcolare il TDOA di segnali provenienti da tre o più trasmettitori, perfettamente sincronizzati, verso un singolo ricevitore [16].

Questa tecnica è utilizzata ampiamente sia in applicazioni militari che civili. Ad esempio, per menzionare un suo tipico impiego nel campo del tracciamento e sorveglianza, possiamo considerare il tracciamento di aerei, veicoli o qualsiasi stazione trasmissiva, calcolando i TDOA verso alcune stazioni riceventi dislocate sul territorio.

La tecnica funziona basandosi sul principio che un qualsiasi impulso emesso da un trasmettitore giunge in tempi differenti a due ricevitori dislocati in posizioni distanti l'uno dall'altro. Di fatto, per una dislocazione fissata dei due ricevitori, il

luogo dei punti dei possibili trasmettitori che danno origine allo stesso TDOA è un iperboloide (una superficie molto simile a due coni rovesciati uniti al vertice). Da notare che i ricevitori non hanno bisogno di conoscere l'esatto momento in maniera assoluta in cui l'impulso sia stato trasmesso, ma solamente la differenza tra gli istanti in cui lo stesso arriva ai ricevitori.

Consideriamo ora un terzo ricevitore dislocato in una terza posizione; questi genererà una seconda misura del TDOA, che permetterà di definire un secondo iperboloide di punti possibili per il trasmettitore. L'intersezione dei due iperboloidi così calcolati determina una zona di possibile dislocazione del trasmettitore stesso.

Introducendo ulteriori ricevitori è possibile determinare altri iperboloidi in numero pari a n-1 (dove n è il numero dei ricevitori) ed altrettante intersezioni con l'area precedentemente determinata dopo ogni misura. Disponendo di 4 ricevitori è possibile determinare l'esatta posizione del trasmettitore in uno spazio tridimensionale. A causa degli errori nella misura in genere si ricorre ad un numero di ricevitori n>4, la cui intersezione difficilmente genera un'unica soluzione, come ci si dovrebbe aspettare nel caso ideale. La ricerca della soluzione si imposta pertanto come un problema di ottimizzazione (tecnica dei minimi quadrati) o utilizzando il filtri di Kalman.

Abbiamo detto che la Multilateration può essere anche utilizzata da un ricevitore per localizzare se stesso misurando il TDOA di un segnale emesso da tre o più trasmettitori sincronizzati posti il locazioni note. Questo metodo è ad esempio utilizzato dai sistemi di navigazione come il sistema inglese DECCA sviluppato durante la Seconda Guerra Mondiale, che utilizzava la differenza di fase di due trasmettitori, invece del TDOA di un impulso per definire l'iperboloide. Questo permetteva ai trasmettitori di lanciare un segnale sinusoidale continuo in broadcast. La differenza di fase e quella del tempo di arrivo è la stessa per un trasmettitore in banda base.

Considerando un emettitore in posizione incognita O(x,y,z), che vogliamo conoscere, e un sistema di multilaterazione con quattro ricevitori in altrettanti posizioni note.

Definite le distanze tra tre ricevitori (R,L,Q) verso un quarto C.

D_L = LC D_Q = QC D_R = RC

Misurando le differenze di arrivo tra l'impulso diretto al ricevitore centrale in C e i restanti ricevitori, espresse dalle seguenti relazioni:

L = 1 c⋅

























Dove (xi, yi, zi) sono le coordinate dell'i-esimo ricevitore e c è la velocità della

luce; ogni equazione definisce un iperboloide e la soluzione delle tre equazioni permette di determinare le coordinate x,y,z incognite.

La multilaterazione è molto più accurata della triangolazione (è molto più semplice misurare accuratamente un tempo che creare un fascio laser molto sottile). Essa dipende da diversi fattori:

● Geometria del ricevitore(i) e del trasmettitore(i) ● Accuratezza della misura del tempo del ricevitore

● Accuratezza del sincronismo tra i ricevitori o trasmettitori.

● Dalla larghezza di banda dell'impulso emesso.

2.7.4 Multilaterazione atomica

Un altro metodo di tipo probabilistico si basa sulla stima della Probabilità più

Verosimile (MLE14_{): si stima la posizione del tracked target minimizzando la}

differenze tra le distanze misurate e quelle stimate. Tale metodo permette di creare una distribuzione random di boe che “auto-determinano” la propria posizione nello spazio.

I problemi statistici di solito impongono la risoluzione di problemi del tipo

P(X | p) ossia il calcolo della probabilità dell'evento X condizionato al verificarsi

dell'evento p, ossia partendo da parametri (p) noti si cerca di predire quelli futuri (X). Se si inverte il problema si può definire L(p | X), ossia stimare quale sia la probabilità associata ad un evento (p) partendo dall'osservazione dei dati sperimentali (X). Per meglio chiarire il concetto, la stima della probabilità più verosimile è: trovare quel valore di probabilità dell'evento che rende più verosimile il verificarsi degli eventi osservati. Facendo l'esempio del lancio della moneta, potremmo pensare

14 Maximum Likelihood Estimate

che p sia la probabilità che si verifichi testa. Immaginando di non conoscere tale probabilità potremmo cercare di stimarlo attraverso prove sperimentali e ricavare p dal numero di lanci stessi.

Sul metodo statistico dell'MLE si basa la tecnica di localizzazione detta

Multilaterazione Atomica. In questo metodo un robot che non conosce la propria

dislocazione nello spazio può stimare la propria posizione se intorno ad essa ci sono almeno tre boe. L'errore nella misura della distanza tra un oggetto che si vuole tracciare e la i-esima boa può essere espressa come la differenza tra la distanza misurata e la distanza Euclidea stimata:

f_ix0, y0, s= sti0−



i−y0

2

x0 e y0 sono le coordinate stimate per il robot, i=1,2,3....,N sono le boe, ti0è il

tempo che ad esempio impiega un segnale ultrasonico a propagarsi dalla robot alla boa i-esima, mentre s è la velocità del suono nell'aria.

Preso un adeguato numero di boe, il calcolo dell'MLE può essere eseguito calcolando il valore quadratico medio del sistema costituito da i equazioni del tipo

fi(x0, y0, s):

Fx0, y0, s=

∑

N

α2_{⋅f i}2

dove il termine αè il peso applicato che per semplicità assumiamo uguale a 1. Se il sistema è costituito da 3 boe si avrà un sistema matematico di altrettante equazioni che ha come unica soluzione la posizione del robot e la velocità del suono

(x0, y0, s).

Varianti di questo metodo sono [16]:

● Multilaterazione Interattiva: l'algoritmo è distribuito su ogni nodo della

rete di boe. L'algoritmo opera su un grafo G di nodi dove gli archi rappresentano la connettività tra due nodi adiacenti. Si parte dalla stima del

nodo sconosciuto con il massimo numero di nodi noti usando la Multilaterazione Atomica da un nodo centrale. A questo punto il nodo centrale conosce la distribuzione degli altri nodi nello spazio. Si riparte con lo stesso metodo da un altro nodo aggiungendo il nodo appena scoperto, ottenendo una migliore accuratezza. Infatti quando un nodo conosce la propria posizione diventa una nuova boa del sistema e questo processo viene iterato fino a conoscere la posizione di ogni singolo nodo della rete.

● Multilaterazione Collaborativa: può capitare a volte che data una

distribuzione di boe random, in alcuni nodi non sia possibile il calcolo della multilaterazione (ad esempio un nodo non ha intorno a sé mai tre nodi con posizione nota, figura 20b). In questi casi un nodo può cercare di risolvere un set di equazioni di multilaterazione in cui uno o più nodi siano sconosciuti cercando di stimare non solo la propria posizione ma anche quella degli altri nodi sconosciuti. Nel caso della figura 20b il processo parte ad esempio dal nodo 2 che per cercare di risolvere il suo sistema chiede la collaborazione al nodo 4 che gli fornisce il suo sistema di equazioni.

2.8 Model matching

Il principio che sta alla base di questo metodo è quello di localizzare la propria posizione trovando la corrispondenza tra una mappa locale, che il robot si ricostruisce in base alle percezioni sensoriali, e una mappa globale dell'ambiente posseduta a priori o ottenuta in fase di apprendimento. Infatti la conoscenza a priori dell'ambiente non è strettamente necessaria, poiché questa può essere costruita passo dopo passo, aggiornandola di continuo; in questo caso il processo di localizzazione e quello di costruzione della mappa si alimentano a vicenda.

scannerizzazione, le caselle verranno annerite se in quel punto è stato individuato un ostacolo, oppure rimarranno vuote se fanno riferimento ad uno spazio vuoto.

Il processo di comparazione può essere quindi schematizzato in cinque fasi principali che sono:

Nella fase 3 occorre un opportuno algoritmo di matching tra le mappe, in grado di creare una funzione di correlazione fra la mappa locale e quella globale; tale funzione dovrà essere poi massimizzata.

Un esempio di questo metodo è l'angle histogram del 1998 in cui uno scanner laser compie delle letture ambientali; tutte le scansioni che appartengono allo stesso muro o ostacolo avranno valori simili e viceversa. Si costruisce quindi l'istogramma tra angoli e valori misurati che andrà comparato con l'istogramma delle mappe memorizzate per cercare quella con il matching massimo.

L'uso di questo metodo deve tener conto di diversi errori di approssimazione della misura ed errori di riflessione, che si verificano quando un sensore ad ultrasuoni percepisce l'eco di un altro sensore e che possono provocare fenomeni di falso positivo (ostacolo dove non c'è) o di falso negativo (spazio libero dove l'ostacolo c'è). Inoltre bisogna tener conto dell'enorme complessità computazionale che il metodo richiede.

2.9 Approcci statistici

Anche questi approcci sono orientati soprattutto alla risoluzione di problemi dinamici che statici, come ad esempio a correggere i vettori di spostamento di un robot; pertanto accenneremo brevemente a tali metodi senza addentrarci in aspetti particolari, più per completezza di analisi del problema “localizzazione” che per reale interesse.

In questa categoria di metodi di localizzazione includiamo:

● Filtro di Kalmann;

● Localizzazione di Markov.

Questi approcci hanno come caratteristica particolare quella di non calcolare una posizione e una orientazione, ma di misurare una densità / distribuzione di probabilità che associa ad ogni punto dello spazio (x,y,z) la probabilità che il robot si trovi nella configurazione corrispondente. Tale probabilità viene aggiornata ogni qualvolta vengano ricevuti nuovi dati sensoriali.

In particolare il filtro di Kalmann tiene in memoria i primi due momenti della densità di probabilità (media e covarianza), mentre la localizzazione di Markov l'intera distribuzione di probabilità.

2.9.1 Filtro di Kalmann

Consiste in un insieme di equazioni matematiche che forniscono una soluzione ricorsiva computazionalmente efficiente e permette la stima degli stati passati, presenti e futuri anche quando la natura del sistema modellato non è nota con precisione.

x∈ℜn _{di un processo tempo discreto che è governato dalla seguente equazione}

lineare e stocastica alle differenze finite:

x_k = Axk−1Bukwk−1

tramite una misura z_∈ℜm _{data da:}

z_k = Hxkvk

le variabili aleatorie wke vkrappresentano rispettivamente il rumore nel

processo e il rumore nella misura. Si assume che esse siano indipendenti e con distribuzione di probabilità normale bianca:

P(w) = N(0,Q) P(v) = N(0,R)

Q ed R sono rispettivamente le matrici di covarianza del rumore nel processo e

di covarianza del rumore nella misura; possono cambiare ad ogni istante di campionamento temprale o ad ogni misura ma assumeremo che siano costanti.

La matrice A(n x m) nell'equazione alle differenze mette in relazione lo stato al precedente istante di campionamento k-1 con lo stato all'istante k, in cui non ci sia né rumore né una funzione di ingresso. La matrice B(n x l) mette in relazione l'eventuale ingresso di controllo u_∈ℜl _{con lo stato x; la matrice H(m x n) nell'equazione della}

misura mette in relazione lo stato con la misura zk. Si suppone inoltre che tutte e tre le

matrici siano costanti.

Facendo un esempio di localizzazione con boe attive, il problema, con un filtro di Kalmann, può essere impostato in questa maniera:

● _x∈ℜ3 _{è lo stato da stimare ovvero le coordinate di posizione (x,y,z);}

● allo stato xk-1si comanda uno spostamento uk; lo stato successivo sarà

e nella ricostruzione odometrica);

● _z∈ℜi _{è la misura (ad esempio sono gli angoli con cui sono viste le}

boe).

Indichiamo con xk∈ℜn la stima a priori dello stato all'istante k che è diretta

conseguenza della conoscenza del processo negli istanti precedenti a k e dell'eventuale input di controllo ukall'istante k e con xk∈ℜ

n _{la stima a posteriori}

dello stato all'istante k, conseguenza della stima a priori e della misura zkeffettuate

all'istante k. Lo scopo del filtro di Kalmann è quello di ridurre al minimo l'errore nella stima a posteriori secondo lo schema di figura:

2.9.2 Localizzazione di Markov

I processi markoviani sono processi stocastici che modellano situazioni in cui:

● La transizione tra stati non è deterministica ma probabilistica;

● le probabilità di transizione non dipendono dal numero di transizioni

effettuate (proprietà di omogeneità);

● la probabilità di transire in uno stato successivo dipende esclusivamente dallo stato attuale (proprietà memoryless).

Sia c_kuno stato al tempo k tra uno dei possibili stati finiti {1,....,M}; assunto che il processo viene eseguito solo da un istante 0 ad un instante N e che gli istanti

iniziale e finale siano noti a priori, la sequenza di stati eseguiti può essere rappresentata da un vettore C = (c₀,...,c_N).

Sia P(c_k | c₀,c₁,...,c_{(k −1)}) la probabilità dello stato c_kal tempo k condizionata a tutti gli stati precedenti k −1. Supposto che il processo sia tale che c_k dipenda solo dal suo stato precedente c_{k −1}e indipendente da tutti gli altri stati precedenti. Tale processo è conosciuto come processo markoviano del primo ordine. Questo implica che la probabilità di trovarsi nello stato c_k al tempo k, dati tutti gli stati precedenti all'istante k −1, dipende solo dallo stato precedente c_{k −1}al tempo k −1:

Per un processo markoviano di grado n,

Pc_k

∣

∣

Nella teoria delle probabilità, un processo stocastico ha proprietà markoviane se la distribuzione di probabilità condizionata degli stati futuri del processo, dato lo stato attuale, dipende solo dallo stato immediatamente precedente, ossia è condizionatamente indipendente dagli stati passati (percorso eseguito dal processo) dato lo stato presente.

Matematicamente, sia X(t) un processo, t > 0 deve valere:

se il processo è anche omogeneo:

Il Processo decisionale di Markov (MDP Markov Decision Process) fornisce una struttura matematica per la modellizzazione di algoritmi decisionali in situazioni dove al cune variabili sono apparentemente casuali e altre sotto il controllo

Pr

[

∣

]

[

∣

]

Pr

[

∣

]

[

∣

]

decisionale del sistema. L'MDP è utilizzato ampiamente in vasto range di problemi di ottimizzazione risolti attraverso la programmazione dinamica e l'apprendimento inventati da Ronald Howard nel 1960. Oggi utilizzato in molti campi come la robotica, controlli automatici, economia e processi industriali.

Il Processo decisionale di Markov un processo di controllo a tempo discreto caratterizzato quindi da un numero finito di stati, ognuno dei quali è costituito da una serie di azioni tra cui il controllo decisionale può scegliere di eseguire. Per ogni stato e azione, una funziona di transizione di stato P_a(s) determina la probabilità di transizione al prossimo stato. Se lo stato corrente di un MDP al tempo t è noto, le transizioni ad un nuovo stato all'istante t + 1 sono indipendenti dagli stati precedenti si parla allora di catene di Markov.

Una catena di Markov descrive lo stato del sistema ad istanti consecutivi. In ognuno di questi istanti il sistema potrebbe essere stato modificato rispetto al suo stato originario per portarsi in un altro stato o rimanere nello stesso stato. I

cambiamenti di stato sono dette transizioni. Un processo con proprietà markoviane è un processo senza memoria ossia non ricorda lo stato in cui si trovava

precedentemente prima di portarsi nello stato attuale e la decisione di passare ad un stato futuro si basa esclusivamente su considerazioni che riguardano questo stato senza considerare il proprio passato.

Nel processo di localizzazione con map matching si definiscono una variabile aleatoria che rappresenta lo stato al passo Xned un vettore V=21 ,,Nn di

distribuzione di probabilità di appartenenza agli stati dopo n transizioni della catena; ad ogni istante temporale, la localizzazione di Markov aggiorna una distribuzione di probabilità V, detta anche Belief, e non più le coordinate del tracked target come avviene con il filtro di Kalmann.