Resolving discrepancies between location information and route data on a navigation device

[0001] The present invention relates to navigation systems, and more particularly, to a navigation device and method for resolving discrepancies between location information and route data on the navigation device.

[0002] In recent years, electronic location devices, especially global positioning systems (GPSs), have become quite commonplace, and have been proven both useful and popular in many different applications or uses. Due to their ever-increasing deployment, most automobile drivers and passengers are now familiar with some type of navigation device that includes some type of positioning system. A navigation device is typically embodied as an integrated unit that provides up-to-the-minute routing information relative to the device's current position, including which roads to follow, where and when to turn, which lanes must be used, and the like.

[0003] FIG. 1 is a pictorial diagram illustrating an exemplary, integrated navigation device 100, such as those commonly found in the prior art. The exemplary navigation device 100 includes a display subsystem 102, which, in this example, is illustrating a map of the immediate surroundings of the navigation device, as well as route information for a user. As is typical with many navigation devices, an icon 104 illustrates the current location of the navigation device 100 (and presumably the vehicle in which it is located), as well as a defined route 106 a driver is to follow to arrive at a specified destination 108.

[0004] As those skilled in the art will appreciate, an exemplary navigation device 100 also frequently includes a number of user inputs, such as control buttons 110, and/or a keypad 112 that includes alpha-numeric keys for text and/or data entry. Of course, those skilled in the art will appreciate that navigation devices come in a variety of configurations with numerous options. The present illustration is meant only as an example, and should not be construed as limiting upon the present invention.

[0005] While most location devices, such as a GPS or wireless telephone, could be designed to be very accurate in determining the location of the device, current location devices are known to include some degree of inaccuracy. For example, most GPS owners know that their device will report a geographic position (in terms of latitude and longitude) for the device that is only accurate within some tolerance. In fact, for most GPS systems, the reported position is accurate within a radius of 10 to 100 meters of the actual position. While in many cases this inaccuracy is unimportant, when the location device is part of a navigation system, and the reported position is 10 meters “off” the actual position, this may cause the navigation system to illustrate a corresponding vehicle's position as traveling down the middle of a busy office lobby, rather than on a street in front of the building.

[0006] FIG. 2 is a pictorial diagram illustrating an exemplary map 200 displayed by a navigation system, such as navigation device 100 of FIG. 1, and further illustrating the problems associated with the inaccuracies of location devices. In particular, the navigation system, in the course of providing up-to-date navigation information to the driver of an automobile, will typically periodically obtain the current position from its location subsystem (such as a GPS unit). Furthermore, in addition to the inaccuracies of the location subsystem, due to the inaccuracies of the navigation system's data, the exact location 202 will fall somewhere off of an established road. For instance, assume that reported location 202 is the most recent position obtained by an integrated navigation device. As can be seen, location 202 does not correspond to any established road. Instead, there are five different road segments, including road segments 204, 206, 208, 210, and 212, that may fall within the understood margin of error. Clearly, this presents a problem for the navigation system, which may ultimately report to the user that the vehicle is traveling down a road, or through a building, that it is not.

[0007] Of course, the map, or route data, that the navigation system uses may also be in error. However, no matter what the error, it is very disconcerting for the navigation system to report that the driver is navigating the vehicle through a lake, down the wrong way of a one-way street, or in the middle of an office building, when in fact, it is not true. Accordingly, what is needed is a navigation system, and a method for implementation on a navigation system, that efficiently resolves discrepancies between a location position as reported by a location service, and the route data relied upon by the navigation system. The present invention addresses this and other issues found in the prior art.

[0008] According to aspects of the present invention, a navigation system for resolving discrepancies between a reported location and route data is presented. The navigation system includes a processor and a memory. The navigation system also includes a location subsystem. The location subsystem provides a reported location to the navigation system. The navigation system is configured to resolve discrepancies between the reported location and route data into a route location on a road identified in the route data, by, first, identifying prospective roads as those roads in the route data that have a road segment within a radius of the reported location. For each identified prospective road, the navigation system generates a score for the prospective road in relation to the reported location. The navigation system is configured to then select the prospective road with the best score, and identify a position on the selected prospective road as the resolved route location.

