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
Algorithms for shaping a particle swarm with a shared input by exploiting non-slip wall contacts
There are driving applications for large populations of tiny robots in robotics, biology, and chemistry. These robots often lack onboard computation, actuation, and communication. Instead, these “robots” are particles carrying some payload and the particle swarm is controlled by a shared control input such as a uniform magnetic gradient or electric field. In previous works, we showed that the 2D position of each particle in such a swarm is controllable if the workspace contains a single obstacle the size of one particle. Requiring a small, rigid obstacle suspended in the middle of the workspace is a strong constraint, especially in 3D. This paper relaxes that constraint, and provides position control algorithms that only require non-slip wall contact in 2D. Both in vivo and artificial environments often have such boundaries. We assume that particles in contact with the boundaries have zero velocity if the shared control input pushes the particle into the wall. This paper provides a shortest-path algorithm for positioning a two-particle swarm, and a generalization to positioning an n-particle swarm. Results are validated with simulations and a hardware demonstration.
more »
« less
- PAR ID:
- 10048941
- Date Published:
- Journal Name:
- Intelligent Robots and Systems (IROS), 2017 IEEE/RSJ International Conference on
- Page Range / eLocation ID:
- 4304 to 4311
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Legged robots have a unique capability of traversing rough terrains and negotiating cluttered environments. Recent control development of legged robots has enabled robust locomotion on rough terrains. However, such approaches mainly focus on maintaining balance for the robot body. In this work, we are interested in leveraging the whole body of the robot to pass through a permeable obstacle (e.g., a small confined opening) with height, width, and terrain constraints. This paper presents a planning framework for legged robots manipulating their body and legs to perform collision-free locomotion through a permeable obstacle. The planner incorporates quadrupedal gait constraint, biasing scheme, and safety margin for the simultaneous body and foothold motion planning. We perform informed sampling for the body poses and swing foot position based on the gait constraint while ensuring stability and collision avoidance. The footholds are planned based on the terrain and the contact constraint. We also integrate the planner with robot control to execute the planned trajectory successfully. We validated our approach in high-fidelity simulation and hardware experiments on the Unitree A1 robot navigating through different representative permeable obstacles.more » « less
-
Abstract Swarm manufacturing is an emerging manufacturing paradigm that employs a heterogeneous swarm of robots to accomplish complex hybrid manufacturing tasks. Cooperative 3D printing (C3DP), a specialized form of swarm manufacturing, enables multiple printers to collaboratively produce large-scale parts, addressing key tradeoffs in additive manufacturing, such as size, speed, quality, and cost. A fundamental challenge in C3DP is ensuring collision-free, time-optimal printing in a shared workspace. This is a complex problem that can be influenced by factors such as the number of printers, part geometry, printer positioning, mobility, and kinematics. In this article, we present SafeZone*, a collision-free and scalable C3DP framework that optimizes printing time by co-considering the geometry (area and shape) and topology (space-connectivity) of a shared workspace during layer partitioning. We first establish a conceptual framework to mathematically represent the topology of a layer through partition graphs. Then, we use a Voronoi tessellation within a constrained optimization framework to control the partition graph and minimize makespan. The Voronoi sites are associated with printer locations, allowing the framework to integrate physical constraints and facilitating solutions for systems with robotic manipulators. Physical testing in a four-printer scenario with robotic arms confirms that SafeZone* enables collision-free printing, resulting in a printing time reduction of 44.63% when compared to the single-printer scenario. Finally, numerical studies reveal trends in the optimal solutions concerning the chromatic number of their resulting partition graphs and the distribution of the printing areas among printers.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
-
Abstract Swarm manufacturing (SM) is an emerging manufacturing paradigm that employs a heterogeneous swarm of robots to accomplish complex hybrid manufacturing tasks. Cooperative 3D Printing (C3DP), a special form of swarm manufacturing, uses multiple printers to print large-scale parts cooperatively and aims to tackle key challenges in the additive manufacturing industry, such as trade-offs among size, speed, quality, and cost. A fundamental challenge in C3DP is how to achieve collision-free, time-efficient printing when multiple printers operate in a shared workspace. This is a complex problem since the solution may depend on a myriad of factors, such as the number of printers, part geometry, printer positioning, mobility, and kinematics, or whether the printing path pre-determined. In this paper, we present SafeZone, a collision-free and scalable C3DP framework that aims to minimize printing time by considering both the geometry and topology (space-connectivity) of the resulting workspace when segmenting the part layer. To achieve this, we use a guided Voronoi tessellation that can only produce degree-3 partitions, which we show to have optimal scheduling properties based on the chromatic number of the resulting partition graph. The sites of the Voronoi tessellation are constrained to only lie on the boundary of their convex hull, thus facilitating collision-free operation in C3DP systems with robotic arms. We demonstrate through physical testing in a 4-printer scenario with SCARA arms that SafeZone can produce collision-free prints, resulting in a printing time reduction of 44.63% when compared to the single-printer scenario. Finally, we show how the partition created by our methodology has a printing time reduction of 22.83% when compared to a naive choice which does not consider workspace topology.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/IROS.2017.8206294
