Un algoritmo di Un algoritmo di Map-MatchingMap-Matching su reti su reti stradali complessestradali complesse

LaureandoLaureandoFlavio PerriFlavio Perri

Facoltà di Scienze MatematicheFacoltà di Scienze MatematicheFisiche e NaturaliFisiche e Naturali

Laurea di I° Livello in Laurea di I° Livello in Tecnologie InformaticheTecnologie Informatiche

Responsabile InternoResponsabile InternoProf. Prof. Giorgio RichelliGiorgio Richelli

Responsabile EsternoResponsabile EsternoIng. Ing. Andrea CorbelliAndrea Corbelli Anno AccademicoAnno Accademico

2006/20072006/2007

Scopo del lavoroScopo del lavoro

Identificazione del percorso

di ogni veicolo

• Dati GPS– Antifurto satellitare– Alcuni milioni di campionamenti

• Mappe digitali (Roma, Milano)

AgendaAgenda

• Il Map-Matching (MM)

• Un nuovo algoritmo di MM– Qmatch

• Conclusioni e sviluppi futuri– Modello previsionale e data-mining

Il Il Map-MatchingMap-Matching

• Concetto di Polling time

• Interpolazione: – Operazione che unisce due

segmenti non contigui sulla mappa

• Problemi tipici:– Errore campionamenti GPS– Complessità della mappa– Errori di propagazione

““Individuare, sulla mappa digitale, il segmento di strada su Individuare, sulla mappa digitale, il segmento di strada su cui l’oggetto si trovava al momento del campionamento”cui l’oggetto si trovava al momento del campionamento”

Il Il Map-Matching on-lineMap-Matching on-line

• Obiettivo: – individuare in tempo reale ogni cambiamento di

posizione dell’oggetto

• Usato in ambienti: GNSS, PNA

• Caratteristiche:– Polling time molto basso (>1 ricez. al secondo)

• Uso limitato di interpolazione

– Identificazione arco corrente in base a limitata serie storica

Il Il Map-Matching off-lineMap-Matching off-line

• Obiettivo: generare percorsi di singoli oggetti (automobili)

• Usato generalmente per analisi– Tempi di percorrenza, modelli del traffico

• Caratteristiche:– Polling time elevato

• Maggiore distanza tra campionamenti • Uso intensivo di interpolazione

– Tutti i punti offrono supporto al Map-Matching

Perché un nuovo algoritmo?Perché un nuovo algoritmo?

• Un problema diversodiverso

– Campionamenti non pensatinon pensati per il Map-Matching• Ampi intervalli di tempo e di spazio tra due acquisizioni• Dati a supporto limitati

– Rete stradale molto complessa (Roma, Milano)

– Inapplicabilità degli algoritmi presenti in letteratura

L’algoritmo L’algoritmo QmatchQmatch

• Principali difficoltà:

– Scelta del corretto arco sulla mappa

– Supporto limitato• Informazioni campionamento• Pochi punti per percorso

– Propagazione dell’errore • Interpolazione• Startup errato

Propagazione dell’errorePropagazione dell’errore

Percorso calcolatoPercorso calcolato

CampionamentoCampionamento

L’algoritmo L’algoritmo QmatchQmatch

• Concetto di “Qualità di un puntoQualità di un punto”– Rispetto alla rete stradale, indipendente dagli altri

• Range QueryRange Query– Sfruttamento dati a supporto

• GPS Quality• Engine Status• Compass• Delta Position

• Punteggio finale al percorso

Range QueryRange Query

• Ellisse d’errore– Direzione asse maggiore uguale

a Compass

• Caratteristiche arco candidato

– Compatibilità geometrica

– Compatibilità fisica

– Compatibilità semantica

L’algoritmo L’algoritmo QmatchQmatch

• Fase preliminare o Pre-Matching– CleanupCleanup ed estrazione inputinput– Assegnazione qualità punti

• Fase centrale – Costruzione parziale percorso

• Fase finale – Completamento e calcolo punteggio percorso

L’algoritmo L’algoritmo Qmatch – fase 1Qmatch – fase 1

PuntoQualit

à

1 0.5

2 5.9

3 10.2

4 1.4

... ...

n 0.8

Range queryRange queryper ogni puntoper ogni punto

Calcolo qualità(p) Cleanup ed

estrazione

Pre-processing

L’algoritmo L’algoritmo Qmatch – fase 2Qmatch – fase 2

PuntoQualit

à

1 0.5

2 5.9

3 10.2

4 1.4

... ...

n 0.8

• SuccessoSuccesso: arco associato

• Associazione non eseguitanon eseguita– Più di un candidato compatibile

Incremento qualitàpunti adiacenti

PuntoQualit

à

1 0.5

2 5.9

3 10.2

4 1.4

... ...

n 0.8

PuntoQualit

à

1 0.5

2 5.9

3 10.2

4 1.4

... ...

n 0.8

PuntoQualit

à

1 0.5

2 8.3

3 10.2

4 3.9

... ...

n 0.8

PuntoQualit

à

1 0.5

2 5.9

3 -1

4 1.4

... ...

n 0.8

L’algoritmo L’algoritmo Qmatch – fase 3Qmatch – fase 3

PuntoQualit

à

1 2.5

2 9.2

3 -1

4 8.3

5 -1

6 -1

7 11.3

... ...

n 1.8

Scegli punto non associato con miglior supporto

•Sfruttamento punti già associati

•Si esegue un matching definitivo

Un percorso ricostruitoUn percorso ricostruito

Andata...Andata... ...e ritorno...e ritorno

StartStart

EndEnd

EndEnd

StartStart

Sviluppi futuriSviluppi futuri

• Modello traffico• Data-mining

– Road-pricing– Marketing

• Implementazione Qmatch molto efficiente

• Progetto di ricerca– IBM– Ipre– Caspur– Politecnico di Bari– ...

Archivio PercorsiEstrazione Percorsi

ConclusioniConclusioni

• Qmatch:– Un nuovo algoritmo di Map-Matching off-line– Una soluzione ad un problema specifico

• Rete stradale complessa• Elevato intervallo di campionamento GPS• Dati a supporto limitati

– Componente di un progetto di ricerca• Modello previsionale e data-mining

GrazieGrazie

Cen-to cen-to cen-to!

On-line vs. Off-lineOn-line vs. Off-line

ProprietàProprietà On-lineOn-line Off-lineOff-line

Punti in ingresso (k) k 1 k = n

Polling time ~ 1/sec >1/minuto

Individuazione su mappa in tempo reale

Sì No

Analisi statistiche In parte Sì

Calcolo percorso globale No Sì

Interpolazione Limitata Necessaria

Uso di tecniche geometriche Sì Sì

StartupStartup errato errato