Software Research
Distributed Computing in Claytronics
In a domain of research defined by many of the greatest challenges facing computer scientists and roboticists today, perhaps none is greater than the creation of algorithms and programming language to organize the actions of millions of sub-millimeter scale catoms in a claytronics ensemble.
As a consequence, the research scientists and engineers of the Carnegie Mellon-Intel Claytronics Research Program have formulated a very broad-based and in-depth research program to develop a complete structure of software resources for the creation and operation of the densely distributed network of robotic nodes in a claytronic matrix.
A notable characteristic of a claytronic matrix is its huge concentration of computational power within a small space. For example, an ensemble of catoms with a physical volume of one cubic meter could contain 1 billion catoms. Computing in parallel, these tiny robots would provide unprecedented computing capacity within a space not much larger than a standard packing container. This arrangement of computing capacity creates a challenging new programming environment for authors of software.
A representation of a matrix of approximately 20,000 catoms can be seen in the left frame of the illustration at the top of this column. Because of its vast number of individual computing nodes, the matrix invites comparison with the worldwide reservoir of computing resources connected through the Internet, a medium that not only distributes data around the globe but also enables nodes on the network to share work from remote locations. The physical concentration of millions of computing nodes in the small space of a claytronic ensemble thus suggests for it the metaphor of an Internet that sits on a desk.
An Internet in a Box – Only Generally Speaking
Comparison with the Internet, however, does not represent much of the novel complexity of a claytronic ensemble. For example, a matrix of catoms will not have wires and unique addresses -- which in cyberspace provide fixed paths on which data travels between computers. Without wires to tether them, the atomized nodes of a claytronic matrix will operate in a state of constant flux. The consequences of computing in a network without wires and addresses for individual nodes are significant and largely unfamiliar to the current operations of network technology.
Languages to program a matrix require a more abbreviated syntax and style of command than the lengthy instructions that widely used network languages such as C++ and Java employ when translating data for computers linked to the Internet. Such widely used programming languages work in a network environment where paths between computing nodes can be clearly flagged for the transmission of instructions while the computers remain under the control of individual operators and function with a high degree of independence behind their links to the network.
In contrast to that tightly linked programming environment of multi-functional machines, where C++, Java and similar languages evolved, a claytronic matrix presents a software developer with a highly organized, single-purpose, densely concentrated and physically dynamic network of unwired nodes that create connections by rotating contacts with the closest neighbors. The architecture of this programming realm requires not only instructions that move packets of data through unstable channels. Matrix software must also actuate the constant change in the physical locations of the anonymous nodes while they are transferring the data through the network.
For the Nodes, It’s All about Cooperation
In this environment, the processes of each individual catom must be entirely dedicated to the operational goal of the matrix – which is the formation of dynamic, 3-dimensional shapes. Yet, given the vast number of nodes, the matrix cannot dedicate its global resources to the micro-management of each catom. Thus, every catom must achieve a state of self-actuation in cooperation with its immediate neighbors, and that modality of local cooperation must radiate through the matrix.
Software language for the matrix must convey concise statements of high-level commands in order to be universally distributed. For this purpose, it must possess an economy of syntax that is uncommon among software languages. In place of detailed commands for individual nodes, it must state the conditions toward which the nodes will direct their motion in local groups. In this way, catoms will organize collective actions that gravitate toward the higher-level goals of the ensemble.
A Seamless Ensemble of Form and Functionality
By providing a design to focus constructive rearrangements of individual nodes, software for the matrix will motivate local cooperation among groups of catoms. This protocol reflects a seamless union between form and functionality in the actuation of catoms. It also underscores the opportunity for high levels of creativity in the design of software for the matrix environment, which manipulates the physical architecture of this robotic medium while directing information through it.
In a hexagonal stacking arrangement, for example, rows of catoms in one layer rest within the slight concavities of catom layers above and below them. That placement gives each catom direct communication with as many as 12 other catoms. Such dynamic groupings provide the stage upon which to program catom motion within local areas of the matrix. Such collective actuation will transform the claytronic matrix into the realistic representations of original objects.
The Research Program
In the Carnegie Mellon-Intel Claytronics Software Lab, researchers address several areas of software development, which are described in this section of the website.
Researchers in the Claytronics project have also created Meld and LDP. These new languages for declarative programming provide compact linguistic structures for cooperative management of the motion of millions of modules in a matrix. The center panel above shows a simulation of Meld in which modules in the matrix have been instructed with a very few lines of highly condensed code to swarm toward a target.
In directing the work of the thousands to millions of individual computing devices in an ensemble, claytronics research also anticipates the inevitability of performance errors and system dysfunctions. Such an intense computational environment requires a comparably dynamic and self-directed process for identifying and debugging errors in the execution of programs. One result is a program known as Distributed Watch Points, represented in the snapshot in the right panel below.
The team's extensive work on catom motion, collective actuation and hierarchical motion planning addresses the need for algorithms that convert groups of catoms into primary structures for building dynamic, 3-dimensional representations. Such structures work in a way that can be compared to the muscles, bones and tissues of organic systems. In claytronics, this special class of algorithms will enable the matrix to work with templates suitable to the representations it renders. In this aspect of claytronics development, researchers develop algorithms that will give structural strength and fluid movement to dynamic forms. Snapshots from the simulation of these studies can be seen in the right-side panel at the top of this column and in the left-side panel below.
The team’s software researchers are also creating algorithms that enable catoms to localize their positions among thousands to millions of other catoms in an ensemble. This relational knowledge of individual catoms to the whole matrix is fundamental to the organization and management of catom groups and the formation of cohesive and fluid shapes throughout the matrix. A pictorial context for examining the dynamics of localization is represented by the snapshot of the elephant simulated in the center panel of images below.
As a first step in developing software to program a claytronic ensemble, the team created DPR-Simulator, a tool that permits researchers to model, test and visualize the behavior of catoms. The simulator creates a world in which catoms take on the characteristics that researchers wish to observe. A Linux-based modeling tool, DPRSim can be
downloaded from the website of the Intel Pittsburgh Lab.
The simulated world of DPRSim manifests characteristics that are crucial to understanding the real-time performance of claytronic ensembles. Most important, the activities of catoms in the simulator are governed by laws of the physical universe. Thus simulated catoms reflect the natural effects of gravity, electrical and magnetic forces and other phenomena that will determine the behavior of these devices in reality. DPRSim also provides a visual display that allows researchers to observe the behavior of groups of catoms. In this context, DPRSim allows researchers to model conditions under which they wish to test actions of catoms. At the top and bottom of this column, images present snapshots from simulations of programs generated through DPRSim. Videos from simulations can be seen on other pages of this site.
