Route Computation Based on Route-Oriented Vehicle Trajectories

• US 20110208429A1
• Filed: 02/24/2010
• Published: 08/25/2011
• Est. Priority Date: 02/24/2010
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Microsoft Corporation
• Inventors: Xie, Xing, Zheng, Yu, Zhang, Chengyang, Lou, Yin
• Granted Patent: US 9,261,376 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• 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 for 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 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; and

specifying a road segment frequently visited by the route-oriented vehicles as a landmark, a frequency being based on a number of route-oriented vehicle logs for the landmark.

2. The method of claim 1, wherein the 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 is greater than or less than a predetermined threshold;

in an event that the time interval is greater than the threshold, partitioning the two consecutive GPS points into two different trajectories; and

in an event that the time interval is less than the threshold, combining the two consecutive GPS points into a trajectory.

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 based at least in part on a time threshold within a distance threshold, the stay point represents a geographical region that the route-oriented vehicle remained stationary for a 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 that the route-oriented vehicles may travel on 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 route-oriented vehicle trajectory passing through the landmarks, the landmark edge to represent frequent 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:

presenting a user interface to receive 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 and connecting a set of connected road segments between each pair of consecutive landmarks of an initial route; and

displaying the route for 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 is identified as a road segment that is frequently visited by route-oriented vehicles;

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

refining the initial path by finding a route that sequentially connects the landmarks, from the starting location to the destination location; 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.

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 route; 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 route based on a sequence of landmarks with corresponding transition times between the landmarks and a least amount of travel time.

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;

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

segmenting the geographical locations into the road segments, a 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.

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;

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 the route-oriented vehicle logs into the route-oriented vehicle trajectories based on a stay point, the stay point determined at least in part on a time threshold within a distance threshold, the stay point represents a geographical region that the route-oriented vehicle remained stationary for a 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 the at least two vertices with a landmark edge, the landmark edge to represent frequent travels between the at least two vertices by the route-oriented vehicles.

16. A system comprising:

a memory;

a processor coupled to the memory to perform acts comprising;

receiving user input to the user interface 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 identifies landmarks on the graph as road segments that are frequently visited by route-oriented vehicles;

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;

presenting the 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 route-oriented vehicle logs, which include a sequence of global positioning system (GPS) points; and

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

18. The system of claim 16, further comprising partitioning the route-oriented 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 route-oriented vehicle trajectory to a corresponding road segment; and

specifying a road segment frequently visited by the route-oriented vehicles as a landmark, a frequency being based on a number of route-oriented vehicle logs for the landmark.