Self-reconfiguring modular robot

From Wikipedia, the free encyclopedia

Modular self-reconfiguring robotic systems or self-reconfigurable modular robots are autonomous kinematic machines with variable morphology. Beyond conventional actuation, sensing and control typically found in fixed-morphology robots, self-reconfiguring robots are also able to deliberately change their own shape by rearranging the connectivity of their parts, in order to adapt to new circumstances, perform new tasks, or recover from damage.

For example, a robot made of such components could assume a worm-like shape to move through a narrow pipe, reassemble into something with spider-like legs to cross uneven terrain, then form a third arbitrary object (like a ball or wheel that can spin itself) to move quickly over a fairly flat terrain; it can also be used for making "fixed" objects, such as walls, shelters, or buildings.

In some cases this involves each module having 2 or more connectors for connecting several together. They can contain electronics, sensors, computer processors, memory and power supplies; they can also contain actuators that are used for manipulating their location in the environment and in relation with each other. A feature found in some cases is the ability of the modules to automatically connect and disconnect themselves to and from each other, and to form into many objects or perform many tasks moving or manipulating the environment.

By saying "self-reconfiguring" or "self-reconfigurable" it means that the mechanism or device is capable of utilizing its own system of control such as with actuators or stochastic means to change its overall structural shape. Having the quality of being "modular" in "self-reconfiguring modular robotics" is to say that the same module or set of modules can be added to or removed from the system, as opposed to being generically "modularized" in the broader sense. The underlying intent is to have an indefinite number of identical modules, or a finite and relatively small set of identical modules, in a mesh or matrix structure of self-reconfigurable modules.

Self-reconfiguration is different from the concept of self-replication, which is not a quality that a self-reconfigurable module or collection of modules needs to possess. A matrix of modules does not need to be able to increase the quantity of modules in its matrix to be considered self-reconfigurable. It is sufficient for self-reconfigurable modules to be produced at a conventional factory, where dedicated machines stamp or mold components that are then assembled into a module, and added to an existing matrix in order to supplement it to increase the quantity or to replace worn out modules.

A matrix made up of many modules can separate to form multiple matrices with fewer modules, or they can combine, or recombine, to form a larger matrix. Some advantages of separating into multiple matrices include the ability to tackle multiple and simpler tasks at locations that are remote from each other simultaneously, transferring through barriers with openings that are too small for a single larger matrix to fit through but not too small for smaller matrix fragments or individual modules, and energy saving purposes by only utilizing enough modules to accomplish a given task. Some advantages of combining multiple matrices into a single matrix is ability to form larger structures such as an elongated bridge, more complex structures such as a robot with many arms or an arm with more degrees of freedom, and increasing strength. Increasing strength, in this sense, can be in the form of increasing the rigidity of a fixed or static structure, increasing the net or collective amount of force for raising, lowering, pushing, or pulling another object, or another part of the matrix, or any combination of these features.

There are two basic methods of segment articulation that self-reconfigurable mechanisms can utilize to reshape their structures: chain reconfiguration and lattice reconfiguration.

Structure and control

Modular robots are usually composed of multiple building blocks of a relatively small repertoire, with uniform docking interfaces that allow transfer of mechanical forces and moments, electrical power and communication throughout the robot. 

The modular building blocks usually consist of some primary structural actuated unit, and potentially additional specialized units such as grippers, feet, wheels, cameras, payload and energy storage and generation.

A taxonomy of architectures

Modular self-reconfiguring robotic systems can be generally classified into several architectural groups by the geometric arrangement of their unit (lattice vs. chain). Several systems exhibit hybrid properties, and modular robots have also been classified into the two categories of Mobile Configuration Change (MCC) and Whole Body Locomotion (WBL).

Lattice architecture: 12 modules of the homogeneous lattice system Micro Unit assembled together shown with corresponding grid and docking points network

• Lattice architecture have their units connecting their docking interfaces at points into virtual cells of some regular grid. This network of docking points can be compared to atoms in a crystal and the grid to the lattice of that crystal. Therefore, the kinematical features of lattice robots can be characterized by their corresponding crystallographic displacement groups (chiral space groups). Usually few units are sufficient to accomplish a reconfiguration step. Lattice architectures allows a simpler mechanical design and a simpler computational representation and reconfiguration planning that can be more easily scaled to complex systems.
• Chain architecture do not use a virtual network of docking points for their units. The units are able to reach any point in the space and are therefore more versatile, but a chain of many units may be necessary to reach a point making it usually more difficult to accomplish a reconfiguration step. Such systems are also more computationally difficult to represent and analyze.
• Hybrid architecture takes advantages of both previous architectures. Control and mechanism are designed for lattice reconfiguration but also allow to reach any point in the space.

Modular robotic systems can also be classified according to the way by which units are reconfigured (moved) into place.

• Deterministic reconfiguration relies on units moving or being directly manipulated into their target location during reconfiguration. The exact location of each unit is known at all times. Reconfiguration times can be guaranteed, but sophisticated feedback control is necessary to assure precise manipulation. Macro-scale systems are usually deterministic.
• Stochastic reconfiguration relies on units moving around using statistical processes (like Brownian motion). The exact location of each unit only known when it is connected to the main structure, but it may take unknown paths to move between locations. Reconfiguration times can be guaranteed only statistically. Stochastic architectures are more favorable at micro scales.

Modular robotic systems are also generally classified depending on the design of the modules.

• Homogeneous modular robot systems have many modules of the same design forming a structure suitable to perform the required task. An advantage over other systems is that they are simple to scale in size (and possibly function), by adding more units. A commonly described disadvantage is limits to functionality - these systems often require more modules to achieve a given function, than heterogeneous systems.
• Heterogeneous modular robot systems have different modules, each of which do specialized functions, forming a structure suitable to perform a task. An advantage is compactness, and the versatility to design and add units to perform any task. A commonly described disadvantage is an increase in complexity of design, manufacturing, and simulation methods.

Other modular robotic systems exist which are not self-reconfigurable, and thus do not formally belong to this family of robots though they may have similar appearance. For example, self-assembling systems may be composed of multiple modules but cannot dynamically control their target shape. Similarly, tensegrity robotics may be composed of multiple interchangeable modules but cannot self-reconfigure.

Motivation and inspiration

There are two key motivations for designing modular self-reconfiguring robotic systems.

