Method for the automated design of decentralized controllers for modular self-reconfigurable robots

• US 6,477,444 B1
• Filed: 07/07/2000
• Issued: 11/05/2002
• Est. Priority Date: 07/07/2000
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Rieffel, Eleanor, Bennett, Forrest H. III
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Marc, McDieunel, Marc, McDieunel
• Application Number:
  US09/611,395
• Time in Patent Office: 851 Days
• Field of Search: 700/245, 700/246, 700/254, 700/250, 700/90, 700/253, 700/257, 700/5, 700/8, 700/9, 700/23, 700/28, 700/91, 700/95, 700/100, 700/1, 702/182, 703/1, 703/2, 703/7, 708/404, 708/406, 708/816, 710/132, 358/408, 358/426, 358/470
• US Class Current: 700/245
• 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

A method and computer-readable medium is provided for designing control software for a module in a self-reconfigurable robot. A genetic method randomly selects a plurality of module software functions for creating a plurality of module control software programs. The plurality of control software programs are then evaluated against a series of tasks and respective fitness functions. The module control software is selected based on the software program having the highest fitness function value for a particular task.

Claims

1. A method for providing software for a module in a self-reconfigurable robot, comprising the steps of:

(a) providing a plurality of software functions for performing a respective plurality of module functions;

(b) constructing a first plurality of software programs for solving a task from the plurality of software functions;

(c) executing the first plurality of software programs to obtain a plurality of respective results;

(d) obtaining a task fitness function for providing a fitness value;

(e) calculating a plurality of respective fitness function values for the first plurality of software programs;

(f) selecting a second plurality of software programs from the first plurality of software programs based on the respective fitness function values; and

,

(g) constructing a third plurality of software programs from the second plurality of programs using a genetic operation.

2. The method of claim 1, wherein the genetic operation is a crossover operation.

3. The method of claim 2, wherein the crossover operation includes obtaining respective parse tree representations of a first and a second (“

parent”

) computer program in the second plurality of software programs to create a first and second (“

child”

) software program by exchanging a randomly selected subtree between the first and second parent computer programs.

4. The method of claim 2, wherein the crossover operation includes obtaining respective parse tree representations of a first and a second (“

parent”

) computer program in the second plurality of software programs to create only a first (“

child”

) software program by exchanging a randomly selected subtree between the first and second parent computer programs.

5. The method of claim 4, wherein the mutation operation includes obtaining a parse tree representation of a first software computer program in the second plurality of computer programs, where the parse tree representation includes a first subtree, and randomly selecting the first subtree and replacing the first subtree with a randomly created second subtree.

6. The method of claim 1, wherein the genetic operation is a mutation operation.

7. The method of claim 1, wherein the genetic operation is a cloning operation.

8. The method of claim 7, wherein the cloning operation includes copying a first software program in the second plurality of software programs.

9. The method of claim 1, wherein the plurality of functions includes a (GetMemory index) function.

10. The method of claim 1, wherein the plurality of functions includes a (MoveLine direction) function.

11. The method of claim 1, wherein the plurality of functions includes a (MoveSingle direction) function.

12. The method of claim 1, wherein the plurality of functions includes a (ReadMessage direction) function.

13. The method of claim 1, wherein the plurality of functions includes a (ReadSensorSelf direction) function.

14. The method of claim 1, wherein the plurality of functions includes a (ReadSensorSelfBroken direction) function.

15. The method of claim 1, wherein the plurality of functions includes a (ReadSensorWall direction) function.

16. The method of claim 1, wherein the plurality of functions includes a (Rotate direction) function.

17. The method of claim 1, wherein the plurality of functions includes a (SendMessage message direction) function.

18. The method of claim 1, wherein the plurality of functions includes a (SetMemory index number) function.

19. The method of claim 1, wherein the plurality of functions includes a (BlockMove direction xpos xneg ypos yneg) function.

20. The method of claim 1, wherein the plurality of functions includes a (And) function.

21. The method of claim 1, wherein the plurality of functions includes a (If) function.

22. The method of claim 1, wherein the plurality of functions includes a (Less) function.

23. The method of claim 1, wherein the plurality of functions includes a (Divide) function.

24. The method of claim 1, wherein the plurality of functions includes a (Modulus) function.

25. The method of claim 1, wherein the plurality of tasks includes a reconfiguration task.

26. The method of claim 1, wherein the module is a sliding module.

27. The method of claim 1, wherein the module is a rotating module.

28. The method of claim 1, wherein the module is a compressable module.

29. The method of claim 1, wherein the task is moving a self-reconfigurable robot through a narrow passage.

30. The method of claim 1, wherein the task is moving the self-reconfigurable robot through a switchback passage.

31. The method of claim 1 wherein the task is moving the self-reconfigurable robot having a broken module through a switchback passage.

32. The method of claim 1, wherein the task is 1) moving the self-reconfigurable robot through a switchback passage, and 2) ejecting a broken module.

33. The method of claim 1, wherein the task is forming a bridge over a gap.

34. The method of claim 1, wherein the task is moving the self-reconfigurable robot toward a goal.

35. The method of claim 1, wherein the task is moving the self-reconfigurable robot toward a goal in the presence of obstacles.

36. The method of claim 1, wherein the module includes a sensor, a motor, and a power source.

37. The method of claim 1, wherein the fitness function includes measuring the distance between a robot location and a selected location.

38. The method of claim 1, wherein the fitness function includes the amount of time to solve the task.

39. The method of claim 1, wherein the fitness function includes the amount of power used to solve the task.

40. The method of claim 1, wherein the robot includes a plurality of modules and where the fitness function includes a number of modules connected.

41. The method of claim 1, wherein the fitness function includes the size of a selected software program in the second plurality of software programs.

42. An article of manufacture, including a computer-readable memory, comprising:

(a) a first plurality of software functions for performing a respective plurality of module functions in a self-reconfigurable robot;

(b) a first software program for randomly selecting a plurality of software functions for forming a first plurality of software programs;

(c) a fitness function for obtaining a respective plurality of fitness function values for the respective first plurality of software programs; and

,

(d) a second software program for constructing a second plurality of software programs from the first plurality of software programs based on the plurality of respective fitness function values.

43. The article of manufacture of claim 42, further comprising:

(e) a third software program for forming a third plurality of software programs from the second plurality of software programs by using a genetic operation on a software program in the second plurality of software programs.

44. A self-reconfigurable robot, comprising:

(a) a first module; and

,

(b) a second module having a memory, coupled to a processor, for storing a software program for solving a task, wherein the software program is constructed from genetic programming and is able to complete the task with a failure of the first module.

45. The self-reconfigurable robot of claim 44, wherein the first module is a sliding module.

46. The self-reconfigurable robot of claim 44, wherein the first module is a rotating module.

47. The self-reconfigurable robot of claim 44, wherein the first module is a compressable module.

48. A self-reconfigurable robot, comprising:

(a) first module; and

,

(b) a second module having a memory, coupled to a processor, for storing a software program for solving a task, wherein the software program is constructed from genetic programming and the first and second modules are able to complete the task with the addition of a plurality of modules storing the software program, respectively.