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.