Path searching system using multiple groups of cooperating agents and method thereof

• US 20040143560A1
• Filed: 12/23/2003
• Published: 07/22/2004
• Est. Priority Date: 01/20/2003
• Status: Abandoned Application

• Current Assignee: Nanyang Polytechnic
• Original Assignee: Nanyang Polytechnic
• Inventors: Zhu, Chun Bao
• Application Number:
  US10/742,950
• Publication Number:
  US 20040143560A1
• Time in Patent Office: Days
• US Class Current: 706/19
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A path searching system (10) based on ACO with a graph generator (12), a path-searching engine (14), a storage medium (16), and a path optimizer (18). Output (20) of the system (10) is an optimal path containing a list of nodes and node links from a start node to a destination node. The graph generator (12) comprises a graph constructor (24), an editor (26), and a search definer (28) and couples to the storage medium (16) to generate a source graph. The path-searching engine (14) processes user inputs from a user input interface (22) that include information specifying a searching problem such as, for example, details of the start node, the destination node, and one or more optimization criteria for the optimal path. The source graph is constructed by the graph constructor (24) based on node/link data (30) and constraint information (32).

Claims

1. A path searching system based on ant colony optimization, said path searching system comprising:

at least one storage medium; and

a path searching engine, coupled to said at least one storage medium, said path searching engine being adapted to perform path searching cycles on a source graph to thereby determine an optimal path between a start node and a destination node, said source graph having a plurality of node links and a plurality of nodes including said start node and said destination node, said path searching cycles being based upon local searching heuristic and global pheromone updating rules.

2. The path searching system of claim 1, and further comprising a graph constructor, coupled to said at least one storage medium, for constructing said source graph based on information associated with said plurality of nodes and said plurality of node links, said information being stored in said storage medium.

3. The path searching system of claim 2, and further comprising an editor for editing said information, said information including constraints associated with said plurality of nodes and said plurality of node links.

4. The path searching system of claim 1, and further comprising a search definer for defining one or more criteria for paths derived from said path searching cycles.

5. The path searching system of claim 1, wherein said local searching heuristic comprises:

a trail intensity factor;

a local search desirability factor; and

a global visibility factor.

6. The path searching system of claim 5, wherein said local search desirability factor is based on distance between a current node and a selected linked node to determine the shortest path.

7. The path searching system of claim 5, wherein said local search desirability factor is based on maximum traveling speed between a current node and a selected linked node to determine the shortest traveling time.

8. The path searching system of claim 5, wherein said path searching engine comprises free cooperating agents, said free cooperating agents not being guided by said global visibility factor.

9. The path searching system of claim 5, wherein said path searching engine is further adapted to determine said path in each of both a forward direction from said start node to said destination node and a reverse direction from said destination node to said node start.

10. The path searching system of claim 9, wherein said path searching engine is further adapted to provide at least two searching groups of cooperating agents for searching in said forward direction.

11. The path searching system of claim 9, wherein said path searching engine is further adapted to provide at least two searching groups of cooperating agents for searching in said reverse direction.

12. The path searching system of claim 9, wherein said path searching engine is further adapted to determine an optimal path from searching in said forward direction and said reverse direction.

13. A method of path searching based on ant colony optimization, said method comprising:

constructing a source graph having a plurality of nodes, each of said plurality of nodes having at least one link to another node of said plurality of nodes;

initializing one or more searching parameters for one or more searching groups; and

performing path searching cycles on said source graph for each of said one or more searching groups to determine an optimal path.

14. The method of claim 13, wherein said constructing comprises:

retrieving data associated with said plurality of nodes; and

identifying a start node and a destination node.

15. The method of claim 14, wherein said initializing comprises defining a predetermined number of cooperating agents for each of said searching groups.

16. The method of claim 15, wherein said initializing further comprises setting a searching direction for each of said searching groups.

17. The method of claim 16, wherein said performing comprises setting a plurality of cycle parameters for each of said searching groups, said plurality of cycle parameters being stored in association with each of said searching groups.

18. The method of claim 17, wherein said performing further comprises placing said predetermined number of cooperating agents for a selected searching group at an initial node, said initial node being either said start node or said destination node.

19. The method of claim 18, wherein said placing comprises:

clearing one or more tabu lists, each of said tabu lists being respectively associated with each of said cooperating agents of said selected searching group; and

entering said initial node into each of said tabu lists.

