Self Organising a Coordinate System

Radhika Nagpal

Amorphous computing and MEMs research will enable novel applications of computing coupled with the environment. For example smart paint that detects shadows on a wall, bridge surfaces that detect load, sensors that monitor chemical concentrations in the soil, or an airplane wing covered with sensors and actuators that reduce. In such environments an important goal is to self-organise global information through collaboration between large number of elements, each of which has limited resources and little global knowledge.

For many such applications, coordinates are required to implement sophisticated control laws. A coordinate system can also assist in pattern generation and shape detection. In addition, a coordinate system can also provide global naming and routing to aid in non-local communication. However since the processors have no knowledge of their location or the orientation of their neighbors, the challenge is for the processors to self organise a logical coordinate system that maps, under some affine transformation, to the physical placement of the processors.

Coordinate System based on Triangulation

A point on a 2-dimensional plane can be uniquely described by its distance from 3 non-colinear reference points. We use this idea of triangulation to form a coordinate system on an amorphous computer. Three non-colinear anchors are chosen and processors determine their distances from each of these anchors.

In an amorphous computer the processors are distributed randomly and densely on a surface, in this case we consider a 2-d plane. Each processor can communicate with a small neighborhood of processors within distance r communication radius. Thus there is a maximum distance associated with a communication hop.

The distance from a source point can be calculated by generating a gradient wave. The source initiates the wave by sending its neighbors a message with a counter set to zero. Each recipient remembers the value of the counter and forwards the message to all its neighbors with the count incremented by one. Hence a wave of messages propagates outwards from the source. The wave is prevented from travelling backwards by maintaining the minimum counter value received and ignoring subsequent messages containing larger values. This distance wave is essentially a breath-first-search tree that calculates the shortest path (in hops) from the source to each processor. However in an Amorphous computer, we see that the shortest path is usually along the shortest distance if the average neighborhood size is higher than 15. Hence, as shown in the picture, the wave forms concentric circles around the source and the hop count gives a good (albeit coarse) estimate of distance from the source.

This estimate can be refined through a smoothing step. Each processor computes an average of its neighbor values and itself. In the 1-d case, a distance wave looks like a staircase function and smoothing results in the straight line that passes through the center of the staircase. Other smoothing functions are being considered. Smoothing (unlike the distance wave) is very sensitive to local variations in the random distribution.

The three anchors can be chosen by an external stimulus or they can select themselves in a distributed manner - like creating a triangle with a compass. Modifications to the algorithms allow for asynchronicity and bounds on the running time and expected error can be derived.

Accuracy

The error in the measurement stems from three sources - errors in measuring distance using gradients due to average density, errors in smoothing due to variations in density and the inherent discrete nature of the problem. However as we see from the pictures the error also has a spatial component to it. This is because the errors in the distance from the three anchors does not combine linearly. Rather the error has a large effect outside the triangle especially behind triangle vertices. But it has less effect along the bisectors of the triangle sides and little to no effect at the centroid of the triangle. This can be derived from the formula for computing the position from the three distances. On the whole however the average error is small (less than half the communication radius) within the triangle. Other methods are also being explored (see paper by Daniel Coore) and seem to have similar average errors.

The lines represent the error between the logical and actual positions before smoothing. The error (length of the lines) increases outside the triangle. The error inside the triangle is small. This is inspite of the fact that the error in computed distances on average is the same for points inside and outside the traingle. Therefore increasing the size of the triangle enclosed by the anchors reduces the overall error. However we can see that the resolution is coarse. The lines look like fans - that means many processors believe that they have the same position relative to the anchors
After smoothing the resolution improves dramatically. However the larger errors (possibly due to edge effects) can not be corrected by smoothing. This pictures plots the level curves of function
(max (floor absolute x) (floor absolute y))

Conclusion

By this technique, randomly distibuted processors can self-organise a coordinate system with low average error and resolution higher than the communication radius. The use of distance waves and triangulation also occurs in Biology. In the morphogenesis of the fly, three anchors are used - the anterior, posterior and dorsal points. Each produces a chemical gradient to effectively form a coordinate system which is used to differentiate the body into segments. The technique of gradients and triangulation has many advantages - it is simple and robust, even when the cell density is non uniform. For more complex surfaces one could form coordinate patches and sew them up into a manifold.