Re-routing apparatus and method for calculating an optimum alternative path to an original path from a position deviated from the original path in a navigation system and a navigation system using the same

• US 7,363,153 B2
• Filed: 08/13/2003
• Issued: 04/22/2008
• Est. Priority Date: 04/24/2003
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Chon, Hae-Don, Nam, Joo-Hyun, Choi, Yong-Ik, Jeon, Ji-Youn
• Primary Examiner(s): Tran; Delena
• Application Number:
  US10/640,791
• Publication Number:
  US 20040215392A1
• Time in Patent Office: 1,714 Days
• Field of Search: 701/200, 701/201, 701/202, 701/207, 701/208, 701/209, 701/210, 701/211, 340/990, 340/988, 340/995
• US Class Current: 701/210
• 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: G08G 1/096811 where the route is computed offboard
• 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/096861 where the immediate route instructions are output to the driver, e.g. arrow signs for next turn
• CPC Class Codes: G08G 1/096883 where input information is obtained using a mobile device, e.g. a mobile phone, a PDA

Abstract

A re-routing apparatus and method for calculating an optimum path from a path deviated position to an original path in a navigation system, and a navigation system using this apparatus and method are disclosed. When a movable body traveling on a predetermined path provided from a navigation system has deviated from the path, links are selected which meet links extending in a direction having small accumulated travel cost from the deviated position link from among links included in the original path, and then paths traveling from the deviated position to the destination via the selected links are determined as re-routing paths. Accordingly, when the movable body has deviated from the predetermined path communication cost to connect with a server can be reduced and another deviation possibility due to time delay taken until new paths are provided can also be reduced by enabling the navigation terminal by itself to calculate the optimum path from the deviated position to the original path without connecting with the server.

Claims

1. A re-routing apparatus in a navigation system, the apparatus comprising:

a deviation information input section for receiving deviated position link information when a movable body traveling on a predetermined original path provided from the navigation system has deviated from the original path;

an adjacent link detecting and judging section for receiving link information and detecting link information of links adjacent to links corresponding to the received link information from map data and determining a relation between detected links and the original path in a process of calculating an optimum path from a deviated position to the original path, when the movable body has deviated from the original path;

a second table for temporarily storing said detected link information on the basis of a determination of the adjacent link detecting and judging section;

a path selecting section for analyzing said link information stored in the second table and selecting reserved links to be included in the optimum path from the deviated position link to any one link from among links included in the original path, on the basis of the judgment result of the adjacent link detecting and judging section;

a first table for storing the link information of the reserved links selected by the path selecting section; and

a re-routing information extracting section for extracting re-routing paths from said reserved links stored in the first table on the basis of the determination of the adjacent link detecting and judging section.

2. The re-routing apparatus as claimed in claim 1, wherein the deviation information input section transmits the deviated position link information to the adjacent link detecting and judging section and enables the adjacent link detecting and judging section to detect links adjacent to the deviated position link.

3. The re-routing apparatus as claimed in claim 1, wherein the second table stores link information including accumulated cost information from the deviated position to a corresponding link according to each link detected by the adjacent link detecting and judging section.

4. The re-routing apparatus as claimed in claim 3, wherein the path selecting section selects a link from among links stored in the second table as a reserved link which has a minimum accumulated cost, stores the selected link in the first table, transmits the reserved link information to the adjacent link detecting and judging section, and enables the adjacent link detecting and judging section to detect links adjacent to the reserved links.

5. The re-routing apparatus as claimed in claim 1, wherein the adjacent link detecting and judging section detects the deviated position link transmitted from the deviation information input section and the links adjacent to the reserved links selected by the path selecting section.

6. The re-routing apparatus as claimed in claim 5, wherein the adjacent link detecting and judging section determines if there exist links meeting the original path from among the detected adjacent links or if there exist destination links from among the detected adjacent links and controls an operation of the second table, the path selecting section and the re-routing information extraction section on the basis of the judgment result.

7. The re-routing apparatus as claimed in claim 6, wherein, as a result of the determination, when there are no links meeting the original path from among the detected adjacent links and there are no destination links from among the detected adjacent links, the adjacent link detecting and judging section stores the detected adjacent links in the second table.

8. The re-routing apparatus as claimed in claim 6, wherein as a result of the determination, when there are destination links from among the detected adjacent links, the adjacent link detecting and judging section enables the re-routing information extraction section to determine the re-routing paths by backtracking the destination link on the basis of the link information stored in the first table.