• Functional advantage: Self reconfiguring robotic systems are potentially more robust and more adaptive than conventional systems. The reconfiguration ability allows a robot or a group of robots to disassemble and reassemble machines to form new morphologies that are better suitable for new tasks, such as changing from a legged robot to a snake robot (snakebot) and then to a rolling robot. Since robot parts are interchangeable (within a robot and between different robots), machines can also replace faulty parts autonomously, leading to self-repair.

Autonomous modular robotics in space

• Economic advantage: Self reconfiguring robotic systems can potentially lower overall robot cost by making a range of complex machines out of a single (or relatively few) types of mass-produced modules.

Both these advantages have not yet been fully realized. A modular robot is likely to be inferior in performance to any single custom robot tailored for a specific task. However, the advantage of modular robotics is only apparent when considering multiple tasks that would normally require a set of different robots.

The added degrees of freedom make modular robots more versatile in their potential capabilities, but also incur a performance tradeoff and increased mechanical and computational complexities.

The quest for self-reconfiguring robotic structures is to some extent inspired by envisioned applications such as long-term space missions, that require long-term self-sustaining robotic ecology that can handle unforeseen situations and may require self repair. A second source of inspiration are biological systems that are self-constructed out of a relatively small repertoire of lower-level building blocks (cells or amino acids, depending on scale of interest). This architecture underlies biological systems' ability to physically adapt, grow, heal, and even self replicate – capabilities that would be desirable in many engineered systems. 

Manufacturer operating in the self-reconfiguring modular robot industry include ABB Ltd., Kawasaki Heavy Industries, Ltd., Yaskawa Electric Corporation, Fanuc Corporation, Kuka AG, Mitsubishi Electric Corporation, Denso Corporation, Nachi-Fujikoshi Corp., Comau S.P.A., Universal Robots A/S, and CMA Robotics S.P.A. 

Application areas

Given these advantages, where would a modular self-reconfigurable system be used? While the system has the promise of being capable of doing a wide variety of things, finding the "killer application" has been somewhat elusive. Here are several examples:

Space exploration

One application that highlights the advantages of self-reconfigurable systems is long-term space missions. These require long-term self-sustaining robotic ecology that can handle unforeseen situations and may require self repair. Self-reconfigurable systems have the ability to handle tasks that are not known a priori, especially compared to fixed configuration systems. In addition, space missions are highly volume- and mass-constrained. Sending a robot system that can reconfigure to achieve many tasks may be more effective than sending many robots that each can do one task.

Telepario

Another example of an application has been coined "telepario" by CMU professors Todd Mowry and Seth Goldstein. What the researchers propose to make are moving, physical, three-dimensional replicas of people or objects, so lifelike that human senses would accept them as real. This would eliminate the need for cumbersome virtual reality gear and overcome the viewing angle limitations of modern 3D approaches. The replicas would mimic the shape and appearance of a person or object being imaged in real time, and as the originals moved, so would their replicas. One aspect of this application is that the main development thrust is geometric representation rather than applying forces to the environment as in a typical robotic manipulation task. This project is widely known as claytronics or Programmable matter (noting that programmable matter is a much more general term, encompassing functional programmable materials, as well).

Bucket of stuff

A third long term vision for these systems has been called "bucket of stuff". In this vision, consumers of the future have a container of self-reconfigurable modules say in their garage, basement, or attic. When the need arises, the consumer calls forth the robots to achieve a task such as "clean the gutters" or "change the oil in the car" and the robot assumes the shape needed and does the task.

History and state of the art

The roots of the concept of modular self-reconfigurable robots can be traced back to the "quick change" end effector and automatic tool changers in computer numerical controlled machining centers in the 1970s. Here, special modules each with a common connection mechanism could be automatically swapped out on the end of a robotic arm. However, taking the basic concept of the common connection mechanism and applying it to the whole robot was introduced by Toshio Fukuda with the CEBOT (short for cellular robot) in the late 1980s.

The early 1990s saw further development from Greg Chirikjian, Mark Yim, Joseph Michael, and Satoshi Murata. Chirikjian, Michael, and Murata developed lattice reconfiguration systems and Yim developed a chain based system. While these researchers started with from a mechanical engineering emphasis, designing and building modules then developing code to program them, the work of Daniela Rus and Wei-min Shen developed hardware but had a greater impact on the programming aspects. They started a trend towards provable or verifiable distributed algorithms for the control of large numbers of modules. 

One of the more interesting hardware platforms recently has been the MTRAN II and III systems developed by Satoshi Murata et al. This system is a hybrid chain and lattice system. It has the advantage of being able to achieve tasks more easily like chain systems, yet reconfigure like a lattice system.

More recently new efforts in stochastic self-assembly have been pursued by Hod Lipson and Eric Klavins. A large effort at Carnegie Mellon University headed by Seth Goldstein and Todd Mowry has started looking at issues in developing millions of modules.

Many tasks have been shown to be achievable, especially with chain reconfiguration modules. This demonstrates the versatility of these systems however, the other two advantages, robustness and low cost have not been demonstrated. In general the prototype systems developed in the labs have been fragile and expensive as would be expected during any initial development.

There is a growing number of research groups actively involved in modular robotics research. To date, about 30 systems have been designed and constructed, some of which are shown below.

Physical systems created

