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
Reshaping Particle Configurations by Collisions with Rigid Objects
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
- NSF-PAR ID:
- 10130230
- Date Published:
- Journal Name:
- IEEE International Conference on Robotics and Automation (ICRA 2019, Montreal CA)
- Page Range / eLocation ID:
- 4436 to 4443
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Abstract The proposal of fault-tolerant quantum computations, which promise to dramatically improve the operation of quantum computers and to accelerate the development of the compact hardware for them, is based on topological quantum field theories, which rely on the existence in Nature of physical systems described by a Lagrangian containing a non-Abelian (NA) topological term. These are solid-state systems having two-dimensional electrons, which are coupled to magnetic-flux-quanta vortexes, forming complex particles, known as anyons. Topological quantum computing (TQC) operations thus represent a physical realization of the mathematical operations involving NA representations of a braid group B n , generated by a set of n localized anyons, which can be braided and fused using a “tweezer” and controlled by a detector. For most of the potential TQC material systems known so far, which are 2D-electron–gas semiconductor structure at high magnetic field and a variety of hybrid superconductor/topological-material heterostructures, the realization of anyon localization versus tweezing and detecting meets serious obstacles, chief among which are the necessity of using current control, i.e., mobile particles, of the TQC operations and high density electron puddles (containing thousands of electrons) to generate a single vortex. Here we demonstrate a novel system, in which these obstacles can be overcome, and in which vortexes are generated by a single electron. This is a ~ 150 nm size many electron InP/GaInP 2 self-organized quantum dot, in which molecules, consisting of a few localized anyons, are naturally formed and exist at zero external magnetic field. We used high-spatial-resolution scanning magneto-photoluminescence spectroscopy measurements of a set of the dots having five and six electrons, together with many-body quantum mechanical calculations to demonstrate spontaneous formation of the anyon magneto-electron particles ( e ν ) having fractional charge ν = n / k, where n = 1–4 and k = 3–15 are the number of electrons and vortexes, respectively, arranged in molecular structures having a built-in (internal) magnetic field of 6–12 T. Using direct imaging of the molecular configurations we observed fusion and braiding of e ν - anyons under photo-excitation and revealed the possibility of using charge sensing for their control. Our investigations show that InP/GaInP 2 anyon-molecule QDs, which have intrinsic transformations of localized e ν - anyons compatible with TQC operations and capable of being probed by charge sensing, are very promising for the realization of TQC.more » « less
-
We propose an approach to mapping tissue and vascular systems without the use of contrast agents, based on moving and measuring magnetic particles. To this end, we consider a swarm of particles in a 1D or 2D grid that can be tracked and controlled by an external agent. Control inputs are applied uniformly so that each particle experiences the same applied forces. We present algorithms for three tasks: (1) Mapping, i.e., building a representation of the free and obstacle regions of the workspace; (2) Subset Coverage, i.e., ensuring that at least one particle reaches each of a set of desired locations; and (3) Coverage, i.e., ensuring that every free region on the map is visited by at least one particle. These tasks relate to a large body of previous work from robot navigation, both from theory and practice, which is based on individual control. We provide theoretical insights that have potential relevance for fast MRI scans with magnetically controlled contrast media. In particular, we develop a fundamentally new approach for searching for an object at an unknown distance D, where the search is subject to two different and independent cost parameters for moving and for measuring. We show that regardless of the relative cost of these two operations, there is a simple O(log D/log log D)-competitive strategy, which is the best possible. Also, we provide practically useful and computationally efficient strategies for higher-dimensional settings. These algorithms extend to any number of particles and show that additional particles tend to reduce the mean and the standard deviation of the time required for each task.more » « less
-
null (Ed.)Ferromagnetic soft materials can generate flexible mobility and changeable configurations under an external magnetic field. They are used in a wide variety of applications, such as soft robots, compliant actuators, flexible electronics, and bionic medical devices. The magnetic field enables fast and biologically safe remote control of the ferromagnetic soft material. The shape changes of ferromagnetic soft elastomers are driven by the ferromagnetic particles embedded in the matrix of a soft elastomer. The external magnetic field induces a magnetic torque on the magnetized soft material, causing it to deform. To achieve the desired motion, the soft active structure can be designed by tailoring the layouts of the ferromagnetic soft elastomers. This paper aims to optimize multi-material ferromagnetic actuators. Multi-material ferromagnetic flexible actuators are optimized for the desired kinematic performance using the reconciled level set method. This type of magnetically driven actuator can carry out more complex shape transformations by introducing ferromagnetic soft materials with more than one magnetization direction. Whereas many soft active actuators exist in the form of thin shells, the newly proposed extended level set method (X-LSM) is employed to perform conformal topology optimization of ferromagnetic soft actuators on the manifolds. The objective function comprises two sub-objective functions, one for the kinematic requirement and the other for minimal compliance. Shape sensitivity analysis is derived using the material time derivative and the adjoint variable method. Three examples are provided to demonstrate the effectiveness of the proposed framework.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICRA.2019.8794405
