iAnt swarm robotic platform and evolutionary algorithms

• US 9,446,512 B1
• Filed: 03/25/2015
• Issued: 09/20/2016
• Est. Priority Date: 03/26/2014
• Status: Active Grant

• Current Assignee: UNM Rainforest Innovations (f/k/a STC.UNM) (The University of New Mexico)
• Original Assignee: UNM Rainforest Innovations (f/k/a STC.UNM) (The University of New Mexico)
• Inventors: Moses, Melanie E., Hecker, Joshua P., Letendre, Kenneth, Stolleis, Karl Andrew
• Primary Examiner(s): Figueroa, Jaime
• Application Number:
  US14/668,741
• Time in Patent Office: 545 Days
• Field of Search: 700/245, 700/246, 700/247, 700/249, 700/250, 700/253, 700/255, 700/258, 700/259, 318/568.11, 318/568.12, 318/568.16
• US Class Current: 1/1
• CPC Class Codes: B25J 9/0084 comprising a plurality of manipulators
• CPC Class Codes: B25J 9/1617 Cellular, reconfigurable manipulator, e.g. cebot
• CPC Class Codes: B25J 9/162 Mobile manipulator, movable base with manipulator arm mounted on it
• CPC Class Codes: G05B 2219/39146 Swarm, multiagent, distributed multitask fusion, cooperation multi robots
• CPC Class Codes: G05B 2219/39168 Multiple robots searching an object
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: G06N 3/008 based on physical entities controlled by simulated intelligence so as to replicate intelligent life forms, e.g. based on robots replicating pets or humans in their appearance or behaviour
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The present invention provides a swarm of robots and a related method of operating the swarm. The robots are programmed to start at a nest and to select a dispersal direction from a uniform random distribution. The robots travel along the dispersal direction until transitioning to a search mode upon reaching a search site, where the robot performs a correlated random walk with fixed step size and direction and using a standard deviation to determine how correlated the direction of the next step of the robot is with the direction of the previous step. If no resource is found within predetermined time t independently determined by each of said robots, the robot returns to the nest and repeats the above steps.

Claims

1. A method of operating a plurality of robots to perform foraging for a resource, comprising the steps of:

programming each robot to know where the nest is and with an inherent leash;

a. each robot is programmed to conduct a uniformed search by traveling to a random first location along a substantially straight path;

b. upon reaching said first location, each of said robots performing a uniformed correlated random walk for a first predetermined time period set by each robot independently of each other for random length of times;

c. if during said first predetermined time period no resource is found, said robot returns to the nest;

d. upon returning to the nest, each robot repeats steps a-c until a resource is found by at least one robot;

e. upon finding a resource, the robot finding the resource collects one or more resources, independently assigns a resource grade to the location, returns to the nest and depending on the resource grade

     1) repeats steps a-c,

     2) returns to the location without sharing the information with other robots, or

     3) transmits a resource found signal informing the other robots of the resource location, said signal based on said resource grade; and

f. upon receiving a resource found signal, depending on the grade of the signal, the robot receiving the signal

     1) repeats steps a-c, or

     2) travels to the location and performs step e if a resource is found and if a resource is not found, performs an informed correlated random walk.

2. The method of claim 1 wherein the signals decay over time.

3. The method of claim 1 wherein said informed correlated random walk decays into a uniformed correlated random walk over time.

4. The method of claim 1 wherein the steps a-e are optimized by a genetic algorithm for unique environments.

5. The method of claim 1 where said resource grade is a function of the environments in which the robots are operating.

6. A method of operating a plurality of robots to perform foraging for a resource, comprising the steps of:

a. programming each of said robots to start at a nest and to select a dispersal direction from a uniform random distribution, said robots travel along said dispersal direction until transitioning to a search mode upon reaching said search site;

b. said search mode comprises a correlated random walk with fixed step size and direction and using a standard deviation to determine how correlated the direction of the next step of the robot is with the direction of the previous step; and

c. returning to said nest if a resource is not found within a predetermined time t.

7. The method of claim 6 further including the step of repeating steps a through c until at least one resource is found by one of said plurality of said robots.

8. The method of claim 7 wherein each robot performs the step of determining time t.

9. The method of claim 8 wherein when a robot locates a resource, said robot performs the steps of collecting the resource, recording a count c of resources found and returning to said nest.

10. The method of claim 9 wherein for a robot that has located a resource, upon returning to said nest, said robot uses c to decide whether to i) return to the location of the resource ii) generate a resource location communication for use by other robots iii) follow a resource location communication generated by another robot or iv) perform steps a and b.

11. The method of claim 10 wherein for a robot that is conducting a search based on receiving a resource location communication, said robot searches using an informed correlated random walk, where the standard deviation of the successive turning angles of the informed random walk decays as a function of time t randomly determined by said robot, producing an initially undirected and localized search that becomes more correlated over time.

12. The method of claim 11 wherein said standard deviation σ

is defined by

σ

=ω

+(4π

−

ω

)e<sup>−

λ

idt</sup>.

13. The method of claim 6 wherein said search mode comprises a correlated random walk with fixed step size and direction θ

_t at time t, defined by θ

_t=N(θ

_t-1, σ

) and using a standard deviation σ

to determine how correlated the direction of the next step of the robot is with the direction of the previous step.

14. The method of claim 10 wherein the robot returns to a previously found resource location if c exceeds a uniform random value and, if c is less than the uniform random value, the robot follows a resource location communication of another robot to another location if a resource location communication is available and if no resource location communication is available, the robot will choose its next search location at random.

15. The method of claim 10 wherein the robot transmits a resource location communication to a list maintained by a server and the server selects a resource location communication from the list and transmits it to one or more robots.

16. The method of claim 15 wherein the strength of a resource location communication decays over time.

17. The method of claim 16 wherein the strength of a resource location communication decays exponentially over time.

18. A method of operating a plurality of robots to perform foraging for a resource, comprising the steps of:

a. programming each of said robots to start at a nest and to select a dispersal direction from a uniform random distribution, said robots travel along said dispersal direction until transitioning to a search mode upon reaching a search site;

b. said search mode comprises a correlated random walk with fixed step size and direction and using a standard deviation to determine how correlated the direction of the next step of the robot is with the direction of the previous step;

c. a robot returns to said nest if a resource is not found within a predetermined time t independently determined by the robot;

d. repeating steps a through c until at least one resource is found by one of said plurality of said robots;

f. when a robot locates a resource, said robot locating the resource performs the steps of collecting the resource, recording a count c of resources found, returning to said nest, and upon returning to said nest, said robot generates a resource location communication and then returns to the resource location if c exceeds a uniform random value and, if c is less than the uniform random value, the robot follows a resource location communication to another location if a resource location communication is available and if no resource location communication is available, the robot will choose its next search location at random; and

g. for a robot that is conducting a search based on receiving a resource location communication, said robot searches the resource location using an informed correlated random walk, where the standard deviation of the successive turning angles of the informed random walk decays as a function of time t randomly determined by said robot, producing an initially undirected and localized search that becomes more correlated over time.

19. The method of claim 18 wherein a robot transmits a resource location communication to a server and said server selects a resource location from the list and transmits it to one or more robots.

20. The method of claim 18 where the steps are optimized by a genetic algorithm.