Project: Emergence

We utilize tools from statistical physics and Markov chain analysis to investigate how macro-scale behaviors in distributed systems of programmable matter can naturally emerge from local micro-behaviors by individual computational units. When this stochastic approach is combined with the amoebot model from the SOPS project, we translate Markov chains defined at a system level into local, distributed algorithms for self-organizing particle systems that are inherently robust — tolerant of particle faults — and oblivious, using very little memory and communication when compared to the stateful SOPS algorithms.

We can then translate distributed, stochastic algorithms for desirable macroscopic behaviors such as clustering, flocking, exploration, or desegregation into the physical mechanics of simple, analog robots. Ultimately, this project will provide a better end-to-end understanding of how microscopic rules can induce macroscopic behaviors, providing a more systematic approach to building and analyzing swarm robotic systems.

Presentations

Invited Talks

• Algorithmic Programmable Matter. Andréa W. Richa. Keynote talk at 22nd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS ’20), Austin, TX, USA (Virtual Event). November 18, 2020. [Video]
• Markov Chains for Programmable Active Matter. Dana Randall. Oxford Discrete Math and Probability Seminar (DMP), Virtual Event. June 9, 2020. [Video]
• Algorithmic Foundations of Programmable Matter. Andréa W. Richa. Keynote talk at International Conference on Distributed Computing and Networking 2020 (ICDCN ’20), Kolkata, India. January 6, 2020.
• Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter. Joshua J. Daymude. 2nd Workshop on Self-Organization in Swarm of Robots (WSSR ’18), Tokyo, Japan. November 4, 2018.
• Algorithmic Foundations of Programmable Matter. Andréa W. Richa. Keynote talk at Latin American Theoretical Informatics 2018 (LATIN ’18), Buenos Aires, Argentina. April 17, 2018.

Conference Talks

• A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. Joshua J. Daymude. International Conference on Randomization and Computation (RANDOM ’19), Boston, MA, USA. September 21, 2019.
• Separation in Heterogeneous Self-Organizing Particle Systems. Andréa W. Richa. ACM Symposium on Principles of Distributed Computing (PODC ’18), London, UK. July 26, 2018.
• Supersmarticle: A Locomoting Robot Made of Robots. Shengkai Li. American Physical Society (APS) March Meeting 2018, Los Angeles, CA, USA. March 9, 2018.
• Local Stochastic Algorithms for Compression and Shortcut Bridging in Programmable Matter. Andréa W. Richa. Joint Mathematics Meetings (JMM ’18) Special Session on Emergent Phenomena in Discrete Models, San Diego, CA, USA. January 12, 2018.
• Phototactic Supersmarticles. Shengkai Li. 2nd International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM ’17), Kyoto, Japan. November 1, 2017.
• A Stochastic Approach to Shortcut Bridging in Programmable Matter. Sarah Cannon. DNA Computing and Molecular Programming – 23rd International Conference (DNA23), Austin, TX, USA. September 26, 2017.
• A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems. Sarah Cannon. ACM Symposium on Principles of Distributed Computing (PODC ’16), Chicago, IL, USA. July 27, 2016.

Poster Presentations

• Self-Organizing Particle Systems: an Abstraction of Programmable Matter. Joshua J. Daymude. Achievement Rewards for College Scientists (ARCS) Awards Dinner 2019, Phoenix, AZ, USA. April 26, 2019.
• Markov Chains, Programmable Matter, and Emergent Behavior. Sarah Cannon. MIT EECS Rising Stars 2018, Cambridge, MA, USA. October 29, 2018.
• Self-Organizing Particle Systems: an Abstraction of Programmable Matter. Joshua J. Daymude. Achievement Rewards for College Scientists (ARCS) Awards Dinner 2018, Phoenix, AZ, USA. April 20, 2018.
• A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. (Best Poster Presentation Award). Cem Gokmen. Georgia Tech Undergraduate Research Spring Symposium, Atlanta, GA, USA. April 17, 2018.
• Compression and Shortcut Bridging in Self-Organizing Particle Systems. Joshua J. Daymude. Google PhD Intern Research Conference (PIRC ’17), Mountain View, CA, USA. July 2017.
• Compression in Self-Organizing Particle Systems. Joshua J. Daymude. Barrett Celebrating Honors Symposium (BCHS ’16), Tempe, AZ, USA. April 12, 2016.

Other Presentations

• Stochastic Algorithms for Programmable Matter. Joshua J. Daymude. Discrete Math Seminar, Tempe, AZ, USA. April 3, 2019.
• Partition Functions, Markov Chains, and Programmable Matter. Sarah Cannon.
  • Berkeley Probability Seminar, Berkeley, CA, USA. February 27, 2019.
  • Simons Institute Fifth Annual Industry Day, Berkeley, CA, USA. February 28, 2019.
  • Simons Institute Geometry of Polynomials Seminar, Berkeley, CA, USA. March 6, 2019.
• Self-Organizing Particle Systems (SOPS). Andréa W. Richa. Tutorial at Dagstuhl Seminar 18331: Algorithmic Foundations of Programmable Matter, Schloss Dagstuhl, Germany. August 16, 2018.
• Separation in Heterogeneous Programmable Matter. Andréa W. Richa. Biological Distributed Algorithms (BDA ’18), London, UK. July 23, 2018.
• A Stochastic Approach to Shortcut Bridging in Programmable Matter. Joshua J. Daymude. Algorithms, Combinatorics, and Optimization (ACO) Student Seminar, Atlanta, GA, USA. October 6, 2017.
• A Markov Chain Approach to Programmable Matter. Sarah Cannon. Big-O Undergraduate Theory Club Seminar, Atlanta, GA, USA. October 2, 2017.
• Local Stochastic Algorithms for Compression and Shortcut Bridging in Programmable Matter. Joshua J. Daymude. Biological Distributed Algorithms (BDA ’17), Washington D.C., USA. July 28, 2017.
• A Distributed and Stochastic Algorithmic Framework for Active Matter. Dana Randall and Andréa W. Richa. Algorithms in the Field (AitF) PI Meeting 2017, Arlington, VA, USA. March 31, 2017.
• A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems. Sarah Cannon.
  • Achievement Rewards for College Scientists (ARCS) 25th Anniversary Celebration, Atlanta, GA, USA. October 18, 2016.
  • Algorithms, Combinatorics, and Optimization (ACO) Student Seminar, Atlanta, GA, USA. September 16, 2016.
  • China Theory Week 2016, Hong Kong, China. August 25, 2016.
  • Dagstuhl Seminar 16271, Dagstuhl, Germany. July 4-8, 2016.

Funding

• Collaborative Research: AF: Medium: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Self-Organizing Particle Systems. Award #2106917 (ASU), Award #2106687 (Georgia Tech). May. 2021 – Present.
• Foundations of Emergent Computation and Self-Organized Adaptation. DoD MURI (Multidisciplinary University Research Initiative) Award #W911NF-19-1-0233. Feb. 2019 – Present.
• Algorithms in the Field: Collaborative Research: A Distributed and Stochastic Algorithmic Framework for Active Matter. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations, Award #1637393 (ASU), Award #1637031 (Georgia Tech). Sept. 2016 – Aug. 2018.
• Algorithms in the Field: Collaborative Research: Distributed and Stochastic Algorithms for Active Matter: Theory and Practice. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations Award #1733680 (ASU), Award #1733812 (Georgia Tech). Jan. 2018 – Dec. 2020.