Search for: All records

Robots have components that work together to accomplish a task. Colloids are particles, usually less than 100 µm, that are small enough that they do not settle out of solution. Colloidal robots are particles capable of functions such as sensing, computation, communication, locomotion and energy management that are all controlled by the particle itself. Their design and synthesis is an emerging area of interdisciplinary research drawing from materials science, colloid science, self-assembly, robophysics and control theory. Many colloidal robot systems approach synthetic versions of biological cells in autonomy and may find ultimate utility in bringing these specialized functions to previously inaccessible locations. This Perspective examines the emerging literature and highlights certain design principles and strategies towards the realization of colloidal robots. 

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. 

To audit political district maps for partisan gerrymandering, one may determine a baseline for the expected distribution of partisan outcomes by sampling an ensemble of maps. One approach to sampling is to use redistricting policy as a guide to precisely codify preferences between maps. Such preferences give rise to a probability distribution on the space of redistricting plans, and Metropolis-Hastings methods allow one to sample ensembles of maps from the specified distribution. Although these approaches have nice theoretical properties and have successfully detected gerrymandering in legal settings, sampling from commonly-used policy-driven distributions is often computationally difficult. As of yet, there is no algorithm that can be used off-the-shelf for checking maps under generic redistricting criteria. In this work, we mitigate the computational challenges in a Metropolized-sampling technique through a parallel tempering method combined with ReCom[11] and, for the first time, validate that such techniques are effective on these problems at the scale of statewide precinct graphs for more policy informed measures. We develop these improvements through the first case study of district plans in Georgia. Our analysis projects that any election in Georgia will reliably elect 9 Republicans and 5 Democrats under the enacted plan. This result is largely fixed even as public opinion shifts toward either party and the partisan outcome of the enacted plan does not respond to the will of the people. Only 0.12% of the ∼ 160K plans in our ensemble were similarly non-responsive. 

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. 

We study the mixing time of a Markov chain on biased permutations, a problem related to self‐organizing lists. We are given probabilities for all such that . The chain iteratively chooses two adjacent elements and , and swaps them with probability . It has been conjectured that is rapidly mixing whenever the set of probabilities are “positively biased,” that is, for all . We define two general classes and give the first proofs that is rapidly mixing for both. We also demonstrate that the chain can have exponential mixing time, disproving the most general version of this conjecture.

 

Abstract Monotonic surfaces spanning finite regions of ℤ d arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. One method that has been used to uniformly generate these surfaces is a Markov chain that iteratively adds or removes a single cube below the surface during a step. We consider a biased version of the chain, where we are more likely to add a cube than to remove it, thereby favouring surfaces that are ‘higher’ or have more cubes below it. We prove that the chain is rapidly mixing for any uniform bias in ℤ 2 and for bias λ > d in ℤ d when d  > 2. In ℤ 2 we match the optimal mixing time achieved by Benjamini, Berger, Hoffman and Mossel in the context of biased card shuffling [2], but using much simpler arguments. The proofs use a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias , where the bias can vary depending on the location of the tile. We show that the chain continues to be rapidly mixing if the biases are close to uniform, but that the chain can converge exponentially slowly in the general setting. 

At the macroscale, controlling robotic swarms typically uses substantial memory, processing power, and coordination unavailable at the microscale, e.g., for colloidal robots, which could be useful for fighting disease, fabricating intelligent textiles, and designing nanocomputers. To develop principles that can leverage physical interactions and thus be used across scales, we take a two-pronged approach: a theoretical abstraction of self-organizing particle systems and an experimental robot system of active cohesive granular matter that intentionally lacks digital electronic computation and communication, using minimal (or no) sensing and control. As predicted by theory, as interparticle attraction increases, the collective transitions from dispersed to a compact phase. When aggregated, the collective can transport non-robot “impurities,” thus performing an emergent task driven by the physics underlying the transition. These results reveal a fruitful interplay between algorithm design and active matter robophysics that can result in principles for programming collectives without the need for complex algorithms or capabilities. 

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.