| Title | How Lyft Creates Hyper-Accurate Maps From Open-Source Maps and Real-Time Data | |
| Date | Monday September 09 2019, @06:55PM | |
| Author | chromas | |
| Topic | ||
| from the $ dept. | ||
How Lyft Creates Hyper-Accurate Maps from Open-Source Maps and Real-Time Data
At Lyft, our novel driver localization algorithm detects map errors to create a hyper-accurate map from OpenStreetMap (OSM) and real-time data. We have fixed thousands of map errors in OSM in bustling urban areas. Later in the post, we share a sample of the detected map errors in Minneapolis with the OSM Community to improve the quality of the map.
[...] Our internal map of the road network is based on OSM, which has been built and improved over the years by the open source community. More recently, larger organizations (such as Apple, Microsoft, Mapbox, Mapillary, Facebook, Uber, Grab, Lyft, etc.)¹ have also worked to improve the map. Akin to Wikipedia as an open-source encyclopedia, OSM as an open-source map may contain missing or erroneous data for several possible reasons. Old roads may have never been mapped, new roads may not have been mapped yet, previously closed roads may be reopened, roads may be digitally vandalized, buildings may be non-existent, turn restrictions may be erroneous, road directions may be incorrectly labeled, and so forth. As OSM is a source for our basemap, we need to monitor its quality and accuracy. Upon detecting map errors in OSM, we work with our Data Curation Team to fix them in OSM. This can be done using our proprietary data.
Before discussing map error detection, it is necessary to have an understanding of what map-matching is. At Lyft, we geo-localize drivers from the sensors embedded in their smartphones. This includes a GPS receiver that receives sparse (due to battery constraints) and often noisy (due to urban canyons) locations.
If we do not have any understanding of the road network, we can only employ a space-free tracking algorithm such as a Kalman Filter, as shown in Fig. 1. Drivers would therefore not be localized on the road network.
However, OSM provides us knowledge of the road network. Taking both a sequence of sparse and noisy GPS traces and a map of the road network as input, map matching algorithms can infer the most accurate trajectory on the road network, as shown in Fig. 2. An example of a map-matching algorithm is the one based on Hidden Markov Models (HMM) developed by Newson and Krumm². The quality of the map is essential for accurate map-matching.
[...] At Lyft, we distinguish two types of road network errors:
- The road network errors that trigger map-matching issues and routing issues, denoted Type I map errors
- The road network errors that mostly trigger routing issues, denoted Type II map errors
[...] GPS accuracy is particularly bad in urban canyons when high density of tall buildings corrupt GPS readings due to multi-path or occlusion.
Even when the road network is correct, if, for example, a driver decides to ignore a turn restriction, the algorithm will generate off-road locations. Those off-road locations unfortunately falsely indicate that the map is wrong.
Using our map error detector, we have fixed and contributed thousands of critical Type I map errors in OpenStreetMap, hoping that it will be beneficial for the OSM community.
| Links |
printed from SoylentNews, How Lyft Creates Hyper-Accurate Maps From Open-Source Maps and Real-Time Data on 2024-04-25 08:26:17