Granted Patent B2

US 10,620,009 · App. 15/912,224 · Granted Apr 14, 2020

Abstract

Claims (91)

1. A computer-implemented method for updating digital maps, the method comprising:

receiving global positioning satellite (GPS) data for a vehicle describing a trip by the vehicle from a starting location to a destination location along a path;

predicting a path of travel of the vehicle from the starting location to the destination location based on known road segments in a map database and the GPS data of the vehicle;

identifying a plurality of candidate GPS points from the GPS data that are potentially inaccurate, the candidate GPS points located along a portion of the path and the plurality of candidate GPS points corresponding to geographical positions that are not associated with known road segments in the map database;

generating a simplified portion of the path that corresponds to the candidate GPS points that are potentially inaccurate;

determining whether to include in the path the simplified portion of the path or a portion of the predicted path of travel that corresponds to the plurality of candidate GPS points;

selecting either the simplified portion of the path or the portion of the predicted path of travel to include in the path based on the determination;

revising the path based on the selection;

updating the map database to include one or more road segments corresponding to the geographical positions of the plurality of candidate GPS points based on the path being revised to include the simplified portion;

generating a map based on the updated map database, the map including an image of the path of the trip overlaid onto the map, wherein the image of the path includes the simplified portion of the path; and

transmitting the map to a device of a service requestor that was in the vehicle during the trip.

2. The computer-implemented method of claim 1 , wherein identifying the plurality of candidate GPS points comprises:

comparing GPS points from the GPS data to the predicted path of travel;

determining an accuracy of each GPS point based on the comparison of each GPS point to the predicted path of travel; and

determining the plurality of candidate GPS points based on the accuracy of each of the plurality of GPS points.

3. The computer-implemented method of claim 1 , wherein generating the simplified portion comprises:

applying a Ramer-Douglas-Peucker algorithm to the plurality of candidate GPS points to generate the simplified portion.

4. The computer-implemented method of claim 1 , wherein determining whether to include in the path the simplified portion of the path or the portion of the predicted path of travel is based on a set of rules.

5. The computer-implemented method of claim 4 , wherein the set of rules includes a neighbor rule specifying to select the simplified portion of the path for inclusion in the path based on an accuracy of GPS points that neighbor the plurality of GPS points associated with the simplified portion, the method further comprising:

identifying, from the GPS data of the vehicle, a first plurality of sequentially ordered GPS points that were received prior to the plurality of candidate GPS points associated with the simplified portion being received;

identifying, from the GPS data of the vehicle, a second plurality of sequentially ordered GPS points that were received after the plurality of candidate GPS points associated with the simplified portion were received;

identifying a first accuracy associated with the first plurality of sequentially ordered GPS points and a second accuracy associated with the second plurality of sequentially ordered GPS points; and

selecting the simplified portion of the path for inclusion in the revised path based on the first accuracy and the second accuracy.

6. The computer-implemented method of claim 4 , wherein the set of rules includes a rule requiring that the plurality of candidate GPS points include a threshold amount of GPS points, the method further comprising:

counting a number of GPS points included in the plurality of candidate GPS points;

comparing the count to a threshold; and

selecting the simplified portion of the path for inclusion in the revised path based on the count exceeding the threshold.

7. The computer-implemented method of claim 4 , wherein the set of rules includes a rule requiring that elapsed times between measurement of each of the plurality of candidate GPS points is less than a threshold, the method further comprising:

determining an amount of time that elapsed from when the location tracking device measured each sequential pair of candidate GPS points included in the plurality of candidate GPS points;

comparing the amount of time to the threshold; and

selecting the simplified portion of the path for inclusion in the revised path based on each amount of time being less than the threshold.

8. The computer-implemented method of claim 4 , wherein the set of rules includes a rule requiring that the speed of the transportation vehicle when the plurality of candidate GPS points were measured be less than a speed threshold, the method further comprising:

calculating a speed of the transportation vehicle between each sequential pair of candidate GPS points when the plurality of candidate GPS points were measured;

comparing the calculated speed to the speed threshold; and

selecting the simplified portion of the path for inclusion in the revised path responsive to the calculated speed being less than the speed threshold.

9. The computer-implemented method of claim 4 , wherein the set of rules includes a rule requiring that the accuracy of the plurality of candidate GPS points be less than an accuracy threshold, the method further comprising:

calculating a median accuracy of the plurality of candidate GPS point with respect to the predicted path of travel of the vehicle; and

selecting the simplified portion of the path for inclusion in the revised path responsive to the median accuracy being less than the accuracy threshold.

10. A computer program product comprising a non-transitory computer readable storage medium storing executable code for calculating a fare for a trip, the code when executed by one or more computer processors causes the one or more computer processors to perform steps comprising:

receiving global positioning satellite (GPS) data for a vehicle describing a trip by the vehicle from a starting location to a destination location along a path;

predicting a path of travel of the vehicle from the starting location to the destination location based on known road segments in a map database and the GPS data of the vehicle;

identifying a plurality of candidate GPS points from the GPS data that are potentially inaccurate, the candidate GPS points located along a portion of the path and the plurality of candidate GPS points corresponding to geographical positions that are not associated with known road segments in the map database;

generating a simplified portion of the path that corresponds to the candidate GPS points that are potentially inaccurate;

determining whether to include in the path the simplified portion of the path or a portion of the predicted path of travel that corresponds to the plurality of candidate GPS points;

