NAVIGATION DEVICE & METHOD

• US 20120209507A1
• Filed: 10/12/2009
• Published: 08/16/2012
• Est. Priority Date: 10/12/2009
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Serbanescu, Alexandru
• Granted Patent: US 8,838,377 B2
• Time in Patent Office: Days
• US Class Current: 701/410
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/04 by terrestrial means G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/165 combined with non-inertial navigation instruments
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

A navigation device comprising a receiver for receiving signals from position sensors, memory having stored therein a seed position and map data which comprises a map of navigable routes in an area, and an output device, such as a display or speaker, for outputting a current location. The navigation device further comprises a processor for determining distance travelled and changes in orientation from the signals and estimating the current location on one of the navigable routes of the map data. The step of estimating comprises using the distance travelled and the changes in orientation to extrapolate from the seed position possible paths along the navigable routes that the navigation device may have travelled and assigning to each path a probability that the navigation device travelled that path. For changes in orientation, the processor expands each path and recalculates the probability that the navigation device travelled that path. The processor assigns the current location to be a current predicted position on the path with the highest probability.

Claims

1. A navigation device comprising:

a receiver arranged to receive signals from position sensors;

a memory having stored therein a seed position and map data which comprises a map of navigable routes in an area;

an output device arranged to output a current location; and

a processor arranged to determine distance travelled and changes in orientation from the signals and further arranged to estimate the current location on one of the navigable routes of the map data by;

using the distance travelled and the changes in orientation to extrapolate from the seed position possible paths along the navigable routes that the navigation device may have travelled and assigning to each path a probability that the navigation device travelled that path,

for changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path, and

assigning the current location to be a current predicted position on the path with the highest probability and then, for further changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path.

2. A navigation device according to claim 1, wherein the probability of each path being the path the navigation device travelled is determined by comparing the changes in orientation with corresponding changes in the angle of the navigable routes of the path.

3. A navigation device according to claim 2, wherein a change in orientation is a discrete event beginning when a change in angle per unit time above a predetermined angle threshold is detected to when changes in angle per unit time stabilise again to less than the predetermined threshold.

4. A navigation device according to claim 1, wherein estimating the current location further comprises expanding each path and recalculating the probability that the navigation device travelled that path for changes in distance.

5. A navigation device according to claim 4, wherein the expansion of the paths and recalculation of the probability is carried out when the change in distance is above a predetermined distance threshold.

6. A navigation device according to claim 1, wherein a probability for a path is determined by determining a probability that a particular change in at least one of orientation and change in distance corresponds to movement along a particular navigable route that forms the path and multiplying this probability with probabilities calculated for other changes in at least one of orientation and changes in distance corresponding to movement along other navigable routes that form the path.

7. A navigation device according to claim 1, wherein the processor is arranged to discard paths from further expansions and calculations when the probability of the navigation device having travelled that path drops below a predetermined probability threshold.

8. A navigation device according to claim, 7, wherein the probability threshold at which a path is discarded is when the path is not one of a number, N, of most likely paths.

9. A navigation device according to claim 1, wherein the processor is arranged to discard each path that is not the path with the highest probability from further expansions and calculations when the number of expansions of the path is above a predetermined expansion threshold.

10. A navigation device according to claim 1, wherein the processor is arranged to set the seed position in memory to the current location when there is only a single possible path.

11. A navigation device according to claim 1, wherein the processor is arranged to disregard the contribution to the paths'"'"' probabilities of routes that are before an initial seed point at which the paths divide.

12. A navigation device according to claim 1, wherein the position sensors comprise sensors arranged to measure at least one of acceleration, speed, distance, time and change in angle.

13. A navigation device according to claim 12, wherein the position sensors comprise at least one of an accelerometer and a gyroscope.

14. A navigation device according to claim 1, wherein the output device is at least one of a display and a speaker.

15. A non-transitory data carrier having stored thereon instructions which, when carried out by a processor connected with a memory, the memory having stored therein a seed position and map data which comprises a map of navigable routes in an area, cause the processor to:

receive position data on distance travelled and changes in orientation;

estimate a current location on one of a plurality of navigable routes of map data from the position data; and

output the current location to an output device;

wherein the step of estimating comprises;

using the distance travelled and changes in orientation to extrapolate from the seed position possible paths along the navigable routes that the navigation device may have travelled and assigning to each path a probability that the navigation device travelled that path,

for changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path, and

assigning the current location to be a current predicted position on the path with the highest probability and then, for further changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path.

16. A method of estimating a current location on a map of navigable routes using position data, the method comprising:

determining distance travelled and changes in orientation from the position data;

using the distance travelled and the changes in orientation to extrapolate from a seed position possible paths along the navigable routes that may have been travelled and assigning to each path a probability that the path was travelled,

for changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path, and

assigning the current location to be a current predicted position on the path with the highest probability and then, for further changes in orientation, expanding each path and recalculating the probability that the navigation device travelled that path.