USING PROBE DATA

COPYRIGHT NOTICE

[0001] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION Field of the Invention

[0002] This invention relates to digital maps of the type for displaying road or pathway information, and more specifically, toward a system and method for verifying map update reports from an unverified reporter. Related Art

[0003] In nearly all developed and developing countries, roadways are becoming more congested and as a result travel times are increasing. The need for accurate and timely traffic information and travel directions continues to grow. Such need has encouraged the rise of personal navigation systems and devices which utilize and display digital maps combined with accurate positioning data. Commuters seeking navigation assistance have embraced this emerging technology, trying to travel the most convenient path, and minimize transportation distance, time, and costs. The effectiveness of such navigation systems is inherently dependent upon the accuracy and completeness of its digital map data.

[0004] Current navigation systems and devices include Personal Navigation

Systems (PNAV), such as dedicated handheld navigation systems, Personal Digital Assistance (PDAs), mobile telephones provided with a navigation module, as well as in-car navigation systems and devices. Typically, the navigation device matches the user's current position on a particular real-life road segment to a digital road segment corresponding to the real-life road segment. The navigation device includes a screen displaying the digital map and indicating the user's position on the digital map. Associated features of the digital road segments are stored in the memory of the PNAV device and may also be displayed for the benefit of the driver. The associated features may include a variety of information regarding the digital road segments or other areas of the digital map, such as traffic directions, road attributes, road geometry, junctions, posted speed limits, taxi stops, point of interest information, another other elements or information. For example, the PNAV device may display the traffic directions of the road segments, such as open in both directions, open only in a forward direction, or blocked, so the driver can choose the open road segments and avoid the blocked roads.

[0005] The associated features, such as openings and road blockages, may be considered by the PNAV device when providing travel directions. When the user enters a desired destination, the PNAV device considers the associated features of the roads between the user's current position and the desired destination to determine the most efficient travel route. Thus, the digital map is more valuable when its data and information regarding the digital road segments and associated features are up-to-date. .

[0006] Map providers strive to keep the digital map data and information accurate and complete. As alluded to above, the location of road blockages, openings, road geometry, and other associated features impact the travel time and distance, and are necessary to provide the most efficient travel directions. The map provider manually identifies the associated features and identifies discrepancies between the associated features of the digital road segments and real-life road segments by surveying the real-life road segments. The map provider then manually updates the database so the digital map provides complete and accurate information about the road segments and associated features.

[0007] A user of the PNAV device may also recognize a discrepancy between the digital road segment and real-life road segment, and may report the discrepancy to the map provider. Such discrepancies are typically reported by submitting a map update report. The map update may be available on the map provider's website. Alternatively, the map update report may be created on the user's navigation device itself, and then sent to the map provider using a sync application. The map update reports may be submitted by any member of the public via the website. Therefore, the reports must be verified by the map provider before the digital map is updated to coincide with the reported discrepancy. Typically, the map provider analyzes the map update report by performing a field survey or manual investigation of the real-life road segment corresponding to the digital real segment in question. If the database editor manually confirms the truth of the map update report, then the digital map is manually updated by editing the map database. Unfortunately, this system and method of manually verifying the map update reports and manually updating the digital maps is very time consuming, error prone, and costly.

SUMMARY OF THE INVENTION

[0008] The invention provides a method for verifying a reported discrepancy in a digital map from an unverified reporter. The method includes the steps of providing a digital map having a plurality of digital road segments with a plurality of associated features; receiving a reported discrepancy for one of the associated features of one of the digital road segments from an unverified reporter; and collecting probe data from a plurality of probes traveling on or around a real-life road segment corresponding to the digital road segment. The method also includes comparing the reported discrepancy to the probe data to verify the reported discrepancy. [0009] This invention also provides a system for verifying a reported discrepancy in a digital map from an unverified reporter. The system includes a digital map having a plurality of digital road segments with a plurality of associated features, and a reported discrepancy for one of the associated features of one of the digital road segments received from the unverified reporter. The system also includes a plurality of probes including probe data traveling on or around a real-life road segment corresponding to the digital road segment, and a verification engine comparing the reported discrepancy to the probe data to determine whether the probe data confirms the reported discrepancy.

[0010] The system and method provide a quick, reliable, and cost effective way to verify map update reports. Comparing the reported discrepancy to the probe data is much quicker than the manual verification and other methods of the prior art. The system and method reduce labor costs and are less error prone than the prior art verification processes. Thus, the digital map is more accurate, up-to-date, and in line with the user's experience of driving with a navigation device in reality.

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] Other advantages of the present invention will be readily appreciated, as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings wherein:

