# Patent

## Title
On-board diagnostics based navigation device for dead reckoning

## Abstract

A computing navigation device is disclosed that includes a processor configured to control a communication module configured to receive a global positioning satellite (GPS) system signal corresponding to a vehicle position of a vehicle. The processor may be further configured to recognize a dropped signal condition in which no operational signal is detected from the GPS system, and to identify a last position of the vehicle corresponding to a time of the dropped signal condition. The processor may be further configured to retrieve on-board diagnostics data from an on-board diagnostics system of the vehicle corresponding with a movement of the vehicle. The computing navigation device may further include a kinematic module configured to calculate a calculated position of the vehicle based on the last position and the movement of the vehicle, and a display configured to display a representation of the calculated position.

## Background
BACKGROUND
Portable electronic devices such as Personal Navigation Devices (PND) are increasingly utilized. A PND includes a Global Positioning System (GPS) receiver configured to receive signals from a group of artificial earth satellites called the Global Navigation Satellite System (GNSS). The GPS receiver uses the arrival time of signals from four or more satellites to compute the distance to each satellite. From the relative distances the GPS receiver is able to determine its position, and therefore a user's position, using geometry and trigonometry.
In some cases a vehicle may be equipped with a navigation device integrated with the vehicle's dashboard, and with the vehicle's electronics. In other cases a portable PND may be brought into the vehicle, and may or may not receive power from the vehicle's power supply. The detected position of the GPS receiver may be depicted as a graphical element superimposed over a map on a display to help a user navigate. The graphical element may remain more or less in the same location on the display while the regions displayed on the superimposed map adjust as the vehicle moves, illustrating movement of the user across the map.
A problem sometimes arises when one or more of the signals from the GNSS are dropped. This may happen, for example, if the vehicle goes into a tunnel, or travels adjacent one or more tall buildings, thereby blocking the signal(s) from reaching the receiver. As a result, erroneous display of the position of the vehicle on the map may occur, causing the user to become lost, confused, or miss a turn.
Efforts have been made to provide dead reckoning with PNDs by providing a PND with a built-in accelerometer. This approach has several drawbacks. First, this approach typically only provides dead reckoning for a few seconds at a time. In addition, this approach involves a double integration of the sensed acceleration, which causes accumulated errors in speed and distance calculations.
SUMMARY
A computing navigation device is disclosed that includes a processor configured to control a communication module configured to receive a global positioning satellite (GPS) system signal corresponding to a vehicle position of a vehicle. The processor may be further configured to recognize a dropped signal condition in which no operational signal is detected from the GPS system, and to identify a last position of the vehicle corresponding to a time of the dropped signal condition. The processor may be further configured to retrieve On-Board Diagnostics (OBD) data from an on-board diagnostics system of the vehicle corresponding with a movement of the vehicle. The computing navigation device may further include a kinematic module configured to calculate a calculated position of the vehicle based on the last position and the movement of the vehicle, and a display configured to display a representation of the calculated position.
This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. Furthermore, the claimed subject matter is not limited to implementations that solve any or all disadvantages noted in any part of this disclosure.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a schematic view of an embodiment of a navigation system for dead reckoning, which includes a computing navigation device for use with a vehicle;
FIG. 2 illustrates a first screen of a graphical user interface that is displayed on a display of the computing navigation device illustrated in FIG. 1, showing a tracked position and a calculated position of the computer navigation device as solid and dashed lines on a map;
FIG. 3 illustrates a second screen of the graphical user interface of FIG. 2, showing a textual graphical element indicating that a computed route based on a calculated position of the computing navigation device is being displayed;
FIG. 4A illustrates a third screen of the graphical user interface of FIG. 2, showing a tracked position indicated by a solid line and a map presented in a first color scheme; and
FIG. 4B illustrates a fourth screen of the graphical user interface of FIG. 2, showing a calculated position indicated by a dashed line and a map presented in a second color scheme; and
FIG. 5 is a flowchart illustrating one embodiment of a method for dead reckoning.



