Markov Chains and Emergent Behavior in Programmable Matter

November 1, 2018
3:00 PM
Halligan 102
Speaker: Sarah Cannon, University of California, Berkeley
Host: Diane Souvaine

Abstract

How can collections of simple computational elements accomplish complicated system-level goals? This question motivates the study of programmable matter, swarm robotics, and even biological systems such as ant colonies. In simplified settings, we've shown collections of abstract particles executing our local stochastic algorithms can accomplish remarkable global objectives, including the fundamental behaviors of compression, separation, optimization, locomotion, and alignment. In several of our algorithms, changing just a single parameter results in a different, but equally desirable, emergent global behavior. Because our distributed algorithms come from Markov chains, we can use tools and insights from Markov chain analysis to predict and rigorously explain their behavior. I will present several simulations of our distributed algorithms for programmable matter; discuss the connection between distributed algorithms and Markov chains; and give a high-level overview of how rigorous proof tools from Markov chain analysis can tell us about the long-run behavior of our distributed algorithms. No prior knowledge of distributed algorithms, programmable matter, or Markov chains is assumed.

Bio

Sarah Cannon is an NSF Mathematical Sciences Postdoctoral Research Fellow at the University of California, Berkeley. She recently completed her Ph.D. in Algorithms, Combinatorics, and Optimization at Georgia Tech, advised by Dana Randall, where she was an NSF Graduate Research Fellow, a Clare Boothe Luce Outstanding Graduate Fellow, and received a Simons Award for Graduate Students in Theoretical Computer Science. Previously, Sarah earned an M.Sc. in Mathematics and the Foundations of Computer Science from the University of Oxford in 2013 and a B.A. in Mathematics, with a minor in Computer Science, from Tufts University in 2012. Her research focuses on mathematical foundations of Markov chains for problems from discrete geometry, and more broadly touches on theoretical computer science; randomized algorithms; Markov chains; stochastic processes; probability; discrete mathematics; emergent behavior; distributed algorithms; programmable matter; and statistical physics.