[0009] In accordance with additional aspects of the present invention, a navigation system for resolving discrepancies between a reported location and route data is presented. The navigation system includes a processor and a memory. The navigation system also includes a location subsystem. The location subsystem provides a reported location to the navigation system. The navigation system is configured to resolve discrepancies between the reported location and route data into a route location on a road identified in the route data, by, first, identifying prospective roads as those roads in the route data that have a road segment with a radius of the reported location. For each identified prospective road, the navigation system is configured to generate a plurality of scores for the prospective road in relation to the reported location, normalize each of the plurality of scores into a common range of values, and determine an overall score for the prospective road according to the commutation of the normalized scores. After determining overall scores for each of the prospective roads, the navigation system is further configured to select the prospective road with the best overall score, and identify a position on the selected prospective road as the route location.

[0010] In accordance with yet further aspects of the present invention, a method, executable by a navigation system, for resolving discrepancies between a reported location and route data, is presented. A reported location is obtained from a location subsystem. Route data identifying a plurality of roads is also obtained. Prospective roads in the route data that have a road segment within a radius of the reported location are identified. For each identified prospective road, a plurality of scores for the prospective road in relation to the reported location are generated. Each of the plurality of scores are normalized into a common range of values. An overall score for the prospective road according to the cumulation of the normalized scores is determined. After determining an overall score for each prospective road, the prospective road with the best overall score is selected, and a position on the selected prospective road is identified as the resolved route location.

[0019] As indicated above, the present invention is directed at a navigation system that provides efficient, improved resolution of discrepancies between location information from a location service, such as a GPS, and route data. As indicated above, in order to resolve the discrepancies between a reported location and route data, a navigation system is adapted according aspects of the present invention, such that for each reported location, the navigation system generates a variety of individual scores for each prospective road, collects the individual scores, and selects the prospective road with the best score as the road on which the vehicle is located, referred to hereafter as the “snap-to” road. It should be appreciated that while the term “road” is used throughout this description, it is used as a generic term for a traverseable route, and used for simplicity purposes. In fact, the term “road” is intended to include almost any type of traverseable route including, but not limited to, streets, paths, trails, walkways, rail lines, subways, and the like. Additionally, while the term “vehicle” is used, and often used interchangeably with the term “automobile,” it is also for illustration and simplicity in description purposes. Vehicle may include, but is certainly not limited to, automobile, motorcycle, boat, bicycle, and the like.

[0020] FIG. 3 is a block diagram illustrating exemplary components of a navigation system 300 suitably configured for implementing aspects of the present invention. The exemplary navigation system 300 includes a processor 302 that executes code 314 for resolving discrepancies between a reported location and route data 312. The navigation system 300 also includes a dynamic memory 304, as well as a more permanent storage 310. As those skilled in the art will appreciate, the dynamic memory 304 is typically used by the processor 302 as short term memory, frequently for temporary variable and data storage, such as prospective road scores (discussed below), but may also be used to store the code 314 for resolving discrepancies between a reported location and route data 312. Additionally, the storage 310 may be non-volatile memory, disk storage, or remote storage. Typically, the code 314 is stored in the storage 310, but, in alternative embodiments, may reside in read-only memory (not shown). Still further, as those skilled in the art will appreciate, while they are illustrated as logically separate in FIG. 3, in an actual embodiment the dynamic memory 304 and storage 310 may be the same memory/storage structure.

[0021] The exemplary navigation system 300 also includes a location subsystem 306. The location subsystem may be a GPS unit, or alternatively, some other location determination service or device. In fact, the location subsystem 306 may actually be a communication link with an external location determination service that periodically provides reported locations to the navigation system 300.

