Saturday, July 16, 2005

Paper: Amorphous Computing

The big site: http://www.swiss.ai.mit.edu/projects/amorphous/

Background
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

Ideas
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.