[0012] Figure 1 is an enlarged exemplary view of a compact, portable navigation system according to an embodiment of the invention including a display screen for presenting a digital map and information to a user;

[0013] Figure 2 is a flow chart according to an embodiment of the invention illustrating method steps;

[0014] Figure 3 is a first example of employing probe data in validation logic wherein the reported discrepancy is a traffic direction; [0015] Figure 4 is a second example of employing probe data in validation logic wherein the reported discrepancy is a traffic direction;

[0016] Figure 5 is a third example of employing probe data in validation logic wherein the reported discrepancy is a traffic direction; and

[0017] Figure 6 is a fourth example of employing probe data in validation logic wherein the reported discrepancy is a traffic direction.

DETAILED DESCRIPTION OF THE INVENTION

[0018] Referring to the Figures, a system and method for verifying a reported discrepancy in a digital map from an unverified reported is generally shown. The system includes a digital map, a plurality of probes including probe data, and a verification engine for comparing the reported discrepancy to the probe data. The method includes receiving the reported discrepancy, collecting the probe data, and comparing the reported discrepancy to the probe data. The method also includes updating the digital map to coincide with the reported discrepancy only if the probe data confirms the reported discrepancy.

[0019] An exemplary digital map of the system is shown in Figure 1. The digital map of Figure 1 is included in a compact, portable vehicle navigation device. Alternatively, the digital map may be included in a handheld device, PDA, mobile phone with navigation software, or another navigation devices. The digital map includes a plurality of digital road segments displayed on a screen. Each digital road segment corresponds to, or is intended by the map provider to correspond to, a real- life road segment. The digital road segments may comprise an entire road, or portion of a road extending between two nodes, two junctions, a node and a junction, or between other parameters. The road segments are displayed on the screen through a bird's eye view, a junction view, or other another view.

[0020] In addition to the digital map, the navigation device typically includes a GPS receiver and a probe. As the navigation device travels along the real-life road segments, the probe collects probe data, such as travel direction, speed information, and other data related to the traveling probe. The probe may transmit or otherwise report its probe data to the map provider at certain time segments. The map provider collects the probe data from the probes and uses the probe data to verify the reported discrepancies, which will be discussed further.

[0021] The map provider strives to maintain updated and accurate probe data for each digital road segment of the digital map. The probe data of each digital road segment typically includes a count for each probe traveling along the real-life road segment corresponding to the digital road segment. The probe data of each road segment is typically collected for numerous time segments, such as on a quarterly basis. The probe data and other digital map information is typically stored and updated in a database maintained by the map provider. The map provider typically employs a satellite, wireless communication, software programs, and other devices known in the art to remotely and passively collect the probe data. The probe data is typically collected from probes of navigation devices, but can be collected from other types of probes.

[0022] Each digital road segment of the digital map has a plurality of associated features. The associated features correspond to, or should correspond to, associated features of the corresponding real-life road segment. The associated features typically include traffic directions, road geometries, and road attributes. The associated features may also include points of interest information, altitude, traffic directions, junctions, posted speed limits, taxi stops, and other elements, features, or information regarding the digital road segment. The traffic directions include open only in a forward direction, open only in a reverse direction, open in both a forward direction and a reverse direction, and a road blockage in all directions. The traffic directions can include other values. The road geometries include a straight path, a curved path, a roundabout, and other geometries. Statistics representing the associated feature of the road segments are also stored in the database, along with the probe data, and are maintained and updated by the map provider. For example, the statistics of one road segment may indicate the road segment is open in both directions, includes a roundabout, and has a speed limit of 40 mph. The associated features of each digital road segment may be manually surveyed and added to the data base. Alternatively, the patterns or trends in the probe data may allow the map provider to determine the associated features of the road segments.

[0023] The associated features of the road segments are continuously being updated and errors or discrepancies between the associated features of the digital road segments and the associated features of real-life road segments are continuously being updated by providers of the digital map. The map provider typically employs a satellite, wireless communication, software programs, and other devices known in the art to remotely provide and update the digital maps of navigation devices.

[0024] At times, a user of the digital map traveling along the real-life road segments recognizes a discrepancy between the associated feature of one of the digital road segments and the real- life road segment, before the map provider is aware of the discrepancy. For example, the digital map may indicate one of the digital road segments is open in a forward direction and a reverse direction, when the corresponding real-life road segment is actually blocked in both directions. In this case, the user informs the map provider of the discrepancy.

