Using multiple levels of costs for a pathfinding computation

• US 5,893,081 A
• Filed: 11/25/1996
• Issued: 04/06/1999
• Est. Priority Date: 11/25/1996
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Poppen, Richard Frederick
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US08/756,263
• Time in Patent Office: 862 Days
• Field of Search: 364/400, 370/254, 370/255, 370/256, 370/351, 395/200.71, 701/25, 701/26, 701/201, 701/202, 705/400
• US Class Current: 705/400
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

A system for computing a path in a processor readable representation of a network which can minimize an identified cost. The cost can include time, distance, tolls paid, ease of turning, quality of scenery, processing time, waiting time, etc. A user of the pathfinding system can choose one or more categories of elements to avoid. For example, the user may want to avoid toll roads in a map of roads. The costs associated with the elements to avoid includes at least two levels of representation. The two levels of representation include a first level and a second level such that the second level is superior to the first level. The pathfinding system will determine a path which minimizes costs.

Claims

1. A computer implemented method for finding a path between an origin and a destination using a processor readable representation of a network, comprising the steps of:

distinguishing a first set of one or more elements in said processor readable representation of said network, each of said first set of elements being associated with one or more original costs;

creating a first set of one or more new costs associated with said first set of elements, said one or more new costs including at least two levels of representation; and

determining a path in said processor readable representation of said network from said origin to said destination, using a processor, said step of determining uses at least one of said new costs.

2. A method according to claim 1, wherein:

said first set of elements is a set of links.

3. A method according to claim 1, wherein:

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

said first set of elements is a set of links representing toll roads.

4. A method according to claim 1, wherein:

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

said first set of elements is a link representing a toll road.

5. A method according to claim 1, wherein:

said step of distinguishing includes receiving an input from a user and identifying elements of said first set based on said input.

6. A method according to claim 1, wherein:

said step of distinguishing includes automatically, without user input, identifying elements of said first set.

7. A method according to claim 1, wherein:

said step of creating includes replacing a preexisting cost with said first cost, said preexisting cost only containing a non-zero magnitude for one level of representation.

8. A method according to claim 1, wherein:

said two levels of representation include a first level and a second level, said second level being superior to said first level.

9. A method according to claim 1, wherein:

said first cost is a non-standard number.

10. A method according to claim 1, wherein:

said first cost can be represented with a non-zero multiple of an infinite integer.

11. A method according to claim 1, wherein:

said first cost is stored in a multi-element data structure.

12. A method according to claim 1, wherein:

said first cost is stored in an array.

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

creating a cost model that includes at least two levels of representation.

14. A method according to claim 1, wherein:

said first set of elements includes a first element having a first cost, said first cost having two levels of representation, said first element represents an aggregate of links;

said two levels of representation of said first cost include a first level and a second level, said first level representing a count of said links in said aggregate.

15. A method according to claim 1, wherein:

said two levels of representation include a first level and a second level, a sum of a magnitude of said first level and a magnitude of said second level being an estimate of a quantity to be minimized.

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

reporting said path.

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

receiving an indication of said origin.

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

receiving an indication of said destination.

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

storing an indication of said origin; and

storing an indication of said destination.

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

distinguishing a second set of one or more elements in said electronic map to avoid; and

creating a second cost associated with a first element of said second set of elements, said second cost including non-zero magnitudes for at least three levels of representation, said step of performing uses said second cost.

21. A method according to claim 20, wherein:

said second cost being greater than said first cost, regardless of said first cost'"'"'s magnitudes and said second cost'"'"'s magnitudes.

22. A method according to claim 1, wherein:

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

23. A method according to claim 22, wherein:

said step of performing attempts to minimize costs.

24. A method according to claim 22, wherein:

said step of determining a path includes the steps of;

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 an origin,

initializing said priority queue,

finding a set of nodes adjacent to said origin,

determining a cost of traveling to each of said adjacent nodes from said origin,

inserting said adjacent nodes into said priority queue, sorted by key,

inserting said adjacent nodes into said visited list,

removing said origin from said priority queue,

finding a set of nodes adjacent to a node at said queue'"'"'s head,

determining a cost of traveling to each of said nodes adjacent to said node at said queue'"'"'s head,

inserting into said priority queue at least a subset of said nodes adjacent to said node at said queue'"'"'s head,

inserting into said visited list, if not already in said visited list with a lower costs, said nodes adjacent to said node at said queue'"'"'s head, and

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

25. A method according to claim 22, wherein:

said electronic map includes links and nodes and said first set of elements is a set of links; and

