Biasing map matched trajectories based on planned route information

• US 10,533,862 B1
• Filed: 11/28/2018
• Issued: 01/14/2020
• Est. Priority Date: 11/28/2018
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Paranjpe, Rohan Abhay, Rubin, Seth Harris, Barker, Joseph Kelly, Guan, Jintao, Parikh, Karan Rajen
• Primary Examiner(s): Sarwar, Babar
• Application Number:
  US16/203,600
• Time in Patent Office: 412 Days
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

A transport service system identifies a map matched trajectory for a transport vehicle based on planned route information and location data associated with a trip. The system receives planned route information and location data for a transport vehicle. For each location data point, the transport service system identifies a set of candidate road segments. Sequential pairs of candidate road segments represent transitions. The system uses a map of the corresponding area to calculate a transition probability, the likelihood of traversing from the first candidate road segment to the second candidate road segment. The system identifies transitions that correspond to the planned route and adjusts the transition probabilities based on the identified planned route transitions. Based on the adjusted probabilities, the transport service system determines a most-likely traversed path for the transport vehicle.

Claims

1. A method comprising:

receiving a planned route from a transport service system, the planned route associated with a trip traveled by a transport service vehicle;

receiving a time series of two or more location data points captured by location sensors on the transport service vehicle;

for each location data point in the time series, identifying a sets of candidate road segments of the transport service vehicle, the candidate road segments representing possible road segments traveled by the transport service vehicle when capturing the location data point;

for each sequential pair of location data points in the time series;

identifying transitions between the sets of candidate road segments associated with the location data points in the sequential pair and in the sequential sets of candidate road segments;

modeling transition probabilities for the identified transitions between the candidate road segments in the sequential sets of candidate road segments;

identifying transitions that correspond to the planned route associated with the trip;

adjusting the transition probabilities by either reducing transition probabilities that do not correspond to the identified transitions or increasing transition probabilities for transitions that correspond to the identified transitions; and

determining most-likely traversed road segments based on the adjusted transition probabilities.

2. The method of claim 1, wherein the transition probability for an identified transition is modeled by the difference between the haversine distance between the corresponding sequential pair of location data points and a routing distance between the corresponding sequential set of candidate road segments.

3. The method of claim 2, wherein the transition probability is adjusted for candidate road segments that do not correspond to the planned route by applying a penalty to the difference between the haversine distance between the corresponding sequential pairs of location data points and a routing distance between the corresponding sequential set of candidate road segments.

4. The method of claim 1, wherein the transition probability is calculated using a Hidden Markov Model.

5. The method of claim 1, further comprising calculating an emission probability, the emission probability based on the likelihood that the transport service vehicle is at a candidate road segment given an observation of the location data at a candidate road.

6. The method of claim 5, further comprising determining, based at least in part on the emission probability and the adjusted transition probability, a most likely path taken by the transport service vehicle.

7. The method of claim 1, wherein the transition probability is calculated for a subset of the sequential pairs of location data points in the time series.

8. The method of claim 1, wherein receiving a planned route from a transport service system further comprises:

receiving a set of latitude and longitude pairs from the transport service system, the latitude and longitude pairs representing coordinates along a planned route;

converting the set of latitude and longitude pairs to a polyline, the polyline including points representing the latitude and longitude pairs; and

identifying road segments and intersections corresponding to polyline based on headings and distances between the points on the polyline.

9. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations comprising:

receiving a planned route from a transport service system, the planned route associated with a trip traveled by a transport service vehicle;

receiving a time series of two or more location data points captured by location sensors on the transport service vehicle;

for each location data point in the time series, identifying a sets of candidate road segments of the transport service vehicle, the candidate road segments representing possible road segments traveled by the transport service vehicle when capturing the location data point;

for each sequential pair of location data points in the time series;

identifying transitions between the sets of candidate road segments associated with the location data points in the sequential pair and in the sequential sets of candidate road segments;

modeling transition probabilities for the identified transitions between the candidate road segments in the sequential sets of candidate road segments;

identifying transitions that correspond to the planned route associated with the trip;

adjusting the transition probabilities by either reducing transition probabilities that do not correspond to the identified transitions or increasing transition probabilities for transitions that correspond to the identified transitions; and

determining most-likely traversed road segments based on the adjusted transition probabilities.

10. The non-transitory computer-readable storage medium of claim 9, wherein the transition probability for an identified transition is modeled by the difference between the haversine distance between the corresponding sequential pair of location data points and a routing distance between the corresponding sequential set of candidate road segments.

11. The non-transitory computer-readable storage medium of claim 10, wherein the transition probability is adjusted for candidate road segments that do not correspond to the planned route by applying a penalty to the difference between the haversine distance between the corresponding sequential pairs of location data points and a routing distance between the corresponding sequential set of candidate road segments.

12. The non-transitory computer-readable storage medium of claim 9, wherein the transition probability is calculated using a Hidden Markov Model.

13. The non-transitory computer-readable storage medium of claim 9, further comprising calculating an emission probability, the emission probability based on the likelihood that the transport service vehicle is at a candidate road segment given an observation of the location data at a candidate road.

14. The non-transitory computer-readable storage medium of claim 13, further comprising determining, based at least in part on the emission probability and the adjusted transition probability, a most likely path taken by the transport service vehicle.

15. The non-transitory computer-readable storage medium of claim 9, wherein the transition probability is calculated for a subset of the sequential pairs of location data points in the time series.

16. The non-transitory computer-readable storage medium of claim 9, wherein receiving a planned route from a transport service system further comprises:

receiving a set of latitude and longitude pairs from the transport service system, the latitude and longitude pairs representing coordinates along a planned route;

converting the set of latitude and longitude pairs to a polyline, the polyline including points representing the latitude and longitude pairs; and

identifying road segments and intersections corresponding to polyline based on headings and distances between the points on the polyline.

17. A system comprising:

a computer processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations comprising;

receiving a planned route from a transport service system, the planned route associated with a trip traveled by a transport service vehicle;

receiving a time series of two or more location data points captured by location sensors on the transport service vehicle;

for each location data point in the time series, identifying a sets of candidate road segments of the transport service vehicle, the candidate road segments representing possible road segments traveled by the transport service vehicle when capturing the location data point;

for each sequential pair of location data points in the time series;

identifying transitions between the sets of candidate road segments associated with the location data points in the sequential pair and in the sequential sets of candidate road segments;

modeling transition probabilities for the identified transitions between the candidate road segments in the sequential sets of candidate road segments;

identifying transitions that correspond to the planned route associated with the trip;

adjusting the transition probabilities by either reducing transition probabilities that do not correspond to the identified transitions or increasing transition probabilities for transitions that correspond to the identified transitions; and

determining most-likely traversed road segments based on the adjusted transition probabilities.

18. The system of claim 17, wherein the transition probability for an identified transition is modeled by the difference between the haversine distance between the corresponding sequential pair of location data points and a routing distance between the corresponding sequential set of candidate road segments.

19. The system of claim 18, wherein the transition probability is adjusted for candidate road segments that do not correspond to the planned route by applying a penalty to the difference between the haversine distance between the corresponding sequential pairs of location data points and a routing distance between the corresponding sequential set of candidate road segments.

20. The system of claim 17, wherein the transition probability is calculated using a Hidden Markov Model.