selecting either the simplified portion of the path or the portion of the predicted path of travel to include in the path based on the determination;

revising the path based on the selection;

updating the map database to include one or more road segments corresponding to the geographical positions of the plurality of candidate GPS points based on the path being revised to include the simplified portion;

generating a map based on the updated map database, the map including an image of the path of the trip overlaid onto the map, wherein the image of the path includes the simplified portion of the path; and

transmitting the map to a device of a service requestor that was in the vehicle during the trip.

11. The computer program product of claim 10 , wherein identifying the plurality of candidate GPS points comprises:

comparing GPS points from the GPS data to the predicted path of travel;

determining an accuracy of each GPS point based on the comparison of each GPS point to the predicted path of travel; and

determining the plurality of candidate GPS points based on the accuracy of each of the plurality of GPS points.

12. A computer-implemented method for updating digital maps, the method comprising:

receiving first global positioning satellite (GPS) data for a first vehicle describing a first trip along a first path by the first vehicle from a first starting location to a first destination location, the first path defined by the first GPS data;

identifying a plurality of candidate GPS points from the first GPS data that are potentially inaccurate, the candidate GPS points located along a portion of the first path and the plurality of candidate GPS points corresponding to geographical positions that are not associated with known road segments in a map database;

simplifying the portion of the first path that corresponds to the plurality of candidate GPS points;

establishing the first path that includes the simplified portion as a first candidate for a true pathway of the first vehicle from the starting location to the destination location during the first trip;

predicting a second path of the first vehicle from the starting location to the destination location based on a combination of known road segments in the map database and the GPS data of the first vehicle;

establishing the second path as a second candidate for the true pathway of the first vehicle from the starting location to the destination location during the first trip;

selecting either the first candidate or the second candidate as the true pathway of the first vehicle;

updating the map database to include one or more road segments corresponding to the simplified portion of the first path based on the first candidate being selected as the true pathway of the first vehicle;

receiving second global positioning satellite (GPS) data for a second vehicle describing a second trip along a second path by the second vehicle from a second starting location to a second destination location, the second path defined by the second GPS data; and

predicting a path of the second vehicle from the second starting location to the second destination location based on the known road segments in the updated map database and the second GPS data of the second vehicle, the predicted path of the second vehicle comprising at least one of the one or more road segments corresponding to the simplified portion of the first path that was included in the updated map database.

13. The computer-implemented method of claim 12 , wherein identifying the plurality of candidate GPS points comprises:

comparing GPS points from the GPS data to the second path;

determining an accuracy of each GPS point based on the comparison of each GPS point to the second path; and

determining the plurality of candidate GPS points based on the accuracy of each of the plurality of GPS points.

14. The computer-implemented method of claim 12 , wherein simplifying the portion of the first path comprises:

applying a Ramer-Douglas-Peucker algorithm to the plurality of candidate GPS points to generate the simplified portion of the first path.

15. The computer-implemented method of claim 12 , wherein selecting either the first candidate or the second candidate as the true pathway of the vehicle is based on a set of rules.

16. The computer-implemented method of claim 15 , wherein the set of rules includes a neighbor rule specifying to select the first candidate as the true pathway based on an accuracy of GPS points that neighbor the plurality of GPS points associated with the simplified portion of the first path, the method further comprising:

identifying, from the GPS data of the vehicle, a first plurality of sequentially ordered GPS points that were received prior to the plurality of candidate GPS points associated with the simplified portion of the first path being received;

identifying, from the GPS data of the vehicle, a second plurality of sequentially ordered GPS points that were received after the plurality of candidate GPS points associated with the simplified portion of the first path were received;

identifying a first accuracy associated with the first plurality of sequentially ordered GPS points and a second accuracy associated with the second plurality of sequentially ordered GPS points; and

selecting the first candidate as the true pathway for the vehicle based on the first accuracy and the second accuracy.

17. The computer-implemented method of claim 15 , wherein the set of rules includes a rule requiring that the plurality of candidate GPS points include a threshold amount of GPS points, the method further comprising:

counting a number of GPS points included in the plurality of candidate GPS points;

comparing the count to a threshold; and

selecting the first candidate as the true pathway based on the count exceeding the threshold.

18. The computer-implemented method of claim 15 , wherein the set of rules includes a rule requiring that elapsed times between measurement of each of the plurality of candidate GPS points is less than a threshold, the method further comprising:

determining an amount of time that elapsed from when the location tracking device measured each sequential pair of candidate GPS points included in the plurality of candidate GPS points;

comparing the amount of time to the threshold; and

selecting the first candidate as the true pathway based on each amount of time being less than the threshold.

19. The computer-implemented method of claim 15 , wherein the set of rules includes a rule requiring that the speed of the transportation vehicle when the plurality of candidate GPS points were measured be less than a speed threshold, the method further comprising:

calculating a speed of the transportation vehicle between each sequential pair of candidate GPS points when the plurality of candidate GPS points were measured;

comparing the calculated speed to the speed threshold; and

selecting the first candidate as the true pathway responsive to the calculated speed being less than the speed threshold.

20. The computer-implemented method of claim 15 , wherein the set of rules includes a rule requiring that the accuracy of the plurality of candidate GPS points be less than an accuracy threshold, the method further comprising:

calculating a median accuracy of the plurality of candidate GPS point with respect to the second path; and

selecting the first candidate as the true pathway responsive to the median accuracy being less than the accuracy threshold.

Assignments (7)