DETAILED DESCRIPTION
FIG. 1 illustrates a navigation system 10 including a computing navigation device 12 for use with a vehicle 22. The computing navigation device 12 may include a processor 14 configured to control, for example, a communication module 16, which is configured to receive one or more signals 20 from a global positioning satellite (GPS) system 18. In the embodiments illustrated, the global positioning satellite (GPS) system is the Global Navigation Satellite System (GNSS), although other satellite positioning systems may be utilized. The signal 20 may correspond to a vehicle position of the vehicle 22. The correspondence may be calculated by the computing navigation device 12 using known methods such as triangulation, or the like.
The computing navigation device 12 may further include a navigation module 56, which in turn includes a kinematic module 34, a signal monitoring module 48, and an OBD data retrieval module 54. The signal monitoring module 48 may be configured to recognize a dropped signal condition in which no operational signal 20 is detected from the GPS system 18. The dropped signal condition may be detected, for example, when no GPS signals are received by the computing navigation device 12, or when fewer than a threshold number of GPS signals used to compute the position of the computing navigation device 12 are received. The threshold number may be four, or another suitable number, for example, three.
The navigation module 56 of the computing navigation device 12 may also be configured to identify a last position 24 of the vehicle 22 corresponding to a time of the dropped signal condition. The OBD data retrieval module 54 may be configured to retrieve on-board diagnostics data, hereinafter referred to as OBD data 26, from an on-board diagnostics system 30 of the vehicle 22, the retrieved OBD data 26 corresponding with a movement of the vehicle 22. The kinematic module 34 may be configured to calculate a calculated position 36 of the vehicle 22 based on the last position 24, and the OBD data 26 of the vehicle 22.
The signal monitoring module 48 may be configured to monitor the GPS signal 20 from the communication module 16 and detect an operational signal condition or a dropped signal condition. The operational signal condition indicates that a sufficient number and/or strength of signals are detected to determine a position of the navigation device 12. The dropped signal condition, as discussed previously, indicates that no operational signal 20 is detected from the GPS system 18. Although the signal module 48 is depicted as communicating through the communication module 16 with the GPS receiver 21, it will be appreciated that alternatively the signal monitoring module 48 may be configured to monitor the signal directly from the GPS receiver 21.
As illustrated in FIG. 1 with decision box 50, if an operational signal condition is detected, then the signal monitoring module 48 may pass the tracked position 46 to the graphical user interface 42 displayed on display 40 via, for example, a graphical user interface 52. But, if no operational signal is detected, which may occur if no signal at all is detected, if the signal strength is below a predetermined threshold, or if signals are detected only from a number of satellites that is below a predetermined threshold and thus insufficient to determine a position of the navigation device 12, then the signal monitoring module 48 is configured to recognize this situation as a dropped signal condition. In response to detecting the dropped signal condition, the signal monitoring module 48 is configured to pass the last position 24 to the kinematic module 34, and communicate with the OBD data retrieval module 54 to pass OBD data 26 to the kinematic module 34. Alternatively, the signal monitoring module 48 is configured to communicate the dropped signal condition directly to the kinematic module 34, which in response is configured to receive OBD data 26 from the communications module 16.
The on-board diagnostics system 30 may be configured to generate OBD data 26, and transmit the OBD data to the communication module 58 via OBD port 59. The OBD port 59 may be a virtual or physical port, and may effect a coupling of the on-board diagnostics system 30 to the computing navigation device 12. The computing navigation device 12 and on-board diagnostics system 30 may be coupled via a wired or wireless coupling, for example.
The OBD data 26 generated by the on-board diagnostics system 30 may be organized to include a plurality of parameters, each of which may include a parameter identifier, and an associate value. The parameters may be used by vehicle technicians to diagnose a vehicle condition. Some parameters may be industry standard parameters 76 utilized by multiple vehicle manufacturers, while others may be model-specific parameters 78 used by the manufacturer of a specific vehicle model.
Example standard parameters 76 that the on-board diagnostics system 30 may be configured to provide include a speed 70 and a steering wheel position 72 of the vehicle 22. Example model specific parameters 78 include a cardinal direction 74 sensed by a compass outfitted on the vehicle 22. Thus, it will be appreciated that the kinematic module 34 may be configured to calculate the calculated position 36 based on one or more of the speed 70, the steering wheel angle 72, and the cardinal direction 74, among other parameters. It should be understood these parameters are merely exemplary, and various other parameters may be used to effect dead reckoning as well.
The kinematic module 34 may be further configured to calculate an updated calculated position of the vehicle 22 based on the calculated position 36 and updated OBD data 26 from the on-board diagnostics system 30. This may be done iteratively such that a substantially continuously updated vehicle position may be displayed on the graphical user interface 42 on display 40 from a substantially continuously updated calculated position 36. The updating of the calculated position 36 may occur until a signal of sufficient strength is detected by the signal monitoring module 48, at which time the navigation module 56 may determine a new tracked position 46, which may be displayed on the graphical user interface 42 on display 40.
The computing navigation device 12 may include a graphical user interface module 52 that is configured to render a graphical user interface 42 on display 40. The graphical user interface module 52 may be configured to display a representation of the tracked position 46 of the vehicle 22 based on the GPS system signal 20, and the calculated position 36 based on the OBD data, on the graphical user interface 42 on display 40.
In some embodiments, the graphical user interface 42 also may be configured to receive a user input to effect selected retrieval of the OBD data 26. For example, during a setup procedure the user may input model information of the user's vehicle, so that model specific parameters 78 may be utilized. As another example, the user may input user preferences for the type of standard parameters 76 to be utilized. It will be appreciated that the computing navigation device may default to receiving the standard parameters indicating speed and steering wheel position, and a user may choose additional parameter options. Through such a set up procedure, the OBD data 26 for retrieval may be selected by the user from one or more standard parameters 76, and/or one or more model specific parameters 78.
The communication module 16, the navigation module 56 and the interface module 52 may all be stored in a memory 58 that is associated with the processor 14. The memory may include non-volatile memory and volatile memory, and the processor 14 may be configured to execute the modules using portions of each.
FIGS. 2, 3, 4A, and 4B illustrate various screens of graphical user interface 42. The graphical user interface 42 may be configured to display the tracked position 46 of the vehicle 22 via a tracked position graphical element 60 during a signal receiving condition which includes an operational signal being received from the GPS system 18 that enables the tracking of the position of the computing navigation device. The graphical user interface 42 may be further configured to display the calculated position 36 of the vehicle 22 via a calculated position graphical element 62 during the dropped signal condition. As described below in further detail, the tracked position graphical element 60 and the calculated position graphical element 62 are distinguishable in appearance.
For example, as illustrated in FIG. 2, the tracked position graphical element 60 may be a line of a first pattern, color and/or thickness, such as a solid line 61, depicting the movement of the vehicle 22 along a map 64 while the navigation module 56 receives a signal 20 from the GPS system 18. The calculated position graphical element 62 may be a line of a second pattern, color and/or thickness, such as a dashed or dotted line 63, depicting the movement of the vehicle 22 along the map 64. Other combinations of distinguishable lines may alternatively be used, such as two different dashed lines, two different colored lines, or lines of two different thicknesses, etc. Some embodiments may include a dropped signal graphical element 65 and/or a signal restored element 67. These elements may also aid the user's awareness of the signal condition.
As shown in FIG. 3, the tracked position graphical element 60 may be a line superimposed on a depiction of the map 64, and the calculated position graphical element 62 may be a floating graphical element on the display during the dropped signal condition such as a text item 71 indicting to the user that the GPS signal has been dropped, and the route is being calculated rather than tracked. The text item 71 may flash or change color to increase visibility. It will be appreciated that other types of floating graphical elements may also be used, such as graphical icons, letters, numbers, etc.
Another example embodiment is illustrated in FIGS. 4A and 4B wherein the tracked position graphical element 60 may be a depiction of the map 64 and/or the entire display displayed in a first color scheme, as schematically depicted with bold lines and hatching in FIG. 4A. The calculated position graphical element 62 may be a depiction of the map 64 and/or the entire display being displayed in a second color scheme, as schematically depicted with relatively thinner lines in FIG. 4B. In other embodiments in which the color scheme of the map or display changes to indicate that the position of the vehicle is being calculated, a graphical depiction of the traveled path may be omitted from the display, such that the current position of the vehicle is shown by a graphical element, but prior calculated positions are not shown.
Some embodiments may include a graphical element depicting the location of the vehicle that may remain in substantially the same location on the display while the regions displayed on the superimposed map adjust as the vehicle moves, depicting movement of the vehicle across the map. Comparison of FIG. 2 to FIG. 3 illustrates such movement although other features of FIG. 2 have been included to illustrate other aspects of various embodiments.
FIG. 5 is a flow chart illustrating an embodiment of a method for dead reckoning. The method may be implemented using the hardware and software components of navigation system 10 described above, or using other suitable hardware and software. The method 200 may include, at 202, receiving a GPS signal from a GPS system having a GPS receiver and being coupled with a moving vehicle. At 204, the method may include recognizing a lack of operational signal from the GPS system as a dropped signal condition. At 206, the method may include passing a last position of the vehicle to a kinematic module upon reaching the dropped signal condition. The passing of the last position may be effected upon recognizing a lack of signal from the GPS system by a signal monitoring module, and the method may further include communicating with an OBD data retrieval module to pass the OBD data to the kinematic module upon recognizing the lack of signal from the GPS system.
At 208, the method may include retrieving OBD data corresponding with a continued movement of the vehicle from an on-board diagnostics system of the vehicle, and passing the OBD data to the kinematic module. As discussed above, retrieving OBD data from the on-board diagnostics system may include retrieving one or more of the speed of the vehicle, the steering wheel angle, and the cardinal direction, among other parameters. In some embodiments, the data is retrieved based on user input instructions that are received from a graphical user interface to effect changes in the display or calculation of the position of the vehicle. At 210, the method may include calculating a calculated position of the vehicle with the kinematic module based on the last position of the vehicle and the OBD data. As discussed above, calculating the calculated position may include performing a calculation based on one or more of a speed of the vehicle, a steering wheel angle, and a cardinal direction, among other parameters. At 212, the method may include displaying the calculated position of the vehicle on a graphical user interface.
Some embodiments may provide a method that may further include displaying a tracked position of the vehicle on the graphical user interface based on the stream of signals from GPS system. Displaying the tracked position of the vehicle may include displaying the position of the vehicle via a tracked position graphical element during a signal receiving condition indicating that an operational signal is being received from the GPS system, and the displaying the calculated position of the vehicle may include displaying the position of the vehicle via a calculated position graphical element during the dropped signal condition. The tracked position graphical element and the calculated position graphical element may be distinguishable in appearance in the various manners described above.
The systems and methods described above may enable efficient calculation of a position of a vehicle upon loss of the ability to sufficiently track the position of the vehicle using global positioning satellites, reducing potential confusion to vehicle operators.
It will be appreciated that the computing navigation device described herein may be any suitable computing device configured to execute the programs described herein. For example, the computing navigation device may be a personal computer, laptop computer, portable data assistant (PDA), computer-enabled wireless telephone, networked computing device, or other suitable computing device, and may be connected to a computer network, such as the Internet. The computing device typically includes a processor and associated volatile and non-volatile memory, and is configured to execute programs stored in non-volatile memory using portions of volatile memory and the processor. As used herein, the terms “program” and “module” refers to software or firmware components that may be executed by, or utilized by, one or more computing devices described herein, and is meant to encompass individual or groups of executable files, data files, libraries, drivers, scripts, database records, etc. It will be appreciated that computer-readable media may be provided having program instructions stored thereon, which upon execution by a computing device, cause the computing device to execute the methods described above and cause operation of the systems described above.
It should be understood that the embodiments herein are illustrative and not restrictive, since the scope of the invention is defined by the appended claims rather than by the description preceding them, and all changes that fall within metes and bounds of the claims, or equivalence of such metes and bounds thereof are therefore intended to be embraced by the claims.

