Turn restriction handling enhancement

• US 20030140022A1
• Filed: 12/27/2002
• Published: 07/24/2003
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: Autodesk, Inc.
• Inventors: Miller, Martin, Robinson, Kevin Glen
• Granted Patent: US 7,124,199 B2
• Time in Patent Office: Days
• US Class Current: 706/19
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method, apparatus, and article of manufacture determine a path on a network. A Global search is commenced for one or more Global paths on the network. Thereafter, when a turn restriction on a first node on the network exists, a hidden node that is not reachable from the first node due to the turn restriction is detected. A Local search commences from the hidden node in a reverse direction creating a Local search path. When the Local search can connect to the Global search, the Local search path is converted to a new Global path, and added as an alternative to the Global search.

Claims

1. A computer-implemented method for determining a path on a network, comprising:

(a) commencing a Global search for one or more Global paths on the network;

(b) determining when a turn restriction on a first node on the network exists;

(c) detecting a hidden node that is not reachable from the first node due to the turn restriction;

(d) commencing a Local search from the hidden node in a reverse direction creating a Local search path; and

(e) when the Local search can connect to the Global search;

(i) converting the Local search path to a new Global path; and

(ii) adding the new Global path as an alternative to the Global search.

2. The method of claim 1, wherein the Local search and the Global search proceed in parallel.

3. The method of claim 2, wherein the Local search starts one or more steps behind the Global search.

4. The method of claim 2, wherein the Local search proceeds at a slower speed than the Global search.

5. The method of claim 1, further comprising:

specifying a maximum number of search steps for the Local search; and

abandoning the Local search when the maximum number has been reached.

6. The method of claim 1, wherein the Local search keeps track of visited nodes and links that were used to arrive at the visited nodes, to ensure that visited nodes can be revisited using all possible links.

7. The method of claim 1, further comprising abandoning the Local search if the hidden node is found by the Global search.

8. The method of claim 1, further comprising abandoning the Local search.

9. The method of claim 1, wherein detecting a hidden node that is not reachable from the first node due to the turn restriction comprises:

obtaining an eligible list that comprises a first list of all links that can be used to travel out of the first node;

obtaining a pending list that comprises a second list of all links that would be applicable to the first node in all other respects except for the turn restriction; and

determining that a hidden node is not reachable from the first node due to the turn restriction when the pending list is not empty.

10. The method of claim 1, wherein the Local search is conducted in a Local search space, wherein the Local search space comprises:

a Local open list comprising directed nodes that have not yet been examined; and

a Local closed list comprising directed nodes that have already been examined.

11. An apparatus for determining a path on a network in computer system comprising:

(a) a computer system having a memory and a data storage device coupled thereto;

(b) an application executing on the computer, wherein the application is configured to;

(i) commence a Global search for one or more Global paths on the network;

(ii) determine when a turn restriction on a first node on the network exists;

(iii) detect a hidden node that is not reachable from the first node due to the turn restriction;

(iv) commence a Local search from the hidden node in a reverse direction creating a Local search path; and

(v) when the Local search can connect to the Global search;

(1) convert the Local search path to a new Global path; and

(2) add the new Global path as an alternative to the Global search.

12. The apparatus of claim 11, wherein the Local search and the Global search proceed in parallel.

13. The apparatus of claim 12, wherein the Local search starts one or more steps behind the Global search.

14. The apparatus of claim 12, wherein the Local search proceeds at a slower speed than the Global search.

15. The apparatus of claim 11, wherein the application is further configured to:

specify a maximum number of search steps for the Local search; and

abandon the Local search when the maximum number has been reached.

16. The apparatus of claim 11, wherein the Local search keeps track of visited nodes and links that were used to arrive at the visited nodes, to ensure that visited nodes can be revisited using all possible links.

17. The apparatus of claim 11, wherein the application is further configured to abandon the Local search if the hidden node is found by the Global search.

18. The apparatus of claim 11, wherein the application is further configured to abandon the Local search when the Local search can connect to the Global search.

19. The apparatus of claim 11, wherein the application is configured to detect a hidden node that is not reachable from the first node due to the turn restriction by:

obtaining an eligible list that comprises a first list of all links that can be used to travel out of the first node;

obtaining a pending list that comprises a second list of all links that would be applicable to the first node in all other respects except for the turn restriction; and

determining that a hidden node is not reachable from the first node due to the turn restriction when the pending list is not empty.

20. The apparatus of claim 11, wherein the Local search is conducted in a Local search space, wherein the Local search space comprises:

a Local open list comprising directed nodes that have not yet been examined; and

a Local closed list comprising directed nodes that have already been examined.

21. An article of manufacture comprising a program storage medium readable by a computer and embodying one or more instructions executable by the computer to perform a method for determining a path on a network, the method comprising:

(a) commencing a Global search for one or more Global paths on the network;

(b) determining when a turn restriction on a first node on the network exists;

(c) detecting a hidden node that is not reachable from the first node due to the turn restriction;

(d) commencing a Local search from the hidden node in a reverse direction creating a Local search path; and

(e) when the Local search can connect to the Global search;

(i) converting the Local search path to a new Global path; and

(ii) adding the new Global path as an alternative to the Global search.

22. The article of manufacture of claim 21, wherein the Local search and the Global search proceed in parallel.

23. The article of manufacture of claim 22, wherein the Local search starts one or more steps behind the Global search.

24. The article of manufacture of claim 22, wherein the Local search proceeds at a slower speed than the Global search.

25. The article of manufacture of claim 21, wherein the method further comprises:

specifying a maximum number of search steps for the Local search; and

abandoning the Local search when the maximum number has been reached.

26. The article of manufacture of claim 21, wherein the Local search keeps track of visited nodes and links that were used to arrive at the visited nodes, to ensure that visited nodes can be revisited using all possible links.

27. The article of manufacture of claim 21, wherein the method further comprises abandoning the Local search if the hidden node is found by the Global search.

28. The article of manufacture of claim 21, the method further comprises abandoning the Local search when the Local search can connect to the Global search.

29. The article of manufacture of claim 21, wherein detecting a hidden node that is not reachable from the first node due to the turn restriction comprises:

obtaining an eligible list that comprises a first list of all links that can be used to travel out of the first node;

obtaining a pending list that comprises a second list of all links that would be applicable to the first node in all other respects except for the turn restriction; and

determining that a hidden node is not reachable from the first node due to the turn restriction when the pending list is not empty.

30. The article of manufacture of claim 21, wherein the Local search is conducted in a Local search space, wherein the Local search space comprises:

a Local open list comprising directed nodes that have not yet been examined; and

a Local closed list comprising directed nodes that have already been examined.