Caching for pathfinding computation

• US 6,377,887 B1
• Filed: 08/06/1999
• Issued: 04/23/2002
• Est. Priority Date: 02/20/1997
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Fernandez, Rodney Jude, Buxton, James Laurence, Poppen, Richard Frederick
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US09/369,545
• Time in Patent Office: 991 Days
• Field of Search: 701/201, 701/202, 701/209, 340/995
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A system for computing a path in an electronic map (or other network) starts a pathfinding exploration in the background while the system is waiting for a request to find a path. The system automatically chooses an origin. The system'"'"'s memory can be divided such that a portion of memory acts as a cache. The data for the nodes in the electronic map are loaded into the cache when needed. The system terminates the pathfinding process when a predetermined condition occurs; for example, a predetermined percentage of the cache is filled. When the system terminates the pathfinding process, the system can start a new pathfinding process from a new origin. Thus, when a user requests a path to be found, the pathfinding process begins with data already loaded in the cache.

Claims

1. A method for computing a path from an origin to a destination using an electronic representation of a map, said electronic representation of said map including map data, the method comprising the steps of:

performing a process for loading map data from a mass storage device into a memory, said map data describes at least a portion of said map;

receiving a request to determine a path from said origin to said destination, said request is received after starting said process; and

determining said path from said origin to said destination using at least a subset of said map data loaded into said memory.

2. A method according to claim 1, further including the step of:

terminating said process when a stopping condition is met or when a pathfinding request is received, said path is determined after terminating said process.

3. A method according to claim 2, wherein:

said steps of performing and terminating are continuously repeated until said step of determining is commenced.

4. A method according to claim 1, wherein:

said process for loading map data includes choosing a starting point in said map, loading map data for said starting point, choosing additional points in said map based on said starting point and loading map data for said additional points.

5. A method according to claim 1, wherein:

said step of performing a process includes an exploration of said electronic representation of said map from a starting point and loading data needed by said exploration.

6. A method according to claim 5, further including the step of:

automatically choosing said starting point in said electronic representation of map.

7. A method according to claim 6, wherein:

said step of automatically choosing said starting point chooses a current position of a vehicle.

8. A method according to claim 6, wherein:

said step of automatically choosing said starting point chooses a position that is a distance from a current position.

9. A method according to claim 5, further including the steps of:

terminating said process when a stopping condition is met or when a pathfinding request is received; and

determining when a predetermined percentage of said memory is filled, said stopping condition is met when said predetermined percentage of said memory is filled.

10. A method according to claim 5, further including the steps of:

terminating said process when a stopping condition is met or when a pathfinding request is received; and

determining when a predetermined quantity of map data has been processed, said stopping condition is met when said predetermined quantity of map data has been processed.

11. A method according to claim 5, further including the step of:

performing a second exploration, said second exploration only considers data residing in said memory when said second exploration commences, data used by said second exploration is marked as being recently used.

12. A method according to claim 1, wherein:

said mass storage device is a CD-ROM.

13. A method according to claim 1, wherein:

said process is a background process.

14. A method for computing a path from an origin to a destination using an electronic representation of a map, said electronic representation of said map including map data, the method comprising the steps of:

performing a process for loading map data from a mass storage device into a memory, said map data describes at least a portion of said map; and

determining a path from said origin to said destination using at least a subset of said map data loaded into said memory, said step of performing a process is performed without storing an indication of said destination.

15. A method for computing a path from an origin to a destination using an electronic representation of a map, said electronic representation of said map including map data, the method comprising the steps of:

performing a process for loading map data from a mass storage device into a memory, said map data describes at least a portion of said map; and

determining a path from said origin to said destination using at least a subset of said map data loaded into said memory, said step of performing a process includes commencing a pathfinding exploration without said pathfinding exploration being requested.

16. A method according to claim 15, further including the step of:

continuing said pathfinding exploration utilizing data in said memory and not loading any additional data into said memory.

17. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for computing a path from an origin to a destination using an electronic representation of a map, said electronic representation of said map including map data, the method comprising the steps of:

performing a process for loading map data from a mass storage device into a memory, said map data describes at least a portion of said map;

receiving a request to determine a path from said origin to said destination, said request is received after starting said process; and

determining said path from said origin to said destination using at least a subset of said map data loaded into said memory;

said process is commenced prior to receiving said request to determine a path.

18. A processor readable storage medium according to claim 17, wherein:

said process for loading map data includes choosing a starting point in said map, loading map data for said starting point, choosing additional points in said map based on said starting point, and loading map data for said additional points.

19. An apparatus, for computing a path from an origin to a destination using an electronic representation of a map, said electronic representation of said map including map data, comprising:

an input device;

an output device;

a memory;

a storage device for storing said electronic representation of said map; and

a processor in communication with said input device, said output device, said memory, and said storage device, said processor programmed to perform the method comprising the steps of;

performing a process for loading map data from said storage device into said memory, said map data describes at least a portion of said map;

receiving a request from said input device to determine a path from said origin to said destination, said request is received after starting said process; and

determining a path from said origin to said destination using at least a subset of said map data loaded into said memory.

20. An apparatus according to claim 19, wherein:

said process for loading map data includes choosing a starting point in said map, loading map data for said starting point into said memory, choosing additional points in said map based on said starting point, and loading map data for said additional points into said memory.