Location, why and how

LBS Research @ CRS4

 

A location-based service (LBS): Servizio d'informazione o d'intrattenimento accessibile attraverso un device mobile che sfrutta la posizione dell'utente per ottenere un valore aggiunto

 

-Sistemi di “raccomandazione” mobili-Navigazione turn by turn-Notifiche  geo-referenziate (push or pull)-Marketing geolocalizzato-Pagamenti e checkin-Scatola nera per assicurazioni

I campi di applicazione

Hype Cycle 2008

Hype Cycle 2012

Yelp

Aiuta nella ricerca diNegozi, bar, ristoranti etc.

Nata a San Francisco60 milioni di visitatori al mese50,000,000$ revenue nel 2010Google offre 500M$ nel 2010

WAZE

Nato in Israele (80 dipendenti)Navigatore social, sempre aggiornato dagli utentiApp: 12 milioni di downloadFund rising: 50M$

Foursquare

Social network geolocalNata a NY100 dipendenti20,000,000 di utentiFund rising > 70M$Asset > 600M$

Wikitude

Augmented RealityUser generatedFreewareNata in Austria

GPS

24 - 32 satelliti 

Calcola posizione, altitudine, velocità, direzione

Il GPS usa la Trilaterazione

Cos'è?

Trilaterazione

Trilaterazione

Nel piano ho bisogno di 3 punti noti per la trilaterazione

Trilaterazione

Nel piano ho bisogno di 3 punti noti per la trilaterazione

Trilaterazione

Nello spazio

GPS e relatività

Relatività ristretta Satelliti  e velocità 14,000 Km/h (il tempo si allunga)

 Relatività generale 

Satelliti e gravità 20,000 Km di quota (il tempo si accorcia)

al netto gli orologi sul satellite vanno avanti di 38micros al giorno

Time-to-Fix

• Cold 15': • Non conosce la posizione corrente 

• Vede 1+ satelliti 

• Scarica l'almanacco (info sulla costellazione dei satelliti)

• Warm: • Conosce la posizione con un errore di 100Km 

• Ha già l'almanacco

• Scarica le effemeridi. 

• Hot or standby: • Conosce la posizione

• Ha l'almanacco e le effemeridi

Spazio, ultima frontiera

GPS is broken indoor

Nel futuro ci saranno gliPseudolites = Pseudo Satellites

Problema: interferenza tra segnale del pseudolite e quello del satellite

Dead reckoning

where I was 1 second ago

where I'll be in 1 second? 

As each estimate of position is relative

to the previous one, errors are

cumulative.

Il contapassi

Notte dei ricercatori – Cagliari 23 Settembre 2011Alberto Serra – CRS4

• Dispositivo usato in ambito sportivoo parte elettronica formata

da accelerometroo parte software che conta

i passi• Distanza nel sistema

misurata mediante passi utente

• Lunghezza passo costante

• Smartphone in qualsiasi posizione

How to detect a step

Accelerometri

http://www.youtube.com/watch?v=KZVgKu6v808

How to detect a step

Compass dell ' iPhone

 

effetto Hall

I codici a barre 2D

Notte dei ricercatori – Cagliari 23 Settembre 2011Alberto Serra – CRS4

Dati posizione

URL

JPGDati

• Barcode + Server: Ricavare i dati sulla posizione (nota) dell’utente JSON

Posizionamento mediante QR

Notte dei ricercatori – Cagliari 23 Settembre 2011Alberto Serra – CRS4

 

Checkpoint + Compass + Step detection

video di alberto http://www.youtube.com/watch?v=HTZFRDBdQck

Problemi ...

Errore della bussolaFalso positivo del passoAttraversamento dei muri

Errore Bussola

Campi magnetici di errore:

apparecchi elettrici,dischi computer,altri telefoni cell 

Giroscopio

 Giroscopio - tende a mantenere il suo asse di rotazione orientato in una direzione fissa: in questo modo può essere usato per misurare le velocità angolari. 

Giroscopio Triassiale - Un giroscopio triassiale permette di misurare le velocità di rotazione attorno ai tre assi (x, y e z) 

Giroscopio

Data una direzione iniziale nota θ0 (es. Nord)

ω velocità angolare

θ (t )=θ0+∫

t 0

t

ω (τ ) dτ

Errori nei giroscopi - I giroscopi sono affetti da un errore che, se integrato, fa divergere linearmente l’angolo. Questo errore, se non trattato, porta alla completa inconsistenza delle misure.

Come caratterizzare l'errore

L’errore medio rilevato nelle diverse sessioni di test è dell'ordine 0,1%

 

Probabilità totale

X= un certo evento, es. sono in "Cucina adesso"A = stavo in "Soggiorno prima"B = stavo in "Camera prima"C = stavo in "Bagno prima"D = stavo in "Cucina prima" P(X) = P(X|A)P(A) + P(X|B)P(B) + P(X|C)P(C) + P(X|D)P(D) 

Trattazione semplificata 3x3

al checkpoint so che la p(x,y) è distribuita come in figura

Trattazione semplificata 3x3

al passo successivo rilevato dai sensori devo ricalcolare la p(x,y) in ogni casella dato che la bussola indica una direzione z:p(A) = p(da B ad A | z) * p(B) + p(da C ad A | z)*p(C) +...

Stima di posizione = casella con probabilità max

Filtro Bayesiano Ricorsivoricalcola la stima della posizione in un sistema di coordinate sulla base dei dati forniti dai sensori

Dalla mappa alla griglia

WiFi fingerprinting

RSS := Received Signal Strength 

Esempio: nel tinello davanti al camino misuro il vettore RSS=[-54,-33,-89]

Wi-Fi Fingerprinting := mappa radio di un'area sulla base del RSS

Stima di posizione := calcolo la probabilità che io sia in X,Y dato che ricevo un certo vettore di RSS

Ho bisogno di un training set preparato in precedenza

Algoritmo della distanza

Dati due vettori RSS (es. x misurato ieri in un posizione nota ed y misurato adesso in una posizione sconosciuta)

Lp :=1N (∑

i=1

N

(x i− y i )p)

1p

Cerca il vettore x nel training set che ha la distanzaLp minima rispetto a y

La posizione di x è la stima della posizione attuale

In alternativa ...

Scegli ad esempio 3 vettori x1,x2, x3 del training set che hanno la distanza Lp minima rispetto a y

Prendi le loro posizioni p1,p2,p3 e calcola il baricentro

Il baricentro è la tua stima

dBm

RSS è un vettore di valori dBm

0 dBm = 1mW

10dBm = 10mW potenza di tx di un laptop

-50dBm = 10nW potenza in rx massima

-90dBm = 1pW potenza in rx minima

Position is Not Enough

to go where we need to go, where we need to go?

Mappa

Dalla mappa al grafo

Se ho il grafo posso usare l'algoritmo per il cammino minimo

Referenze

http://www.marcomonetti.it/?tag=trilaterazione Hype Cycle di Gartner engineerguyvideo channel on youtube http://en.wikipedia.org/wiki/Bayes%27_theorem http://en.wikipedia.org/wiki/Recursive_Bayesian_estimation P. Prasithsangaree, P. Krishnamurthy, e P. Chrysanthis, «On indoor position location with wireless LANs», in Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on, 2002, vol. 2, pagg. 720–724.

Davide CarboniLBS research @ CRS4

dcarboni@crs4.ithttp://geoweb.crs4.it

Domande?