Measuring the accuracy of map matched trajectories

• US 10,415,984 B2
• Filed: 02/13/2018
• Issued: 09/17/2019
• Est. Priority Date: 12/29/2017
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Cai, Xiao, Yao, Shijing, Nguyen, Thi Duong
• Primary Examiner(s): Nguyen, Tan Q
• Application Number:
  US15/895,988
• Publication Number:
  US 20190204096A1
• Time in Patent Office: 581 Days
• Field of Search: 701417
• 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: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3885 Transmission of map data to client devices; Reception of map data by client devices

Abstract

A transport service system determines the accuracy of a map matched trajectory using a forward probability algorithm. A transport vehicle on a trip relays location data to the system. The system uses a map of the corresponding area and the location data to calculate an emission probability, the likelihood of a candidate road being associated with a location data point, and a transition probability, the likelihood of a second state occurring after a first state. The joint probability of the emission and transition probabilities is used to determine a total number of zero forward probability occurrences and an average forward probability associated with the trip. These metrics are used to measure the accuracy of the map matching algorithm for the trip.

Claims

1. A method comprising:

receiving from a transport service vehicle raw location data, the location data associated with a timestamp and a trip;

receiving from a transport service system a map of an area associated with the transport service vehicle and the trip, the map containing information on viable trajectories for the transport service vehicle;

calculating with a Hidden Markov Model an emission probability, the emission probability based on the likelihood that the transport service vehicle is at a road segment given an observation of the location data at a candidate road;

calculating with a Hidden Markov Model a transition probability, the transition probability based on the likelihood that for a current state, the transport service vehicle will transition to a next state; and

based on the joint probability of the emission and transition probabilities, determining a total number of zero forward probability occurrences and an average forward probability associated with the trip.

2. The method of claim 1, wherein the total number of zero forward probability occurrences and the average forward probability associated with a trip is used to evaluate the accuracy of a map matched trajectory associated with the trip.

3. The method of claim 1, wherein the total number of zero forward probability occurrences and the average forward probability of one or more trips associated with a given area are used to evaluate the accuracy of the map associated with a map matching process in the area.

4. The method of claim 1, wherein the emission probability is directly related to the haversine distance from a given GPS data point and a candidate road.

5. The method of claim 1, wherein the transition probability is modeled by the difference between the haversine distance between the current state and the next state and a routing distance between a road segment candidate of the current state and a road segment candidate of the next state.

6. The method of claim 1, further comprising:

receiving high precision location data from a transport vehicle equipped with a high precision location tracking device;

comparing a high precision location data route corresponding to the high precision location data to a map matched route associated with the trip;

based on discrepancies between the high precision location data route and the map matched route associated with the trip, identifying errors in the map matched route;

combining the average forward probability and zero forward probability occurrences with the identified errors as a metric for the accuracy of the map matched route.

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

receiving from a transport service vehicle raw location data, the location data associated with a timestamp and a trip;

receiving from a transport service system a map of an area associated with the transport service vehicle and the trip, the map containing information on viable trajectories for the transport service vehicle;

calculating with a Hidden Markov Model an emission probability, the emission probability based on the likelihood that the transport service vehicle is at a road segment given an observation of the location data at a candidate road;

calculating with a Hidden Markov Model a transition probability, the transition probability based on the likelihood that for a current state, the transport service vehicle will transition to a next state; and

based on the joint probability of the emission and transition probabilities, determining a total number of zero forward probability occurrences and an average forward probability associated with the trip.

8. The computer-readable storage medium of claim 7, wherein the total number of zero forward probability occurrences and the average forward probability associated with a trip is used to evaluate the accuracy of a map matched trajectory associated with the trip.

9. The computer-readable storage medium of claim 7, wherein the total number of zero forward probability occurrences and the average forward probability of one or more trips associated with a given area are used to evaluate the accuracy of the map associated with a map matching process in the area.

10. The computer-readable storage medium of claim 7, wherein the emission probability is directly related to the haversine distance from a given GPS data point and a candidate road.

11. The computer-readable storage medium of claim 7, wherein the transition probability is modeled by the difference between the haversine distance between the current state and the next state and a routing distance between a road segment candidate of the current state and a road segment candidate of the next state.

12. The computer-readable storage medium of claim 7, further comprising:

receiving high precision location data from a transport vehicle equipped with a high precision location tracking device;

comparing a high precision location data route corresponding to the high precision location data to a map matched route associated with the trip;

based on discrepancies between the high precision location data route and the map matched route associated with the trip, identifying errors in the map matched route;

combining the average forward probability and zero forward probability occurrences with the identified errors as a metric for the accuracy of the map matched route.

13. 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 from a transport service vehicle raw location data, the location data associated with a timestamp and a trip;

receiving from a transport service system a map of an area associated with the transport service vehicle and the trip, the map containing information on viable trajectories for the transport service vehicle;

calculating with a Hidden Markov Model an emission probability, the emission probability based on the likelihood that the transport service vehicle is at a road segment given an observation of the location data at a candidate road;

calculating with a Hidden Markov Model a transition probability, the transition probability based on the likelihood that for a current state, the transport service vehicle will transition to a next state; and

based on the joint probability of the emission and transition probabilities, determining a total number of zero forward probability occurrences and an average forward probability associated with the trip.

14. The system of claim 13, wherein the total number of zero forward probability occurrences and the average forward probability associated with a trip is used to evaluate the accuracy of a map matched trajectory associated with the trip.

15. The system of claim 13, wherein the total number of zero forward probability occurrences and the average forward probability of one or more trips associated with a given area are used to evaluate the accuracy of the map associated with a map matching process in the area.

16. The system of claim 13, wherein the emission probability is directly related to the haversine distance from a given GPS data point and a candidate road.

17. The system of claim 13, wherein the transition probability is modeled by the difference between the haversine distance between the haversine distance between the current state and the next state and a routing distance between a road segment candidate of the current state and a road segment candidate of the next state.

18. The system of claim 13, further comprising:

receiving high precision location data from a transport vehicle equipped with a high precision location tracking device;

comparing a high precision location data route corresponding to the high precision location data to a map matched route associated with the trip;

based on discrepancies between the high precision location data route and the map matched route associated with the trip, identifying errors in the map matched route;

combining the average forward probability and zero forward probability occurrences with the identified errors as a metric for the accuracy of the map matched route.