Proceedings

Truncating Shortest Path Search for Efficient Map-Matching

Takashi Imamichi, Takayuki Osogami, Rudy Raymond

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 589-594.

Abstract

We study the problem of map-matching, or finding the route on a road network from a trace of noisy and sparse observed points, particularly when a huge number of points are given. The algorithms based on Hidden Markov Models (HMMs) are known to achieve high accuracy for noisy and sparse data but suffer from high computational cost. We find that the bottleneck of the HMM-based map-matching is in the shortest path search for calculating transition probabilities. We propose a technique to truncate the shortest path search before finding all the shortest paths in the HMM-based map-matching without losing accuracy. We run the one-to-many shortest path searches on the reversed network and terminate the searches based on the log likelihood of the Viterbi algorithm. Computational experiments show that the proposed approaches can reduce the computational cost by a factor of at least 5.4.

Takashi Imamichi, Takayuki Osogami, and Rudy Raymond. 2016. Truncating Shortest Path Search for Efficient Map-Matching. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 589–594. https://ijcai.org/proceedings/2016/90
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards