Patent ID: 8838377

Claim:
A navigation device comprising: a receiver arranged to receive signals from position sensors indicative of the position of the navigation device; 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 traveled and changes in orientation from the signals and further arranged to estimate the current location of the navigation device on one of the navigable routes of the map data by: using the determined distance traveled and the changes in orientation to extrapolate from the seed position a first set of possible paths along the navigable routes that the navigation device may have traveled and assigning to each path of the first set of possible paths a probability that the navigation device traveled that path, for further changes in at least one of orientation and distance, using the determined distance traveled and changes in orientation to expand each of the first set of possible paths to determine a second set of possible paths and assigning to each path of the second set of possible paths a probability that the navigation device traveled that path, and assigning the current location to be a current predicted position of the navigation device on the path with the highest probability of the second set of possible paths.