An official website of the United States government
We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). Upon activation of the field, each particle moves maximally in the same direction until forward progress is blocked by a stationary obstacle or another stationary particle. In an open workspace, this system model is of limited use because it has only two controllable degrees of freedom—all particles receive the same inputs and move uniformly. We show that adding a maze of obstacles to the environment can make the system drastically more complex but also more useful. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR, and OR operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a FAN-OUT gate cannot be generated. We resolve this missing component with the help of 2 9 1 particles, which can create FAN-OUT gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.
more »
« less
Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)
In this video, we present theoretical and practical methods for achieving arbitrary reconfiguration of a set of objects, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction. This concept can be used for a wide range of applications in which particles do not have their own energy supply or in which they are subject to the same global control commands. A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work (some of which was presented during SoCG 2015) made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are theoretical characterizations of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons; a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements. Hardware experiments show the efficacy of these procedures, demonstrating the usefulness of this novel approach.
more »
« less
- PAR ID:
- 10163095
- Date Published:
- Journal Name:
- 36th International Symposium on Computational Geometry (SoCG 2020)
- Volume:
- 164
- Page Range / eLocation ID:
- 72:1--72:5
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Multistable structures have widespread applications in the design of deployable aerospace systems, mechanical metamaterials, flexible electronics, and multimodal soft robotics due to their capability of shape reconfiguration between multiple stable states. Recently, the snap-folding of rings, often in the form of circles or polygons, has shown the capability of inducing diverse stable configurations. The natural curvature of the rod segment (curvature in its stress-free state) plays an important role in the elastic stability of these rings, determining the number and form of their stable configurations during folding. Here, we develop a general theoretical framework for the elastic stability analysis of segmented rings (e.g., polygons) based on an energy variational approach. Combining this framework with finite element simulations, we map out all planar stable configurations of various segmented rings and determine the natural curvature ranges of their multistable states. The theoretical and numerical results are validated through experiments, which demonstrate that a segmented ring with a rectangular cross-section can show up to six distinct planar stable states. The results also reveal that, by rationally designing the segment number and natural curvature of the segmented ring, its one- or multiloop configuration can store more strain energy than a circular ring of the same total length. We envision that the proposed strategy for achieving multistability in the current work will aid in the design of multifunctional, reconfigurable, and deployable structures.more » « less
-
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16), which can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.more » « less
-
Achlioptas, Dimitris; Végh, László A (Ed.)We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.more » « less
-
In DNA nanotechnology, DNA molecules are designed, engineered, and assembled into arbitrary-shaped architectures with predesigned functions. Static DNA assemblies often have delicate designs with structural rigidity to overcome thermal fluctuations. Dynamic structures reconfigure in response to external cues, which have been explored to create functional nanodevices for environmental sensing and other applications. However, the precise control of reconfiguration dynamics has been a challenge due partly to flexible single-stranded DNA connections between moving parts. Deformable structures are special dynamic constructs with deformation on double-stranded parts and single-stranded hinges during transformation. These structures often have better control in programmed deformation. However, related deformability and mechanics including transformation mechanisms are not well understood or documented. In this review, we summarize the development of dynamic and deformable DNA nanostructures from a mechanical perspective. We present deformation mechanisms such as single-stranded DNA hinges with lock-and-release pairs, jack edges, helicity modulation, and external loading. Theoretical and computational models are discussed for understanding their associated deformations and mechanics. We elucidate the pros and cons of each model and recommend design processes based on the models. The design guidelines should be useful for those who have limited knowledge in mechanics as well as expert DNA designers.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.SoCG.2020.72
