Although soft devices (grippers, actuators, and elementary robots) are rapidly becoming an integral part of the broad field of robotics, autonomy for completely soft devices has only begun to be developed. Adaptation of conventional systems of control to soft devices requires hard valves and electronic controls. This paper describes completely soft pneumatic digital logic gates having a physical scale appropriate for use with current (macroscopic) soft actuators. Each digital logic gate utilizes a single bistable valve—the pneumatic equivalent of a Schmitt trigger—which relies on the snap-through instability of a hemispherical membrane to kink internal tubes and operates with binary high/low input and output pressures. Soft, pneumatic NOT, AND, and OR digital logic gates—which generate known pneumatic outputs as a function of one, or multiple, pneumatic inputs—allow fabrication of digital logic circuits for a set–reset latch, two-bit shift register, leading-edge detector, digital-to-analog converter (DAC), and toggle switch. The DAC and toggle switch, in turn, can control and power a soft actuator (demonstrated using a pneu-net gripper). These macroscale soft digital logic gates are scalable to high volumes of airflow, do not consume power at steady state, and can be reconfigured to achieve multiple functionalities from a single design (including configurations that receive inputs from the environment and from human users). This work represents a step toward a strategy to develop autonomous control—one not involving an electronic interface or hard components—for soft devices.
Particle computation: complexity, algorithms, and logic
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
- NSF-PAR ID:
- 10048937
- Date Published:
- Journal Name:
- Natural Computing
- ISSN:
- 1567-7818
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
-
Ta-Shma, Amnon (Ed.)We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff ≥ k bits are 1) and k-AND (outputs 0 iff ≥ k bits are 0), and thus can be seen as an interpolation between AC⁰ and TC⁰. We establish a tight multi-switching lemma for GC⁰(k) circuits, which bounds the probability that several depth-2 GC⁰(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC⁰ circuits lifts to depth-d size-s^{.99} GC⁰(.01 log s) circuits with no loss in parameters (other than hidden constants). Our result has the following applications: - Size-2^Ω(n^{1/d}) depth-d GC⁰(Ω(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)). - Size-n^Ω(log n) GC⁰(Ω(log² n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)). - There is a seed length O((log m)^{d-1}log(m/ε)log log(m)) pseudorandom generator against size-m depth-d GC⁰(log m) circuits, matching the AC⁰ lower bound of Håstad up to a log log m factor (extending a result of Lyu (CCC, 2022)). - Size-m GC⁰(log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).more » « less
-
Consider many particles actuated by a uniform global external field (e.g. gravitational or magnetic fields). This paper presents analytical results using workspace obstacles and global inputs to reshape such a group of particles. Shape control of many particles is necessary for conveying information, construction, and navigation. First we show how the particles’ characteristic angle of repose can be used to reshape the particles by controlling angle of attack and the magnitude of the driving force. These can then be used to control the force and torque applied to a rectangular rigid body. Next, we examine the full set of stable, achievable mean and variance configurations for the shape of a particle group in two canonical environments: a square and a circular workspace. Finally, we show how workspaces with linear boundary layers can be used to achieve a more rich set of mean and variance configurations.more » « less
-
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
-
Polymorphic gates are reconfigurable devices that deliver multiple functionalities at different temperature, supply voltage or external inputs. Capable of working in different modes, polymorphic gate is a promising candidate for embedding secret information such as fingerprints. In this paper, we report five polymorphic gates whose functionality varies in response to specific control input and propose a circuit fingerprinting scheme based on these gates. The scheme selectively replaces standard logic cells by polymorphic gates whose functionality differs with the standard cells only on Satisfiability Don’t Care conditions. Additional dummy fingerprint bits are also introduced to enhance the fingerprint’s robustness against attacks such as fingerprint removal and modification. Experimental results on ISCAS and MCNC benchmark circuits demonstrate that our scheme introduces low overhead. More specifically, the average overhead in area, speed and power are 4.04%, 6.97% and 4.15% respectively when we embed 64-bit fingerprint that consists of 32 real fingerprint bits and 32 dummy bits. This is only half of the overhead of the other known approach when they create 32-bit fingerprints.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s11047-017-9666-6
