We consider programmable matter that consists of computationally limited devices (which we call particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and establish or release bonds with one another. Under this model, we investigate the feasibility of solving fundamental problems relevant to programmable matter. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information (e.g., particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system), and requires only constant memory per particle.
A variety of work related to programmable matter has recently been proposed and investigated. One can distinguish between active and passive systems. In passive systems, the computational units either have no intelligence (moving and bonding is based only on their structural properties or interactions with their environment), or have limited computational capabilities but cannot control their movements. Examples of research on are DNA computing @cite_25 @cite_29 @cite_5 @cite_2 , tile self-assembly systems (e.g., the surveys in @cite_20 @cite_3 @cite_31 ), and population protocols @cite_11 . We will not describe these models in detail as they are of little relevance to our approach. , on the other hand, are composed of computational units which can control the way they act and move in order to solve a specific task. We discuss prominent examples of active systems here, as they are more comparable to our work.
@cite_29 @cite_3 @cite_2 @cite_5 @cite_31 @cite_25 @cite_20 @cite_11
2054579370 2079425200 1567090568 2148219472 2050994027 1977312644 2044709436 1565089780
Abstract We show how DNA-based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first solving several decision problems. Our methods also enable random sampling of satisfying assignments. We first give an introduction to the field of tile-based self-assembly, focusing primarily on theoretical models and their algorithmic nature. We start with a description of Winfree’s abstract Tile Assembly Model (aTAM) and survey a series of results in that model, discussing topics such as the shapes which can be built and the computations which can be performed, among many others. Next, we introduce the more experimentally realistic kinetic Tile Assembly Model (kTAM) and provide an overview of kTAM results, focusing especially on the kTAM’s ability to model errors and several results targeted at preventing and correcting errors. We then describe the 2-Handed Assembly Model (2HAM), which allows entire assemblies to combine with each other in pairs (as opposed to the restriction of single-tile addition in the aTAM and kTAM) and doesn’t require a specified seed. We give overviews of a series of 2HAM results, which tend to make use of geometric techniques not applicable in the aTAM. Finally, we discuss and define a wide array of more recently developed models and discuss their various tradeoffs in comparison to the previous models and to each other. Molecular self-assembly presents a bottom-up' approach to the fabrication of objects specified with nanometre precision. DNA molecular structures and intermolecular interactions are particularly amenable to the design and synthesis of complex molecular objects. We report the design and observation of two-dimensional crystalline forms of DNA that self-assemble from synthetic DNA double-crossover molecules. Intermolecular interactions between the structural units are programmed by the design of sticky ends' that associate according to Watson-Crick complementarity, enabling us to create specific periodic patterns on the nanometre scale. The patterned crystals have been visualized by atomic force microscopy. Understanding how linear strings fold into 2-D and 3-D shapes has been a long sought goal in many fields of both academia and industry. This paper presents a technique to design self-assembling and self-reconfigurable systems that are composed of strings of very simple robotic modules. We show that physical strings that are composed of a small set of discrete polygonal or polyhedral modules can be used to programmatically generate any continuous area or volumetric shape. These modules can have one or two degrees of freedom (DOFs) and simple actuators with only two or three states. We describe a subdivision algorithm to produce universal polygonal and polyhedral string folding schemas, and we prove the existence of a continuous motion to reach any such folding. This technique is validated with dynamics simulations as well as experiments with chains of modules that pack on a regular cubic lattice. We call robotic programmable universally foldable strings “moteins” as motorized proteins. This short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, simulates any tile assembly system. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchal model, where large assemblies can bind together on one step, we encounter an infinite set, of infinite hierarchies, each with strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested. The tools of molecular biology were used to solve an instance of the directed Hamiltonian path problem. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This experiment demonstrates the feasibility of carrying out computations at the molecular level. Self-assembly is the process by which small components automatically assemble themselves into large, complex structures. Examples in nature abound: lipids self-assemble a cell's membrane, and bacteriophage virus proteins self-assemble a capsid that allows the virus to invade other bacteria. Even a phenomenon as simple as crystal formation is a process of self-assembly. How could such a process be described as "algorithmic?" The key word in the first sentence is automatically. Algorithms automate a series of simple computational tasks. Algorithmic self-assembly systems automate a series of simple growth tasks, in which the object being grown is simultaneously the machine controlling its own growth. Many biological systems are composed of unreliable components which self-organize efficiently into systems that can tackle complex problems. One such example is the true slimemold Physarum polycephalum which is an amoeba-like organism that seeks food sources and efficiently distributes nutrients throughout its cell body. The distribution of nutrients is accomplished by a self-assembled resource distribution network of small tubes with varying diameter which can evolve with changing environmental conditions without any global control. In this paper, we use a phenomenological model for the tube evolution in slime mold and map it to a path formation protocol for wireless sensor networks. By selecting certain evolution parameters in the protocol, the network may evolve toward single paths connecting data sources to a data sink. In other parameter regimes, the protocol may evolve toward multiple redundant paths. We present detailed analysis of a small model network. A thorough understanding of the simple network leads to design insights into appropriate parameter selection. We also validate the design via simulation of large-scale realistic wireless sensor networks using the QualNet network simulator.