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.

Refereed Journal Papers

• Programming active cohesive granular matter with mechanically induced phase changes, Shengkai Li, Bahnisikha Dutta, Sarah Cannon, Joshua J. Daymude, Ram Avinery, Enes Aydin, Andréa W. Richa, Daniel I. Goldman, Dana Randall. Science Advances, vol. 7, issue 17, 2021. DOI: 10.1126/sciadv.abe8494 [Full Text]
• A stochastic approach to shortcut bridging in programmable matter. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. Natural Computing, 17(4) pp. 723-741, 2018. [Full Text]
• Phototactic supersmarticles. William Savoie, Sarah Cannon, Joshua J. Daymude, Ross Warkentin, Shengkai Li, Andréa W. Richa, Dana Randall, and Daniel I. Goldman. Artificial Life and Robotics, 23(4) pp. 459-468, 2018. [Video/Simulation] [Full Text]

Refereed Conference Proceedings

• Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. Shunhao Oh, Dana Randall, Andréa W. Richa. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023).
• A local stochastic algorithm for separation in heterogeneous self-organizing particle systems. Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), pp. 54:1-54:22, 2019.
• Brief Announcement: A local stochastic algorithm for separation in heterogeneous self-organizing particle systems. Sarah Cannon, Joshua J. Daymude, Cem Gokmen, Dana Randall, and Andréa W. Richa. In Proceedings of the 2018 ACM Principles of Distributed Computing (PODC ’18), pp. 483-485, 2018.
• A stochastic approach to shortcut bridging in programmable matter. Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. In DNA Computing and Molecular Programming — 23rd International Conference (DNA23), pp. 122-138, 2017. [Simulation]
• A Markov chain algorithm for compression in self-organizing particle systems. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC ’16), pp. 279-288, 2016. [Simulation]

Other Publications

• Phototactic Supersmarticles. Sarah Cannon, Joshua J. Daymude, William Savoie, Ross Warkentin, Shengkai Li, Daniel I. Goldman, Dana Randall, and Andréa W. Richa. Appeared at the 2nd International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM ’17). 2017. [Video/Simulation]

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.

People

Current Team

Andréa W. Richa

PI / President’s Professor, Arizona State University[Website]

Dana Randall

PI / Professor, Georgia Institute of Technology[Website]

Daniel I. Goldman

PI / Professor, Georgia Institute of Technology[Website]

Sarah Cannon

Assistant Professor, Claremont McKenna University[Website]

Joshua J. Daymude

Professor, Arizona State University[Website]

Shengkai Li

PhD Student, Georgia Institute of Technology[Website]

Todd Murphey

PI/Professor, Northwestern University

[website]

Jamison Weber

Postdoctoral Scholar, Arizona State University

Ana Pervan

Robotics Engineer, Wayve[website]

Anya Chaturvedi

Factory Automation Engineer, Intel[website]

Joseph Briones

Ph.D Student, Arizona State University[website]

Shunhao Oh

Ph.D Student, Georgia Institute of Technology[website]

Bahnisikha Dutta

PhD Student, Georgia Institute of Technology[Website]

William Savoie

PhD, Georgia Institute of Technology 2019 [Website]

Ross Warkentin

Masters of Science, Georgia Institute of Technology 2017[Website]

Cem Gokmen

Undergraduate Researcher, Georgia Institute of Technology 2018[Website]

Marta Andrés Arroyo

Undergraduate Researcher, University of Granada[Website]

Rebecca Martin

Ph.D Student, Carnegie Melon University[website]

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.