9. The re-routing apparatus as claimed in claim 6, wherein, as a result of the determination, when the detected adjacent links include at least one link, which is not a destination link but meets the original path, the adjacent link detecting and judging section enables the re-routing information extraction section to determine the re-routing paths by backtracking links meeting the original path, on the basis of the link information stored in the first table.

10. The re-routing apparatus as claimed in claim 6, wherein, as a result of the determination, when the detected adjacent links include at least one link, which is not a destination link but meets the original path, the adjacent link detecting and judging section enables the path selecting section to select a link having a minimum cost from among predetermined number of link information meeting the original path, which is a cost necessary for traveling from the deviated position to the destination via corresponding link, and enables the re-routing information extraction section to determine the re-routing paths by backtracking the links selected by the path selecting section, on the basis of the link information stored in the first table.

11. A re-routing method in a navigation system, the method comprising the steps of:

(1) when a movable body traveling on a predetermined original path provided from the navigation system has deviated from the path, extracting a deviated position link information from map data; and

(2) selecting links meeting links extending in a direction having small accumulated travel cost from the deviated position link from among links included in the original path and determining which paths are re-routing paths, wherein the re-routing paths are paths extending from a deviated position to the destination via the selected links.

12. The re-routing method as claimed in claim 11, wherein in step 2 a first one of links meeting a link extending in a direction having a small accumulated travel cost from the deviated position is determined as the re-routing path.

13. A re-routing method of a navigation system, the method comprising the steps of:

(1) when a movable body traveling on a predetermined original path provided from the navigation system has deviated from the path, extracting a deviated position link information from map data; and

(2) selecting links meeting links extending in a direction having small accumulated travel cost from the deviated position link from among links included in the original path and determining which paths are re-routing paths, wherein the re-routing paths are paths extending from a deviated position to the destination via the selected links, wherein a first one of links meeting a link extending in a direction having a small accumulated travel cost from the deviated position is determined as the re-routing path,

wherein step 2 further comprises;

(2-1) detecting link information adjacent to the deviated position link from map data;

(2-2) checking in sequence if there exists a destination link among the detected links or if there exists a link meeting the original path from among the detected links;

(2-3) as a result of checking in step 2-2, when there exists the destination link or the link meeting the original path among the detected links, determining which paths are re-routing paths to the destination via the link;

(2-4) as a result of checking in step 2-2, when there is no destination link or the link meeting the original path from among the detected links, storing the detected link information temporarily; and

(2-5) selecting a link with a minimum accumulated travel cost necessary for traveling from the deviated position link to the corresponding link from among the temporarily stored link information; and

repeating steps 2-1 to 2-5 after detecting link information adjacent to the selected link.

14. A re-routing method in a navigation system, the method comprising the steps of:

(1) when a movable body traveling on a predetermined original path provided from the navigation system has deviated from the path, extracting a deviated position link information from map data; and

(2) selecting links meeting links extending in a direction having small accumulated travel cost from the deviated position link from among links included in the original path and determining which paths are re-routing paths, wherein the re-routing paths are paths extending from a deviated position to the destination via the selected links, wherein, information about a predetermined number of links meeting the link extending in the direction having a small accumulated travel cost from the deviated position link is compared with each other, so as to select a link having a minimum sum of a first cost necessary for traveling from the deviated position to a corresponding link and a second cost necessary for traveling from the link to destination, and then a path from the deviated position through the selected link to the destination is determined as the re-routing path.

15. The re-routing method as claimed in claim 14, wherein step 2 further comprises the steps of:

(2-6) detecting link information adjacent to the deviated position link from said map data;

(2-7) checking if there exists a link meeting the original path among the detected links;

(2-8) as a result of checking in step 2-7, when there is no link meeting the original path from among the detected links, storing the link information temporarily, selecting a link has a minimum accumulated cost from among the stored link information, and repeating steps 2-6 to 2-8 after detecting links adjacent to the selected link;

(2-9) as a result of checking in step 2-7, when there exists the link meeting the original path from among the detected links, checking if a link of the original path, meeting the detected links is a destination link; and

(2-10) as a result of checking in step 2-9 when the link of the original path, meeting the detected links is the destination link, determining re-routing paths by backtracking the destination link.

16. The re-routing method as claimed in claim 15, wherein step 2 further comprises the steps of:

(2-11) as a result of checking in step 2-9 when the link of the original path meeting the detected links is not the destination link, storing the link information of the original path meeting the detected links, while counting the number of times by which the detected links and the original path meet each other;

