Sarah Cannon

Sarah Cannon, Topher Pankow, Wesley Pegden et al.

This paper gives a new algorithm for sampling tree-weighted partitions of a large class of planar graphs. Formally, the tree-weighted distribution on $k$-partitions of a graph weights $k$-partitions proportional to the product of the number of spanning trees of each partition class. Recent work on computational redistricting analysis has driven special interest in the conditional distribution where all partition classes have the same size (balanced partitions). One class of Markov chains in wide use aims to sample from balanced tree-weighted $k$-partitions using a sampler for balanced tree-weighted 2-partitions. Previous implementations of this 2-partition sampler would draw a random spanning tree and check whether it contains an edge whose removal produces a balanced 2-component forest, rejecting if not. In practice, this is a significant computational bottleneck. We show that in fact it is possible to sample from the balanced tree-weighted 2-partition distribution directly, without first sampling a spanning tree; the acceptance and rejection rates are the same as in previous samplers. We prove that on a wide class of planar graphs encompassing network structures typically arising from the geographic data used in computational redistricting, our algorithm takes expected linear time $O(n)$. Notably, this is asymptotically faster than the best known method to generate random trees, which is $O(n \log^2 n)$ for approximate sampling and $O(n^{1 + \log \log \log n / \log \log n})$ for exact sampling. Additionally, we show that a variant of our algorithm also gives a speedup to $O(n \log n)$ for exact sampling of uniformly random trees on these families of graphs, improving the bounds for both exact and approximate sampling. We implement our algorithm and benchmark it on grid graphs, finding that it outperforms the standard bipartitioning method in the widely-used GerryChain library.

Sara Anderson, Sarah Cannon, Brooke Feinberg et al.

In the computational study of political redistricting, feasibility necessitates the use of a discretization of regions such as states, counties, and towns. In nearly all cases, researchers use a dual graph, whose vertices represent small geographic units (such as census blocks or voting precincts) with edges for geographic adjacency. A political districting plan is a partition of this graph into connected subgraphs that satisfy certain additional properties, such as connectedness, compactness, and equal population. Though dual graphs underlie nearly all computational studies of political redistricting, little is known about their properties. This is a unique graph class that has been described colloquially as `nearly planar, nearly triangulated,' but thus far there has been a lack of evidence to support this description. In this paper we study dual graphs for counties, census tracts, and census block groups across the United States in order to understand and characterize this graph class. We also consider several random graph models (most based on randomly perturbing grids or Delauney triangulations of random point sets), and determine which most closely resemble dual graphs under key metrics. This work lays an initial foundation for understanding and modeling the properties of dual graphs; this will provide invaluable insight to researchers developing algorithms using them to understand, assess, and quantify the properties of political districting plans.

Shengkai Li, Bahnisikha Dutta, Sarah Cannon et al.

Active matter physics and swarm robotics have provided powerful tools for the study and control of ensembles driven by internal sources. At the macroscale, controlling swarms typically utilizes significant 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 that can leverage physics of interactions and thus can be utilized 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, to test theoretical predictions. We consider the problems of aggregation, dispersion, and collective transport. As predicted by the theory, as a parameter representing interparticle attraction increases, the robots transition from a dispersed phase to an aggregated one, forming a dense, compact collective. When aggregated, the collective can transport non-robot "impurities" in their environment, thus performing an emergent task driven by the physics underlying the transition. These results point to a fruitful interplay between algorithm design and active matter robophysics that can result in new nonequilibrium physics and principles for programming collectives without the need for complex algorithms or capabilities.

Sarah Cannon, Joshua J. Daymude, Cem Gokmen et al.

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.

Sarah Cannon, Joshua J. Daymude, William Savoie et al.

Smarticles, or smart active particles, are small robots equipped with only basic movement and sensing abilities that are incapable of rotating or displacing individually. We study the ensemble behavior of smarticles, i.e., the behavior a collective of these very simple computational elements can achieve, and how such behavior can be implemented using minimal programming. We show that an ensemble of smarticles constrained to remain close to one another (which we call a supersmarticle), achieves directed locomotion toward or away from a light source, a phenomenon known as phototaxing. We present experimental and theoretical models of phototactic supersmarticles that collectively move with a directed displacement in response to light. The motion of the supersmarticle is approximately Brownian, and is a result of chaotic interactions among smarticles. The system can be directed by introducing asymmetries among the individual smarticle's behavior, in our case by varying activity levels in response to light, resulting in supersmarticle biased motion.