Saturday, July 16, 2005

Paper: Amorphous Computing

The big site:

Nice problem statement:

How does one engineer prespecified , coherent behavior from the
cooperation of immense numbers of unreliable parts that are interconnected in
unknown irregular and time varying ways ?

All techniques for organizing computation assume: preciseness and reliability.
We may be giving up these in amorphous computing.

Appropriate organizing principles and programming methodogies for controlling amorhpous systems.

Bio examples: Marker propagation via diffusion, control of shape via cell mobility

Getting acceptable answers, not the right answers, even in the face of unrelability.

An amorphous computing system is a system of irregularly placed, async, locally interacting computing elements.

Related areas: Self-organizing systems

Gradient phenomenon. Growing points. Inhibition of gradient by another gradient. Tropism (only particles near A spread the scent from B)

GPL compiler which takes abstract concepts like growing points etc and compiles a set of identical rules for all the modules.
Serial conceptualization of the underlying parallel computation.

Implementation at at the particle level:
Weiss's system
Program at each module: set of independent rules
A set of binary markers, and rules are enabled by boolean combo of markers.
Markers controlled by messages, rules and timers.

Group based hierarchies

forming a set of modules into a group. These groups then can form higher groups. Each group does something specailized. Hierarchy of groups.

Like organization of cells into tissues, tissues into organs, and organs into systems

Future ideas:
Can one create a language of shapes - analogous to the growing point language - that would permit programmers to generate prespecified macroscopic shapes in amorhpous media, by prescribing local shae changes by individual particles ?

The most powerful techniques for amorphous computing will be the ones that will tie computation intimately to particle activiation and mobility, and to physical constraints from the environment.

Skipped Cellular Computing

Programmable Self-Assembly Using Biologically Inspired Multiagent Control

Gives good insight into
1. The need for specialized decentralized approahces for global behavior
2. What special constraints do such systems impose ?
3. Limitations of existing approaches like hierarchy based centrazlied control ?
4. Exploiting new areas like: morphogenesis and developmental biology

An interesting point it makes relevant to my project here:
How can we decompose a global problems into the primitives which we know how to do ?
Can this be automated like a compiler ?
What are those primitives which are general enough or useful enough to be used widely enough by a large number of global tasks ?

Multiagent Control of Self-reconfigurable Robots

This paper is the same as the Emergent Structures paper.
See the Powerpoint PPT I gave for that paper.

Thursday, June 30, 2005


  • Suitable for Real time analysis using a input, analysis, output loop
  • The time step is used to solve the differential equations of motion of a collection of particle masses.

What are the forces they consider:

  • Mechanical forces from distortion of connected elements
  • Viscous damping forces based on node velocity
  • Contact forces due to collision of surfaces
  • Forces spec as boundary conditions: applied loads etc

    How does the process work ?
    With the forces known on each node, acceleration is calculated. Then the velocity and position at the end of each time step can be calculated using numeric methods for ODEs. (Fourth order Runge Kutta method and an implicit trapezoid method)

    Insights for Claytronics
    One thing to realize here is that for our Claytronics , we don’t really need time steps as we are not considering motion right now. Its just a static analysis
    Second, the forces will be much simpler than described above, resulting in MUCH less computation and faster computation (probably tractable for catoms)

    Accuracy of this method
    The author applies it to two problems: beam with large displacements (max load bearable) and a double frame. The results match very well with theory and finite element analysis.

    Computationally intensive. But this paper analyzes dynamic situations, where movement is involved. In our case, it’s a case of analyzing static equilibrium , which is much simpler. They consider lot of dynamic forces and they have truss or beam elements which significantly complicate analysis.

Wednesday, June 29, 2005

Paper: Distributed Control for 3D Metamorphosis

Paper link

Useful comments
Metamorphic robot systems

Homegenity of modules Advantages: Robustness , adaptability and mass production

Challenge for dist systems for self reconfig is that each module must decide its next move based on the desired final configuration and only its local state , which includes delayed or incomplete global information obtained via communication from other modules

Important Related work
Motion planning: Simulated annealing techniques to drive the reconfig process.
Distributed control: disitrbuted sim annealing approach
Approach of meta modules à treat multiple modules as one and move them together

Emergent structures: another interesting approach : final config is not prespecified but emerges as local rules are applied to the catoms. The specific shape is undeterministic , the emergent structure has some desired functionality.

Key Ideas
Goal ordering:the main idea in the paper
The paper gives an ordering of all the neighbouring empty sites which should be filled as part of the final configuration. The modules them move into the neighouring sites in increasing order.
Ordered goal constraints. Empty Locations in the final goal are filled in a predefined globally known partial order. à introduces monotoicity and stability of the system

Three algorithms are developed based on “ordered-goal” constraint.
a. One is distance based where modules move towards closed unfulfilled goal.
b. Heat based à simulate a heat flow from goal targets to modules along the temperature gradient
c. Hybrid of these two.

Motion constraints
This paper has an indepth discussion and formal. of motion constraints. Main ones are blocking constraints, connectivity constraints and fixed base constraint: one of the modules remains fixed during the entire re-config.

The problem: two different types
Motion planning and motion control problems
Motion planning: given I and F , output all the single steps that lead from I to F. (centr. Approach)
Motion control: give current config, F and current state, output a single step that moves towards final configuration
A hybrid of two also works

Module capabilities assumed (and prob required also in the simulator)
Nice discussion of catom capabilities required for distributed control: Each catom decides where to move based on : 1. current site 2. its current state 3. state of neighbors (from local communicatin) 4. Each catom also has limited sensing to determine collision and disconnection detection

Some specific issues faced in distributed control
Stability, Local Minima, overcrowding (hindering further movement)

The way movement happens:

There are three phases:
1. Reset phase : like a barrier in parallel comm.: all catoms come in sync
2. Communication phase: All modules communicate about their current positions and state
3. Decision phase: decide where to move

Goal Ordering

Two methods to reach unfulfilled goal positions ( sites which need to be filled to reach the global specified structure):
a. distance based method: Euclidean distance
b. heat based method: empty sites near to goals are given higher temperature. High temperature vacant positions are given higher priority.

They use the methods to make different shapes like falt disk, solid ball, hollow ball and cup. The time required is linear in the number of modules , which is pretty good.

Other Future ideas

Decompose a shape into a set of simple ones , design reconfiguration algorithms for each simple shape and then recombine the steps.