Programming Language for Claytronic Ensembles

The Motion of Each Node Is the Object of the Program

For more than a half-century, computer programming languages have evolved many branches to address the accelerating growth in the power of computers and changes in machine configuration to manage information moving through complex networks.   One measure then of the scope of innovation posed by claytronics can be seen in its requirement for a new branch of programming language to enable communication within a distributed network of millions of modular robots. This makes the development of programming languages to control the highly innovative form of distributed computing implemented for a claytronics ensemble a key focus of investigation for the Carnegie Mellon-Intel Claytronics Research Project.

The landscape of systems nanotechnology to which claytronics introduces the programmer presents a largely unexplored architecture for the use of computing machines.   The structure of its vast distributed network features an enormous capacity for parallel computing.   A unique feature of this structure is enormous processing power in a confined space.   The intimate relationship among many tiny yet powerful computing machines accentuates a compelling novelty in the style of programming for a claytronics ensemble.  

While evolution thus far in programming languages has coaxed machines and networks to greater change of internal status, the purpose of programming in claytronics is to achieve changes in the external status of the machines themselves.   The point of the programming is to translate commands into the motion of each machine in its relationship to every other machine.

Programming thus evolves in claytronics from the objective of moving information through static and fixed networks into communication that commands a new dimension in the expressions of computing machines.   From the powerfully confined space of a claytronics ensemble, programming languages begin to explore the largely untapped structural fluidity of millions of tiny robotic modules, which combine their responses to the programmer 's instructions to express a desired state of communication in 3-dimensional space.

To further this evolution in the language of computer programmers, the Carnegie Mellon-Intel Claytronics Research Project in this early stage of its work has created the basis for the evolution of two new programming languages.

Meld

Meld addresses the need to write computer code for an ensemble of robots from a global perspective, enabling the programmer to concentrate on the overall performance of the matrix while finessing the resource-consuming alternative of writing individual instructions for every one of the thousands to millions of catoms in the ensemble.   This form of logical programming represents a heuristic solution to the challenge of controlling the action of such a great number of individual computing nodes.

Meld employs a declarative language that has roots in the logic of P2, a language created for the management of static, overlay networks that share information from many sources of traffic.   Although P2 evolved for networks with a static topology, Meld extends its programming logic to control motion among robotic modules in claytronic ensembles.

Concise Instructions to More Machines  

From a resource standpoint, as measured in many fewer lines of code, Meld is a language whose programs produce results comparable to programs that are from 20 to 30 times longer when written in C++.   This efficiency yields a substantial economy of scale in the operational time and reliability of the matrix.   It also reduces the time a programmer needs to write the code.

Meld provides a reliable paradigm for efficiency in the actuation of cooperative motion among millions of nano-scale robots.   It does this by declaring positions that individual robots achieve within clusters by common rules for direct contact.   Meld manages motion as a continuous process of rule-solving. Each robot engages its contacts until it satisfies all rules it can declare about its physical relationship.

The rules of Meld engage each module in a proving of facts.   The facts stipulate a robot ’s position in relation to neighboring modules.   In effect, this rule-making provides a map for motion.   Applying the rules, a catom achieves a final position when all rules are satisfied.   By their nature, the rules enforce cooperative motions that build the global design of the 3-dimensional object that the ensemble is programmed to represent.    

The logic of proof, which follows from a meldian declaration of positions, results in cooperative motions.   This procedure yields the important result of reducing erroneous moves, such as blocking the motion of neighboring modules or moving modules into isolated or untenable positions, which threaten the stability and integrity of the matrix.

Meld enforces rules by requiring existence of a direct connection between neighboring modules before a fact can be recognized as satisfied.   In effect, this means that every fact and every rule relate first to the location of modules.  

This programming of direct relationships among catoms establishes a context in which particular nodes share facts.   The topology of these relationships narrows the field of information and facts.   In this framework, the language actuates the motion of an individual module.   At the same time, it enables the declaration of a general state of network topology.   Thus, large numbers of modules can test and satisfy the declaration.   The process of rule testing is continuous and widely distributed.   Every individual robot receives necessary facts to determine whether it has satisfied rules governing its location.   At all times, every robot remains in a state of motion or readiness to move.   The evaluation of rules in the ensemble is tireless.   Each catom continues to evaluate its position in relation to a next best move -- even after it has stopped moving.  

Another way of characterizing this dynamic aspect of declarative program is to recognize that rules for combining facts produce new facts that continue to be proven until all rules of proof have been satisfied.   Because most if not all baseline facts state the locations of individual modules in relative positions, the rules drive the proofs until final positions represent the global shape desired for the ensemble.

Revising History the Meld Way    

Motion in the matrix also has a dynamic effect on the quality of historical facts, which are wedded to relative past positions.   Because the process of satisfying rules continues, new positions frequently render previously true facts to be false, particularly when prior truths declare the locations of neighboring robots.   Obviously, the lingering profile of prior positions that hold no future veracity would be rife with error if used in new declarations, just as their presence also wastes space in the physical memory of an ongoing process.  

Meld dismisses old truths that have become false.   The program not only deletes no longer true facts.   It also erases all prior facts derived from them.   With this scrubbing routine, Meld ’s linguistic process constantly refreshes the information upon which the matrix shapes its design.

The programming of motion in Meld enables each robot to actuate with a cooperative relationship to the planned design of the matrix.   It motivates individual modules to move in relation to other modules into positions that support the global result.  

As a language for programming modular robots, Meld provides an efficient logic for writing programs and a linguistic structure suited to the matrix.   At the same time, its interpretation of this programming environment concentrates on the topology of the ensemble and the base facts related to the location of modules through data from sensors on the devices.   An important result is the avoidance of false moves that confuse neighboring modules or isolate a module after it moves.

In this heuristic, Meld also yields an extensive view of the status of the matrix, a set of base facts that contributes to insight about the overall operation while opening approaches to debugging.   Because states other than motion will be modeled as the architecture of the matrix develops, the utility of Meld will be evaluated further in relation to its adaptability as a structure for program logic that can structure changes that extend beyond the current definitions of base facts, which it has demonstrated a capacity to manage.

Locally Distributed Predicates (LDP)

While Meld approaches the management of the matrix from the perspective of logic programming, LDP employs distributive pattern matching.   As a further development of program languages for the matrix, LDP, which stands for Locally Distributed Predicates, provides a means of matching distributed patterns.   This tool enables the programmer to address a larger set of variables with Boolean logic that matches paired conditions and enables the program to search for larger patterns of activity and behavior among groups of modules in the matrix.

While addressing variable conditions related to time, topology and the status of modules, LDP triggers specific actions in parallel with other expressions governing local groups of modules.   A reactive language, LDP grows from earlier research into the analysis of distributed local conditions, which has been used to trigger debugging protocols.   From this base, LDP adds language that enables the programmer to build operations that can be used for more general purposes in the development of the shape of the matrix.

LDP shares with Meld the achievement of dramatically shorter code, the automatic distribution of the program through the matrix and automatic messaging about conditions in the matrix.

As it originates in the research to evaluate conditions throughout the ensemble, its strength is in detection and description of distributed conditions.   From this perspective, it programs locally, focusing upon a bounded number of modules in contact groups while basing its predicates upon Boolean (if, then) expressions, which expand the basic set of variables that the programmer can manage throughout the matrix.

---

Publications and Documents

---