Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our universal coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.
Many approaches have been proposed with potential applications in smart coating; these can be categorized as active and passive systems. In passive systems, particles move based only on their structural properties and interactions with their environment, or have only limited computational ability but lack control of their motion. Examples include population protocols @cite_12 as well as molecular computing models such as DNA self-assembly systems (see, e.g., the surveys in @cite_4 @cite_15 @cite_14 ) and slime molds @cite_7 @cite_8 .
@cite_14 @cite_4 @cite_7 @cite_8 @cite_15 @cite_12
2436246434 2085992503 2962873476 2962724035
Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our universal coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice. 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 The idea behind universal coating is to have a thin layer of a specific substance covering an object of any shape so that one can measure a certain condition (like temperature or cracks) at any spot on the surface of the object without requiring direct access to that spot. We study the universal coating problem in the context of self-organizing programmable matter consisting of simple computational elements, called particles , that can establish and release bonds and can actively move in a self-organized way. Based on that matter, we present a worst-case work-optimal universal coating algorithm that uniformly coats any object of arbitrary shape and size that allows a uniform coating. Our particles are anonymous, do not have any global information, have constant-size memory, and utilize only local interactions. We give a detailed description of the geometry of single droplet patterns in a non- local isoperimetric problem. In particular we focus on the sharp interface limit of the Ohta- Kawasaki free energy for diblock copolymers, regarded as a paradigm for those energies modeling physical systems characterized by a competition between short and a long-range interactions. Exploiting fine properties of the regularity theory for minimal surfaces, we extend previous partial results in different directions and give robust tools for the geometric analysis of more complex patterns. where u is the order parameter of a two-phases system confined in ⊂ R n , and and m are two nonnegative numerical parameters. The two terms in the energy mimic attractive short-range and repulsive long-range energies between the phases. More precisely the first term is local, it favors minimal interface area and drives the system toward a partition into few pure phases while the second term, involving a Coulomb-like kernel G, is non-local and favor a fine mixing of the phases. A detailed description of the energy is given in § 1. The competition between these two terms is expected to induce the formation of highly regular mesoscopic patterns, whose geometry strongly depends on the choice of the parameters and m (e.g. spherical spots, cylinders, gyroids and lamellae). 0.1. The Ohta-Kawasaki functional for diblock copolymers. The model we consider arises as a simplification of a Ginzburg-Landau functional proposed by Ohta and Kawasaki in their pioneering paper (41) as a possible description of a diblock copolymers' (DBC) system. Even though it is questionable whether such an energy actually describes DBCs (see Choksi and Ren (15), Muratov (39) and Niethammer and Oshita (40)), nevertheless it is a first, and mathematically non-trivial, attempt to capture some of the main features of these systems. For such a reason it deserved over the last twenty years great attention from both the mathematical and the physical