Inferring waypoints using shortest paths
Desmond, Daniel A.
Brown, Kenneth N.
Sun SITE Central Europe / RWTH Aachen University
We present a method for reconstructing intermediate destinations from a GPS trace of a multi-part trip, without access to aggregated statistics or datasets of previous traces. The method uses repeated forwards and backwards shortest-path searches. We evaluate the algorithm empirically on multi-part trips on real route maps. We show that the algorithm can achieve up to 97% recall, and that the algorithm degrades gracefully as the GPS traces become sparse and irregular.
GPS trace , Shortest-path search , Multi-part trip , Route map
Desmond, D. A. and Brown, K. N. (2016) 'Inferring waypoints using shortest paths', in Greene, D., MacNamee, B. and Ross, R. (eds.) Proceedings of the 24th Irish Conference on Artificial Intelligence and Cognitive Science, Dublin, Ireland, 20-21 September. CEUR Workshop Proceedings, 1751, pp. 45-56.