Caching for pathfinding computation

• US 5,978,730 A
• Filed: 02/20/1997
• Issued: 11/02/1999
• Est. Priority Date: 02/20/1997
• Status: Expired due to Term

• Current Assignee: Sony Corporation (Sony Group Corp.), Tele Atlas North America (TomTom NV)
• Original Assignee: Sony Corporation (Sony Group Corp.), Etak, Inc. (TomTom NV)
• Inventors: Fernandez, Rodney Jude, Buxton, James Laurence, Poppen, Richard Frederick
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US08/802,733
• Time in Patent Office: 985 Days
• Field of Search: 340/988, 340/989, 340/990, 340/995, 364/400, 370/351, 701/201, 701/202, 701/203, 701/209
• US Class Current: 701/202
• 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 loading data into a processor readable storage medium, comprising the steps of:

choosing, automatically, a first origin in a processor readable representation of a network;

commencing a pathfinding exploration using a processor, said pathfinding exploration explores from said first origin, said steps of choosing and commencing being performed without a pathfinding computation being requested;

loading sets of data, as needed by said pathfinding exploration, into said processor readable storage medium;

terminating said pathfinding exploration when a predefined condition is met;

receiving a request to compute a path from a new origin and a new destination;

storing an indication of said new origin and an indication of said new destination; and

computing a path from said new origin to said new destination using at least a subset of said loaded data, said step of computing a path being performed after said step of commencing.

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

choosing, automatically, a second origin in said processor readable representation of a network without said pathfinding computation being requested;

commencing a second pathfinding exploration using said processor, said second pathfinding exploration explores from said second origin;

loading new sets of data, as needed by said second pathfinding exploration, into said processor readable storage medium; and

terminating said second pathfinding exploration when said predefined condition is met.

3. A method according to claim 1, wherein:

said predefined condition is met when a path is requested.

4. A method according to claim 1, wherein:

said steps of choosing, commencing, loading and terminating are performed as a background process.

5. A method according to claim 1, wherein:

said data is stored on a CD-ROM; and

said step of loading loads said data from said CD-ROM into a cache memory.

6. A method according to claim 1, wherein:

said steps of choosing and commencing are performed without storing an indication of a destination.

7. A method according to claim 1, wherein:

said processor readable representation of a network is an electronic map;

said electronic map includes a plurality of nodes, each node having at least one cost for traveling to or from an adjacent node; and

said step of commencing a pathfinding exploration includes;

(a) setting up a priority queue and a visited list, said priority queue stores node identifications and keys, said visited list stores node identifications and costs of traveling from said origin;

(b) initializing said priority queue to include said origin;

(c) finding a set of nodes adjacent to said origin;

(d) determining a cost of traveling to each of said adjacent nodes from said origin;

(e) inserting said adjacent nodes into said priority queue, sorted by cost;

(f) inserting said adjacent nodes into said visited list;

(g) removing said origin from said priority queue;

(h) finding a set of nodes adjacent to a node at said priority queue'"'"'s head;

(i) determining a cost of traveling to each of said nodes adjacent to said node at said priority queue'"'"'s head;

(j) inserting into said priority queue at least a subset of said nodes adjacent to said node at said priority queue'"'"'s head;

(k) inserting into said visited list, if not already in said visited list with a lower cost, said nodes adjacent to said node at said priority queue'"'"'s head; and

(l) removing from said priority queue said node at said priority queue'"'"'s head.

8. A method according to claim 7 wherein:

said key includes a cost of traveling from said origin and said key does not include any information about a destination.

9. A method according to claim 7, wherein:

said predefined condition is met when a cost for traveling from said origin to said node at said priority queue'"'"'s head reaches a predetermined threshold.

10. A method according to claim 1, wherein:

said processor readable representation of a network is an electronic map.

11. A method according to claim 10, wherein:

said step of choosing a first origin chooses a current position of a vehicle.

12. A method according to claim 10, wherein:

said step of choosing a first origin chooses a position in said electronic map that is a distance from a current position.

13. A method according to claim 10, wherein:

said sets of data are loaded into a cache memory in said processor readable storage medium.

14. A method according to claim 13, wherein:

said processor readable storage medium is memory; and

said cache memory is a portion of said memory.

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

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

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

determining when a predetermined number of nodes have been processed, said predefined condition is met when said predetermined number of nodes have been processed.

17. A method according to claim 13, further including the step of:

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