[0025] The user typically informs the provider by submitting a map update report describing the reported discrepancy. The map update report may be created on the user's navigation device itself, and then sent to the map provider using a sync application. Map update report forms are also accessible to the public on a website maintained by the map provider and may be submitted by any member of the public. Thus, the map provider receives the reported discrepancy from an unverified reporter, and must verify the reported discrepancy, i.e. check whether the reported discrepancy is true and accurately reflects the associated feature of the real-life road segment. The map provider proceeds to update the digital map to coincide with the reported discrepancy only if the reported discrepancy is confirmed as accurate.

[0026] Rather than manually verifying the reported discrepancy, the map provider employs the method of the subject invention. As illustrated in the flow diagram of Figure 2, upon receiving the reported discrepancy from the unverified reporter, the method includes automatically collecting probe data from the probes traveling on or around the real- life road segment. Next, the method includes automatically comparing the reported discrepancy to the probe data to verify the reported discrepancy. If the probe data confirms the reported discrepancy, i.e. establishes the reported discrepancy as true, then the method includes automatically updating the digital map to coincide with the reported discrepancy. The system typically includes a verification engine with a software program automatically comparing the reported discrepancy to the probe data and updating the digital map if the reported discrepancy is confirmed. This automated method eliminates the need for a map provider to manually investigate and manually confirm the reported discrepancy, which saves a significant amount of time, money, and labor. Thus, the digital map is more accurate, up- to-date, and in line with the user's experience of driving with a navigation device in reality.

[0027] The step of comparing the reported discrepancy to the probe data may vary, depending on the associated feature and type of reported discrepancy. The type of probe data collected and employed also varies, depending on the associated feature and type of reported discrepancy. The probe data collected typically includes a count for each probe traveling on the real-life road segment corresponding to the digital road segment in question, at a particular time segment. To improve accuracy and reliability of the method, a minimum count threshold is defined, and the digital map is only updated if the total number of collected counts is at least the minimum count threshold.

[0028] The method typically includes employing the probe data in validation logic to yield a probe data value, which is used to verify the reported discrepancy. The method also includes defining at least one discrepancy threshold value, which is compared to the probe data value and used to confirm the reported discrepancy. A plurality of discrepancy thresholds may be defined to confirm various associated features. As shown in Figure 2, comparison of the probe data value to the discrepancy threshold typically generates a statement on the validity of the reported discrepancy. In one embodiment, if the probe data value is at least the discrepancy threshold value, then the statement confirms the reported discrepancy. However, if the probe data value were less than the discrepancy threshold, then the statement would reject the reported discrepancy. The statement may also indicate the probe data value is in a gray or unreliable zone and cannot confirm the reported discrepancy.

[0029] As alluded to above, the steps vary depending on whether the associated feature is traffic direction, road geometry, or another associated feature. When the associated feature is traffic direction, the steps also vary depending on the type of reported discrepancy. In a first example, as shown in Figure 3, the unverified reporter reports the traffic direction (associated feature) of a real-life road segment is open only in a forward direction (reported discrepancy), but the digital map indicates the traffic direction of the road segment is open in both the forward direction and a reverse direction. To determine the validity of the reported discrepancy of the first example, which is open only in a forward direction, the probe data collected includes a count for each probe traveling in the forward direction on the real-life road segment, and a count for each probe traveling in the reverse direction on the real-life road segment. The probe data is collected at four different time segments, on a quarterly basis, as shown in Figure 3. The probe data is employed in validation logic to yield a probe data value. The validation logic includes dividing the number of counts in the forward direction by the sum of the counts in the forward direction and the counts in the reverse direction to yield the probe data value of about 99.09%. One of the discrepancy threshold values is defined as at least 90%, indicating open only in the forward direction. In this example, the probe data value is greater than the discrepancy threshold, so the method generates a statement confirming the reported discrepancy, i.e. stating the reported discrepancy is true. The digital map is automatically updated to coincide with the confirmed reported discrepancy.

