Research Abstracts - 2007

Our ability to control emergent phenomena depends on decomposing them into aspects susceptible to independent engineering. The amorphous medium abstraction separates what behavior is desired on a continuous space and how the behavior is implemented on a sensor/actuator network approximating the space, while the Proto language provides a means of composing self-organizing primitives on an amorphous medium. We thus separate the engineering problem into three components: a discrete kernel to emulate an amorphous medium and distribute code, a compiler for Proto, and implementations of high-level coordination and homeostasis primitives, allowing simple and concise expression of programs controlling spatial behaviors. Programs written using our implementation of this framework have been verified in simulation on over ten thousand nodes, as well as on a network of Berkeley Motes.

Self-Managing Systems Engineering

The study of self-organizing systems has now reached the tool-building phase, in which a new discipline of self-managing systems engineering can begin to emerge.

The next step is to refine the principles of self-organization into a system of composable parts suitable for engineering---as the principles of electromagnetism are captured for electronic engineering in components like capacitors, transistors and resistors.

To transform a science into an engineering discipline, we must identify an operating range, decouple aspects of the problem from one another, create standard interfaces for composition, identify primitive components which conform to the standards, and create rules of abstraction which hide the complexity of systems of components.

We have begun this process in the domain of sensor/actuator network applications, observing that in many applications, the network is deployed to approximate a physical space, and that what is being programmed is the space rather than the network. This observation allows us to decouple self-management problems using the amorphous medium abstraction, so that global behavior descriptions in our Proto language can be compiled automatically into locally executed code which produces emergent phenomena matching the global description. We have experimentally verified our code both in simulation and (for small programs) on a network of sensor/actuator nodes (Berkeley Motes).

Examples

Plane wave

Snapshots of a plane wave program being verified on 10,000 simulated devices and on a network of 16 motes. In the simulator, the period and direction of the wave is determined by the placement of source (yellow) and destination (magenta) markers in the devices' sensor field. For the Mote verification, a synthetic coordinate is supplied for phase.

Threat Avoidance

Snapshot of a threat avoidance program being verified on 1,000 simulated devices. The nodes calculate a probability of survival given the known threats (orange) and create a gradient of best movements to guide a traveller to the destination (pink)

Target Tracking

Snapshot of a target tracking program being verified on 100 simulated devices. Nodes detecting the target (orange) calculate their average location and transmit it back to the node monitoring the data (purple).

References:

[1] Jacob Beal and Jonathan Bachrach. Infrastructure for Engineered Emergence on Sensor/Actuator Networks. To appear in IEEE Intelligent Systems, 21(1), March/April 2006.