System for pathfinding

• US 6,016,485 A
• Filed: 02/13/1998
• Issued: 01/18/2000
• Est. Priority Date: 02/13/1998
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Suranyi, Edward Joseph, Amakawa, Koji
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US09/023,504
• Time in Patent Office: 704 Days
• Field of Search: 340/989, 340/990, 340/995, 364/400, 370/254, 370/255, 370/256, 370/351, 395/200.71, 701/25, 701/26, 701/201, 701/202, 705/400, 709/241, 700/90
• US Class Current: 705/400
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

A system is disclosed for determining a path in a network that decreases the number of disk accesses needed during the pathfinding computation. The network is divided in to a set of tiles. Certain sub-paths are pre-computed. The pre-computed sub-paths are grouped into webs. When finding a path, the system will perform a pathfinding exploration within the tile for the origin and a pathfinding exploration within the tile for the destination. A number of the webs will be used with the two explorations to determine a path from the origin to the destination.

Claims

1. A method for determining a path in a processor readable representation of a network from an origin to a destination, said processor readable representation of said network including one or more tiles, the method comprising the steps of:

determining whether said origin and said destination are located in a single tile;

determining whether said origin and said destination are located in tiles within a proximity threshold of each other;

performing a first path exploration with a processor to determine said path using a first set of one or more webs, if said origin and said destination are located in a single tile;

performing a second path exploration with said processor to determine said path using a second set of one or more webs, if said origin and said destination are located in tiles within said proximity threshold of each other;

performing a third path exploration with said processor to determine said path using a third set of one or more webs, if said origin and said destination are located in separate tiles not within said proximity threshold of each other; and

reporting said path.

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

receiving an indication of said origin; and

receiving an indication of said destination.

3. A method according to claim 1, wherein:

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

4. A method according to claim 1, wherein:

said first path exploration uses at least an origin tile and a first self web associated with said origin tile.

5. A method according to claim 4, wherein said step of performing a first path exploration includes the steps of:

exploring from said origin inside said origin tile; and

exploring from said destination within said origin tile and said first self web.

6. A method according to claim 1, wherein:

said second path exploration uses at least an origin tile, a first self web associated with said origin tile, a destination tile, a second self web associated with said destination tile and a too-close web.

7. A method according to claim 6, wherein said step of performing a second path exploration includes the steps of:

exploring from said origin using said origin tile and said first self web; and

exploring from said destination using said destination tile, said second self web and said too-close web.

8. A method according to claim 1, wherein:

said third path exploration uses at least an origin tile, a first vicinity web associated with said origin tile, a destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web.

9. A method according to claim 8, wherein:

said third path exploration additionally uses a first self web associated with said origin tile and a second self web associated with said destination tile; and

data for said first self web and data for said first vicinity web are combined.

10. A method according to claim 1, wherein:

said first path exploration uses at least an origin tile and a first self web associated with said origin tile;

said second path exploration uses at least an origin tile, a first self web associated with said origin tile, a destination tile, a second self web associated with said destination tile and a too-close web; and

said third path exploration uses at least an origin tile, a first self web associated with said origin tile, a first vicinity web associated with said origin tile, a destination tile, a second self web associated with said destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web.

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

receiving an indication of said origin; and

receiving an indication of said destination.

12. A method according to claim 1, wherein:

said third path exploration uses an origin tile, a first self web associated with said origin tile, a first vicinity web associated with said origin tile, a destination tile, a second self web associated with said destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web.

13. A method according to claim 12, wherein:

said step of performing a third path exploration includes building said path.

14. A method according to claim 12, wherein said step of performing a third path exploration includes the steps of:

exploring from said origin using said origin tile, said first vicinity web and said first self web; and

exploring from said destination using said destination tile, said second vicinity web, said second self web and said exit-to-entrance web.

15. A method according to claim 14, wherein:

said step of exploring from said destination proceeds until a priority queue is empty.

16. A method for determining a path in an electronic map of roads from an origin to a destination, said electronic map including one or more tiles, data representing said origin being part of a first tile in said electronic map, the method comprising the steps of:

reading data for at least said first tile;

determining whether said destination is in said first tile;

reading data for at least a second tile if said destination is not in said first tile;

determining whether said first tile is within a proximity threshold of said second tile, if said destination is not in said first tile;

reading data for at least an exit-to-entrance web, data for a first vicinity web and data for a second vicinity web, if said destination is not in said first tile and if said first tile is not within said proximity threshold of said second tile;

reading data for at least a first self web if said destination is in said first tile;

reading said data for at least said first self web, data for a second self web and data for a too-close web if said destination is not in said first tile and if said first tile is within said proximity threshold of said second tile;

performing one or more path explorations using a processor and at least said data read; and