System	Class, DOF	Author	Year
CEBOT	Mobile	Fukuda et al. (Tsukuba)	1988
Polypod	chain, 2, 3D	Yim (Stanford)	1993
Metamorphic	lattice, 6, 2D	Chirikjian (Caltech)	1993
Fracta	lattice, 3 2D	Murata (MEL)	1994
Fractal Robots	lattice, 3D	Michael(UK)	1995
Tetrobot	chain, 1 3D	Hamline et al. (RPI)	1996
3D Fracta	lattice, 6 3D	Murata et al. (MEL)	1998
Molecule	lattice, 4 3D	Kotay & Rus (Dartmouth)	1998
CONRO	chain, 2 3D	Will & Shen (USC/ISI)	1998
PolyBot	chain, 1 3D	Yim et al. (PARC)	1998
TeleCube	lattice, 6 3D	Suh et al., (PARC)	1998
Vertical	lattice, 2D	Hosakawa et al., (Riken)	1998
Crystalline	lattice, 4 2D	Vona & Rus, (Dartmouth)	1999
I-Cube	lattice, 3D	Unsal, (CMU)	1999
Micro Unit	lattice, 2 2D	Murata et al.(AIST)	1999
M-TRAN I	hybrid, 2 3D	Murata et al.(AIST)	1999
Pneumatic	lattice, 2D	Inou et al., (TiTech)	2002
Uni Rover	mobile, 2 2D	Hirose et al., (TiTech)	2002
M-TRAN II	hybrid, 2 3D	Murata et al., (AIST)	2002
Atron	lattice, 1 3D	Stoy et al., (U.S Denmark)	2003
S-bot	mobile, 3 2D	Mondada et al., (EPFL)	2003
Stochastic	lattice, 0 3D	White, Kopanski, Lipson (Cornell)	2004
Superbot	hybrid, 3 3D	Shen et al., (USC/ISI)	2004
Y1 Modules	chain, 1 3D	Gonzalez-Gomez et al., (UAM)	2004
M-TRAN III	hybrid, 2 3D	Kurokawa et al., (AIST)	2005
AMOEBA-I	Mobile, 7 3D	Liu JG et al., (SIA)	2005
Catom	lattice, 0 2D	Goldstein et al., (CMU)	2005
Stochastic-3D	lattice, 0 3D	White, Zykov, Lipson (Cornell)	2005
Molecubes	hybrid, 1 3D	Zykov, Mytilinaios, Lipson (Cornell)	2005
Prog. parts	lattice, 0 2D	Klavins, (U. Washington)	2005
Microtub [6]	chain, 2 2D	Brunete, Hernando, Gambao (UPM)	2005
Miche	lattice, 0 3D	Rus et al., (MIT)	2006
GZ-I Modules	chain, 1 3D	Zhang & Gonzalez-Gomez (U. Hamburg, UAM)	2006
The Distributed Flight Array	lattice, 6 3D	Oung & D'Andrea (ETH Zurich)	2008
Evolve	chain, 2 3D	Chang Fanxi, Francis (NUS)	2008
EM-Cube	Lattice, 2 2D	An, (Dran Computer Science Lab)	2008
Roombots	Hybrid, 3 3D	Sproewitz, Moeckel, Ijspeert, Biorobotics Laboratory, (EPFL)	2009
Programmable Matter by Folding	Sheet, 3D	Wood, Rus, Demaine et al., (Harvard & MIT)	2010
Sambot	Hybrid, 3D	HaiYuan Li, HongXing Wei, TianMiao Wang et al., (Beihang University)	2010
Moteins	Hybrid, 1 3D	Center for Bits and Atoms, (MIT)	2011
ModRED	Chain, 4 3D	C-MANTIC Lab, (UNO/UNL)	2011
Programmable Smart Sheet	Sheet, 3D	An & Rus, (MIT)	2011
SMORES	Hybrid, 4, 3D	Davey, Kwok, Yim (UNSW, UPenn)	2012
Symbrion	Hybrid, 3D	EU Projects Symbrion and Replicator	2013
ReBiS - Re-configurable Bipedal Snake	Chain, 1, 3D	Rohan, Ajinkya, Sachin, S. Chiddarwar, K. Bhurchandi (VNIT, Nagpur)	2014
Soft Mod. Rob. Cubes	Lattice, 3D	Vergara, Sheng, Mendoza-Garcia, Zagal (UChile)	2017

Some current systems

Polybot G3 Modular self-reconfigurable robot

PolyBot G3 (2002)

A chain self-reconfiguration system. Each module is about 50 mm on a side, and has 1 rotational DOF. It is part of the PolyBot modular robot family that has demonstrated many modes of locomotion including walking: biped, 14 legged, slinky-like, snake-like: concertina in a gopher hole, inchworm gaits, rectilinear undulation and sidewinding gaits, rolling like a tread at up to 1.4 m/s, riding a tricycle, climbing: stairs, poles pipes, ramps etc. More information can be found at the polybot webpage at PARC.

Metamorphosis by a self-reconfigurable robot, M-TRAN III

M-TRAN III (2005)

A hybrid type self-reconfigurable system. Each module is two cube size (65 mm side), and has 2 rotational DOF and 6 flat surfaces for connection. It is the 3rd M-TRAN prototypes. Compared with the former (M-TRAN II), speed and reliability of connection is largely improved. As a chain type system, locomotion by CPG (Central Pattern Generator) controller in various shapes has been demonstrated by M-TRAN II. As a lattice type system, it can change its configuration, e.g., between a 4 legged walker to a caterpillar like robot. See the M-TRAN webpage at AIST.

AMOEBA-I (2005)

AMOEBA-I, a three-module reconfigurable mobile robot was developed in Shenyang Institute of Automation (SIA), Chinese Academy of Sciences (CAS) by Liu J G et al. AMOEBA-I has nine kinds of non-isomorphic configurations and high mobility under unstructured environments.Four generations of its platform have been developed and a series of researches have been carried out on their reconfiguration mechanism, non-isomorphic configurations, tipover stability, and reconfiguration planning. Experiments have demonstrated that such kind structure permits good mobility and high flexibility to uneven terrain. Being hyper-redundant, modularized and reconfigurable, AMOEBA-I has many possible applications such as Urban Search and Rescue (USAR) and space exploration.

Stochastic-3D (2005)

 

High spatial resolution for arbitrary three-dimensional shape formation with modular robots can be accomplished using lattice system with large quantities of very small, prospectively microscopic modules. At small scales, and with large quantities of modules, deterministic control over reconfiguration of individual modules will become unfeasible, while stochastic mechanisms will naturally prevail. Microscopic size of modules will make the use of electromagnetic actuation and interconnection prohibitive, as well, as the use of on-board power storage. 

Three large scale prototypes were built in attempt to demonstrate dynamically programmable three-dimensional stochastic reconfiguration in a neutral-buoyancy environment. The first prototype used electromagnets for module reconfiguration and interconnection. The modules were 100 mm cubes and weighed 0.81 kg. The second prototype used stochastic fluidic reconfiguration and interconnection mechanism. Its 130 mm cubic modules weighed 1.78 kg each and made reconfiguration experiments excessively slow. The current third implementation inherits the fluidic reconfiguration principle. The lattice grid size is 80 mm, and the reconfiguration experiments are under way.

Molecubes in motion

Molecubes (2005)

