Data processing: generic control systems or specific application – Specific application – apparatus or process – Robot control
Reexamination Certificate
2000-07-07
2002-11-05
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Robot control
C700S001000, C700S095000, C700S100000, C700S254000, C708S404000, C708S406000, C702S182000, C703S001000, C703S002000, C703S007000
Reexamination Certificate
active
06477444
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to modular robots, and in particular, software for modular robots.
BACKGROUND
Modular hardware that can reconfigure itself is usually referred to as a self-reconfigurable modular robot. A self-reconfigurable modular robot is composed of many identical modules and does not resemble the common view of a robot. Each module typically has a power source, processor, memory, motor, sensors, singly or in combination. The modules can attach to and detach from each other. Individual modules on their own can do little, but the robot, using the capabilities of the individual modules, can reconfigure itself to solve problems.
Advantages of self-reconfigurable modular robots include physical adaptability to varying problems and environments, robustness since identical modules can replace each other in the event of failure, and economies of scale in the manufacturing process.
Examples of self-reconfiguring modular robots include:
1) CMU's I-cubes as described in C. Ünsal, H. Kiliççöte, P. K. Khosla, “A 3-D Modular Self-Reconfigurable Bipartite Robotic System: Implementation and Motion Planning,” submitted to Autonomous Robots Journal, special issue on Modular Reconfigurable Robots, 2000;
2) USC-ISI's Spider Link Models, P. Will, A. Castano and W-M. Shen, “Robot Modularity for Self-Reconfiguration,” Proc. SPIE Sensor Fusion and Decentralized Control II, pp. 236-245, Boston, September 1999.
3) Dartmouth's Molecular Robots, Kotay, K., Rus, D., Vona, M. and McGray, C., “The Self-reconfiguring robotic molecule: design and control algorithms”. In Proceeding of the 1998 International Conference on Intelligent Robots and Systems, 1998;
4) Crystalline Robots, Rus, D., M. Vona, “Self-Reconfiguration Planning with Compressible Unit Modules”. In 1999 IEEE Int. Conference on Robotics and Automation;
5) MSU's Reconfigurable Adaptable Micro-Robot, R. L. Tummala, R. Mukherjee, D. Aslam, N. Xi, S. Mahadevan, J. Weng, “Reconfigurable Adaptable Micro-Robot”, Proc. 1999 IEEE International Conference on Systems, Man, and Cybernetics, Tokyo, Japan, October 1999;
6) Johns Hopkins University, s Metamorphic Robots, Amit Pamecha, Imme Ebert-Uphoff, Gregory S. Chirikjian, AUseful Metrics for Modular Robot Motion Planning, IEEE Transactions on Robots and Automation, pp. 531-545, Vol.13, No.4, August 1997 (“Pamecha”);
7) Xerox PARC's PolyBot, Yim, Mark, Duff, David G., Roufas, Kimon D. IEEE Intl. Conf. On Robotics and Automation (ICRA), 2000; and,
8) Proteo robots Hristo Bojinov, Arancha Casal, Tad Hogg, “Emergent Structures in Modular Self-reconfigurable Robots”, IEEE Intl. Conf. on Robotics and Automation (ICRA) 2000.
It is difficult to design effective software for self-reconfiguring modular robots. It is desirable to have the software completely decentralized and completely autonomous, so that tasks can be performed without reference to a central controller, whether human or machine. The hope is that eventually hundreds, or even millions, of modules will work together. Decentralized control takes advantage of the computational power of the individual modules and requires less communication bandwidth. All modules typically run the same software program, but behave differently depending on individual sensor values, internal state, and messages received from nearby modules.
Thus, there is a desire to provide decentralized software controllers for self-reconfigurable modular robots that act at a local level but achieve useful global behavior.
SUMMARY OF INVENTION
A method and computer-readable medium is provided for designing a software program for a module in a self-reconfigurable robot.
The method includes the step of providing a plurality of software functions for performing a respective plurality of module functions. A first plurality of software programs for solving a task is constructed from the plurality of software functions. The first plurality of software programs are executed to obtain a plurality of results. The method includes the step of providing a fitness function for obtaining a fitness function value for the first plurality of software programs. A second plurality of software programs is selected from the first plurality of software programs based on the respective fitness function values. The second plurality of software programs is modified, by a genetic operation, to form a third plurality of software programs.
According to an aspect of the present invention, the genetic operation is a crossover, mutation and/or cloning operation, singly or in combination.
According to an aspect of the present invention, the crossover operation includes obtaining respective parse tree representations of a first and 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 program.
According to another aspect of the present invention, the mutation operation includes obtaining a parse tree representation of a first software program in the second plurality of computer programs The parse tree includes a first subtree. The first subtree is randomly selected and replaced with a randomly created second subtree.
According to another aspect of the present invention, the cloning operation includes copying a first software program in the second plurality of software programs.
According to another aspect of the present invention, the plurality of functions include: (GetMemory index), (MoveLine direction), (MoveSingle direction), (ReadMessage direction), (ReadSensorSelf direction), (ReadSensorSelfBroken direction), (ReadSensorWall direction), (Rotate direction), (SendMessage message direction) (SetMemory Index value), (BlockMove xpos xneg ypos yneg), (And), (If), (Less), (Divide), (Modules) functions, either singly or in combination.
According to another aspect of the present invention, the module is a sliding module, a rotating module and/or a compressible module.
According to another aspect of the present invention, the task is moving a self-reconfigurable robot through a narrow passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot through a switchback passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot having a broken module through a switchback passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot through a switchback passage and ejecting a broken module.
According to another aspect of the present invention, the task is forming a bridge over a gap.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot toward a goal.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot toward a goal in the presence of obstacles.
According to another aspect of the present invention, a module includes a sensor, a motor and a power source, singly or in combination.
According to another aspect of the present invention, the fitness function includes measuring the distance between a robot location and a selected location.
According to another aspect of the present invention, a module in a self-reconfigurable robot with software created by genetic programming is provided. The module includes a processor coupled to memory. The memory stores a software program for solving a problem, wherein the software program is constructed from a genetic program.
An article of manufacture, including computer readable memory is provided. The computer readable memory includes a first plurality of software functions for performing a respective plurality of module tasks in a self-reconfigurable robot. A first software program randomly selects a first plurality of functions to form a plurality of software programs. A fitness function obtains a respective plurality of fitness function values for the respective first plurality of software programs. A second soft
Bennett, III Forrest H.
Rieffel Eleanor
Cuchlinski Jr. William A.
Fliesler Dubb Meyer & Lovejoy LLP
Fuji 'Xerox Co., Ltd.
Marc McDieunel
LandOfFree
Method for the automated design of decentralized controllers... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the automated design of decentralized controllers..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the automated design of decentralized controllers... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2988322