reporting said path.

17. A method for using a processor to determine a path in an electronic map from an origin to a destination, said electronic map including one or more tiles, the method comprising the steps of:

determining whether said origin and said destination are located in a single tile;

determining whether said origin and said destination are located in tiles within a proximity threshold of each other;

performing a path exploration to determine said path, said step of performing a path exploration uses at least an origin tile, a first vicinity web associated with said origin tile, a destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web if said origin and said destination are located in tiles not within said proximity threshold of each others, and

reporting said path.

18. A method according to claim 17, wherein:

said step of performing a path exploration includes;

determining a path from said origin to said first vicinity web;

determining a path from said second vicinity web to said destination; and

determining a path from said first vicinity web to said second vicinity web.

19. A method for determining a path in an electronic map from an origin to a destination, said electronic map including data divided into tiles, the method comprising:

determining whether said origin and said destination are within a first tile;

reading data for said first tile;

reading data for a first self web, said first self web being associated with said first tile;

exploring, using a processor, between said origin and said destination using said data for said first tile and said data for said self web if said origin and said destination are both within said first tile, said step of exploring determines said path from said origin to said destination; and

reporting said path.

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

receiving an indication of said origin in said electronic map; and

receiving an indication of said destination in said electronic map.

21. A method according to claim 19, wherein:

said step of exploring includes a first exploration from said origin and a second exploration from said destination.

22. A method according to claim 21, wherein:

said first exploration uses said data for said first tile; and

said second exploration uses said data for said first tile and said data for said first self web.

23. 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 comprising the steps of:

determining whether said origin and said destination are located in a single tile;

determining whether said origin and said destination are located in tiles within a proximity threshold of each other;

performing a first path exploration to determine said path using a first set of one or more webs, if said origin and said destination are located in a single tile;

performing a second path exploration to determine said path using a second set of one or more webs, if said origin and said destination are located in tiles within said proximity threshold of each other; and

performing a third path exploration to determine said path using a third set of one or more webs, if said origin and said destination are located in separate tiles not within said proximity threshold of each other.

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

reporting said path.

25. A processor readable storage medium according to claim 23, wherein:

said second path exploration uses at least an origin tile, a first self web associated with said origin tile, a destination tile, a second self web associated with said destination tile and a too-close web.

26. A processor readable storage medium according to claim 23, wherein:

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

27. A processor readable storage medium according to claim 23, wherein:

said first path exploration uses at least an origin tile and a first self web associated with said origin tile.

28. A processor readable storage medium according to claim 27, wherein said step of performing a first path exploration includes the steps of:

exploring from said origin inside said origin tile; and

exploring from said destination within said origin tile and said first self web.

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

said third path exploration uses at least an origin tile, a first vicinity web associated with said origin tile, a destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web.

30. A processor readable storage medium according to claim 29, wherein said step of performing a third path exploration includes the steps of:

exploring from said origin using at least said origin tile and said first vicinity web; and

exploring from said destination using at least said destination tile, said second vicinity web and said exit-to-entrance web.

31. 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 determining a path in an electronic map from an origin to a destination, said electronic map including a plurality of tiles, the method comprising the steps of:

determining whether said origin and said destination are located in a single tile;

determining whether said origin and said destination are located in tiles within a proximity threshold of each other;

performing a path exploration to determine said path, said step of performing a path exploration uses at least an origin tile, a first vicinity web associated with said origin tile, a destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web if said origin and said destination are located in tiles not within said proximity threshold of each other, and

reporting said path.

32. An apparatus for determining a path in an electronic map from an origin to a destination, said electronic map including one or more tiles, comprising

an output device;

a processor, in communication with said output device; and

a processor readable storage medium for storing code, said processor readable storage medium being in communication with said processor, said code capable of programming said processor to perform the steps of;

determining whether said origin and said destination are located in a single tile,

determining whether said origin and said destination are located in tiles within a proximity threshold of each other,

performing a first path exploration to determine said path using a first set of one or more webs, if said origin and said destination are located in a single tile,

performing a second path exploration to determine said path using a second set of one or more webs, if said origin and said destination are located in tiles within said proximity threshold of each other,

performing a third path exploration to determine said path using a third set of one or more webs, if said origin and said destination are located in separate tiles not within said proximity threshold of each other, and

reporting said path.

33. An apparatus according to claim 32, wherein:

said first path exploration uses at least an origin tile and a first self web associated with said origin tile.

34. An apparatus according to claim 32, wherein:

said second path exploration uses at least an origin file, a first self web associated with said origin tile, a destination tile, a second self web associated with said destination tile and a too-close web.

35. An apparatus according to claim 32, wherein:

said third path exploration uses at least an origin tile, a first vicinity web associated with said origin tile, a destination tile, a second vicinity web associated with said destination tile and an exit-to-entrance web.

