Inferring waypoints using shortest paths

Desmond, Daniel A.; Brown, Kenneth N.

Inferring waypoints using shortest paths

cb

Files

2429.pdf(1.04 MB)

Published Version

Date

2016-09

Authors

Desmond, Daniel A.

Brown, Kenneth N.

Publisher

Sun SITE Central Europe / RWTH Aachen University

Abstract

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.

Keywords

GPS trace , Shortest-path search , Multi-part trip , Route map

Citation

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.