ROUTE DETERMINATION SYSTEM

• US 20090276150A1
• Filed: 05/05/2008
• Published: 11/05/2009
• Est. Priority Date: 05/04/2007
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Inventors: Vorlander, Peter
• Granted Patent: US 9,129,530 B2
• Time in Patent Office: Days
• 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
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver

Abstract

A system for determining a route is provided. The system includes a method for determining estimation function values corresponding to a plurality of vertices on a first graph, where the first graph corresponds to a first route network. The method further includes searching for a first route from a first starting point to the destination on a second graph based on the estimation function values. The system further includes a storage unit and a processor coupled to the storage unit for receiving graph data, where the processor is configured to determine estimation function values corresponding to a plurality of vertices on the first graph corresponding to a first route network, and is further configured to search for a route from a first starting point to the destination on a second graph based on the estimation function values. The device may further include an input unit, a clock unit, a traffic message receiver, and/or a position determining unit.

Claims

1. A method of determining a route comprising:

determining estimation function values corresponding to a plurality of vertices on a first graph corresponding to a first route network, where an estimation function value for a vertex in the plurality of vertices represents a lower bound on costs associated with a route from the vertex to a destination; and

searching for a first route from a first starting point to the destination on a second graph based on the estimation function values, the second graph associated with a plurality of elements.

2. The method of claim 1, where the step of determining an estimation function value for the vertex comprises searching for a route on the first graph from the vertex to the destination on the first graph.

3. The method of claim 2, where the step of searching for the route from the vertex to the destination is performed using Dijkstra'"'"'s algorithm on the first graph.

4. The method of claim 2, where the step of searching for the route from the vertex to the destination is performed using an A*-algorithm on the first graph.

5. The method of claim 2, where the step of determining an estimation function value for the vertex comprises searching for a route on the first graph starting at the destination and expanding towards the first starting point.

6. The method of claim 1 further comprising searching for a second route from the first starting point to the destination on the second graph based on the estimation function values, the second route being different from the first route.

7. The method of claim 6, where the second route comprises at least one of an alternative route from the starting point to the destination or a route from a second starting point to the destination.

8. The method of claim 6, further comprising monitoring a current position relative to the first route from the original starting point to the destination, where the step of searching for the second route is automatically initiated based on a result of the step of monitoring the current position.

9. The method of claim 6 further comprising monitoring changes of costs associated with at least one of the elements of the second graph, where the step of searching for the second route is automatically initiated based on a result of the step of monitoring changes of costs.

10. The method of claim 1 further comprising:

storing at least a subset of the estimation function values; and

retrieving at least one estimation function value from the subset.

11. The method of claim 1, where the step of determining the estimation function values is done using a first cost model, and the step of searching for the first route is done using a second cost model.

12. The method of claim 11, where costs associated with at least one element of the first graph according to the first cost model are time-independent.

13. The method of claim 11, where costs associated with at least one of the plurality of elements of the second graph according to the second cost model are variable.

14. The method of claim 13, further comprising:

adjusting the costs based on at least one of user preferences, a traffic information signal, a time of day, or a date.

15. The method of claim 14, where the step of adjusting comprises increasing the costs for at least one element relative to the first cost model.

16. The method of claim 13, where costs associated with an element of the first graph according to a first cost model represent a lower bound on costs associated with a corresponding element of the second graph according to the second cost model.

17. The method of claim 1, where the first graph is defined so that an average time to search for a route on the first graph is faster than an average time to search for a route on the second graph.

18. The method of claim 1, where the first graph has fewer vertices than the second graph.

19. The method of claim 1, where each vertex in the plurality of vertices on the first graph represents at least one road segment of a road network, the method further comprising the step of neglecting turning restrictions on the road network.

20. The method of claim 19, further comprising the step of considering one-way restrictions in determining the route.

21. The method of claim 1, where the first graph includes a plurality of edges, each edge in the plurality of edges representing at least one road segment of a road network;

and where the second graph includes a plurality of vertices, each vertex in the plurality of vertices representing at least one road segment of the road network.

22. The method of claim 20, where one of the first graph and the second graph is a dual graph of the other.

23. The method of claim 1, where the first graph is identical to the second graph.

24. The method of claim 1, further comprising:

performing a route search on a third graph; and

utilizing a result of the route search on the third graph to determine the estimation function values for the plurality of vertices.

25. The method of claim 1, where the step of determining an estimation function value for the vertex comprises searching for a route from the vertex to the destination on the first graph based on pre-calculated information on the first graph.

26. The method of claim 1, further comprising:

determining whether an estimation function value for a given vertex has been determined; and

if no estimation function value for the given vertex has been determined, determining the estimation function value for the given vertex.

27. The method of claim 1, where the first graph and the second graph each represents one of a road network, a computer network, a ferry connection, a data connection, a network of power transmission line, a network of airplane routes, or an infrastructure network.

28. The method of claim 1, where the method is performed by a navigation system.

29. A device for determining a route to a destination comprising:

a storage unit for storing data defining a plurality of elements for at least one of a first graph and a second graph; and

a processor coupled to the storage unit to retrieve the graph data, where the processor is configured to determine estimation function values corresponding to a plurality of vertices on the first graph corresponding to a first route network, where an estimation function value for a vertex in the plurality of vertices represents a lower bound on costs associated with a route from the vertex to a destination, and to search for a route from a first starting point to the destination on a second graph based on the estimation function values, the second graph associated with a plurality of elements.

30. The device of claim 29, where the processor is configured to search for a route on the first graph to determine the estimation function values.

31. The device of claim 29, where the processor is configured to search for a route starting at the destination and expanding towards the first starting point to determine the estimation function values.

32. The device of claim 29, where the processor is configured to search for a route to the destination based on the determined estimation function values.

33. The device of claim 29, further comprising:

a second storage unit coupled to the processor for storing the determined estimation function values.

34. The device of claim 29, where the processor is configured to determine the estimation function values based on a first cost model, and to search for the route from the starting point to the destination based on a second cost model.

35. The device of claim 34, where costs associated with at least one element of the first graph according to the first cost model are time-independent.

36. The device of claim 35 where costs associated with at least one of the plurality of element of the second graph according to the second cost model are variable.

37. The device of claim 34, where costs associated with an element of the first graph according to a first cost model represent a lower bound on costs associated with a corresponding element of the second graph according to the second cost model.

38. The device of claim 34, further comprising:

an input unit coupled to the processor to receive a user input, where the processor is configured to adjust costs associated with the second cost model based on the user input.

39. The device of claim 34, further comprising:

a clock unit coupled to the processor and configured to determined at least one of a time and date, where the processor is configured to adjust costs associated with the second cost model based on the at least one of the time and date.

40. The device of claim 34, further comprising:

a traffic message receiver coupled to the processor and configured to receive a traffic information signal, where the processor is configured to adjust costs associated with the second cost model based on the traffic information signal.

41. The device of claim 34, where the processor is configured to adjust costs associated with the second cost model by increasing the costs associated with the second cost model for at least one element relative to the first cost model.

42. The device of claim 29 further comprising:

a position determining unit couple to the processor to determine a current vehicle position, where the processor is configure to compare the current vehicle position to the route from the starting point to the destination, and to search for a route from the current vehicle position to the destination on the second graph based on a result of the comparison.

43. The device of claim 29, where the first graph is defined so that an average time to search for a route on the first graph is faster than an average time to search for a route on the second graph.

44. A navigation system, comprising:

a device for determining a route to a destination, the device comprising;

a storage unit for storing data defining a plurality of elements for at least one of a first graph and a second graph; and

a processor coupled to the storage unit to retrieve the graph data, where the processor is configured to determine estimation function values corresponding to a plurality of vertices on the first graph corresponding to a first route network, where an estimation function value for a vertex in the plurality of vertices represents a lower bound on costs associated with a route from the vertex to a destination, and to search for a route from a first starting point to the destination on a second graph based on the estimation function values, the second graph associated with a plurality of elements; and

an output unit to output information corresponding to the route.

45. A tangible machine readable medium containing a sequence of instructions executable by a processor for executing a method of determining a route, the method comprising:

determining estimation function values corresponding to a plurality of vertices on a first graph corresponding to a first route network, where an estimation function value for a vertex in the plurality of vertices represents a lower bound on costs associated with a route from the vertex to a destination; and

searching for a first route from a first starting point to the destination on a second graph based on the estimation function values, the second graph associated with a plurality of elements.

46. The tangible machine readable medium of 45, where the step of determining an estimation function value for the vertex comprises searching for a route on the first graph from the vertex to the destination on the first graph.

47. The tangible machine readable medium of 46, where the step of searching for the route from the vertex to the destination is performed using Dijkstra'"'"'s algorithm on the first graph.

48. The tangible machine readable medium of 46, where the step of searching for the route from the vertex to the destination is performed using an A*-algorithm on the first graph.

49. The tangible machine readable medium of 46, where the step of determining an estimation function value for the vertex comprises searching for a route on the first graph starting at the destination and expanding towards the first starting point.

50. The tangible machine readable medium of 45, the method further comprising searching for a second route from the first starting point to the destination on the second graph based on the estimation function values, the second route being different from the first route.

51. The tangible machine readable medium of 50, where the second route comprises at least one of an alternative route from the starting point to the destination or a route from a second starting point to the destination.

52. The tangible machine readable medium of 50, the method further comprising monitoring a current position relative to the first route from the original starting point to the destination, where the step of searching for the second route is automatically initiated based on a result of the step of monitoring the current position.

53. The tangible machine readable medium of 50, the method further comprising monitoring changes of costs associated with at least one of the elements of the second graph, where the step of searching for the second route is automatically initiated based on a result of the step of monitoring changes of costs.

54. The tangible machine readable medium of 45, the method further comprising:

storing at least a subset of the estimation function values; and

retrieving at least one estimation function value from the subset.

55. The tangible machine readable medium of 45, where the step of determining the estimation function values is done using a first cost model, and the step of searching for the first route is done using a second cost model.

56. The tangible machine readable medium of 55, where costs associated with at least one element of the first graph according to the first cost model are time-independent.

57. The tangible machine readable medium of 55, where costs associated with at least one of the plurality of elements of the second graph according to the second cost model are variable.

58. The tangible machine readable medium of 57, the method further comprising:

adjusting the costs based on at least one of user preferences, a traffic information signal, a time of day, or a date.

59. The tangible machine readable medium of 58, where the step of adjusting comprises increasing the costs for at least one element relative to the first cost model.

60. The tangible machine readable medium of 57, where costs associated with an element of the first graph according to a first cost model represent a lower bound on costs associated with a corresponding element of the second graph according to the second cost model.

61. The tangible machine readable medium of 45, where the first graph is defined so that an average time to search for a route on the first graph is faster than an average time to search for a route on the second graph.

62. The tangible machine readable medium of 45, where the first graph has fewer vertices than the second graph.

63. The tangible machine readable medium of 45, where each vertex in the plurality of vertices on the first graph represents at least one road segment of a road network, the method further comprising the step of neglecting turning restrictions on the road network.

64. The tangible machine readable medium of 63, the method further comprising the step of considering one-way restrictions in determining the route.

65. The tangible machine readable medium of 45, where the first graph includes a plurality of edges, each edge in the plurality of edges representing at least one road segment of a road network;

and where the second graph includes a plurality of vertices, each vertex in the plurality of vertices representing at least one road segment of the road network.

66. The tangible machine readable medium of 64, where one of the first graph and the second graph is a dual graph of the other.

67. The tangible machine readable medium of 45, where the first graph is identical to the second graph.

68. The tangible machine readable medium of 45, the method further comprising:

performing a route search on a third graph; and

utilizing a result of the route search on the third graph to determine the estimation function values for the plurality of vertices.

69. The tangible machine readable medium of 45, where the step of determining an estimation function value for the vertex comprises searching for a route from the vertex to the destination on the first graph based on pre-calculated information on the first graph.

70. The tangible machine readable medium of 45, the method further comprising:

determining whether an estimation function value for a given vertex has been determined; and

if no estimation function value for the given vertex has been determined, determining the estimation function value for the given vertex.

71. The tangible machine readable medium of 45, where the first graph and the second graph each represents one of a road network, a computer network, a ferry connection, a data connection, a network of power transmission line, a network of airplane routes, or an infrastructure network.

72. The tangible machine readable medium of 45, where the method is performed by a navigation system.