[0022] The exemplary navigation system 300 also typically includes a presentation subsystem 308. As shown in FIG. 1, a presentation subsystem is frequently a graphics display system that can illustrate maps or routes, as well as text. However, the present invention is not limited to a graphics display system. For example, the presentation subsystem 308 may be a communication channel that provides navigation information to an external device or system.

[0023] As already indicated above, the storage 310 will typically include route data 312, for determining and displaying a present location, and for determining a navigation information for navigating a potential path between an origin and destination. However, in an alternative embodiment, the navigation system 300 may obtain route data 312 from an external source, and store that data temporarily in the dynamic memory 304. For purposes of the remaining discussion, route data 312 comprises, but is not limited to, information regarding roads (or, more particularly, road segments); locations, directions and geometries of the roads; inter-connections between the roads; and attributes describing road segments including, but not limited to, speed limit, turn restrictions, type of road, and the like.

[0024] While various components of an exemplary navigation system have been presented and described, it should be appreciated that the above-identified components of the exemplary navigation system are logical components, not necessarily actual components, and may be divided or combined into any number of actual components. Furthermore, a typical navigation system may include other components not described herein. Accordingly, the above-described exemplary navigation system 300 should be viewed as illustrative only, and not construed as limiting upon the present invention.

[0025] As indicated above, the navigation system 300 executes code 314 that enables it to resolve the discrepancies between a reported location and the route data 312. FIGS. 4A-4C are a flow diagram illustrating an exemplary routine 400, suitable for implementation by a navigation system 300, for resolving discrepancies between a reported location and route data 312 as it functions to provide up-to-date navigation information to a user or external system. As a preliminary matter, those skilled in the art will appreciate that a typical navigation system 300, especially an integrated unit such as navigation device 100 (FIG. 1), is frequently designed to operate in a continual manner, i.e., once initialized and operating, the navigation system continually provides navigation or position information to the driver or user of the system. Accordingly, exemplary routine 400 includes a begin terminal, but does not have an end terminal. Instead, the routine 400 is shown as continually operating, presumably until the navigation system 300 is powered down.

[0026] Beginning at block 402, the navigation system 300 acquires a reported position/location from a location source, such as the location subsystem 306. Typically, this reported position will be given in terms of a coordinate comprising a latitude and longitude value. As indicated above, other information, such as speed limits, road heading, elevation, and the like may also be retrieved at that time. At block 404, the exemplary routine 400 determines/identifies all prospective roads that lie within a predetermined radius of the reported position. For example, FIG. 5 is a pictorial diagram illustrating the exemplary map 102 shown in FIG. 1, and further illustrating the selection of prospective roads within a pre-determined radius of the reported position. As indicated above, in one embodiment, those roads that lie within a pre-determined radius, such as radius 502, are considered prospective roads in reconciling the discrepancies between a reported location and route data. More particularly, assuming that location 202 is the reported location/position, and that radius 502 identifies the predetermined radius to consider, any one of five road segments, including road segments 204, 206, 208, 210, and 212, should be considered as prospective roads. It should be noted, however, that in an alternative embodiment, the actual radius may not be predetermined, but rather determined at the time of selecting prospective roads. In particular, in one embodiment, the radius used for determining whether a road is a prospective road is determined according to the device speed. Accordingly, while in an actual embodiment, a predetermined radius is used, it should be viewed as illustrative, and not limiting upon the present invention.

[0027] With reference to FIG. 4A, at control block 406, a “for” loop is begun for each of the prospective roads identified in block 404. In other words, as those skilled in the art will readily recognize, this “for” loop is a control structure that carries out the steps between its start (control block 406) and a corresponding end (control block 420) for each of the prospective roads. The “for” loop iterates through each of the prospective roads, performing the steps in the construct.

