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
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces
We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles ("agents") and a particular target region ("tumor") within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by a number of simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising.
more »
« less
- NSF-PAR ID:
- 10219780
- Date Published:
- Journal Name:
- 2020 IEEE International Conference on Robotics and Automation (ICRA)
- Page Range / eLocation ID:
- 2508 to 2514
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
For biomedical applications in targeted therapy delivery and interventions, a large swarm of micro-scale particles (“agents”) has to be moved through a maze-like environment (“vascular system”) to a target region (“tumor”). Due to limited on-board capabilities, these agents cannot move autonomously; instead, they are controlled by an external global force that acts uniformly on all particles. In this work, we demonstrate how to use a time-varying magnetic field to gather particles to a desired location. We use reinforcement learning to train networks to efficiently gather particles. Methods to overcome the simulation-to-reality gap are explained, and the trained networks are deployed on a set of mazes and goal locations. The hardware experiments demonstrate fast convergence, and robustness to both sensor and actuation noise. To encourage extensions and to serve as a benchmark for the reinforcement learning community, the code is available at Github.more » « less
-
more » « less
Abstract In the field of optical imaging, the ability to image tumors at depth with high selectivity and specificity remains a challenge. Surface enhanced resonance Raman scattering (SERRS) nanoparticles (NPs) can be employed as image contrast agents to specifically target cells in vivo; however, this technique typically requires time-intensive point-by-point acquisition of Raman spectra. Here, we combine the use of “spatially offset Raman spectroscopy” (SORS) with that of SERRS in a technique known as “surface enhanced spatially offset resonance Raman spectroscopy” (SESORRS) to image deep-seated tumors in vivo. Additionally, by accounting for the laser spot size, we report an experimental approach for detecting both the bulk tumor, subsequent delineation of tumor margins at high speed, and the identification of a deeper secondary region of interest with fewer measurements than are typically applied. To enhance light collection efficiency, four modifications were made to a previously described custom-built SORS system. Specifically, the following parameters were increased: (i) the numerical aperture (NA) of the lens, from 0.2 to 0.34; (ii) the working distance of the probe, from 9 mm to 40 mm; (iii) the NA of the fiber, from 0.2 to 0.34; and (iv) the fiber diameter, from 100 µm to 400 µm. To calculate the sampling frequency, which refers to the number of data point spectra obtained for each image, we considered the laser spot size of the elliptical beam (6 × 4 mm). Using SERRS contrast agents, we performed in vivo SESORRS imaging on a GL261-Luc mouse model of glioblastoma at four distinct sampling frequencies: par-sampling frequency (12 data points collected), and over-frequency sampling by factors of 2 (35 data points collected), 5 (176 data points collected), and 10 (651 data points collected). In comparison to the previously reported SORS system, the modified SORS instrument showed a 300% improvement in signal-to-noise ratios (SNR). The results demonstrate the ability to acquire distinct Raman spectra from deep-seated glioblastomas in mice through the skull using a low power density (6.5 mW/mm2) and 30-times shorter integration times than a previous report (0.5 s versus 15 s). The ability to map the whole head of the mouse and determine a specific region of interest using as few as 12 spectra (6 s total acquisition time) is achieved. Subsequent use of a higher sampling frequency demonstrates it is possible to delineate the tumor margins in the region of interest with greater certainty. In addition, SESORRS images indicate the emergence of a secondary tumor region deeper within the brain in agreement with MRI and H&E staining. In comparison to traditional Raman imaging approaches, this approach enables improvements in the detection of deep-seated tumors in vivo through depths of several millimeters due to improvements in SNR, spectral resolution, and depth acquisition. This approach offers an opportunity to navigate larger areas of tissues in shorter time frames than previously reported, identify regions of interest, and then image the same area with greater resolution using a higher sampling frequency. Moreover, using a SESORRS approach, we demonstrate that it is possible to detect secondary, deeper-seated lesions through the intact skull.
-
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
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICRA40945.2020.9196551
