Implementation and evaluation of a Map Matching algorithm

Map matching is still one of the most active research topics in science despite having been on the scene for many years. The main reason for this longevity is the emergence of commercial sectors in which the localization of moving objects is fundamental. Both in open and closed environments. Very common examples are autonomous driving and orientation in closed spaces with the presence of obstacles. In this thesis,we will see the implementation of a Map Matching algorithm and some of its possible variations. We will begin by introducing the problem of Map Matching and its relevance in today's world. Indeed, the proliferation of devices capable of communicating with GPS to obtain the coordinates of own position and the development of entire commercial sectors, such as, for example, the automotive, make the problem of localization one of the most studied. All this leads Map Matching to be one of the most important active research branches. Since this problem has a wide scope of application, the article provides a classification of various methods invented in recent years. Furthermore, some possible application scenarios are illustrated below to give an idea of the multiple uses of Map Matching. Among them, the most important are real-time and off-line scenarios; that is when the localization problem is faced and solved, with a certain margin of error, during the movement of the object to be localized or, instead, when the problem is faced later by memorizing the path of the moving object by collecting its positions over time. In our opinion, the real-time scenario is the most interesting and, consequently, we have focused our analysis on one of the most promising algorithms produced by scientific research, which is called Spatial-Temporal Proximity and Improved Weighted Circle (STP-IWC). This is an improvement of an already published process, which bases its operation on the Spatial-Temporal Proximity method, that is the identification of the road the object is traveling among those that fall within a specific area around its position in a given moment. This technique, unfortunately, has a weak point, which occurs during the calculation phase of the candidate road. The algorithm is unable to determine the candidate when two consecutive points of the trajectory are located in the bisector of a road intersection. Furthermore, the calculation of the candidate road requires parameters, called weights, which moderate the impact of the distance between the road and the trajectory point, and the divergence between the directions of the candidate and the trajectory during the calculation of the result. Moreover, these parameters have a high impact on the complexity of the algorithm. For these reasons, the algorithm we are going to see has been proposed and it is more advanced and robust than the one presented so far. Its name is Spatial-Temporary Proximity and Improved Weighted Circle (STP-IWC) and adds the concept of directional similarity between the trajectory and the candidate road. This new idea is implemented in the procedure with another parameter called “b”. In addition, the candidate road calculation mechanism has been modified so that the weights of the previous version are calculated dynamically thus improving performance. We will therefore see the implementation of different versions of this algorithm, moving from the less complex one, in which the weights are fixed and decided a priori, to the actual STP-IWC version of which we will show a possible implementation. We will then compare the results obtained and see how they differ in terms of performance. Finally, we will propose any improvements both to the code and to the implemented versions that could be a starting point for subsequent papers.

Il Map Matching è ancora uno degli argomenti di ricerca più attività in ambito scientifico nonostante sia presente sulla scena da molti anni. La principale ragione di questa longevità è l'affermarsi di settori commerciali in cui la localizzazione degli oggetti in movimento è fondamentale. Sia in ambienti aperti quanto in locali chiusi. Esempi molto comuni sono la guida autonoma e l'orientamento in spazi chiusi con la presenza di ostacoli. In questo articolo vedremo l'implementazione di un algoritmo di Map Matching e alcune delle sue possibili variazioni. Inizieremo introducendo il problema del Map Matching e la sua rilevanza nel mondo di oggi. Infatti, il proliferare di dispositivi in grado di comunicare con il GPS per ottenere le coordinate della propria posizione e lo sviluppo di interi settori commerciali, come, ad esempio, quello automobilistico, rendono il problema della localizzazione uno dei più studiati. Ciò porta il Map Matching ad essere uno dei rami di ricerca più importanti ad attivi. Poiché questo problema ha un vasto campo di applicazione, in questo articolo viene fornita una classificazione dei vari metodi inventati negli ultimi anni. Inoltre, di seguito, sono illustrati alcuni possibili scenari applicativi per dare un'idea dei molteplici utilizzi del Map Matching. Tra i più importanti ci sono gli scenari real-time e off-line; quando cioè il problema di localizzazione viene affrontato e risolto, con un certo margine di errore, durante lo spostamento dell'oggetto da localizzare o, invece, quando il problema viene affrontato in un momento successivo memorizzando il percorso dell'oggetto in movimento raccogliendo le sue posizioni nel tempo. A nostro avviso lo scenario in tempo reale è quello più interessante e, di conseguenza, abbiamo focalizzato la nostra analisi su uno degli algoritmi più promettenti prodotti dalla ricerca scientifica, che si chiama Spatial-Temporal Proximity and Improved Weighted Circle (STP-IWC). Si tratta di un miglioramento di un processo già pubblicato, che basa il suo funzionamento sul metodo Spatial-Temporal Proximity, ovvero dell'identificazione della strada che l'oggetto sta percorrendo tra quelle che ricadono in una determinata area attorno alla sua posizione in un dato momento. Questa tecnica, purtroppo, ha un punto debole, che si presenta in fase di calcolo della strada candidata. L'algoritmo non è in grado di determinare la candidata quando due punti consecutivi della traiettoria si trovano nella bisettrice di un incrocio stradale. Inoltre, il calcolo della strada candidata richiede dei parametri, detti pesi, i quali moderano l'impatto della distanza tra la strada e il punto della traiettoria, e la divergenza tra le direzioni della candidata e della traiettoria durante il calcolo del risultato. Inoltre, questi parametri hanno un elevato impatto sulla complessità dell’algoritmo. Per questi motivi è stato proposto l’algoritmo che andremo a vedere, il quale è più avanzato e robusto rispetto a quello presentato finora. Il suo nome è Spatial Temporary Proximity and Improved Weighted Circle (STP-IWC) e aggiunge il concetto di somiglianza direzionale tra la traiettoria e la strada candidata. Questa nuova idea viene implementata nella procedura con un altro parametro chiamato “b”. Inoltre, il meccanismo di calcolo della strada candidata è stato modificato in modo che i pesi della versione precedente vengano calcolati dinamicamente migliorando così le prestazioni. Vedremo quindi l'implementazione di diverse versioni di questo algoritmo, passando da quella meno complessa in cui i pesi sono fissati e decisi a priori, alla versione STP IWC vera e propria di cui mostreremo, appunto, una possibile implementazione. Successivamente confronteremo i risultati ottenuti e vedremo come differiscono in termini di prestazioni. Infine, proporremo eventuali miglioramenti sia al codice che alle versioni implementate che potrebbero essere spunto per elaborati successivi.