[0028] As a first step in the “for” loop, at block 408, the exemplary routine 400 determines scores for a prospective road. Determining scores for a prospective road is described in greater detail with regard to FIGS. 6A and 6B.

[0029] FIGS. 6A and 6B are a flow diagram illustrating an exemplary subroutine 600 suitable for use by the exemplary routine 400 of FIG. 4, for determining scores for a prospective road. Beginning at block 602, the exemplary subroutine 600 obtains road data corresponding to the prospective road. Typically, the subroutine 600 will obtain the prospective road's data from the route data 314 in the storage 310.

[0030] At block 604, a route position on the prospective road is determined according to the shortest distance between the reported position and the prospective road. This route position represents the location which, if the routine 400 ultimately determines that this prospective road is the “snap-to” road to which the reported location belongs, will become the “snap-to position”, or the “official”, position for determining further routing information. At block 606, a distance score is determined according to the distance between the reported position and the prospective road. More particularly, a distance score is determined according to the distance between the reported position and the “snap-to” position on the prospective road.

[0031] At block 608, the current device speed (presumably using the navigation device or some other related tracking module), is obtained. Typically, the current device speed is provided by the location subsystem 306, but in an alternative embodiment, may be obtained from a vehicle's speedometer. At block 610, a device speed score is determined according to the device speed obtained at block 608 and the prospective road's assigned speed, if available. This type of score can be especially useful in evaluating whether the prospective road is the actual road. For example, if the prospective road is a residential road with a posted 25 mile per hour speed limit, and the current device speed is 55 miles per hour, this may strongly indicate that the prospective road is not a suitable candidate as the “snap-to” road and it would receive a lower score.

[0032] At block 612, a road classification score is determined according to the device speed and the prospective road's classification. This is not the same as comparing device speed to posted speed. Rather, it is a comparison/score considering the speed with known attributes of the prospective road. As an example, if the device speed is 45 miles an hour, and the road's classification is listed as a one-lane dirt road, the prospective road may merit a lower score as being less likely.

[0033] At block 614, the current heading for the navigation device (or navigation system) is obtained. At block 616, a device heading score is determined according to the device heading obtained in block 614 and the prospective road's heading. According to one embodiment, the device heading score is determined according to the difference in angle between the two headings. For example, if the device heading is 45°, and the prospective road's heading is 80°, the prospective road would very likely receive a poor score. On the other hand, if the device heading is 45°, and the prospective road's heading is 42°, a difference of just 3°, then a relatively high score may be merited.

[0034] At block 618, a route score is determined for whether the prospective road is on, or part of, a pre-determined route. As those familiar with navigation devices will recognize, navigation devices are frequently used to plot out prospective routes between an origin and destination. Thus this route, being the pre-determined route, may provide a strong indication as to which of the prospective roads should be considered as the “snap-to” road.

[0035] After determining the various scores described above, the exemplary routine 600 terminates.

[0036] Returning again to FIG. 4, after determining the various scores for the prospective road, at decision block 410, a determination is made as to whether historical data is available. More particularly, a determination is made as to whether the navigation system has retained historical data as to previous route positions. If historical data is not available, the exemplary routine 400 proceeds to block 414 (FIG. 4B). However, if historical data is available, at block 412, a series of historical scores are determined for the prospective road. Determining historical scores for the prospective road is described in greater detail in regard to FIG. 7.

[0037] FIG. 7 is a flow diagram illustrating an exemplary subroutine 700, suitable for use by the exemplary routine 400 of FIG. 4, for determining historical scores based on historical data associated with the prospective road. Beginning at block 702, historical data associated with previous route positions is obtained. In one embodiment, historical data includes information regarding previous route positions. In addition to the route position, information associated with each saved route position, such as device speed, heading, “snap-to” or “official” position, and the like, will typically be stored as part of the historical data. For example, in an actual embodiment, up to three route positions are stored for subsequent use and evaluation, either in the dynamic memory 304 or storage 310. However, any number of historical positions may be used to determine historical scores, and the present invention should not be limited to any particular number.