## Claims

1. A computing navigation device on board a vehicle, comprising:
a processor configured to execute:
a communication module configured to receive a global positioning satellite (GPS) system signal corresponding to a vehicle position of a vehicle and configured to recognize a dropped signal condition in which no operational signal is detected from the GPS system and GPS data is not being received, and configured to identify a last position of the vehicle corresponding to a time of the dropped signal condition, and configured to retrieve OBD data from an on-board diagnostics system of the vehicle corresponding with a movement of the vehicle;
a kinematic module configured to calculate a calculated position of the vehicle based on the last position and the OBD data when the dropped signal condition is recognized by the communication module; and
a graphical user interface configured to display a calculated position graphical element representing the calculated position during the dropped signal condition when GPS data is not being received and display a tracked position graphical element representing a path of the vehicle determined based on the GPS system signal during a signal receiving condition indicating an operational signal is being received from the GPS system, the tracked position graphical element and the calculated position graphical element being distinguishable in appearance.

2. The computing navigation device of claim 1, wherein the graphical user interface is further configured to display a tracked position of the vehicle based on the GPS system signal.

3. The computing navigation device of claim 1, wherein:
the tracked position graphical element is a line of a first pattern, color and/or thickness, depicting the movement of the vehicle along a map; and
the calculated position graphical element is a line of a second pattern, color and/or thickness, depicting the movement of the vehicle along the map.

