Affiliations: Polish-Japanese Institute of Information Technology, Koszykowa 86, 02-008 Warsaw, Polska, [email protected]; [email protected]
Note: [] Address for correspondence: Polish-Japanese Institute of Information Technology, Koszykowa 86, 02-008 Warsaw, Polska Also works: Division of Mathematics, Informatics and Applied Mathematics, The University of Warsaw, Banacha 2, 02-097 Warszawa, Poland The authors are supported by the grants: No N516 077837 from the Ministry of Science and Higher Education of the Republic of Poland, No SP/I/1/77065/10 from the the National Centre for Research and Development (NCBiR) and No ST/SI/01/2011 from the Polish Japanese Institute of Information Technology (PJIIT).
Abstract: Recently, GPS car navigation became popular enough for a significant number of drivers in any large city to be able to potentially send their current GPS positions and velocities to a central traffic-managing server in real time. This data could be used to reconstruct a map of current traffic in the whole city and make predictions for the future, which would be valuable for traffic control, congestion analysis and prevention. The difficulty lying in the traffic reconstruction problem is that the number of cars equipped with a GPS transmitter is a small in comparison with the total number of cars in the road network. Information obtained from GPS transmitters is therefore rare and incomplete, raising the problem of approximating travel velocities from sparse information. In this context, the paper proposes approaches to solving two problems: (1) of reconstruction of routes of the individual cars in a street graph from a temporal stream of its coordinates and (2) of approximating the average velocity on a given street from irregular time series of instantaneous velocities of cars passing through that street. Determining the car's position in the road network is quite expensive computationally when done in a naive way, so we propose a method to speed up the car's localization based on the R-tree data structure [10]. Additionally, a resilient propagation neural network [13] is applied to approximate the average velocity on any edge of a street graph. Our methods were applied to one of the problems announced in the competition organized in June 2010 by Tom-Tom - a company producing automotive navigation systems [15]. The results of experiments show the capacity of our approach to make useful predictions.
Keywords: machine learning, data mining, spatio-temporal data mining, GPS, R-Tree, GIS, neural networks
