We consider a solution of automata similar to Population Protocols and Network Constructors. The automata (or nodes) move passively in a well-mixed solution and can cooperate by interacting in pairs. Every such interaction may result in an update of the local states of the nodes. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. We may think of such nodes as the smallest possible programmable pieces of matter. The model that we introduce here is a more applied version of Network Constructors, imposing physical (or geometrical) constraints on the connections. Each node can connect to other nodes only via a very limited number of local ports, therefore at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. We show that this restricted model is still capable of forming very practical 2D or 3D shapes. We provide direct constructors for some basic shape construction problems. We then develop new techniques for determining the constructive capabilities of our model. One of the main novelties of our approach, concerns our attempt to overcome the inability of such systems to detect termination. In particular, we exploit the assumptions that the system is well-mixed and has a unique leader, in order to give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size @math of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that the nodes can self-organize w.h.p. into arbitrarily complex shapes while still detecting termination of the construction.
Systems and solutions inspired by nature have often turned out to be extremely practical and efficient. For example, the bottom-up approach of nature inspires the fabrication of biomaterials by attempting to mimic these phenomena with the aim of creating new and varied structures with novel utilities well beyond the gifts of nature @cite_11 . Moreover, there is already a remarkable amount of work envisioning our future ability to engineer computing and robotic systems by manipulating molecules with nanoscale precision. Ambitious long-term applications include molecular computers @cite_18 and miniature (nano)robots for surgical instrumentation, diagnosis and drug delivery in medical applications (e.g. it has very recently been reported that DNA nanorobots could even kill cancer cells @cite_26 ) and monitoring in extreme conditions (e.g. in toxic environments). However, the road towards this vision passes first through our ability to discover . The gain of developing such a theory will be twofold: It will give some insight to the role (and the mechanisms) of network formation in the complexity of natural processes and it will allow us engineer artificial systems that achieve this complexity.
@cite_18 @cite_26 @cite_11
2166918926 2085992503 2143177102 1986292487
Recent work on molecular programming has explored new possibilities for computational abstractions with biomolecules, including logic gates, neural networks, and linear systems. In the future such abstractions might enable nanoscale devices that can sense and control the world at a molecular scale. Just as in macroscale robotics, it is critical that such devices can learn about their environment and reason under uncertainty. At this small scale, systems are typically modeled as chemical reaction networks. In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference. In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities. We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations. As with standard sum-product inference, this procedure yields exact results for tree-structured graphs, and approximate solutions for loopy graphs. Self-assembly of active, robotic agents, rather than of passive agents such as molecules, is an emerging research field that is attracting increasing attention. Active self-assembly techniques are especially attractive at very small spatial scales, where alternative construction methods are unavailable or have severe limitations. Building nanostructures by using swarms of very simple nanorobots is a promising approach for manufacturing nanoscale devices and systems. The method described in this paper allows a group of simple, physically identical, identically programmed and reactive (i.e., stateless) agents to construct and repair polygonal approximations to arbitrary structures in the plane. The distributed algorithms presented here are tolerant of robot failures and of externally-induced disturbances. The structures are self-healing, and self-replicating in a weak sense. Their components can be re-used once the structures are no longer needed. A specification of vertices at relative positions, and the edges between them, is translated by a compiler into reactive rules for assembly agents. These rules lead to the construction and repair of the specified shape. Simulation results are presented, which validate the proposed algorithms. Abstract Recent advances in synthetic biology, in particular towards the engineering of DNA-based circuits, are providing tools to program man-designed functions within biological cells, thus paving the way for the realization of biological nanoscale devices, known as nanomachines. By stemming from the way biological cells communicate in the nature, Molecular Communication (MC), i.e., the exchange of information through the emission, propagation, and reception of molecules, has been identified as the key paradigm to interconnect these biological nanomachines into nanoscale networks, or nanonetwork. The design of MC nanonetworks built upon biological circuits is particularly interesting since cells possess many of the elements required to realize this type of communication, thus enabling the design of cooperative functions in the biological environment. In this paper, a systems-theoretic modeling is realized by analyzing a minimal subset of biological circuit elements necessary to be included in an MC nanonetwork design where the message-bearing molecules are propagated via free diffusion between two cells. The obtained system-theoretic models stem from the biochemical processes underlying cell-to-cell MC, and are analytically characterized by their transfer functions, attenuation and delay experienced by an information signal exchanged by the communicating cells. Numerical results are presented to evaluate the obtained analytical expressions as functions of realistic biological parameters. The impressive capabilities of the mammalian brain—ranging from perception, pattern recognition and memory formation to decision making and motor activity control—have inspired their re-creation in a wide range of artificial intelligence systems for applications such as face recognition, anomaly detection, medical diagnosis and robotic vehicle control. Yet before neuron-based brains evolved, complex biomolecular circuits provided individual cells with the ‘intelligent’ behaviour required for survival. However, the study of how molecules can ‘think’ has not produced an equal variety of computational models and applications of artificial chemical systems. Although biomolecular systems have been hypothesized to carry out neural-network-like computations in vivo and the synthesis of artificial chemical analogues has been proposed theoretically, experimental work has so far fallen short of fully implementing even a single neuron. Here, building on the richness of DNA computing and strand displacement circuitry, we show how molecular systems can exhibit autonomous brain-like behaviours. Using a simple DNA gate architecture that allows experimental scale-up of multilayer digital circuits, we systematically transform arbitrary linear threshold circuits (an artificial neural network model) into DNA strand displacement cascades that function as small neural networks. Our approach even allows us to implement a Hopfield associative memory with four fully connected artificial neurons that, after training in silico, remembers four single-stranded DNA patterns and recalls the most similar one when presented with an incomplete pattern. Our results suggest that DNA strand displacement cascades could be used to endow autonomous chemical systems with the capability of recognizing patterns of molecular events, making decisions and responding to the environment.