(2-12) when the number of times, by which the detected links and the original path meet each other, is larger than a predetermined number set in advance in step (2-11), selecting a link has minimum cost necessary for traveling from the deviated position to the destination via corresponding link from among the already stored link information; and

(2-13) determining the re-routing paths by backtracking the link selected in step (2-12).

17. The re-routing method as claimed in claim 16, wherein, in step 2-11 only a link, which has minimum cost necessary for traveling to the destination via the link of the original path meeting the detected links, is stored until the number of times, by which the detected links and the original path meet each other, exceeds the predetermined number set in advance.

18. The re-routing method as claimed in claim 15, wherein step 2 further comprises the step of (2-14) determining a re-routing error, when the cost exceeds a predetermined cost set in advance, which is a cost necessary for traveling from the deviation from the original path to the destination via the link having minimum cost selected in step 2-12.

19. A navigation system comprising:

a re-routing apparatus comprising;

a first table for storing link information of reserved links selected by a path selecting section;

a second table for temporarily storing detected link information on the basis of a determination of an adjacent link detecting and judging section;

the path selecting unit coupled to both of the first and second tables,

wherein, the re-routing apparatus calculates an optimum path from a path deviated position to an original path received from an information server via a mobile terminal, when a movable body traveling on a predetermined original path provided from the navigation system has deviated from the original path.

20. The navigation system as claimed in claim 19, wherein the re-routing apparatus further comprises:

a deviation information input section for receiving deviated position link information, when the movable body has deviated from the original path;

the adjacent link detecting and judging section for receiving link information and detecting link information of links adjacent to links corresponding to the received link information from map data, and determining a relation between the detected links and the original path in a process of calculating an optimum path from the deviated position to the original path, when the movable body has deviated from the original path;

the path selecting section for analyzing the link information stored in the second table and selecting reserved links to be included in an optimum path from the deviated position link to any one link from among links included in the original path, on the basis of the determination of the adjacent link detecting and judging section; and

a re-routing information extracting section for extracting re-routing paths from the links stored in the first table, on the basis of the determination of the adjacent link detecting and judging section.

21. The navigation system as claimed in claim 20, wherein the deviation information input section transmits the deviated position link information to the adjacent link detecting and judging section, and enables the adjacent link detecting and judging section to detect links adjacent to the deviated position link.

22. The navigation system as claimed in claim 20, wherein the second table stores link information including accumulated cost information from the deviated position to a corresponding link according to each link detected by the adjacent link detecting and judging section.

23. The navigation system as claimed in claim 22, wherein the path selecting section selects a link from among the links stored in the second table as reserved link, which has a minimum accumulated cost, and stores the selected link in the first table, and transmits the reserved link information to the adjacent link detecting and judging section and enables the adjacent link detecting and judging section to detect links adjacent to the reserved links.

24. The navigation system as claimed in claim 20, wherein the adjacent link detecting and judging section detects the deviated position link transmitted from the deviation information input section and the links adjacent to the reserved links selected by the path selecting section.

25. The navigation system as claimed in claim 24, wherein the adjacent link detecting and judging section determines if there exists links meeting the original path from among the detected adjacent links, or if there exists destination links from among the detected adjacent links, and controls an operation of the second table, the path selecting section and the re-routing information extraction section on the basis of the determination.

26. The navigation system as claimed in claim 25, wherein as a result of the determination, when there are no links meeting the original path from among the detected adjacent links and there are no destination links from among the detected adjacent links, the adjacent link detecting and judging section stores the detected adjacent links in the second table.

27. The navigation system as claimed in claim 25, wherein as a result of the determination, when there are destination links from among the detected adjacent links, the adjacent link detecting and judging section enables the re-routing information extraction section to determine the re-routing paths by backtracking the destination link, on the basis of the link information stored in the first table.

28. The navigation system as claimed in claim 25, wherein as a result of the determination, when the detected adjacent links include at least one link, which is not a destination link but meets the original path, the adjacent link detecting and judging section enables the re-routing information extraction section to determine the re-routing paths by backtracking links meeting the original path, on the basis of the link information stored in the first table.

29. The navigation system as claimed in claim 25, wherein as a result of the determination, when the detected adjacent links include at least one link, which is not a destination link but meets the original path, the adjacent link detecting and judging section enables the path selecting section to select a link having a minimum cost from among predetermined number of link information meeting the original path, which is an cost necessary for traveling from the deviated position to the destination via corresponding link, and enables the re-routing information extraction section to determine the re-routing paths by backtracking the links selected by the path selecting section, on the basis of the link information stored in the first table.