Utilizing artificial neural networks to evaluate routes based on generated route tiles

Patent metadata

Field	Value
Publication number	US-10989544-B2
Application number	US-201916706441-A
Country	US
Kind code	B2
Filing date	Dec 6, 2019
Priority date	Dec 29, 2017
Publication date	Apr 27, 2021
Grant date	Apr 27, 2021

Abstract

This disclosure covers methods, non-transitory computer readable media, and systems that generate route tiles reflecting both GPS locations and map-matched locations for regions along a route traveled by a client device associated with a transportation vehicle. For example, in some implementations, the disclosed systems use an artificial neural network to analyze the route tiles and determine route-accuracy metrics indicating GPS locations or map-matched locations for particular regions along the route. The disclosed systems can then use the route-accuracy metrics to facilitate transport of requestors by, for example, determining a distance of the route or a location of a client device associated with a transportation vehicle.

First claim

We claim:

1. A system comprising:
at least one processor; and
at least one non-transitory computer readable storage medium storing instructions that, when executed by the at least one processor, cause the system to:
identify a set of training GPS locations and a set of training map-matched locations for a training route;
analyze the set of training GPS locations and the set of training map-matched locations utilizing an artificial neural network to generate predicted-route-accuracy metrics;
train the artificial neural network to select between GPS locations and map-matched locations by comparing the predicted-route-accuracy metrics to ground-truth-route-accuracy metrics; and
modify a digital map by utilizing the trained artificial neural network to analyze GPS locations for a route travelled by a client device and map-matched locations of the digital map.

2. The system of claim 1 , further comprising instructions that, when executed by the at least one processor, cause the system to:
determine a set of training regions corresponding to the training route; and
generate a training route tile for a training region of the set of training regions based on a subset of training GPS locations and a subset of training map-matched locations corresponding to the training region.

3. The system of claim 2 , further comprising instructions that, when executed by the at least one processor, cause the system to generate the training route tile by:
generating a first training image for the training region based on the subset of training GPS locations; and
generating a second training image for the training region based on the subset of training map-matched locations.

4. The system of claim 2 , further comprising instructions that, when executed by the at least one processor, cause the system to analyze the training route tile utilizing the artificial neural network to generate a predicted-route-accuracy-metric, the predicted-route-accuracy metric comprising at least one of: a predicted accuracy classifier, a predicted distance, a predicted path, or a predicted GPS noise level.

5. The system of claim 4 , further comprising instructions that, when executed by the at least one processor, cause the system to:
identify a ground-truth-route-accuracy metric, the ground-truth-route-accuracy metric comprising at least one of a ground-truth accuracy classifier, a ground-truth distance, a ground-truth path, or a ground-truth GPS noise level; and
compare the predicted-route-accuracy metrics to the ground-truth-route-accuracy metrics by applying a loss function to the predicted-route-accuracy metric and the ground-truth-route-accuracy metric.

6. The system of claim 1 , wherein the set of training GPS locations comprise simulated training GPS locations, the system further comprising instructions that, when executed by the at least one processor, cause the system to generate the simulated training GPS locations by:
determining a road network comprising the training route;
creating simulated route locations for the training route within the road network; and
generating the simulated training GPS locations by transforming the simulated route locations based on a GPS-noise model.

7. The system of claim 6 , further comprising instructions that, when executed by the at least one processor, cause the system to generate the simulated training GPS locations based on the GPS-noise model by utilizing a diagonal matrix comprising a noise deviation and Weiner process.

8. The system of claim 6 , further comprising instructions that, when executed by the at least one processor, cause the system to train the GPS-noise model based on historical GPS traces.

9. A non-transitory computer readable medium storing instructions thereon that, when executed by at least one processor, cause a computer system to:
identify a set of training GPS locations and a set of training map-matched locations for a training route;
analyze the set of training GPS locations and the set of training map-matched locations utilizing an artificial neural network to generate predicted-route-accuracy metrics;
train the artificial neural network to select between GPS locations and map-matched locations by comparing the predicted-route-accuracy metrics to ground-truth-route-accuracy metrics; and
modify a digital map by utilizing the trained artificial neural network to analyze GPS locations for a route travelled by a client device and map-matched locations of the digital map.

10. The non-transitory computer readable medium of claim 9 , further comprising instructions that, when executed by the at least one processor, cause the computer system to:
determine a set of training regions corresponding to the training route; and
generate a training route tile for a training region of the set of training regions based on a subset of training GPS locations and a subset of training map-matched locations corresponding to the training region.

11. The non-transitory computer readable medium of claim 10 , further comprising instructions that, when executed by the at least one processor, cause the computer system to generate the training route tile by:
generating a first training image for the training region based on the subset of training GPS locations; and
generating a second training image for the training region based on the subset of training map-matched locations.

12. The non-transitory computer readable medium of claim 10 , further comprising instructions that, when executed by the at least one processor, cause the computer system to analyze the training route tile utilizing the artificial neural network to generate a predicted-route-accuracy-metric, the predicted-route-accuracy metric comprising at least one of: a predicted accuracy classifier, a predicted distance, a predicted path, or a predicted GPS noise level.

13. The non-transitory computer readable medium of claim 12 , further comprising instructions that, when executed by the at least one processor, cause the computer system to:
identify a ground-truth-route-accuracy metric, the ground-truth-route-accuracy metric comprising at least one of a ground-truth accuracy classifier, a ground-truth distance, a ground-truth path, or a ground-truth GPS noise level; and
compare the predicted-route-accuracy metrics to the ground-truth-route-accuracy metrics by applying a loss function to the predicted-route-accuracy metric and the ground-truth-route-accuracy metric.

14. The non-transitory computer readable medium of claim 9 , wherein the set of training GPS locations comprise simulated training GPS locations, and further comprising instructions that, when executed by the at least one processor, cause the computer system to generate the simulated training GPS locations by:
determining a road network comprising the training route;
creating simulated route locations for the training route within the road network; and
generating the simulated training GPS locations by transforming the simulated route locations based on a GPS-noise model by utilizing a diagonal matrix comprising a noise deviation and Weiner process.

15. A method comprising:
identifying a set of training GPS locations and a set of training map-matched locations for a training route;
analyzing the set of training GPS locations and the set of training map-matched locations utilizing an artificial neural network to generate predicted-route-accuracy metrics;
training the artificial neural network to select between GPS locations and map-matched locations by comparing the predicted-route-accuracy metrics to ground-truth-route-accuracy metrics; and
modifying a digi

Assignees

• Lyft Inc

Inventors

• Haque Asif
• Murphy James Kevin
• Malek Yuanyuan

Classifications

• G01C21/30 Primary

  Map- or contour-matching · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N3/045

  Combinations of networks · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title