36. A method for using a processor to determine a path in an electronic map from an origin to a destination, said electronic map including one or more tiles, the method comprising the steps of:

determining whether said origin and said destination are located in tiles within a proximity threshold of each other;

performing a path exploration to determine said path using at least an origin tile, a too-close web and a destination tile if said origin and said destination are located in tiles within said proximity threshold of each other; and

reporting said path.

37. A method according to claim 36, wherein:

said step of performing a path exploration additionally uses a first self web associated with said origin tile and a second self web associated with said destination tile; and

said step of performing a path exploration includes the steps of;

exploring from said origin using said origin tile and said first self web, and

exploring from said destination using said destination tile, said second self web and said too-close web.

38. A method for using a processor to determine a path in an electronic map from an origin to a destination, said electronic map including one or more tiles, the method comprising the steps of:

reading data for at least a first tile, a first web of pre-computed paths and a second web of pre-computed paths, said origin being in said first tile;

performing a pathfinding exploration to find said path from said origin to said destination, said path traverses in said first tile, said first web and said second web; and

reporting said path.

39. A method for using a processor to determine a path in an electronic map from an origin to a destination, the method comprising the steps of:

reading data for a first region of said electronic map, said first region including said origin;

reading data for a second region of said electronic map, said second region including said destination;

reading data for a first set of pre-computed paths, said first set of pre-computed paths comprises pre-computed paths within a vicinity of said first region;

reading data for a second set of pre-computed paths, said second set of pre-computed paths comprises pre-computed paths between said first region and said second region;

performing a pathfinding exploration to determine said path from said origin to said destination using said data for said first region, said data for said second region, said data for said first set of pre-computed paths and said data for said second set of pre-computed paths; and

reporting said path.

40. A method according to claim 39, further including the step of:

reading data for a third set of pre-computed paths, said second set of pre-computed paths comprises pre-computed paths within a vicinity of said second region, said step of performing a pathfinding exploration uses said data for said third set of pre-computed paths.

41. A method according to claim 40, wherein:

said first region is a first tile;

said second region is a second tile;

said first set of pre-computed paths is a first vicinity web associated with said first tile;

said second set of pre-computed paths is a second vicinity web associated with said second tile; and

said third set of pre-computed paths is an exit-to-entrance web.

42. A method for using a processor to determine a path in an electronic map from an origin to a destination, the method comprising the steps of:

reading data for a first region of said electronic map, said first region including said origin;

reading data for a second region of said electronic map, said second region including said destination;

reading data for a first set of pre-computed paths, said first set of pre-computed paths comprises pre-computed paths within a vicinity of said second region;

reading data for a second set of pre-computed paths, said second set of pre-computed paths comprises pre-computed paths between said first region and said second region;

performing a pathfinding exploration to determine said path from said origin to said destination using said data for said first region, said data for said second region, said data for said first set of pre-computed paths and said data for said second set of pre-computed paths; and

reporting said path.

43. A method for using a processor to determine a path in an electronic map from an origin to a destination, the method comprising the steps of:

determining whether said origin and said destination are located within a proximity of each other;

performing a first path exploration to determine said path using a first set of one or more webs, if said origin and said destination are located within said proximity of each other;

performing a second path exploration to determine said path using a second set of one or more webs, if said origin and said destination are not located within said proximity of each other; and

reporting said path.

44. A method according to claim 43, wherein:

said first set of one or more webs includes a self web if said origin and said destination are in a single tile.

45. A method according to claim 43, wherein:

said first path exploration is only performed if said origin and said destination are located within said proximity of each other and said origin and said destination are not in a single tile; and

said method further includes the step of performing a third path exploration to determine said path using a third set of one or more webs, if said origin and said destination are located in a single tile.

46. A method according to claim 43, wherein:

said first path exploration is only performed if said origin and said destination are located within a single tile.

47. A method according to claim 43, wherein:

said first set of one or more webs includes a too-close web if said origin and said destination are not in a single tile.

48. A method for using a processor to determine a path in an electronic map from an origin to a destination, said electronic map including data divided into tiles, the method comprising the steps of:

determining whether said origin and said destination are within a proximity threshold of each other;

reading data for said first tile, said first tile includes said origin;

reading data for said second tile, said second tile includes said destination;

reading data for a too-close web associated with said first tile;

determining said path between said origin and said destination using said data for said first tile, said data for said second tile and said data for said too-close web if said origin and said destination are within a proximity threshold of each other; and

reporting said path.

49. A method according to claim 48, further including the steps of:

reading data for a first self web associated with said first tile;

reading data for a second self web associated with said second tile, said step of determining uses said data for said first self web and said data for said second self web.