Caching for pathfinding computation

Claim 3

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.

Claim 4

A method according to claim 1, wherein: said predefined condition is met when a path is requested.

Claim 5

A method according to claim 1, wherein: said steps of choosing, commencing, loading and terminating are performed as a background process.

Claim 6

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.

Claim 7

A method according to claim 1, wherein: said steps of choosing and commencing are performed without storing an indication of a destination.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

A method according to claim 1, wherein: said processor readable representation of a network is an electronic map.

Claim 12

A method according to claim 10, wherein: said step of choosing a first origin chooses a current position of a vehicle.

Claim 13

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.

Claim 14

A method according to claim 10, wherein: said sets of data are loaded into a cache memory in said processor readable storage medium.

Claim 15

A method according to claim 13, wherein: said processor readable storage medium is memory; and said cache memory is a portion of said memory.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 23

A method according to claim 20, wherein: said background process loads data from a CD-ROM to a cache.

Claim 24

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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.

Claim 37

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.

Claim 38

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.

Claim 39

A processor readable storage medium according to claim 28, wherein: said steps of choosing, commencing, loading and terminating are performed as a background process.