CS 201: Algorithmic Foundations of Programmable Matter, ANDREA RICHA, Arizona State University

Speaker: Andrea Richa
Affiliation: Arizona State University

ABSTRACT: Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute fully distributed, local, asynchronous algorithms to self-organize and solve system-wide problems such as movement, configuration, and coordination. Self-organizing particle systems (SOPS) have many interesting applications like coating objects for monitoring and repair purposes and forming nano-scale devices for surgery and molecular-scale electronic structures. In this talk, we describe our work on establishing an algorithmic foundations for programmable matter. We investigate how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles. We start by investigating shape formation, leader election and coating in SOPS.  We then utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into asynchronous, distributed, local algorithms for self-organizing particle systems that drive the emergent phenomenon of compression, expansion, bridging, and phototaxing, also establishing direct ties to the notion of “active matter” in physics. BIO: Professor Andrea W. Richa joined Arizona State University (ASU) in 1998. She is currently affiliated with the Biomimicry Center at ASU, and the Biosocial Complexity Initiative in general. Prof. Richa’s main areas of expertise are in distributed/network algorithms and computing in general.  Her work has been widely cited, and includes work on bio-inspired distributed algorithms, distributed load balancing, packet routing, wireless network modeling and topology control, wireless jamming, data mule networks, underwater optical networking, and distributed hash tables (DHTs). Dr. Richa received the 2017 Best Senior Researcher award from the School of Computing, Informatics, and Decision Systems Engineering (CIDSE) at ASU. She was the recipient of an NSF CAREER Award in 1999, and the keynote speaker and program\general chair of several prestigious conferences, including recently being the Program Committee Chair of the 31st International Symposium on Distributed Computing (DISC), 2017. For a selected list of her publications and other accomplishments, CV, and current research projects, please visit www.public.asu.edu/~aricha or sops.engineering.asu.edu.

Hosted by Professor Eli Gafni

Date/Time:
Date(s) - Jan 18, 2018
4:15 pm - 5:45 pm

Location:
3400 Boelter Hall
420 Westwood Plaza Los Angeles California 90095