This hybrid self-reconfiguring system was built by the Cornell Computational Synthesis Lab to physically demonstrate artificial kinematic self-reproduction. Each module is a 0.65 kg cube with 100 mm long edges and one rotational degree of freedom. The axis of rotation is aligned with the cube's longest diagonal. Physical self-reproduction of a three- and a four-module robots was demonstrated. It was also shown that, disregarding the gravity constraints, an infinite number of self-reproducing chain meta-structures can be built from Molecubes.

The Programmable Parts (2005)

The programmable parts are stirred randomly on an air-hockey table by randomly actuated air jets. When they collide and stick, they can communicate and decide whether to stay stuck, or if and when to detach. Local interaction rules can be devised and optimized to guide the robots to make any desired global shape. More information can be found at the programmable parts web page.

SuperBot (2006)

 

The SuperBot modules fall into the hybrid architecture. The modules have three degrees of freedom each. The design is based on two previous systems: Conro (by the same research group) and MTRAN (by Murata et al.). Each module can connect to another module through one of its six dock connectors. They can communicate and share power through their dock connectors. Several locomotion gaits have been developed for different arrangements of modules. For high-level communication the modules use hormone-based control, a distributed, scalable protocol that does not require the modules to have unique ID's.

Miche (2006)

 

The Miche system is a modular lattice system capable of arbitrary shape formation. Each module is an autonomous robot module capable of connecting to and communicating with its immediate neighbors. When assembled into a structure, the modules form a system that can be virtually sculpted using a computer interface and a distributed process. The group of modules collectively decide who is on the final shape and who is not using algorithms that minimize the information transmission and storage. Finally, the modules not in the structure let go and fall off under the control of an external force, in this case gravity. More details at Miche (Rus et al.).

A 10-module configuration of the Distributed Flight Array in flight.

 

The Distributed Flight Array (2009)

The Distributed Flight Array is a modular robot consisting of hexagonal-shaped single-rotor units that can take on just about any shape or form. Although each unit is capable of generating enough thrust to lift itself off the ground, on its own it is incapable of flight much like a helicopter cannot fly without its tail rotor. However, when joined together, these units evolve into a sophisticated multi-rotor system capable of coordinated flight and much more.

Roombots (2009)

Roombots have a hybrid architecture. Each module has three degree of freedom, two of them using the diametrical axis within a regular cube, and a third (center) axis of rotation connecting the two spherical parts. All three axes are continuously rotatory. The outer Roombots DOF is using the same axis-orientation as Molecubes, the third, central Roombots axis enables the module to rotate its two outer DOF against each other. This novel feature enables a single Roombots module to locomote on flat terrain, but also to climb a wall, or to cross a concave, perpendicular edge. Convex edges require the assembly of at least two modules into a Roombots "Metamodule". Each module has ten available connector slots, currently two of them are equipped with an active connection mechanism based on mechanical latches. Roombots are designed for two tasks: to eventually shape objects of daily life, e.g. furniture, and to locomote, e.g. as a quadruped or a tripod robot made from multiple modules.

Sambot (2010)

Being inspired form social insects, multicellular organism and mophogenetic robots. The aim of the Sambot is to develop swarm robotics and conduct research on the swarm intelligence, self-assembly and co-evolution of the body and brain for autonomous morphogeneous. Differing from swarm robot, self-reconfigurable robot and morphgenetic robot, the research focuses on self-assembly swarm modular robots that interact and dock as an autonomous mobile module with others to achieve swarm intelligence and furtherly discuss the autonomous construction in space station and exploratory tools and artificial complex structures. Each Sambot robot can run as an autonomous individual in wheel and besides, using combination of the sensors and docking mechanism, the robot can interact and dock with the environments and other robots. By the advantage of motion and connection, Sambot swarms can aggregate into a symbiotic or whole organism and generate locomotion as the bionic articular robots. In this case, some self-assembling, self-organizing, self-reconfiguring, and self-repairing function and research are available in design and application view. Inside the modular robot whose size is 80(W)X80(L)X102(H) mm, MCU (ARM and AVR), communication (Zigbee), sensors, power, IMU, positioning modules are embedded. More information can be found at Self-assembly Swarm Modular Robots

Motein

Moteins (2011)

It is mathematically proven that physical strings or chains of simple shapes can be folded into any continuous area or volumetric shape. Moteins employ such shape-universal folding strategies, with as few as one (for 2D shapes) or two (for 3D shapes) degrees of freedom and simple actuators with as few as two (for 2D shapes) or three (for 3D shapes) states per unit.

Symbrion (2013)

Symbrion (Symbiotic Evolutionary Robot Organisms) was a project funded by the European Commission between 2008 - 2013 to develop a framework in which a homogeneous swarm of miniature interdependent robots can co-assemble into a larger robotic organism to gain problem-solving momentum. One of the key aspects of Symbrion is inspired by the biological world: an artificial genome that allows storing and evolution of suboptimal configurations in order to increased the speed of adaptation. A large part of the developments within Symbrion is open-source and open-hardware.

Quantitative accomplishment