4. The computing navigation device of claim 1, wherein the calculated position graphical element is selected from the group consisting of a text item, graphical icon, letter, number, and color scheme.

5. The computing navigation device of claim 1, further comprising a user interface configured to receive a user input data to effect selected retrieval of one or more standard parameters and/or model specific parameters in the OBD data.

6. The computing navigation device of claim 1, wherein the kinematic module is further configured to calculate an updated calculated position of the vehicle based on the calculated position and updated OBD data from the on-board diagnostics system.

7. The computing navigation device of claim 1, further comprising a signal monitoring module configured to monitor the GPS signal, and configured to pass the last position to the kinematic module and communicate with an OBD data retrieval module to pass the OBD data to the kinematic module.

8. The computing navigation device of claim 1, wherein the OBD data includes a speed, a steering wheel angle, and a cardinal direction of the vehicle.

9. The computing navigation device of claim 1, wherein the kinematic module is configured to calculate the calculated position based on one or more of a speed of the vehicle, a steering wheel angle, and a cardinal direction.

10. A method for dead reckoning, comprising:
receiving a GPS signal from a GPS system with a GPS receiver coupled with a moving vehicle;
displaying on a graphical user interface, on board the vehicle, a tracked position graphical element representing a path of the vehicle determined based on the GPS signal during a signal receiving condition indicating an operational signal is being received from the GPS system;
recognizing a lack of an operational signal from the GPS system as a dropped signal condition;
passing a last position of the vehicle to a kinematic module upon reaching the dropped signal condition during the dropped signal condition;
retrieving OBD data corresponding with a continued movement of the vehicle from an on-board diagnostics system of the vehicle during the dropped signal condition;
calculating a calculated position of the vehicle with the kinematic module based on the last position of the vehicle and the OBD data during the dropped signal condition; and
displaying on the graphical user interface a calculated position graphical element representing a path of the vehicle determined based on the kinematic module during the dropped signal condition, the calculated position graphical element visually distinguishable from the tracked position graphical element.

