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
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
- 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
-
null (Ed.)Variability in the execution time of computing tasks can cause load imbalance in high-performance computing (HPC) systems. When configuring system- and application-level parameters, engineers traditionally seek configurations that will maximize the mean computational throughput. In an HPC setting, however, high-throughput configurations that do not account for performance variability could result in poor load balancing. In order to determine the effects of performance variance on computationally expensive numerical simulations, the High-Performance LINPACK solver is optimized by using multiobjective optimization to maximize the mean and minimize the standard deviation of the computational throughput on the High-Performance LINPACK benchmark. We show that specific configurations of the solver can be used to control for variability at a small sacrifice in mean throughput. We also identify configurations that result in a relatively high mean throughput, but also result in a high throughput variability.more » « less
-
Microrobotics has the potential to revolutionize many applications including targeted material delivery, assembly, and surgery. The same properties that promise breakthrough solutions—small size and large populations—present unique challenges for controlling motion. Robotic manipulation usually assumes intelligent agents, not particle systems manipulated by a global signal. To identify the key parameters for particle manipulation, we used a collection of online games in which players steer swarms of up to 500 particles to complete manipulation challenges. We recorded statistics from more than 10 000 players. Inspired by techniques in which human operators performed well, we investigate controllers that use only the mean and variance of the swarm. We prove that mean position is controllable and provide conditions under which variance is controllable. We next derive automatic controllers for these and a hysteresis-based switching control to regulate the first two moments of the particle distribution. Finally, we employ these controllers as primitives for an object manipulation task and implement all controllers on 100 kilobots controlled by the direction of a global light source.more » « less
-
Robot-assisted femur repair has been of increased interest in recent literature due to the success of robot-assisted surgeries and current reoperation rates for femur fracture surgeries. The current limitation of robot-assisted femur fracture surgery is the lack of large force generation and sufficient workspace size in traditional mechanisms. To address these challenges, our group has created a 3-RRPS parallel mechanism, Robossis, which maintains the strength of parallel mechanisms while improving the translational and rotational workspace volume. In this paper, an optimal design methodology of parallel mechanisms for application to robot-assisted femur fracture surgery using a single-objective genetic algorithm is proposed. The genetic algorithm will use a single-objective function to evaluate the various configurations based on the clinical and mechanical design criteria for femur fracture surgery as well as the global conditioning index. The objective function is composed of the desired translational and rotational workspaces based on the design criteria, dynamic load-carrying capacity, and the homogeneous Jacobian global conditioning index. Lastly, experimental results of Robossis were obtained to validate the kinematic solution and the mechanism itself; Robossis had an average error of 0.31 mm during experimental force testing.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICRA.2019.8794405
