Browse Prior Art Database

Route Inference in Low Sampling Rate Trajectory Data

IP.com Disclosure Number: IPCOM000244507D
Publication Date: 2015-Dec-17
Document File: 5 page(s) / 158K

Publishing Venue

The IP.com Prior Art Database

Abstract

The amount of spatial trajectory data is growing faster than ever with the rapid increased availa-bility of GPS embedded mobile devices in vehicles. In this work, we address the problem of learning statistical spatio-temporal models for inferring possible traversed routes focusing on low sampling rate trajectory data. Inferring possible routes for low sampling rate trajectory data is a challenging problem for two reasons. First, the sparsity of the data where the time gap between two consecutive GPS observation can be large due to data storage issue or signal loss in places like urban canyons. The sparsity can extend from several minutes to hours, which increases the uncertainty on the traversed route. Second, historical data and road information (speed, stop lights etc.) may not readily available or inaccurate. We investigate the use of Bayesian t=interference approach to this problem combining knowledge expert with information learned from the data. Our approach is evaluated trajectory data sets comparing ground traversed routes to the inferred one. The key contribution of this model is the ability to learn popular routes and turns. The model defines a prior model that assumes vehicle are travelling on shortest path and updates the probability of routes when more and more historical trajectory data is available.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 37% of the total text.

Page 01 of 5

Route Inference in Low Sampling Rate Trajectory Data

Introduction:

The study of spatial trajectory dates back to centuries. People have long been interested to find how things move. With the advancement of location positioning and wireless communi- cation technology, more and more mobile devices are equipped with Global Positioning Sys- tem. The GPS trackers are nowadays installed in many places, such as smart phones, vehi- cles, planes and wild animals. The rapid growth of spatial trajectory data enables the study of many applications that were previously not possible. In this ID, we focus on how to infer traversed route from low sampling rate trajectory data. Inferring possible routes for low sampling rate trajectory data is a challenging problem for two reasons. First, the sparsity of the data where the time gap between two consecutive GPS observation can be large due to data storage issue or signal loss in places like urban canyons. The sparsity can extend from several minutes to hours, which increases the uncertainty on the traversed route. Second, historical data and road information (speed, stop lights etc.) may not readily available or inaccurate. We investigate the use of Bayesian inference approach to this problem combin- ing knowledge expert with information learned from the data.

With the increasing number of vehicles that run on electricity, and concern on congestions in the city, open road tolling becomes an attractive direction in the future. With this work, it is possible to identify the route that vehicles have been traversed without slowing down the vehicle; hence, technically enables open road tolling. It also builds a foundation of a series location based service research in the future in the domain of city mobility analytics. With the implementation of this algorithm, it is possible to study the mobility patterns of human, vehicle and animals etc.

Description:

Notations and Problem Definition

Assume that vehicle must run on a road network. A road network is a directed graph ( , ) where is a set of vertices representing the intersections and terminal points of the road segments, and is a set of edges representing road segments between vertices.

The data studied in this ID is from vehicle GPS log. The log contains a collection of longitude and latitude coordinates with timestamps. From the log, we can create a set of historical path : { → ⋯ → } , which is a set of connected road segments.

The goal of this ID is to find the most likely route for any given two points ( , ) on the road network and a given duration of the trip , that is, ( | , , ).

Path Inference Model:
Use Bayes Rules, the probability can be broken in two parts:

                    ( | , , ) ∝ Pr( | , , )Pr( | , ),
where ( | , , ) is the temporal model and ( | , ) is the spatial model.

Spatial model:


Apply Markov assumption on the set of road transitions in the road network,

Pr( | , ) = Pr( , , , … , | , ) = Pr( | , ) ∏ Pr( | , , )

!

.


Page 02 of 5...