Route computation based on route-oriented vehicle trajectories

• US 9,261,376 B2
• Filed: 02/24/2010
• Issued: 02/16/2016
• Est. Priority Date: 02/24/2010
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zheng, Yu, Lou, Yin, Zhang, Chengyang, Xie, Xing
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): King, Rodney P
• Application Number:
  US12/712,053
• Publication Number:
  US 20110208429A1
• Time in Patent Office: 2,183 Days
• Field of Search: 701/201, 701/209, 701/213, 701/400, 701/408, 701/468, 701/446, 701/527, 701/533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/10 by using measurements of speed or acceleration G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/16 by integrating acceleration or speed, i.e. inertial navigation
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01S 19/42 Determining position

Abstract

Techniques for providing a route based on route-oriented vehicle trajectories are described. This disclosure describes receiving GPS logs and extracting route-oriented vehicle trajectory content from the GPS log data to pertain to a single trip. Next, the process maps each route-oriented vehicle trajectory to a corresponding road segment to construct a landmark graph. A landmark is a road segment frequently visited by route-oriented vehicles. The process includes receiving a user query with a starting point and a destination point; searching the landmark graph for a sequence of landmarks with corresponding transition times and a least amount of travel time. Then the process identifies and connects sets of road segments between each pair of consecutive landmarks, and displays a route to a user with a nearest landmark to the starting point, other landmarks along the route, and another nearest landmark to the destination point.

Claims

1. A method implemented at least partially by a processor, the method comprising:

collecting a sequence of global positioning system (GPS) points from route-oriented vehicle logs;

identifying geographical locations from the route-oriented vehicle logs, the geographical locations representing locations where route-oriented vehicles travelled as recorded in the vehicle logs;

extracting route-oriented vehicle trajectories from the route-oriented vehicle logs, the route-oriented vehicle trajectories representing individual trips; and

constructing a landmark graph based at least in part on the route-oriented vehicle trajectories by;

associating each route-oriented vehicle trajectory to a corresponding road segment;

determining a first frequency that a first road segment is visited by the route-oriented vehicles and at least a second frequency that other road segments are visited by the route-oriented vehicles, the first frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the first road segment, and the second frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the other road segments;

comparing the first frequency to the second frequency; and

identifying a landmark, the landmark being the first road segment when the first frequency is greater than the second frequency.

2. The method of claim 1, wherein the first road segment is a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline.

3. The method of claim 1, further comprising:

determining whether a time interval between two consecutive GPS points meets or exceeds a predetermined threshold; and

partitioning the two consecutive GPS points into two different trajectories based on whether the time interval between the two consecutive GPS points meets or exceeds the threshold.

4. The method of claim 1, further comprising dividing the route-oriented vehicle trajectories into separate trajectories when a stay point is identified, the stay point representing a geographical region in which a route-oriented vehicle remained within a threshold distance for a threshold time period.

5. The method of claim 1, wherein the associating each route-oriented vehicle trajectory to a corresponding road segment comprises:

identifying candidate road segments and correlating the candidate road segments to candidate projection points;

detecting the candidate projection points on candidate edges;

identifying a probability that a GPS point matches a candidate point computed based on a distance between two points;

identifying a list of road segments based on determining a shortest path from a first candidate projection point to a second candidate projection point;

generating a candidate graph for the route-oriented vehicle trajectory with a set of candidate projection points and a set of edges to represent the shortest paths between neighboring candidate points; and

determining a road segment that matches the trajectory.

6. The method of claim 1, wherein the constructing the landmark graph further comprises:

computing a number of route-oriented vehicle trajectories that connect any of the landmarks; and

connecting the landmarks with a landmark edge when there is at least a subset of the route-oriented vehicle trajectories passing through the landmarks, the landmark edge to represent travels between the landmarks by the route-oriented vehicles.

7. The method of claim 1, further comprising:

determining a median time cost for travelling on a landmark edge, the landmark edge to connect one landmark to another landmark.

8. The method of claim 1, further comprising:

receiving a user query with a starting point and a destination point for directions;

searching the landmark graph for an initial route that is represented by a sequence of landmarks with corresponding transition times and a least amount of travel time;

computing a set of connected road segments between each pair of consecutive landmarks of an initial route; and

providing data indicating a route including the directions with landmarks from the starting point to the destination point.

9. One or more computer-readable media encoded with instructions that, when executed by a processor, perform acts comprising:

presenting a user interface on a display of a portable electronic device, the user interface to access a service application that provides map-based services;