[0038] At block 704 a continuity score is determined for whether the prospective road is the same as the previous road in the historical information. This is based on observed information that once on a road, a driver will tend to stay on that road for some time. At block 706, the exemplary routine 700 obtains connectivity data for the prospective road. Connectivity data represents information in the route data 312 that indicates whether various road segments are connected, or interconnected. In other words, the connectivity data includes the data from which it can be determined whether one can actually navigate from one road segment to another. Correspondingly, at block 708, a connectivity score is determined as to the likelihood of reaching the prospective route position on the prospective road from the previous, historical route positions.

[0039] At block 710, a historical speed score is determined according to the current speed versus the historical speeds of the navigation device. Similarly, at block 712, a historical heading score is determined as to the current navigation device heading versus the historical navigation device headings. After determining these historically based scores, the exemplary routine 700 terminates.

[0040] Returning again to FIGS. 4A-4C, after having determined historical scores for the prospective road, at block 414 (FIG. 4B), the previously determined scores are normalized. Normalizing the scores is simply taking each determined score and placing it in a range of values that can be compared to other scores. For example, with regard to the distance between the reported location and the shortest distance to the prospective road, that distance may be twenty meters. However, it is unreasonable to compare a raw score of twenty meters to the difference, in degrees, between the navigation device heading and the prospective road heading. Thus, normalizing a score will typically involve translating a particular score into a range of values such that can be generally compared to other scores. Normalizing a score, in one embodiment, entails translating raw scores into a value between 0.0 and 1.0. Alternatively, normalizing the scores may involve translating the raw scores into numbers between 0 and 100. Any normalization scale may be utilized in the present invention, and the invention is not limited to any particular normalization scale. Furthermore, a particular score may be normalized according to a combination of multiple factors that may or may not directly immediately related to the score to be normalized. For example, when normalizing a score for device heading, consideration may be given as to the device speed (or speed score) since at low speeds, the device heading is frequently inaccurate.

[0041] After normalizing the scores, at block 416, the exemplary routine applies optional pre-determined weightings, typically through the application of some weighting function, to some or all of the normalized scores/values. Weighting particular scores provides an opportunity to give more value to any particular score. For example, distance from the reported location to this prospective road may be valued higher than the reported device speed, such that if the distance between the reported position and the prospective route position is very small, this may be valued higher than if the navigation device speed is lower than the speed posted for the prospective road. By weighting the individual scores, particular implementations can be fine tuned according to implementation preferences.

[0042] While separated into two logical steps, those skilled in the art will appreciate that normalizing and weighting may be implemented in a single step. Accordingly, the separation of normalizing and weighting should be viewed as illustrative only, and should not be construed as limiting upon the present invention.

[0043] After normalizing and weighting the scoring values, the overall score for the prospective road is determined. In one embodiment, this overall score is a sum of all of the normalized, weighted scores.

[0044] At control block 420, which corresponds to the end of the “for” loop begun in control block 406, the routine 400 either returns back to control block 406 to process and score other prospective roads, or proceeds to block 422 (FIG. 4C), which would indicate that all of the prospective roads have been scored.

[0045] At block 422, after all prospective roads have been scored, the exemplary routine 400 selects the prospective road with the best overall score as the “snap-to” road. At block 424, the current information relating to this selection, such as the “snap-to” road, route position, device heading, speed, and the like, is stored as historical data for subsequent use (such as described in regard to FIG. 7). At block 426, the exemplary routine 400 notifies the presentation subsystem 308 of the current route position, along with any other information that is typically presented to the display subsystem, for display update purposes. At delay block 428, the exemplary routine 400 delays for some predetermined amount of time, or until the next reported location/position is available. Thereafter, the routine returns again to block 402 and the process repeats.

[0046] While the various embodiments, including the preferred embodiment, of the invention have been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention.