Navigation method, medium, and system

• US 8,392,111 B2
• Filed: 08/03/2007
• Issued: 03/05/2013
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ryu, Hee-seob, Lea, Jong-ho, Lee, Yong-beom
• Primary Examiner(s): Jen, Ian
• Application Number:
  US11/882,699
• Publication Number:
  US 20080033636A1
• Time in Patent Office: 2,041 Days
• Field of Search: 701/209, 701/210, 701/200, 359/124
• US Class Current: 701/410
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

A method, medium, and system providing an updating traveling route to a user. The navigation system includes a route selecting unit to select an optimal route for an item to traverse based on calculated performance indexes of a plurality of alternative routes for the traversal, a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received external information regarding sections of available traversals after a predetermined point in each alternative route beyond a current point of the current traversal, and a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes.

Claims

1. A navigation system included in an item, comprising:

a route selecting unit to select an optimal route to a destination point for traversal by the item based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received congestion information from a remote device, remote from the navigation system, of respectively identified sections of available traversals after a predetermined point in each of the alternative routes beyond a current point of the current traversal;

a requesting unit to request, from the remote device, congestion information regarding each of the respectively identified sections of the available traversals after the predetermined point in one or more of the alternative routes beyond the current point of the current traversal; and

a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes,

wherein the remote device provides congestion information on a plurality of positions or sections to one or more items for respective item traversals, and

wherein the item and the one or more items are mobile devices.

2. The navigation system of claim 1, wherein the requesting unit

requests, from the remote device, the congestion information regarding the sections of the available traversals after the predetermined point in each of the alternative routes beyond the current point of the current traversal.

3. The navigation system of claim 1, wherein the remote device is a navigation server comprising a database with the congestion information on the plurality of positions or sections available for traversal.

4. The navigation system of claim 1, wherein the predetermined point is a predetermined crossroad in each of the alternative routes before the item traveling along the current traversal reaches the predetermined crossroad.

6. The navigation system of claim 1, wherein a performance index of an alternative route is a sum of performance indexes of a plurality of sections that are divided from a corresponding predetermined point on the alternative route.

7. The navigation system of claim 6, wherein the performance index is determined by at least one of a time required to pass through each divided section, the distance of each divided section, information on a fare for each divided section, and traffic information of each divided section.

8. The navigation system of claim 1, wherein, when a specific condition is identified by the remote device as occurring in a predetermined alternative route, the performance index calculating unit predicts an affected point where the item will encounter an area that is affected by the specific condition, and recalculates the performance indexes of the alternative routes based on the performance indexes of the sections divided from the predetermined point, the predicted affected point, and an identified point where the specific condition originates or occurs.

9. The navigation system of claim 8, wherein the performance index calculating unit predicts the affected point based on a traveling speed of the item and a determined spread rate for the specific condition in the area.

10. The navigation system of claim 8, wherein the performance index calculating unit predicts the affected point based on at least one of a deterministic queuing theory and a shockwave theory.

11. The navigation system of claim 1, wherein one or more of other items traversing routes in respective sections of available traversals beyond the current point of the current traversal provide the congestion information to the navigation system regarding the respective sections of the available traversals beyond the current point of the current traversal.

12. The navigation system of claim 1, further comprising:

an output unit to selectively output information on the optimal route and the updated optimal route.

13. The navigation system of claim 1, further comprising:

a detecting unit to detect a specific condition related to a traveling state of the item; and

a transmitting unit to transmit congestion information on a corresponding section in which the specific condition is detected to the remote device for provision to other navigation systems.

14. The navigation system of claim 13, wherein the specific condition is a variation in a traversal speed of the item.

15. The navigation system of claim 1, wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on the received external information if a request for the received congestion information is sent to the remote device, where the request is sent to the remote device when a traversal time for the item to reach the predetermined point meets a predetermined threshold time.

36. The navigation system of claim 1, wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the performance index calculating unit to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.

5. A navigation system, comprising:

a route selecting unit to select an optimal route to a destination point for traversal by an item to traverse based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received external information of respectively identified sections of available traversals after a predetermined point in each of the alternative routes beyond a current point of the current traversal;

a requesting unit to request, from an external device, the external information regarding each of the respective identified sections of the available traversals after the predetermined point in one or more of the alternative routes beyond the current point of the current traversal; and

a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes,

wherein the item is a vehicle and the navigation system is a navigation system within the vehicle.

34. The navigation system of claim 5, wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the performance index calculating unit to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.

16. A navigation method, comprising:

selecting an optimal route to a destination point for traversal by an item based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

recalculating the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received congestion information from a remote device of respectively identified sections of available traversals after a predetermined point in each of the alternative routes beyond a current point of the current traversal;

requesting from the remote device the congestion information regarding the sections of the available traversals after the predetermined point in one or more of the alternative routes beyond the current point of the current traversal; and

selectively updating and outputting the optimal route during the current traversal based on the recalculated performance indexes,

wherein the remote device provides congestion information on a plurality of positions or sections to one or more items for respective item traversals, and is remote from a navigation system, of the item, performing the selecting, recalculating, and selective updating.

17. The navigation method of claim 16, wherein the

requesting from the remote device of the congestion information is regarding the sections of the available traversals after the predetermined point in each of the alternative routes beyond the current point of the current traversal.

18. The navigation method of claim 16, wherein the predetermined point is a predetermined crossroad in each of the alternative routes before the item traveling along the current traversal reaches the predetermined crossroad.

19. The navigation method of claim 16, wherein the item is a vehicle and the navigation system is a navigation system within the vehicle.

20. The navigation method of claim 16, wherein a performance index of an alternative route is a sum of performance indexes of a plurality of sections that are divided from a corresponding predetermined point on the alternative route.

21. The navigation method of claim 20, wherein the performance index is determined by at least one of a time required to pass through each divided section, the distance of each divided section, information on a fare for each divided section, and traffic information of each divided section.

22. The navigation method of claim 16, wherein, when a specific condition is identified by the remote device as occurring in a predetermined alternative route, the navigation method further comprises predicting an affected point where the item will encounter an area that is affected by the specific condition, and recalculating the performance indexes of the alternative routes based on the performance indexes of the sections divided from the predetermined point, the predicted affected point, and an identified point where the specific condition originates or occurs.

23. The navigation method of claim 22, wherein the predicting of the affected point further comprises predicting the affected point based on a traveling speed of the item and a determined spread rate for the specific condition in the area.

24. The navigation method of claim 22, wherein the predicting of the affected point further comprises predicting the affected point based on at least one of a deterministic queuing theory and a shockwave theory.

25. The navigation method of claim 16, further comprising providing, from one or more of other items traversing routes in respective sections of available traversals beyond the current point of the current traversal, the congestion information to the navigation system regarding the respective sections of the available traversals beyond the current point of the current traversal.

26. The navigation method of claim 16, further comprising:

detecting a specific condition related to a traveling state of the item; and

transmitting congestion information on a corresponding section in which the specific condition is detected to the remote device for provision to external navigation systems.

27. The navigation method of claim 26, wherein the specific condition is a variation in a traversal speed of the item.

28. The navigation method of claim 16, further comprising selectively requesting the received congestion information based a traversal time for the item to reach the predetermined point meeting a predetermined threshold time.

29. At least one non-transitory medium comprising computer readable code to control at least one processing element to implement the method of claim 16.

35. The navigation method of claim 16, wherein the recalculating of the performance indexes of the alternative routes during the current traversal of the selected optimal route is based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the recalculating of the performance indexes to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.

30. A navigation system of an item, comprising:

a route selecting unit to select an optimal route for traversal by the item based on calculated performance indexes of a plurality of alternative routes for the traversal;

a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received congestion information from a remote device, remote from the navigation system, of respectively identified sections of available traversals after a predetermined point in each of the alternative routes beyond a current point of the current traversal;

a requesting unit to request, from the remote device, the congestion information regarding each of the respective identified sections of the available traversals after the predetermined point in one or more of the alternative routes beyond the current point of the current traversal; and

a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes,

wherein the remote device provides congestion information on a plurality of positions or sections to one or more items for respective item traversals,

wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted to encounter traffic congestion after the traffic congestion spreads from an origination point.

31. A navigation system, comprising:

a route selecting unit to select an optimal route to a destination point for traversal by an item to traverse based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received external information regarding sections of available traversals after a predetermined point in each alternative route beyond a current point of the current traversal; and

a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes,

wherein the item is a vehicle and the navigation system is a navigation system within the vehicle, and

wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the performance index calculating unit to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.

32. A navigation method, comprising:

selecting an optimal route to a destination point for traversal by an item based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

recalculating the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received congestion information from a remote device regarding sections of available traversals after a predetermined point in each alternative route beyond a current point of the current traversal; and

selectively updating and outputting the optimal route during the current traversal based on the recalculated performance indexes,

wherein the remote device provides congestion information on a plurality of positions or sections to one or more items for respective item traversals, and is remote from a navigation system, of the item, performing the selecting, recalculating, and selective updating, and

wherein the recalculating of the performance indexes of the alternative routes during the current traversal of the selected optimal route is based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the recalculating of the performance indexes to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.

33. A navigation system included in an item, comprising:

a route selecting unit to select an optimal route to a destination point for traversal by the item based on calculated performance indexes of a plurality of alternative routes to the destination point for the traversal;

a performance index calculating unit to recalculate the performance indexes of the alternative routes during a current traversal of the selected optimal route based on received congestion information from a remote device, remote from the navigation system, regarding sections of available traversals after a predetermined point in each alternative route beyond a current point of the current traversal; and

a route changing unit to selectively update the optimal route during the current traversal based on the recalculated performance indexes,

wherein the remote device provides congestion information on a plurality of positions or sections to one or more items for respective item traversals,

wherein the item and the one or more items are mobile devices, and

wherein the performance index calculating unit recalculates the performance indexes of the alternative routes during the current traversal of the selected optimal route based on at least one predicted point in the sections beyond the current point of the current traversal for respective alternative routes where the item is predicted by the performance index calculating unit to encounter predicted traffic congestion, wherein the predicted traffic congestion is a prediction of a spreading of known traffic congestion from a known origination point of the known traffic congestion.