receiving user input to the user interface indicating a starting location and a destination location;

accessing a landmark graph constructed from route-oriented vehicle trajectories, a landmark being identified when a first frequency of route-oriented vehicles visiting a road segment is compared to a second frequency of route-oriented vehicles visiting a second or subsequent road segment and the first frequency is greater than the second frequency;

computing an initial path, based on the starting location and the destination location, between each pair of consecutive landmarks of the initial path; and

refining the initial path by finding a route that sequentially connects the landmarks, from the starting location to the destination location.

10. The computer-readable media of claim 9, in response to the initial path, further comprising:

calculating additional paths from the starting location to each terminal point of the landmarks on the initial path; and

determining the additional paths for unidirectional and bidirectional road segments.

11. The computer-readable media of claim 9, further comprising:

searching the landmark graph for the initial path based on a sequence of landmarks with corresponding transition times between the landmarks and a least amount of travel time; and

visually presenting the route to a user, the route illustrating a nearest landmark to the starting location, any landmarks along the route, and another nearest landmark to the destination location.

12. The computer-readable media of claim 9, further comprising:

collecting the route-oriented vehicle logs that include a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles;

determining geographical locations from the route-oriented vehicle logs, the geographical locations to represent regions where the variety of route-oriented vehicles have travelled as recorded in the vehicle logs; and

segmenting the geographical locations into the road segments, a road segment including a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline.

13. The computer-readable media of claim 9, further comprising:

extracting route-oriented vehicle trajectories from route-oriented vehicle logs, the route-oriented vehicle logs are represented with a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles engaged in business related transportation;

representing individual trips based on a sequence of road segments with transition times with route-oriented vehicle trajectories;

determining when a time interval between two consecutive GPS points is greater than or less than a predetermined threshold;

in an event that the time interval between two consecutive GPS points is greater the predetermined threshold, partition the two consecutive GPS points into two different trajectories;

or

in an event that the time interval between the two consecutive GPS points is less than the predetermined threshold, use the two consecutive GPS points in a trajectory.

14. The computer-readable media of claim 9, further comprising determining when to partition route-oriented vehicle logs into the route-oriented vehicle trajectories based on a stay point, the stay point represents a geographical region in which the route-oriented vehicle remained within a threshold distance for a threshold time period.

15. The computer-readable media of claim 9, further comprising constructing the landmark graph based at least in part on the route-oriented vehicle trajectories by:

matching each route-oriented vehicle trajectory to a corresponding road segment;

representing the landmark as a vertex on the landmark graph; and

connecting at least two vertices with a landmark edge, the landmark edge to represent travels between the at least two vertices by at least a subset of the variety of route-oriented vehicles by a number of times greater than a threshold.

16. A system comprising:

a memory;

one or more processors coupled to the memory having instructions to perform acts comprising;

receiving user input indicating a starting location, a destination location, and a time of day and a category of day;

accessing a landmark graph stored in a database, the landmark graph identifying landmarks on the landmark graph, landmarks being identified as road segments having a threshold frequency of visits by a variety of vehicles, the threshold frequency being greater than the frequency of visits by a variety of vehicles on other road segments;

searching the landmark graph for an initial route based on a sequence of landmarks and a least amount of travel time based at least in part on the starting location and the destination location;

calculating an initial path between each pair of consecutive landmarks of the initial route; and

presenting the initial route with nearest landmark to the starting location, landmarks along the route, and another nearest landmark to the destination location for the time of day and the category of day as specified.

17. The system of claim 16, further comprising:

collecting vehicle logs, which include a sequence of global positioning system (GPS) points from the variety of vehicles;

extracting vehicle trajectories from the vehicle logs, the vehicle trajectories representing individual trips made by the variety of vehicles;

partitioning the vehicle trajectories made by the variety of vehicles into multiple partitions according to times of day and categories of days; and

generating landmark graphs of landmarks for each of the multiple partitions, wherein the accessing accesses the landmark graph associated with the time of day and the category of day.

18. The system of claim 16, further comprising partitioning the vehicle trajectories into multiple parts based on a time of a day and a category of day.

19. The system of claim 16, further comprising computing paths between each pair of consecutive landmarks of the initial route, a path is a set of connected road segments.

20. The system of claim 16, further comprising:

associating each vehicle trajectory to a corresponding road segment; and

specifying a road segment visited at a greater frequency relative to another road segment as a landmark, the greater frequency being determined based on a number of vehicle logs for the landmark.