11. The method of claim 10, wherein:
the tracked position graphical element is a line of a first pattern, color and/or thickness, depicting the movement of the vehicle along a map; and
the calculated position graphical element is a line of a second pattern, color and/or thickness, depicting the movement of the vehicle along the map.

12. The method of claim 10, wherein the retrieving OBD data from the on-board diagnostics system includes retrieving one or more of a speed, a steering wheel angle, and a cardinal direction of the vehicle.

13. The method of claim 10, wherein the calculating the calculated position includes performing a calculation based on one or more of a speed, a steering wheel angle, and a cardinal direction of the vehicle.

14. The method of claim 10, wherein the passing the last position is effected upon the recognizing a lack of signal from the GPS system, wherein the method further comprises:
communicating with an OBD data retrieval module to pass the OBD data to the kinematic module upon the recognizing the lack of signal from the GPS system.

15. The method of claim 10, wherein the OBD data is retrieved based on user input instructions that are received from the graphical user interface to effect changes in display or calculation of the position of the vehicle.

16. A navigation system on board a vehicle, comprising:
a computing navigation device configured to receive an operational GPS signal from a GPS system sufficient to track a position of the computing navigation device during a signal receiving condition, and to receive from an on-board diagnostic system of a vehicle OBD data indicative of a movement of the vehicle, the computing navigation device including:
a processor configured to:
monitor the GPS signal from the GPS system;
recognize a dropped signal condition in which no operational GPS signal is detected from the GPS system and GPS data is not being received by the computing navigation device;
identify a last position of the vehicle upon reaching the dropped signal condition;
receive OBD data from the on-board diagnostic system upon reaching the dropped signal condition; and
calculate a calculated position of the vehicle based on the last position and the OBD data during the dropped signal condition; and

a display coupled with the processor and configured to display the tracked position during the signal receiving condition, and to display the calculated position during the dropped signal condition, the tracked position visually distinguishable from the calculated position.