20. The method of claim 19, wherein said performing further comprises:

selecting a cooperating agent from said selected searching group;

choosing a next node for a selected cooperating agent based on a probability function;

determining whether said next node is in a tabu list associated with said selected cooperating agent; and

repeating said selecting, said choosing and said determining for remaining cooperating agents of said selected searching group.

21. The method of claim 20, wherein said repeating comprises adding said next node to said tabu list when not already in said tabu list.

22. The method of claim 21, wherein said repeating further comprises checking whether said tabu list provides a valid path when said next node is said finishing node.

23. The method of claim 22, wherein said performing further comprises storing said valid path when said tabu list provides said valid path.

24. The method of claim 23, wherein said performing further comprises evaluating said valid path to determine whether to update a cycle parameter of said plurality of cycle parameters, said cycle parameter corresponding to a best path for said selected searching group.

25. The method of claim 24, and further comprising checking whether said selected searching group has another cooperating agent for said selecting, said choosing, said determining and said repeating.

26. The method of claim 25, and further comprising updating trails on links using quantity of trail substance per unit of length of one or more stored valid paths.

27. The method of claim 26, and further comprising computing trail intensity for every link of each of said stored valid paths.

28. The method of claim 27, and further comprising comparing said best path from each of said one or more searching groups to determine said optimal path.

29. A product comprising computer usable medium having a computer program recorded thereon for path searching based on ant colony optimization, said product comprising:

computer program code means for constructing a source graph having a plurality of nodes, each of said plurality of nodes having at least one link to another node of said plurality of nodes;

computer program code means for initializing one or more searching parameters for one or more searching groups; and

computer program code means for performing path searching cycles on said source graph for each of said one or more searching groups to determine an optimal path.

30. The product of claim 29, wherein said computer program code means for constructing comprises:

computer program code means for retrieving data associated with said plurality of nodes; and

computer program code means for identifying a start node and a destination node.

31. The product of claim 30, wherein said computer program code means for initializing comprises computer program code means for defining a predetermined number of cooperating agents for each of said searching groups.

32. The product of claim 31, wherein said computer program code means for initializing further comprises computer program code means for setting a searching direction for each of said searching groups.

33. The product of claim 32, wherein said computer program code means for performing comprises computer program code means for setting a plurality of cycle parameters for each of said searching groups, said plurality of cycle parameters being stored in association with each of said searching groups.

34. The product of claim 33, wherein said computer program code means for performing further comprises computer program code means for placing said predetermined number of cooperating agents for a selected searching group at an initial node, said initial node being either said start node or said destination node.

35. The product of claim 34, wherein said computer program code means for placing comprises:

computer program code means for clearing one or more tabu lists, each of said tabu lists being respectively associated with each of said cooperating agents of said selected searching group; and

computer program code means for entering said initial node into each of said tabu lists.

36. The product of claim 35, wherein said computer program code means for performing further comprises:

computer program code means for selecting a cooperating agent from said selected searching group;

computer program code means for choosing a next node for a selected cooperating agent based on a probability function;

computer program code means for determining whether said next node is in a tabu list associated with said selected cooperating agent; and

computer program code means for repeating said selecting, said choosing and said determining for remaining cooperating agents of said selected searching group.

37. The product of claim 36, wherein said computer program code means for repeating comprises computer program code means for adding said next node to said tabu list when not already in said tabu list.

38. The product of claim 37, wherein said computer program code means for repeating further comprises computer program code means for checking whether said tabu list provides a valid path when said next node is said finishing node.

39. The product of claim 38, wherein said computer program code means for performing further comprises computer program code means for storing said valid path when said tabu list provides said valid path.

40. The product of claim 39, wherein said computer program code means for performing further comprises computer program code means for evaluating said valid path to determine whether to update a cycle parameter of said plurality of cycle parameters, said cycle parameter corresponding to a best path for said selected searching group.

41. The product of claim 40, and further comprising computer program code means for checking whether said selected searching group has another cooperating agent for said selecting, said choosing, said determining and said repeating.

42. The product of claim 41, and further comprising computer program code means for updating trails on links using quantity of trail substance per unit of length of one or more stored valid paths.

43. The product of claim 42, and further comprising computer program code means for computing trail intensity for every link of each of said stored valid paths.

44. The product of claim 43, and further comprising computer program code means for comparing said best path from each of said one or more searching groups to determine said optimal path.