• The robot with most active modules has 56 units (polybot centipede, PARC)
• The smallest actuated modular unit has a size of 12 mm
• The largest actuated modular unit (by volume) has the size of 8 m^3 (GHFC)giant helium filled catoms, CMU
• The strongest actuation modules are able to lift 5 identical horizontally cantilevered units.(PolyBot g1v5, PARC)
• The fastest modular robot can move at 23 unit-sizes/second.(CKbot, dynamic rolling, ISER'06)
• The largest simulated system contained many hundreds of thousands of units.

Challenges, solutions, and opportunities

Since the early demonstrations of early modular self-reconfiguring systems, the size, robustness and performance has been continuously improving. In parallel, planning and control algorithms have been progressing to handle thousands of units. There are, however, several key steps that are necessary for these systems to realize their promise of adaptability, robustness and low cost. These steps can be broken down into challenges in the hardware design, in planning and control algorithms and in application. These challenges are often intertwined.

Hardware design challenges

The extent to which the promise of self-reconfiguring robotic systems can be realized depends critically on the numbers of modules in the system. To date, only systems with up to about 50 units have been demonstrated, with this number stagnating over almost a decade. There are a number of fundamental limiting factors that govern this number:

• Limits on strength, precision, and field robustness (both mechanical and electrical) of bonding/docking interfaces between modules
• Limits on motor power, motion precision and energetic efficiency of units, (i.e. specific power, specific torque)
• Hardware/software design. Hardware that is designed to make the software problem easier. Self-reconfiguring systems have more tightly coupled hardware and software than any other existing system.

Planning and control challenges

Though algorithms have been developed for handling thousands of units in ideal conditions, challenges to scalability remain both in low-level control and high-level planning to overcome realistic constraints:

• Algorithms for parallel-motion for large scale manipulation and locomotion
• Algorithms for robustly handling a variety of failure modes, from misalignments, dead-units (not responding, not releasing) to units that behave erratically.
• Algorithms that determine the optimal configuration for a given task
• Algorithms for optimal (time, energy) reconfiguration plan
• Efficient and scalable (asynchronous) communication among multiple units

Application challenges

Though the advantages of Modular self-reconfiguring robotic systems is largely recognized, it has been difficult to identify specific application domains where benefits can be demonstrated in the short term. Some suggested applications are

• Space exploration and Space colonization applications, e.g. Lunar colonization
• Construction of large architectural systems
• Deep sea exploration/mining
• Search and rescue in unstructured environments
• Rapid construction of arbitrary tools under space/weight constraints
• Disaster relief shelters for displaced peoples
• Shelters for impoverished areas which require little on-the-ground expertise to assemble

Grand Challenges

Several robotic fields have identified Grand Challenges that act as a catalyst for development and serve as a short-term goal in absence of immediate killer apps. The Grand Challenge is not in itself a research agenda or milestone, but a means to stimulate and evaluate coordinated progress across multiple technical frontiers. Several Grand Challenges have been proposed for the modular self-reconfiguring robotics field:

• Demonstration of a system with >1000 units. Physical demonstration of such a system will inevitably require rethinking key hardware and algorithmic issues, as well as handling noise and error.
• Robosphere. A self-sustaining robotic ecology, isolated for a long period of time (1 year) that needs to sustain operation and accomplish unforeseen tasks without any human presence.
• Self replication A system with many units capable of self replication by collecting scattered building blocks will require solving many of the hardware and algorithmic challenges.
• Ultimate Construction A system capable of making objects out of the components of, say, a wall.
• Biofilter analogy If the system is ever made small enough to be injected into a mammal, one task may be to monitor molecules in the blood stream and allow some to pass and others not to, somewhat like the blood–brain barrier. As a challenge, an analogy may be made where system must be able to:
  • be inserted into a hole one module's diameter.
  • travel some specified distance in a channel that is say roughly 40 x 40 module diameters in area.
  • form a barrier fully conforming to the channel (whose shape is non-regular, and unknown beforehand).
  • allow some objects to pass and others not to (not based on size).
  • Since sensing is not the emphasis of this work, the actual detection of the passable objects should be made trivial.

Inductive transducers

A unique potential solution that can be exploited is the use of inductors as transducers. This could be useful for dealing with docking and bonding problems. At the same time it could also be beneficial for its capabilities of docking detection (alignment and finding distance), power transmission, and (data signal) communication. A proof-of-concept video can be seen here. The rather limited exploration down this avenue is probably a consequence of the historical lack of need in any applications for such an approach.

Google Groups

Self-Reconfiguring and Modular Technology is a group for discussion of the perception and understanding of the developing field.robotics.

Modular Robotics Google Group is an open public forum dedicated to announcements of events in the field of Modular Robotics. This medium is used to disseminate calls to workshops, special issues and other academic activities of interest to modular robotics researchers. The founders of this Google group intend it to facilitate the exchange of information and ideas within the community of modular robotics researchers around the world and thus promote acceleration of advancements in modular robotics. Anybody who is interested in objectives and progress of Modular Robotics can join this Google group and learn about the new developments in this field.

Websites dedicated specifically to exploring this technology

• "Flexibility Envelope". Self Reconfiguring Modular Robotics And The Future Created.
• "Self Reconfigurable Modular Technology". Collection of Web Sites, Web Pages, Video Clips, Articles, and Documents.

Natural computing

From Wikipedia, the free encyclopedia

Natural computing, also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials (e.g., molecules) to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence, artificial immune systems, fractal geometry, artificial life, DNA computing, and quantum computing, among others.

 

Computational paradigms studied by natural computing are abstracted from natural phenomena as diverse as self-replication, the functioning of the brain, Darwinian evolution, group behavior, the immune system, the defining properties of life forms, cell membranes, and morphogenesis. Besides traditional electronic hardware, these computational paradigms can be implemented on alternative physical media such as biomolecules (DNA, RNA), or trapped-ion quantum computing devices.

Dually, one can view processes occurring in nature as information processing. Such processes include self-assembly, developmental processes, gene regulation networks, protein–protein interaction networks, biological transport (active transport, passive transport) networks, and gene assembly in unicellular organisms. Efforts to understand biological systems also include engineering of semi-synthetic organisms, and understanding the universe itself from the point of view of information processing. Indeed, the idea was even advanced that information is more fundamental than matter or energy. The Zuse-Fredkin thesis, dating back to the 1960s, states that the entire universe is a huge cellular automaton which continuously updates its rules. Recently it has been suggested that the whole universe is a quantum computer that computes its own behaviour.

Nature-inspired models of computation

The most established "classical" nature-inspired models of computation are cellular automata, neural computation, and evolutionary computation. More recent computational systems abstracted from natural processes include swarm intelligence, artificial immune systems, membrane computing, and amorphous computing. Detailed reviews can be found in many books .

Cellular automata

A cellular automaton is a dynamical system consisting of an array of cells. Space and time are discrete and each of the cells can be in a finite number of states. The cellular automaton updates the states of its cells synchronously according to the transition rules given a priori. The next state of a cell is computed by a transition rule and it depends only on its current state and the states of its neighbors. 

Conway's Game of Life is one of the best-known examples of cellular automata, shown to be computationally universal. Cellular automata have been applied to modelling a variety of phenomena such as communication, growth, reproduction, competition, evolution and other physical and biological processes.

Neural computation

Neural computation is the field of research that emerged from the comparison between computing machines and the human nervous system. This field aims both to understand how the brain of living organisms works (brain theory or computational neuroscience), and to design efficient algorithms based on the principles of how the human brain processes information (Artificial Neural Networks, ANN ).

An artificial neural network is a network of artificial neurons. An artificial neuron A is equipped with a function ${\displaystyle f_{A}}$, receives n real-valued inputs ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ with respective weights ${\displaystyle w_{1},w_{2},\ldots ,w_{n}}$, and it outputs ${\displaystyle f_{A}(w_{1}x_{1}+w_{2}x_{2}+\ldots +w_{n}x_{n})}$. Some neurons are selected to be the output neurons, and the network function is the vectorial function that associates to the n input values, the outputs of the m selected output neurons. Note that different choices of weights produce different network functions for the same inputs. Back-propagation is a supervised learning method by which the weights of the connections in the network are repeatedly adjusted so as to minimize the difference between the vector of actual outputs and that of desired outputs. Learning algorithms based on backwards propagation of errors can be used to find optimal weights for given topology of the network and input-output pairs.

Evolutionary computation

Evolutionary computation is a computational paradigm inspired by Darwinian evolution. 

An artificial evolutionary system is a computational system based on the notion of simulated evolution. It comprises a constant- or variable-size population of individuals, a fitness criterion, and genetically inspired operators that produce the next generation from the current one. The initial population is typically generated randomly or heuristically, and typical operators are mutation and recombination. At each step, the individuals are evaluated according to the given fitness function (survival of the fittest). The next generation is obtained from selected individuals (parents) by using genetically inspired operators. The choice of parents can be guided by a selection operator which reflects the biological principle of mate selection. This process of simulated evolution eventually converges towards a nearly optimal population of individuals, from the point of view of the fitness function.

The study of evolutionary systems has historically evolved along three main branches: Evolution strategies provide a solution to parameter optimization problems for real-valued as well as discrete and mixed types of parameters. Evolutionary programming originally aimed at creating optimal "intelligent agents" modelled, e.g., as finite state machines. Genetic algorithms applied the idea of evolutionary computation to the problem of finding a (nearly-)optimal solution to a given problem. Genetic algorithms initially consisted of an input population of individuals encoded as fixed-length bit strings, the genetic operators mutation (bit flips) and recombination (combination of a prefix of a parent with the suffix of the other), and a problem-dependent fitness function. Genetic algorithms have been used to optimize computer programs, called genetic programming, and today they are also applied to real-valued parameter optimization problems as well as to many types of combinatorial tasks. 

Estimation of Distribution Algorithm (EDA), on the other hand, are evolutionary algorithms that substitute traditional reproduction operators by model-guided ones. Such models are learned from the population by employing machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled or generated from guided-crossover.

Swarm intelligence

Swarm intelligence, sometimes referred to as collective intelligence, is defined as the problem solving behavior that emerges from the interaction of individual agents (e.g., bacteria, ants, termites, bees, spiders, fish, birds) which communicate with other agents by acting on their local environments. 

Particle swarm optimization applies this idea to the problem of finding an optimal solution to a given problem by a search through a (multi-dimensional) solution space. The initial set-up is a swarm of particles, each representing a possible solution to the problem. Each particle has its own velocity which depends on its previous velocity (the inertia component), the tendency towards the past personal best position (the nostalgia component), and its tendency towards a global neighborhood optimum or local neighborhood optimum (the social component). Particles thus move through a multidimensional space and eventually converge towards a point between the global best and their personal best. Particle swarm optimization algorithms have been applied to various optimization problems, and to unsupervised learning, game learning, and scheduling applications.

In the same vein, ant algorithms model the foraging behaviour of ant colonies. To find the best path between the nest and a source of food, ants rely on indirect communication by laying a pheromone trail on the way back to the nest if they found food, respectively following the concentration of pheromones if they are looking for food. Ant algorithms have been successfully applied to a variety of combinatorial optimization problems over discrete search spaces.

Artificial immune systems

Artificial immune systems (a.k.a. immunological computation or immunocomputing) are computational systems inspired by the natural immune systems of biological organisms. 

Viewed as an information processing system, the natural immune system of organisms performs many complex tasks in parallel and distributed computing fashion. These include distinguishing between self and nonself, neutralization of nonself pathogens (viruses, bacteria, fungi, and parasites), learning, memory, associative retrieval, self-regulation, and fault-tolerance. Artificial immune systems are abstractions of the natural immune system, emphasizing these computational aspects. Their applications include computer virus detection, anomaly detection in a time series of data, fault diagnosis, pattern recognition, machine learning, bioinformatics, optimization, robotics and control.

Membrane computing

Membrane computing investigates computing models abstracted from the compartmentalized structure of living cells effected by membranes. A generic membrane system (P-system) consists of cell-like compartments (regions) delimited by membranes, that are placed in a nested hierarchical structure. Each membrane-enveloped region contains objects, transformation rules which modify these objects, as well as transfer rules, which specify whether the objects will be transferred outside or stay inside the region. Regions communicate with each other via the transfer of objects. The computation by a membrane system starts with an initial configuration, where the number (multiplicity) of each object is set to some value for each region (multiset of objects). It proceeds by choosing, nondeterministically and in a maximally parallel manner, which rules are applied to which objects. The output of the computation is collected from an a priori determined output region.

Applications of membrane systems include machine learning, modelling of biological processes (photosynthesis, certain signaling pathways, quorum sensing in bacteria, cell-mediated immunity), as well as computer science applications such as computer graphics, public-key cryptography, approximation and sorting algorithms, as well as analysis of various computationally hard problems.

Amorphous computing

In biological organisms, morphogenesis (the development of well-defined shapes and functional structures) is achieved by the interactions between cells guided by the genetic program encoded in the organism's DNA.

Inspired by this idea, amorphous computing aims at engineering well-defined shapes and patterns, or coherent computational behaviours, from the local interactions of a multitude of simple unreliable, irregularly placed, asynchronous, identically programmed computing elements (particles). As a programming paradigm, the aim is to find new programming techniques that would work well for amorphous computing environments. Amorphous computing also plays an important role as the basis for "cellular computing" (see the topics synthetic biology and cellular computing, below).

Synthesizing nature by means of computing

Artificial life

Artificial life (ALife) is a research field whose ultimate goal is to understand the essential properties of life organisms  by building, within electronic computers or other artificial media, ab initio systems that exhibit properties normally associated only with living organisms. Early examples include Lindenmayer systems (L-systems), that have been used to model plant growth and development. An L-system is a parallel rewriting system that starts with an initial word, and applies its rewriting rules in parallel to all letters of the word.

Pioneering experiments in artificial life included the design of evolving "virtual block creatures" acting in simulated environments with realistic features such as kinetics, dynamics, gravity, collision, and friction. These artificial creatures were selected for their abilities endowed to swim, or walk, or jump, and they competed for a common limited resource (controlling a cube). The simulation resulted in the evolution of creatures exhibiting surprising behaviour: some developed hands to grab the cube, others developed legs to move towards the cube. This computational approach was further combined with rapid manufacturing technology to actually build the physical robots that virtually evolved. This marked the emergence of the field of mechanical artificial life. 

The field of synthetic biology explores a biological implementation of similar ideas. Other research directions within the field of artificial life include artificial chemistry as well as traditionally biological phenomena explored in artificial systems, ranging from computational processes such as co-evolutionary adaptation and development, to physical processes such as growth, self-replication, and self-repair.

Nature-inspired novel hardware

All of the computational techniques mentioned above, while inspired by nature, have been implemented until now mostly on traditional electronic hardware. In contrast, the two paradigms introduced here, molecular computing and quantum computing, employ radically different types of hardware.

Molecular computing

Molecular computing (a.k.a. biomolecular computing, biocomputing, biochemical computing, DNA computing) is a computational paradigm in which data is encoded as biomolecules such as DNA strands, and molecular biology tools act on the data to perform various operations (e.g., arithmetic or logical operations). 

The first experimental realization of special-purpose molecular computer was the 1994 breakthrough experiment by Leonard Adleman who solved a 7-node instance of the Hamiltonian Path Problem solely by manipulating DNA strands in test tubes. DNA computations start from an initial input encoded as a DNA sequence (essentially a sequence over the four-letter alphabet {A, C, G, T}), and proceed by a succession of bio-operations such as cut-and-paste (by restriction enzymes and ligases), extraction of strands containing a certain subsequence (by using Watson-Crick complementarity), copy (by using polymerase chain reaction that employs the polymerase enzyme), and read-out. Recent experimental research succeeded in solving more complex instances of NP-complete problems such as a 20-variable instance of 3SAT, and wet DNA implementations of finite state machines with potential applications to the design of smart drugs. 

DNA tile self-assembly of a Sierpinski triangle, starting from a seed obtained by the DNA origami technique

 

One of the most notable contributions of research in this field is to the understanding of self-assembly. Self-assembly is the bottom-up process by which objects autonomously come together to form complex structures. Instances in nature abound, and include atoms binding by chemical bonds to form molecules, and molecules forming crystals or macromolecules. Examples of self-assembly research topics include self-assembled DNA nanostructures such as Sierpinski triangles or arbitrary nanoshapes obtained using the DNA origami technique, and DNA nanomachines such as DNA-based circuits (binary counter, bit-wise cumulative XOR), ribozymes for logic operations, molecular switches (DNA tweezers), and autonomous molecular motors (DNA walkers). 

Theoretical research in molecular computing has yielded several novel models of DNA computing (e.g. splicing systems introduced by Tom Head already in 1987) and their computational power has been investigated. Various subsets of bio-operations are now known to be able to achieve the computational power of Turing machines.

Quantum computing

A quantum computer processes data stored as quantum bits (qubits), and uses quantum mechanical phenomena such as superposition and entanglement to perform computations. A qubit can hold a "0", a "1", or a quantum superposition of these. A quantum computer operates on qubits with quantum logic gates. Through Shor's polynomial algorithm for factoring integers, and Grover's algorithm for quantum database search that has a quadratic time advantage, quantum computers were shown to potentially possess a significant benefit relative to electronic computers.

Quantum cryptography is not based on the complexity of the computation, but on the special properties of quantum information, such as the fact that quantum information cannot be measured reliably and any attempt at measuring it results in an unavoidable and irreversible disturbance. A successful open air experiment in quantum cryptography was reported in 2007, where data was transmitted securely over a distance of 144 km. Quantum teleportation is another promising application, in which a quantum state (not matter or energy) is transferred to an arbitrary distant location. Implementations of practical quantum computers are based on various substrates such as ion-traps, superconductors, nuclear magnetic resonance, etc. As of 2006, the largest quantum computing experiment used liquid state nuclear magnetic resonance quantum information processors, and could operate on up to 12 qubits.

Nature as information processing

The dual aspect of natural computation is that it aims to understand nature by regarding natural phenomena as information processing. The two main directions of research in this area are systems biology and synthetic biology.

Systems biology

Computational systems biology (or simply systems biology) is an integrative and qualitative approach that investigates the complex communications and interactions taking place in biological systems. Thus, in systems biology, the focus of the study is the interaction networks themselves and the properties of biological systems that arise due to these networks, rather than the individual components of functional processes in an organism. This type of research on organic components has focused strongly on four different interdependent interaction networks: gene-regulatory networks, biochemical networks, transport networks, and carbohydrate networks. 

Gene regulatory networks comprise gene-gene interactions, as well as interactions between genes and other substances in the cell. Genes are transcribed into messenger RNA (mRNA), and then translated into proteins according to the genetic code. Each gene is associated with other DNA segments (promoters, enhancers, or silencers) that act as binding sites for activators or repressors for gene transcription. Genes interact with each other either through their gene products (mRNA, proteins) which can regulate gene transcription, or through small RNA species that can directly regulate genes. These gene-gene interactions, together with genes' interactions with other substances in the cell, form the most basic interaction network: the gene regulatory networks. They perform information processing tasks within the cell, including the assembly and maintenance of other networks. Models of gene regulatory networks include random and probabilistic Boolean networks, asynchronous automata, and network motifs.

Another viewpoint is that the entire genomic regulatory system is a computational system, a genomic computer. This interpretation allows one to compare human-made electronic computation with computation as it occurs in nature.

A comparison between genomic and electronic computers

	Genomic computer	Electronic computer
Architecture	changeable	rigid
Components construction	as-needed basis	from the start
Coordination	causal coordination	temporal synchrony
Distinction between hardware and software	No	Yes
Transport media	molecules and ions	wires

In addition, unlike a conventional computer, robustness in a genomic computer is achieved by various feedback mechanisms by which poorly functional processes are rapidly degraded, poorly functional cells are killed by apoptosis, and poorly functional organisms are out-competed by more fit species.

Biochemical networks refer to the interactions between proteins, and they perform various mechanical and metabolic tasks inside a cell. Two or more proteins may bind to each other via binding of their interactions sites, and form a dynamic protein complex (complexation). These protein complexes may act as catalysts for other chemical reactions, or may chemically modify each other. Such modifications cause changes to available binding sites of proteins. There are tens of thousands of proteins in a cell, and they interact with each other. To describe such a massive scale interactions, Kohn maps were introduced as a graphical notation to depict molecular interactions in succinct pictures. Other approaches to describing accurately and succinctly protein–protein interactions include the use of textual bio-calculus or pi-calculus enriched with stochastic features.

Transport networks refer to the separation and transport of substances mediated by lipid membranes. Some lipids can self-assemble into biological membranes. A lipid membrane consists of a lipid bilayer in which proteins and other molecules are embedded, being able to travel along this layer. Through lipid bilayers, substances are transported between the inside and outside of membranes to interact with other molecules. Formalisms depicting transport networks include membrane systems and brane calculi.

Synthetic biology

Synthetic biology aims at engineering synthetic biological components, with the ultimate goal of assembling whole biological systems from their constituent components. The history of synthetic biology can be traced back to the 1960s, when François Jacob and Jacques Monod discovered the mathematical logic in gene regulation. Genetic engineering techniques, based on recombinant DNA technology, are a precursor of today's synthetic biology which extends these techniques to entire systems of genes and gene products.

Along with the possibility of synthesizing longer and longer DNA strands, the prospect of creating synthetic genomes with the purpose of building entirely artificial synthetic organisms became a reality. Indeed, rapid assembly of chemically synthesized short DNA strands made it possible to generate a 5386bp synthetic genome of a virus.

Alternatively, Smith et al. found about 100 genes that can be removed individually from the genome of Mycoplasma Genitalium. This discovery paves the way to the assembly of a minimal but still viable artificial genome consisting of the essential genes only.

A third approach to engineering semi-synthetic cells is the construction of a single type of RNA-like molecule with the ability of self-replication. Such a molecule could be obtained by guiding the rapid evolution of an initial population of RNA-like molecules, by selection for the desired traits.

Another effort in this field is towards engineering multi-cellular systems by designing, e.g., cell-to-cell communication modules used to coordinate living bacterial cell populations.

Cellular computing

Computation in living cells (a.k.a. cellular computing, or in-vivo computing) is another approach to understand nature as computation. One particular study in this area is that of the computational nature of gene assembly in unicellular organisms called ciliates. Ciliates store a copy of their DNA containing functional genes in the macronucleus, and another "encrypted" copy in the micronucleus. Conjugation of two ciliates consists of the exchange of their micronuclear genetic information, leading to the formation of two new micronuclei, followed by each ciliate re-assembling the information from its new micronucleus to construct a new functional macronucleus. The latter process is called gene assembly, or gene re-arrangement. It involves re-ordering some fragments of DNA (permutations and possibly inversion) and deleting other fragments from the micronuclear copy. From the computational point of view, the study of this gene assembly process led to many challenging research themes and results, such as the Turing universality of various models of this process. From the biological point of view, a plausible hypothesis about the "bioware" that implements the gene-assembly process was proposed, based on template guided recombination.

Other approaches to cellular computing include developing an in vivo programmable and autonomous finite-state automaton with E. coli, and designing and constructing in vivo cellular logic gates and genetic circuits that harness the cell's existing biochemical processes.

Scientists create first billion-atom biomolecular simulation

by Nick Njegomir, Los Alamos National Laboratory

Original link:  https://phys.org/news/2019-04-scientists-billion-atom-biomolecular-simulation.html?fbclid=IwAR0dekR6eqtJoHBgLR1zNSJZ6c1QWvBX7NDzhtiXOeBGUssX0yHu_gOgAsg 

Researchers at Los Alamos National Laboratory have created the largest simulation to date of an entire gene of DNA, a feat that required one billion atoms to model and will help researchers to better understand and develop cures for diseases like cancer.

"It is important to understand DNA at this level of detail because we want to understand precisely how genes turn on and off," said Karissa Sanbonmatsu, a structural biologist at Los Alamos. "Knowing how this happens could unlock the secrets to how many diseases occur."

Modeling genes at the atomistic level is the first step toward creating a complete explanation of how DNA expands and contracts, which controls genetic on/off switching.

Sanbonmatsu and her team ran the breakthrough simulation on Los Alamos' Trinity supercomputer, the sixth fastest in the world. The capabilities of Trinity primarily support the National Nuclear Security Administration stockpile stewardship program, which ensures safety, security, and effectiveness of the nation's nuclear stockpile.

DNA is the blueprint for all living things and holds the genes that encode the structures and activity in the human body. There is enough DNA in the human body to wrap around the earth 2.5 million times, which means it is compacted in a very precise and organized way.

The long, string-like DNA molecule is wound up in a network of tiny, molecular spools. The ways that these spools wind and unwind turn genes on and off. Research into this spool network is known as epigenetics, a new, growing field of science that studies how bodies develop inside the womb and how diseases form.

When DNA is more compacted, genes are turned off and when the DNA expands, genes are turned on. Researchers do not yet understand how or why this happens.

While atomistic model is key to solving the mystery, simulating DNA at this level is no easy task and requires massive computing power.

"Right now, we were able to model an entire gene with the help of the Trinity supercomputer at Los Alamos," said Anna Lappala, a polymer physicist at Los Alamos. "In the future, we'll be able to make use of exascale supercomputers, which will give us a chance to model the full genome."

Exascale computers are the next generation of supercomputers and will run calculations many times faster than current machines. With that kind of computing power, researchers will be able to model the entire human genome, providing even more insight into how genes turn on and off.

In the new study published in the Journal of Computational Chemistry April 17, the Los Alamos team partnered with researchers from the RIKEN Center for Computational Science in Japan, the New Mexico Consortium and New York University to collect a large number of different kinds of experimental data and put them together to create an all-atom model that is consistent with that data.

Simulations of this kind are informed by experiments, including chromatin conformation capture, cryo-electron microscopy and X-ray crystallography as well as a number of sophisticated computer modeling algorithms from Jaewoon Jung (RIKEN) and Chang-Shung Tung (Los Alamos).