DETECTION OF MAP ANOMALIES
`
`Inventors:
`
`Sundar Annamalai
`
`Naomi Chopra
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`This application claims priority to and the benefit of Indian Provisional
`
`Application 201741039669, filed on November 7, 2017, which is incorporated by
`
`reference herein in its entirety.
`
`BACKGROUND
`
`
`Field
`
`The described ernbodirnents relate generally to detecting errors in digital maps,
`
`and more specifically to inferring the existence of erroneous map data based on
`
`analysis of actual vehicle trace data.
`
`Description of Related Art
`
`[0001]
`
`Digital maps are used for a variety of functions, including providing
`
`navigation assistance to drivers and riders.
`
`[0002]
`
`Inaccuracies often exist in digital map data. For example, data may have
`
`been collected incorrectly, and is thus represented incorrectly in the map. Or, changes
`
`in the road network may have occurred since the map data was collected, for example
`
`because of construction of new roads, closure of existing roads, or addition and
`
`removal of traffic flow restrictions.
`
`[0003]
`
`Inaccurate map data inhibits the ability to provide efficient navigation
`
`routing to drivers and vehicles, and can create a safety hazard.
`
`
`
`Inventors:
`
`Sundar Annamalai
`
`Naomi Chopra
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`This application claims priority to and the benefit of Indian Provisional
`
`Application 201741039669, filed on November 7, 2017, which is incorporated by
`
`reference herein in its entirety.
`
`BACKGROUND
`
`
`Field
`
`The described ernbodirnents relate generally to detecting errors in digital maps,
`
`and more specifically to inferring the existence of erroneous map data based on
`
`analysis of actual vehicle trace data.
`
`Description of Related Art
`
`[0001]
`
`Digital maps are used for a variety of functions, including providing
`
`navigation assistance to drivers and riders.
`
`[0002]
`
`Inaccuracies often exist in digital map data. For example, data may have
`
`been collected incorrectly, and is thus represented incorrectly in the map. Or, changes
`
`in the road network may have occurred since the map data was collected, for example
`
`because of construction of new roads, closure of existing roads, or addition and
`
`removal of traffic flow restrictions.
`
`[0003]
`
`Inaccurate map data inhibits the ability to provide efficient navigation
`
`routing to drivers and vehicles, and can create a safety hazard.
`
`
`
`SUMMARY
`
`[0004]
`
`Described embodiments enable the identification of erroneous digital map
`
`data. A route guidance engine provides guidance from a first point to a second point
`
`along a road network, using data stored in a map database. The route guidance engine
`
`determines, for each recommended route, whether a vehicle actually travels the
`
`recommended route, or instead travels a different route from the first to the second
`
`point.
`
`[0005]
`
`A map anomaly detection (MAD) engine compares the trace data (that is,
`
`the data showing the actual path traveled by the vehicle) to the recommended route
`
`data for a particular trip from the first point to the second point. The MAD engine
`
`identifies points along the recommended route that are not included in the trace. The
`
`MAD engine also identifies points along the trace that are not included in the
`
`recommended route. From these two data sets, the MAD engine identifies section
`
`pairs—that is, nearby segments of the recommended route polyline and the trace
`
`polyline—and then performs a filtering step to reduce false positives and false
`
`negatives.
`
`[0006]
`
`The MAD engine then aggregates data for all trips from the first point to the
`
`second point within a particular time period of interest, and further aggregates all trips
`
`from all starting points to ending points. The resulting set of points, or a most-
`
`frequently occurring set of points, are points where the stored map data is likely
`
`incorrect.
`
`[0007]
`
`In some embodiments, the MAD engine can automatically correct the map
`
`data, for example by inferring the existence of a road segment, the non-existence of a
`
`
`
`road segment, or the existence or lack thereof of a turn restriction. In various
`
`embodiments, the set of points can be used to identify and correct map data errors in a
`
`significantly more efficient manner than is conventionally required.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0008]
`
`Fig. 1 illustrates a system for identifying anomalies in map data in
`
`accordance with one embodiment.
`
`[0009]
`
`Fig. 2 is a flowchart illustrating steps for providing recommended route
`
`guidance to a requester in accordance with one embodiment.
`
`[0010]
`
`Fig. 3 is a flowchart illustrating a method for identifying anomalies in map
`
`data in accordance with one embodiment.
`
`[0011]
`
`Fig. 4 illustrates an example of a polyline before and after interpolation in
`
`accordance with one embodiment.
`
`[0012]
`
`Fig. 5 illustrates the identification of points that are present on only one of a
`
`trace route polyline and a recommended route polyline in accordance with one
`
`embodiment.
`
`[0013]
`
`Figs. 6A, 6B, and 6C illustrate example section pairs of polyline segments
`
`that are discarded in accordance with one embodiment.
`
`[0014]
`
`Fig. 7 illustrates a section pair of polyline segments that are evaluated
`
`according to one embodiment.
`
`[0015]
`
`Fig. 8 illustrates locations of potentially erroneous map data in accordance
`
`with one embodiment.
`
`
`
`[0016]
`
`Fig. 9 illustrates clustering of potentially erroneous map data locations in
`
`accordance with one embodiment.
`
`[0017]
`
`Fig. 10 is a diagram illustrating an example of a computer system upon
`
`which described embodiments may be implemented.
`
`DETAILED DESCRIPTION
`
`[0018]
`
`Fig. 1 illustrates a system 100 for identifying anomalies in map data in
`
`accordance with one embodiment. System 100 includes route guidance engine 110,
`
`map database 106, trace database 102, route guidance database 104, and map anomaly
`
`detection (MAD) engine 108.
`
`[0019]
`
`Map database 106 includes map data for a geographic region. Map data
`
`includes a road network and attributes of the network, such as how road segments are
`
`connected to one another, and the manner in which segments may be traversed. Route
`
`guidance engine 110 receives requests for route guidance, provides recommended route
`
`guidance to the requester using data from map database 106, determines the route
`
`actually taken, and stores the recommended route and actual traced route in route
`
`guidance database 104 and trace database 102, respectively. Trace data may be
`
`collected, for example, using an in-vehicle device or a mobile device such as a
`
`smartphone, adapted to collect location information on behalf of a driver who has
`
`opted-in to such data collection, or as part of an autonomous vehicle system. Route
`
`guidance database 104 includes, for a given starting location to a given destination
`
`location, recommended routing information that was provided to a requester. Thus, for
`
`a particular starting point, which we refer to generally as ”point A,” and a particular
`
`ending point, ”point B,” it is possible to query both the trace database 102 and route
`
`
`
`guidance database 104 to identify what routes were recommended for that trip based
`
`on map data from map database 106, and which routes were actually taken by vehicles
`
`traveling from point A to point B.
`
`[0020]
`
`Fig. 2 is a flowchart illustrating steps for providing recommended route
`
`guidance to a requester in accordance with one embodiment. Route guidance engine
`
`110 receives 202 a request for route guidance, for example from a driver or autonomous
`
`vehicle attempting to navigate from a first location (point A) to a second location (point
`
`B). Route guidance engine 110 uses map data from map database 106 to compute and
`
`provide 204 a recommended route to the requester. The route actually taken by the
`
`vehicle is determined 206 and stored 208 in trace database 102, along with the
`
`recommended route. In various embodiments, route guidance engine 110 associates
`
`the trace data and recommended route with a common identifier, such as a trip ID, to
`
`facilitate subsequent analysis.
`
`[0021]
`
`While many vehicles travel along the recommended navigation group,
`
`others avoid or deviate from the recommended route for at least a portion of their
`
`travel. This may be the result of a decision by the driver or autonomous vehicle
`
`unrelated to an error in the recommended route guidance, or it may in fact be the result
`
`of an error in the recommended route stemming from an error in the underlying map
`
`data from map database 106. MAD engine 108 analyzes actual trace data compared to
`
`recommended routing data to infer the existence of errors in the map data, and further
`
`explained below.
`
`[0022]
`
`Fig. 3 is a flowchart illustrating a method for identifying anomalies in map
`
`data in accordance with one embodiment. We again assume for purposes of this
`
`illustration that we are examining a route from a first point, point A, to a second point,
`
`
`
`point B, within the road network, and that existing map data for the road network
`
`including points A and B are stored in map database 106.
`
`[0023]
`
`MAD engine 108 retrieves 302 from trace database 102 trace data for a trip
`
`that took place from point A to point B. MAD engine 108 also retrieves 304 from route
`
`guidance database 104 the suggested route that was suggested for the vehicle to take
`
`from point A to point B. Each route polyline is then interpolated 306 in one
`
`embodiment so that, for each of the two polylines, its points are within some maximum
`
`distance of each other — for example, 5 meters. Fig. 4 illustrates an example of a polyline
`
`before 402 and after 404 interpolation.
`
`[0024]
`
`MAD engine 108 then identifies points that are in one polyline but not the
`
`other. That is, MAD engine 108 identifies 310 points that are on the recommended route
`
`but not on the actual (trace) route, and identifies 312 all points that are on the actual
`
`route but not on the recommended route. In one embodiment, to determine whether a
`
`point on one polyline is also on the other polyline, MAD engine 108 determines
`
`whether there is a point on the other polyline within a threshold distance (e.g., 15
`
`meters) of the point on the first polyline. If so, then the point is considered to be on both
`
`polylines, if not, the point is considered to be missing from the other polyline. Fig. 5
`
`illustrates the results of these determinations — points 502 and 504 (in red on the figures
`
`as filed) are on the actual (trace) polyline, but not on the recommended route polyline.
`
`Points 506 and 508 (in blue on the figures as filed) are on the recommended route
`
`polyline, but not on the trace polyline.
`
`[0025]
`
`As can be seen in Fig. 5, there are now regions of the road network at
`
`various areas between A and B where the recommended route is not part of the trace,
`
`and the trace is not part of the recommended route. MAD engine 108 creates 314 section
`
`
`
`pairs for subsequent processing by identifying these regions. In one embodiment, first
`
`MAD engine 108 identifies a section as a set of consecutive points on a route which are
`
`not part of the other route. Sections from the two routes are paired with each other to
`
`form a section pair if the two sections are within a threshold distance of each other, as
`
`may be selected by the implementer. For example, points 502 and 506 are pairs within
`
`a region, and points 504 and 508 are pairs within a separate region.
`
`[0026]
`
`MAD engine 108 then checks each section pair to determine whether to
`
`discard 316 the pair or consider evaluating it. In one embodiment, pairs are discarded
`
`unless at least one of the pair is of at least a first threshold amount in length, and the
`
`pair have lengths that differ by a second threshold amount.
`
`[0027]
`
`For example, referring to Fig. 6A, segment 602, derived from the trace
`
`polyline, and segment 604, from the recommended route polyline, cover too short a
`
`distance to be considered significant — the difference in their location could easily be
`
`explained by noise in the GPS signal, for example. In one embodiment, MAD engine
`
`108 discards segments if they are shorter than 200 meters in length.
`
`[0028]
`
`In Fig. 6B, the sections are both too long to be meaningfully analyzed — for
`
`example, a driver may simply have chosen to go via a different route for a reason not
`
`related to the accuracy of the recommended route. In one embodiment, segments
`
`longer than 2 kilometers are discarded by MAD engine 108. And in Fig. 6C, while the
`
`segments are of appropriate length, their lengths are too similar to infer significance —
`
`perhaps the driver used local knowledge to drive a different route of similar length
`
`even though the recommended route would also have sufficed. Thus, in one
`
`embodiment, MAD engine 108 discards segments unless the segment from one route is
`
`at least 40% greater in length than the other segment. Finally, Fig. 7 illustrates a section
`
`
`
`pair that is suitable for evaluation — the routes are of sufficient length, but not of the
`
`same length.
`
`[0029]
`
`MAD engine 108 repeats a18 this process for each trip traced and
`
`recommended from points A to B over some period of interest — for example, one day.
`
`In one embodiment, the process is then repeated across all trips from all origin to all
`
`destination points within the map region of interest, e.g., a city. In this example, then,
`
`all trips taken over the course of a particular day in a particular city are then be part of
`
`the aggregated data set.
`
`[0030]
`
`In one embodiment, points are represented as latitude/longitude pairs. To
`
`allow for measurement error, in one embodiment locations are rounded to four decimal
`
`places before aggregation, meaning that two locations that differ only in the fifth
`
`decimal place of latitude or longitude will be considered the same point for purposes of
`
`analysis.
`
`[0031]
`
`Following the aggregation steps, MAD engine 108 can identify points in
`
`map database 106 that are the most frequently occurring in the aggregated data — that
`
`is, the points where recommended routes and actual trace data are most frequently
`
`inconsistent. Fig. 8 illustrates an example illustration showing points in the city of New
`
`Delhi, India, where inconsistencies exist. MAD engine 108 in some embodiments
`
`clusters points from the aggregated list based on trips which affect them, as illustrated
`
`in Fig. 9. If MAD engine 108 determines that two points are frequently impacted by
`
`common trips—that is, a point P frequently occurs in trips from A to B, and another
`
`point Q frequently occurs in trips from A to B—then they are included in the same
`
`cluster. In one embodiment, MAD engine 108 uses a Jaccard similarity to measure
`
`distance between points.
`
`
`
`[0032]
`
`In various embodiments, MAD engine 108 analyzes the clustered results and
`
`provides a likely error type. In some embodiments, MAD engine 108 automatically
`
`updates data in map database 106 to correct the determined error.
`
`[0033]
`
`Examples of errors that can be automatically detected by MAD engine 108
`
`include missing road segments, extraneous road segments, wrongly connected road
`
`segments, missing turn restrictions, incorrect turn restrictions, missing or incorrect
`
`directionality, wrong road connections across lanes, and wrong geometry of roads.
`
`[0034]
`
`FIG. 10 is a block diagram illustrating components of an example machine
`
`for reading and executing instructions from a machine-readable medium. Specifically,
`
`FIG. B shows a diagrammatic representation of system 100 in the example form of a
`
`computer system 1000. The computer system 1000 can be used to execute instructions
`
`1024 (e. g., program code or software) for causing the machine to perform any one or
`
`more of the methodologies (or processes) described herein. In alternative
`
`embodiments, the machine operates as a standalone device or a connected (e. g.,
`
`networked) device that connects to other machines. In a networked deployment, the
`
`machine may operate in the capacity of a server machine or a client machine in a
`
`server-client system environment 100, or as a peer machine in a peer-to-peer (or
`
`distributed) system environment 100.
`
`[0035]
`
`The machine may be a server computer, a client computer, a personal
`
`computer (PC), a tablet PC, a set-top box (STB), a smartphone, an internet of things
`
`(IoT) appliance, a network router, switch or bridge, or any machine capable of
`
`executing instructions 1024 (sequential or otherwise) that specify actions to be taken by
`
`that machine. Further, while only a single machine is illustrated, the term ”machine”
`
`shall also be taken to include any collection of machines that individually or jointly
`
`
`
`execute instructions 1024 to perform any one or more of the methodologies discussed
`
`herein.
`
`[0036]
`
`The example computer system 1000 includes one or more processing units
`
`(generally processor 1002). The processor 1002 is, for example, a central processing unit
`
`(CPU), a graphics processing unit (GPU), a digital signal processor (DSP), a controller, a
`
`state machine, one or more application specific integrated circuits (ASle), one or more
`
`radio-frequency integrated circuits (RFle), or any combination of these. The computer
`
`system 1000 also includes a main memory 1004. The computer system may include a
`
`storage unit 1016. The processor 1002, memory 1004, and the storage unit 1016
`
`communicate via a bus 1008.
`
`[0037]
`
`In addition, the computer system 1000 can include a static memory 1006, a
`
`graphics display 1010 (e.g., to drive a plasma display panel (PDP), a liquid crystal
`
`display (LCD), or a projector). The computer system 1000 may also include
`
`alphanumeric input device 1012 (e.g., a keyboard), a cursor control device 1014 (e. g., a
`
`mouse, a trackball, a joystick, a motion sensor, or other pointing instrument), a signal
`
`generation device 1018 (e. g., a speaker), and a network interface device 1020, which also
`
`are configured to communicate via the bus 1008.
`
`[0038]
`
`The storage unit 1016 includes a machine-readable medium 1022 on which is
`
`stored instructions 1024 (e. g., software) embodying any one or more of the
`
`methodologies or functions described herein. For example, the instructions 1024 may
`
`include the functionalities of modules of the system 130 described in FIG. 1. The
`
`instructions 1024 may also reside, completely or at least partially, within the main
`
`memory 1004 or within the processor 1002 (e.g., within a processor’s cache memory)
`
`during execution thereof by the computer system 1000, the main memory 1004 and the
`
`10
`
`
`
`processor 1002 also constituting machine-readable media. The instructions 1024 may be
`
`transmitted or received over a network 1026 (e. g., network 120) via the network
`
`interface device 1020.
`
`[0039]
`
`While machine-readable medium 1022 is shown in an example embodiment
`
`to be a single medium, the term ”machine-readable medium" should be taken to
`
`include a single medium or multiple media (e. g., a centralized or distributed database,
`
`or associated caches and servers) able to store the instructions 1024. The term
`
`”machine-readable medium” shall also be taken to include any medium that is capable
`
`of storing instructions 1024 for execution by the machine and that cause the machine to
`
`perform any one or more of the methodologies disclosed herein. The term ”machine-
`
`readable medium" includes, but not be limited to, data repositories in the form of solid-
`
`state memories, optical media, and magnetic media.
`
`[0040]
`
`In addition to the embodiments specifically described above, those of skill in
`
`the art will appreciate that the invention may additionally be practiced in other
`
`embodiments.
`
`[0041]
`
`Within this written description, the particular naming of the components,
`
`capitalization of terms, the attributes, data structures, or any other programming or
`
`structural aspect is not mandatory or significant unless otherwise noted, and the
`
`mechanisms that implement the described invention or its features may have different
`
`names, formats, or protocols. Further, the system may be implemented via a
`
`combination of hardware and software, as described, or entirely in hardware elements.
`
`Also, the particular division of functionality between the various system components
`
`described here is not mandatory; functions performed by a single module or system
`
`component may instead be performed by multiple components, and functions
`
`11
`
`
`
`performed by multiple components may instead be performed by a single component.
`
`Likewise, the order in which method steps are performed is not mandatory unless
`
`otherwise noted or logically required.
`
`It should be noted that the process steps and
`
`instructions of the present invention could be embodied in software, firmware or
`
`hardware, and when embodied in software, could be downloaded to reside on and be
`
`operated from different platforms used by real time network operating systems.
`
`[0042]
`
`Algorithmic descriptions and representations included in this description
`
`are understood to be implemented by computer programs. Furthermore, it has also
`
`proven convenient at times, to refer to these arrangements of operations as modules or
`
`code devices, without loss of generality.
`
`[0043]
`
`Unless otherwise indicated, discussions utilizing terms such as ”selecting”
`
`or ”computing” or ”determining” or the like refer to the action and processes of a
`
`computer system, or similar electronic computing device, that manipulates and
`
`transforms data represented as physical (electronic) quantities within the computer
`
`system memories or registers or other such information storage, transmission or
`
`display devices.
`
`[0044]
`
`The present invention also relates to an apparatus for performing the
`
`operations herein. This apparatus may be specially constructed for the required
`
`purposes, or it may comprise a general-purpose computer selectively activated or
`
`reconfigured by a computer program stored in the computer. Such a computer
`
`program may be stored in a non-transitory computer readable storage medium, such
`
`as, but is not limited to, any type of disk including floppy disks, optical disks, DVDs,
`
`CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access
`
`memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific
`
`12
`
`
`
`integrated circuits (ASle), or any type of media suitable for storing electronic
`
`instructions, and each coupled to a computer system bus. Furthermore, the computers
`
`referred to in the specification may include a single processor or may be architectures
`
`employing multiple processor designs for increased computing capability.
`
`[0045]
`
`The algorithms and displays presented are not inherently related to any
`
`particular computer or other apparatus. Various general-purpose systems may also be
`
`used with programs in accordance with the teachings above, or it may prove
`
`convenient to construct more specialized apparatus to perform the required method
`
`steps. The required structure for a variety of these systems will appear from the
`
`description above. In addition, a variety of programming languages may be used to
`
`implement the teachings above.
`
`[0046]
`
`Finally, it should be noted that the language used in the specification Has
`
`Bean principally selected for readability and instructional purposes, and may not have
`
`been selected to delineate or circumscribe the inventive subject matter. Accordingly, the
`
`disclosure of the present invention is intended to be illustrative, but not limiting, of the
`
`scope of the invention.
`
`[0047]
`
`We claim:
`
`13
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
