Map matching imprecise trajectories for smart mobility applications

• Main Author: Jagadeesh, George Rosario
• Other Authors: Thambipillai Srikanthan
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2019
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/89847; http://hdl.handle.net/10220/47724
• Institution: Nanyang Technological University

Trajectory data generated by smart mobile devices are useful for inferring traffic conditions and travel patterns in order to enable smart mobility. The effective utilisation of such data depends on a crucial step known as map matching that matches raw trajectories to paths in a transport network. Existing trajectory-based applications mostly rely on relatively precise trajectories generated by the Global Positioning System (GPS). However, it is preferable to use noisy trajectories generated by alternative technologies such as Wi-Fi positioning and cellular network positioning due to their high energy efficiency, availability in GPS-denied environments and better privacy protection. Furthermore, bandwidth and storage-space considerations dictate that trajectories be sampled sparsely. This thesis examines the challenging problem of map matching such noisy and sparse trajectories in an accurate and efficient manner. Following a critical review of the literature, a Hidden Markov Model (HMM) based algorithm is proposed for map matching temporally sparse trajectories with high levels of location measurement noise. It includes new probabilistic models for modelling the measurement noise and representing the probability of transitioning between candidate points on a road network. Evaluations with several imprecise trajectory datasets show that the proposed algorithm is consistently more accurate compared to a widely-used baseline algorithm and produces a 55% reduction in the overall map matching error. An innovative approach is adopted to further improve the robustness of the HMM-based map matching algorithm against noise and sparsity in the input data. The HMM-based algorithm is complemented with a model of drivers’ route choice in order to assess partial paths produced by the former from the perspective of route preference. A multinomial logit route choice model, estimated from a real trajectory dataset, is used to calculate the probability of a path being chosen among several alternative paths, which are generated by an effective choice set generation procedure. Experimental results show that the use of the route choice model leads to a 12% reduction in the error with respect to the HMM-based algorithm. Online map matching of imprecise trajectories incurs substantial output latencies and computation times, thereby rendering them unsuitable for real-time applications. This limitation is addressed by devising optimization techniques for improving the timeliness and efficiency of map matching. A heuristic technique based on a probabilistic measure is presented to enable early generation of partial state sequences in the HMM by an online variant of the Viterbi algorithm. This results in an overall reduction of 33% in the output latency with negligible loss of accuracy. A novel method is proposed for accelerating a computationally expensive step involved in probabilistic map matching, namely, the computation of many-to-many shortest paths between candidate points. This produces a reduction of up to 78% in the overall computation time. The above research contributions have led to the realization of an efficient map matching solution that is robust to high levels of imprecision in the input data. The applicability of the proposed map matching solution for an important smart mobility application, namely, traffic condition estimation, is evaluated. For this, a system that estimates road-segment-wise running speeds from imprecise trajectory data is proposed. The system relies on a confidence-based filtering approach to cope with the uncertainties in the map-matched paths. It also includes a novel method of estimating the stopping delays at intersections along the paths. Experimental results show that despite relying on noisy and sparse trajectories, the accuracy of speed estimates produced by the system are found to be within the range generally considered acceptable for applications that use traffic data. As the collection of sparse non-GPS trajectories from smartphone users imposes only marginal energy, bandwidth and privacy costs on them, the contributions of this thesis can potentially pave the way for large scale deployment of trajectory-based smart mobility applications.