[0030] In a second example, as shown in Figure 4, the unverified reporter may report the traffic direction of a real- life road segment is open only in a reverse, but the digital road segment of the digital map indicates the traffic direction is open in both the forward direction and a reverse direction. To determine the validity of the reported discrepancy, which is open only in the reverse direction, the probe data collected includes a count for each probe traveling in the forward direction on the real-life road segment, and a count for each probe traveling in the reverse direction on the real-life road segment. The probe data is collected at four different time segments, as shown in Figure 4. The probe data is employed in validation logic to yield a probe data value. The validation logic includes dividing the number of counts in the reverse direction by the sum of the counts in the forward direction and the counts in the reverse direction to yield the probe data value of about 99.09%. One of the discrepancy threshold values is defined as at least 90%, indicating open only in the reverse direction. In this example, the probe data value is greater than the discrepancy threshold, so the method generates a statement confirming the reported discrepancy, i.e. stating the reported discrepancy is true. The digital map is automatically updated to coincide with the reported discrepancy. [0031] In yet another embodiment, as shown in Figure 5, the unverified reporter may report the traffic direction of a real-life road segment is open in a forward direction and open in a reverse direction, when the digital road segment of the digital map indicates the traffic direction is blocked. To determine the validity of the reported discrepancy, which is open in a forward direction and open in a reverse direction, the probe data collected includes a count for each probe traveling in the forward direction on the real- life road segment, and a count for each probe traveling in the reverse direction on the real-life road segment. The probe data is collected at four different time segments, as shown in Figure 5. The probe data is employed in validation logic to yield a probe data value. The validation logic includes dividing the number of counts in the forward direction by the sum of the counts in the forward direction and the counts in the reverse direction to yield the probe data value of about 50.72%. One of the discrepancy threshold values is defined as less than 80%, indicating open in both the forward direction and the reverse direction. In this example, the probe data value is less than the discrepancy threshold, so the method generates a statement confirming the reported discrepancy, i.e. stating the reported discrepancy is true. The digital map is automatically to coincide with the confirmed reported discrepancy.

[0032] In a fourth embodiment, as shown in Figure 6, the unverified reporter may report the traffic direction (associated feature) of a certain real-life road segment is a road blockage in both directions (reported discrepancy), when the digital road segment of the digital map indicates the traffic direction of the road segment is open in both directions. To determine the validity of the reported discrepancy, which is the road blockage in both directions, the probe data is collected for the allegedly blocked real-life road segment, and also for all the real-life road segments adjacent the allegedly blocked road segment. Further, the probe data collected includes a count for each probe traveling on the allegedly blocked real-life road segment, and a count for each probe traveling on one of the road segments adjacent the allegedly blocked road segment. The adjacent real- life road segments are typically at the beginning and end of a street, before or after a driver encounters the blockage. The probe data is collected at four different time segments, as shown in Figure 6. The counts of the allegedly blocked road segment are collected for each time segment to provide a probe data value for each time segment. Also, the counts of all the adjacent real-life road segments, on both sides of the allegedly closed road segment, at one of the time segments, are added together to provide another probe data value for each time segment. The discrepancy threshold values are defined as at least 20 for the sum of the adjacent road segments at each time segment, and less than 5 for the allegedly blocked road segment at each time segment, which indicates a road blockage of the real- life road segment in both directions. In other words, if the sum of the counts of the adjacent road segments is at least 20; and the counts of the allegedly blocked road segment is less than 5, for each time segment, then the discrepancy report is confirmed. In this example, the probe data value for the adjacent road segments is greater than 20 at each time segment, and the other probe data value for the allegedly blocked road segment is less than 5 for each time segment, so the method generates a statement confirming the reported discrepancy, i.e. stating the reported discrepancy is true. The digital map is automatically updated to coincide with the confirmed reported discrepancy.

[0033] In a fifth example, the unverified reporter may report the road geometry (associated feature) of a real-life road segment is a roundabout (reported discrepancy), when the digital road segment of the digital map indicates the road geometry is straight. To determine the validity of the reported discrepancy, which is a roundabout in the road segment, the probe data collected includes counts and a corresponding coordinate for each probe traveling on the real-life road segment. The probe data is collected at several different time segments. Comparing the reported discrepancy to the probe data includes determining whether the coordinates of the counts present a circle pattern. If so, the method generates a statement confirming the reported discrepancy, and the digital map is automatically updated to include the roundabout.

[0034] As shown in Figure 2, in addition to establishing a minimum count threshold, the method of verifying the reported discrepancy can include additional steps to improve accuracy and reliability of the method. Typically, a plurality of scope requirements are set by the map provider, and updating the digital map to coincide with the reported discrepancy occurs only if the reported discrepancy matches the scope requirements.

[0035] A first scope requirement includes probe data. If no probe data for the digital road segments corresponding to the reported discrepancy exists in the database, then the method will not proceed to compare the probe data to the reported discrepancy, and the map will not be updated.

[0036] Another scope requirement is a geometry match. Thus, the method includes verifying the digital road segment corresponding to the reported discrepancy matches a real-life road segment, stored in the map provider's database. A third scope requirement includes statistics representing the associated feature of the digital road segment. The method requires confirming the database includes statistics representing the associated feature of the digital road segment. For example, if the unverified reporter submits a reported discrepancy for a traffic direction of a particular road segment, the method includes confirming statistics representing a traffic direction of the particular road segment exists in the database. If the database lacks statistics, then the digital map will not be updated.

[0037] Obviously, many modifications and variations of the present invention are possible in light of the above teachings and may be practiced otherwise than as specifically described while within the scope of the appended claims.