said two levels of representation include a first level and a second level, said second level being superior to said first level, said second level being a multiple of a non-zero power of an infinite integer.

26. A method for creating an electronic map, comprising the steps of:

identifying nodes,

identifying a set of links between nodes;

identifying a first subset of links to attempt to avoid;

assigning costs for traversing said set of links, at least a first subset of one or more costs including a first level of representation and a second level of representation, said second level of representation being superior to said first level of representation, said first subset of one or more costs being associated with said first subset of links; and

storing data representing said nodes, said links and said costs in a map database, said map database residing in a processor readable storage medium.

27. A method according to claim 26, wherein:

the step of storing includes storing data representing said costs in an array.

28. A method according to claim 26, wherein:

said second level of representation including a multiple of a non-zero power of an infinite number.

29. A machine including one or more processor readable storage elements, said one or more processor readable storage elements storing an electronic map generated by the method of claim 26, said one or more processor readable storage elements further include processor readable code for using said electronic map to determine a path from an origin to a destination.

30. A method of enhancing an electronic map database, said map database including nodes, links between nodes and costs of links, the method comprising the steps of:

receiving an input identifying a set of links to attempt to avoid;

creating an indication of a second level of costs for said set of links; and

storing said indication of second level of costs in a processor readable storage medium, said stored second level of costs being associated with said electronic map database such that said electronic map database and said second level of costs can be used to determine a path in said electronic map database from an origin to a destination that attempts to avoid said set of links.

31. A method according to claim 30, wherein:

the step of storing includes storing data representing said second level of costs in an array.

32. A method according to claim 30, wherein:

said step of creating includes replacing a preexisting cost with a new cost, said new cost being a product of said preexisting cost and an infinite number.

33. A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method of finding a path using a processor readable representation of a network, said processor readable code comprising:

first program code, said first program code finds a first path from a first node to a second node, said first path including a first set of one or more links and a first set of one or more costs;

second program code, said second program code finds a second path from said first node to said second node, said second path including a second set of one or more links and a second set of one or more costs, at least one of said second set of costs having at least two levels of representation, and

third program code, said third program code chooses said first path because said first set of one or more costs is more efficient than said second set of one or more costs.

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

said two levels of representation include a first level and a second level, said second level being superior to said first level.

35. A processor readable storage medium according to claim 34, further including:

fourth program code, said fourth program code creates a cost model for said network.

36. A processor readable storage medium according to claim 34, wherein said third program code chooses said first path at least partially based on dynamic traffic conditions.

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

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

38. A processor readable storage medium according to claim 37, wherein:

said third program code determines a first sum of said first set of costs and a second sum of said second set of costs; and

said third program code determines that said first sum is less than said second sum.

39. A processor readable storage medium according to claim 38, wherein:

said first sum and said second sum are stored in a computer memory.

40. An apparatus for finding a path from an origin to a destination using a processor readable representation of a network, comprising:

an input device;

a processor readable storage device capable of storing at least a portion of said processor readable representation of said network;

a display; and

a processor in communication with said input device, said storage device and said display, said processor being programmed to;

distinguish a first set of one or more elements in said network;

create a first cost associated with a first element of said first set of elements, said first cost including at least two levels of representation; and

determine a path from said origin to said destination using said first cost.

41. An apparatus according to claim 40, wherein:

said two levels of representation include a first level and a second level, said second level being superior to said first level.

42. A apparatus according to claim 40, wherein:

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

43. 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 of finding a path from an origin to a destination using a processor readable representation of a network, said method comprising the steps of:

distinguishing a first set of one or more elements in said network, each of said first set of elements being associated with one or more original costs;

creating a first set of one or more new costs associated with said first set of elements, said new costs including at least two levels of representation; and

determining a path in said processor readable representation of said network from said origin to said destination using at least one of said new costs.

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

reporting said path.

45. A processor readable storage medium according to claim 43, wherein:

said two levels of representation include a first level and a second level, said second level being superior to said first level.

46. A processor readable storage medium according to claim 45, wherein:

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

47. A processor readable storage medium according to claim 45, wherein:

said step of distinguishing can be used to identify a traffic problem; and

said step of determining finds a path that avoids said traffic problem.

48. 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 of finding a path from an origin to a destination using a processor readable representation of a network, said method comprising the steps of:

creating an indication of a second level of costs for a set of one or more elements in said processor readable representation of a network; and

determining a path in said processor readable representation of said network from said origin to said destination using said second level of costs.

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

storing said indication of said second level of costs.

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

reporting said path.