Collaborative Research: AF: Medium: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Self-Organizing Particle Systems

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Self-organization can be viewed as a phenomenon whereby unanticipated global configurations and patterns of a collective emerge from fully distributed and simplistic rules performed by each individual, without any global coordination or external intervention. Self-organization and emergent behavior arise naturally across many fields: distributed systems and swarm robotics in computer science, interacting particle systems in physics, population dynamics and flock coordination in biology, autonomous systems in robotics and control theory, and smart materials, to name a few. Recently, the synergy between discrete probability, algorithms and statistical physics has provided a new approach for designing self-organizing particle systems by harnessing collective, emergent behavior of physical systems. The laws of physics play an increasingly important role in collective behavior at the nano- and micro-scales, especially since individual agents are far less capable than their macroscopic counterparts. Yet, while the principles of statistical physics have motivated many experimental systems, little has been done to make the corresponding underlying distributed algorithms rigorous. This project investigates how to program collections of agents to perform tasks by modeling the dynamics as self-organizing particle systems performing steps of Markov chains through local interactions that can be rigorously analyzed. The limiting distributions of these chains have distinct equilibrium characteristics that can be used to program collective behavior. The principal investigators take a three-pronged approach: First, they introduce and study generalizations of common statistical physics models, such as the Potts, Ising and hard-core models, to better capture the constraints imposed by micro-scale systems of interacting agents. Next, they explore methods to better understand the nonequilibrium dynamics of these systems long before convergence and possibly subject to forces that make the Markov chains nonreversible. Finally, they explore how collective systems might be programmed through deliberate placement of obstacles and features in the environment, rather than programming the agents themselves, as many of these tiny agents are incapable of any sophisticated (traditional) computation. As an example of programming the environment, a new version of the Schelling segregation model is being studied where people move with higher probabilities if they are unhappy with the local demographics of their neighborhoods, but these preferences can be somewhat mitigated by the placement of desirable urban infrastructures that modify individuals' incentive structures and biases. The project is having impact in promoting and advancing interdisciplinary research across many fields; education, through advanced graduate courses and broad, interdisciplinary talks; diversity at the graduate, undergraduate, and faculty levels; outreach to the general public and for K-12 education; and municipal planning, through coordination with regional planning faculty and the City of Atlanta. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.