18. A method according to claim 13, further including the step of:

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

19. A method according to claim 9, wherein:

said step of continuing is performed after said step of terminating said pathfinding exploration when a predefined condition is met.

22. A method according to claim 19, wherein:

said steps of running and terminating are continuously repeated until said step of performing a pathfinding calculation is commenced.

20. A method for computing a path in an electronic representation of a network, comprising the steps of:

running a background process for loading network data from a mass storage device into a memory, said background process includes an exploration of said network from a chosen origin and loading data needed by said exploration;

terminating said background process when a stopping condition is met or when a pathfinding calculation is requested;

storing a first origin and a first destination; and

determining a path from said first origin to said first destination, after terminating said background process, using said network data loaded into said memory.

21. A method according to claim 20, wherein:

said background process loads data from a CD-ROM to a cache.

23. An apparatus for pathfinding, comprising:

a processor;

a memory, in communication with said processor; and

a processor readable storage medium;

in communication with said processor and said memory;

said processor programmed to perform the method of;

choosing, automatically, a first origin in an electronic map;

commencing a pathfinding exploration, said pathfinding exploration explores from said first origin, said steps of choosing and commencing being performed without a pathfinding computation being requested;

loading sets of data, as needed by said pathfinding exploration, from said processor readable storage medium into a cache portion of said memory;

terminating said pathfinding exploration when a predefined condition is met;

receiving a request to compute a path from a new origin and a new destination,

storing an indication of said new origin and an indication of said new destination, and

computing a path from said new origin to said new destination using at least a subset of said data loaded in said cache portion of said memory, said step of computing being performed after said step of terminating.

24. An apparatus according to claim 23, wherein:

said step of choosing includes said processor choosing a position in said electronic map that is a distance from a current position of a vehicle.

25. An apparatus according to claim 23, wherein said method further includes the step of:

determining when a predetermined amount of data is loaded in said memory said predefined condition is met when said predetermined amount of data is loaded in said memory.

26. An apparatus according to claim 23, wherein is said method further includes the steps of:

choosing, automatically, a new origin in said electronic map without said pathfinding computation being requested;

commencing a second pathfinding exploration using said processor;

loading new sets of data, as needed by said second pathfinding exploration, from said processor readable storage medium into said cache portion of said memory; and

terminating said second pathfinding exploration when said predefined condition is met.

27. A method for loading data for pathfinding, comprising the steps of:

choosing, automatically, a first origin in an electronic map;

commencing a pathfinding exploration using a processor, said pathfinding exploration explores from said first origin, said steps of choosing and commencing being performed without a destination being indicated;

loading data, as needed by said pathfinding exploration, into a cache memory;

terminating said pathfinding exploration when a predefined condition is met;

storing a new origin and a new destination; and

computing a path from said new origin to said new destination using at least a subset of said data loaded in said cache memory, said step of computing being performed after said step of commencing.

28. A processor readable storage medium, said processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming a processor to perform a method comprising the steps of:

choosing, automatically, a first origin in an electronic map;

commencing a pathfinding exploration using a processor, said pathfinding exploration explores from said first origin, said steps of choosing and commencing being performed without a pathfinding computation being requested;

loading data, as needed by said pathfinding exploration, into said processor readable storage medium;

terminating said pathfinding exploration when a predefined condition is met;

receiving a request to compute a path from a new origin and a new destination storing an indication of said new origin and an indication of said new destination; and

computing a path from said new origin to said new destination using at least a subset of said loaded data, said step of computing being performed after said step of commencing.

29. A processor readable storage medium according to claim 28, wherein:

said data is loaded into a cache memory; and

said cache memory is a portion of main memory.

30. A processor readable storage medium according to claim 28, wherein said method further includes the step of:

determining when a predetermined percentage of said processor readable storage medium is filled, said predefined condition is met when said predetermined percentage of said processor readable storage medium is filled.

31. A processor readable storage medium according to claim 28, wherein:

said data is stored in a CD-ROM; and

said step of loading loads said data from said CD-ROM into a cache memory.

32. A processor readable storage medium according to claim 28, wherein:

said steps of choosing and commencing are performed without storing an indication of a destination.

33. A processor readable storage medium according to claim 28, wherein said method further includes the step of:

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

34. A processor readable storage medium according to claim 28, wherein:

said steps of choosing, commencing, loading and terminating are performed as a background process.