skip to main content


Title: A local stochastic algorithm for separation in heterogeneous self-organizing particle systems
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16), which can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.  more » « less
Award ID(s):
1803325
NSF-PAR ID:
10332924
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
pproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Page Range / eLocation ID:
54:1-54:22
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We present local distributed, stochastic algorithms for alignment in self-organizing particle systems (SOPS) on two-dimensional lattices, where particles occupy unique sites on the lattice, and particles can make spatial moves to neighboring sites if they are unoccupied. Such models are abstractions of programmable matter, composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational capabilities. We consider oriented particle systems, where particles are assigned a vector pointing in one of q directions, and each particle can compute the angle between its direction and the direction of any neighboring particle, although without knowledge of global orientation with respect to a fixed underlying coordinate system. Particles move stochastically, with each particle able to either modify its direction or make a local spatial move along a lattice edge during a move. We consider two settings: (a) where particle configurations must remain simply connected at all times and (b) where spatial moves are unconstrained and configurations can disconnect. Our algorithms are inspired by the Potts model and its planar oriented variant known as the planar Potts model or clock model from statistical physics. We prove that for any q ≥ 2, by adjusting a single parameter, these self-organizing particle systems can be made to collectively align along a single dominant direction (analogous to a solid or ordered state) or remain non-aligned, in which case the fraction of particles oriented along any direction is nearly equal (analogous to a gaseous or disordered state). In the connected SOPS setting, we allow for two distinct parameters, one controlling the ferromagnetic attraction between neighboring particles (regardless of orientation) and the other controlling the preference of neighboring particles to align. We show that with appropriate settings of the input parameters, we can achieve compression and expansion, controlling how tightly gathered the particles are, as well as alignment or nonalignment, producing a single dominant orientation or not. While alignment is known for the Potts and clock models at sufficiently low temperatures, our proof in the SOPS setting are significantly more challenging because the particles make spatial moves, not all sites are occupied, and the total number of particles is fixed. 
    more » « less
  2. Abstract

    Additive manufacturing, no longer reserved exclusively for prototyping components, can create parts with complex geometries and locally tailored properties. For example, multiple homogenous material sources can be used in different regions of a print or be mixed during printing to define properties locally. Additionally, heterogeneous composites provide an opportunity for another level of tuning properties through processing. For example, within particulate-filled polymer matrix composites before curing, the presence of an applied electric and/or magnetic fields can reorient filler particles and form hierarchical structures depending on the fields applied. Control of particle organization is important because effective material properties are highly dependent on the distribution of filler material within composites once cured. While previous work in homogenization and effective medium theories have determined properties based upon ideal analytic distributions of particle orientations and spatial location, this work expands upon these methods generating discrete distributions from quasi-Monte Carlo simulations of the electromagnetic processing event. Results of simulations provide predicted microarchitectures from which effective properties are determined via computational homogenization.

    These particle dynamics simulations account for dielectric and magnetic forces and torques in addition to hydrodynamic forces and hard particle separation. As such, the distributions generated are processing field dependent. The effective properties for a composite represented by this distribution are determined via computational homogenization using finite element analysis (FEA). This provides a path from constituents, through processing parameters to effective material properties. In this work, we use these simulations in conjunction with a multi-objective optimization scheme to resolve the relationships between processing conditions and effective properties, to inform field-assisted additive manufacturing processes.

    The constituent set providing the largest range of properties can be found using optimization techniques applied to the aforementioned simulation framework. This key information provides a recipe for tailoring properties for additive manufacturing design and production. For example, our simulation results show that stiffness for a 10% filler volume fraction can increase by 34% when aligned by an electric field as compared to a randomly distributed composite. The stiffness of this aligned sample is also 29% higher in the direction of the alignment than perpendicular to it, which only differs by 5% from the random case [1]. Understanding this behavior and accurately predicting composite properties is key to producing field processed composites and prints. Material property predictions compare favorably to effective medium theory and experimentation with trends in elastic and magnetic effective properties demonstrating the same anisotropic behavior as a result of applied field processing. This work will address the high computational expense of physics simulation based objective functions by using efficient algorithms and data structures. We will present an optimization framework using nested gradient searches for micro barium hexaferrite particles in a PDMS matrix, optimizing on composite magnetization to determine the volume fraction of filler that will provide the largest range of properties by varying the applied electric and magnetic fields.

     
    more » « less
  3. The Schelling model of segregation was introduced in economics to show how micro-motives can influence macro-behavior. Agents on a lattice have two colors and try to move to a different location if the number of their neighbors with a different color exceeds some threshold. Simulations reveal that even such mild local color preferences, or homophily, are sufficient to cause segregation. In this work, we propose a stochastic generalization of the Schelling model, based on both race and wealth, to understand how carefully architected placement of incentives, such as urban infrastructure, might affect segregation. In our model, each agent is assigned one of two colors along with a label, rich or poor. Further, we designate certain vertices on the lattice as “urban sites,” providing civic infrastructure that most benefits the poorer population, thus incentivizing the occupation of such vertices by poor agents of either color. We look at the stationary distribution of a Markov process reflecting these preferences to understand the long-term effects. We prove that when incentives are large enough, we will have ”urbanization of poverty,” an observed effect whereby poor people tend to congregate on urban sites. Moreover, even when homophily preferences are very small, if the incentives are large and there is income inequality in the two-color classes, we can get racial segregation on urban sites but integration on non-urban sites. In contrast, we find an overall mitigation of segregation when the urban sites are distributed throughout the lattice and the incentives for urban sites exceed the homophily biases. We prove that in this case, no matter how strong homophily preferences are, it will be exponentially unlikely that a configuration chosen from stationarity will have large, homogeneous clusters of agents of either color, suggesting we will have racial integration with high probability. 
    more » « less
  4. The motion of cells orthogonal to the direction of main flow is of importance in natural and engineered systems. The lateral movement of red blood cells (RBCs) distal to sudden expansion is considered to influence the formation and progression of thrombosis in venous valves, aortic aneurysms, and blood-circulating devices and is also a determining parameter for cell separation applications in flow-focusing microfluidic devices. Although it is known that the unique geometry of venous valves alters the blood flow patterns and cell distribution in venous valve sinuses, the interactions between fluid flow and RBCs have not been elucidated. Here, using a dilute cell suspension in an in vitro microfluidic model of a venous valve, we quantified the spatial distribution of RBCs by microscopy and image analysis, and using micro-particle image velocimetry and 3D computational fluid dynamics simulations, we analyzed the complex flow patterns. The results show that the local hematocrit in the valve pockets is spatially heterogeneous and is significantly different from the feed hematocrit. Above a threshold shear rate, the inertial separation of streamlines and lift forces contribute to an uneven distribution of RBCs in the vortices, the entrapment of RBCs in the vortices, and non-monotonic wall shear stresses in the valve pockets. Our experimental and computational characterization provides insights into the complex interactions between fluid flow, RBC distribution, and wall shear rates in venous valve mimics, which is of relevance to understanding the pathophysiology of thrombosis and improving cell separation efficiency.

     
    more » « less
  5. Trapping diffusive particles at surfaces is a key step in many systems in chemical and biological physics. Trapping often occurs via reactive patches on the surface and/or the particle. The theory of boundary homogenization has been used in many prior works to estimate the effective trapping rate for such a system in the case that either (i) the surface is patchy and the particle is uniformly reactive or (ii) the particle is patchy and the surface is uniformly reactive. In this paper, we estimate the trapping rate for the case that the surface and the particle are both patchy. In particular, the particle diffuses translationally and rotationally and reacts with the surface when a patch on the particle contacts a patch on the surface. We first formulate a stochastic model and derive a five-dimensional partial differential equation describing the reaction time. We then use matched asymptotic analysis to derive the effective trapping rate, assuming that the patches are roughly evenly distributed and occupy a small fraction of the surface and the particle. This trapping rate involves the electrostatic capacitance of a four-dimensional duocylinder, which we compute using a kinetic Monte Carlo algorithm. We further use Brownian local time theory to derive a simple heuristic estimate of the trapping rate and show that it is remarkably close to the asymptotic estimate. Finally, we develop a kinetic Monte Carlo algorithm to simulate the full stochastic system and then use these simulations to confirm the accuracy of our trapping rate estimates and homogenization theory. 
    more » « less