MURI award brings ASU to the forefront of emergent computing

What do you get when you combine computer science, physics, robotics and nanotechnology? The opportunity to advance the fundamental understanding of how tiny computer particles can work together to do great things — without any human intervention.

Arizona State University Professor Andrea Richa is part of a U.S. Department of Defense Multidisciplinary University Research Initiative effort that seeks to make these fundamental research discoveries in the project “Formal Foundations of Algorithmic Matter and Emergent Computation.”

The DOD MURI program supports cross-disciplinary, multi-institution research teams looking to understand or achieve things never done before. DOD research offices have sponsored MURI program projects that yield significant breakthroughs, sustain scientific advancement and foster the growth of graduate students in cutting-edge fields.

In 2019, the DOD issued 24 high-profile, highly competitive MURI awards totaling $169 million. Richa and her ASU team will receive $808,000 of a total $6 million MURI award with the rest distributed among her collaborators at the Georgia Institute of Technology, the Massachusetts Institute of Technology and Northwestern University.  

“This is a fantastic opportunity,” said Richa, a professor of computer science in the School of Computing, Informatics, and Decision Systems Engineering, one of the six Ira A. Fulton Schools of Engineering at ASU. “I’d like to thank the DOD for this great opportunity to do fundamental research that’s high risk but also high impact.”

Basic individuals can cooperate to achieve complex emergent behavior

A tiny ant can only do so much on its own, but with the entire colony, ants can do amazing things: carry large objects, form bridges across gaps and even create rafts to travel safely in flooded conditions. Individual ants can’t perform these feats alone, but the way they interact causes collective behavior to emerge. Broadly, emergence occurs when the whole is greater than the sum of its parts, meaning the whole has properties its parts do not have, and these properties come about because of interactions among the parts. 

The study of emergent behavior has been around for decades, even before computers. And it can be seen in all aspects of society — we just don’t pay attention to it.

In society, emergent behavior is evident when we observe content going viral on social media, people gathering in crowds or drivers stalling in traffic jams. All these behaviors are the result of localized interactions — someone retweeting a video, the tendency to follow others to a point of interest, or “rubbernecking” while passing an accident — that induce these surprising behaviors.

In the nanotechnology realm, tiny computers with limited computational capabilities could also do amazing things as a group, behaving like “matter” that self-reconfigures to repair wounds, seal nuclear reactor leaks or fix spacecraft cracks in flight, all without human intervention. But first, scientists and engineers need to better understand emergent behaviors so they can be predicted and built effectively.

“If we get our overarching goal of understanding, predicting and synthesizing the local rules for the emergent behaviors we want, and also of building the systems that can carry out these rules, it’s a huge thing,” Richa said.

Difficult computational questions require algorithmic answers

It may seem trivial to induce emergent behaviors, but it’s actually a fundamental problem not well understood.

It would be easy for a scientist to direct these computational “particles” if they had a bird’s-eye view of the entire system and what needed to be done. However, from the viewpoint of an individual particle, this is much more complicated, especially when each individual particle has limited memory and computational abilities, lacking knowledge of its location and the number of particles in the group.

“It’s easy from the global perspective to form a bridge with hundreds of ants, but if you are the ant, how do you do it?” asks Richa, who also works on bio-inspired computer science research at the ASU Biodesign Institute.

The MURI project will explore local algorithmic rules and computations the particles need to perform to reach a desired emergent behavior. In addition to more standard computational rules, the MURI team will leverage the physics and energy dynamics controlling particle movement and interactions as tools for algorithmic design, leading to the notion of algorithmic matter.

The team will employ a continuous feedback loop of developing theories and experimentation over the five-year period of the MURI award.

“We want to better understand what causes emergent behavior so we can start predicting when it will happen,” Richa said. “We’ll then leverage these predictions to synthesize the physical characteristics and the local rules that each of the individuals will follow so the system exhibits the desired emergent behavior. Each step in the process is new territory that will pave the way for micro- and nanoscale autonomous, task-oriented algorithmic matter engineered systems.”

Algorithmic matter systems could one day fight cancer alongside the immune system, lead to new paradigms for additive and subtractive manufacturing and enable other self-healing and self-replication capabilities for new and unexpected applications.

Professor Andrea Richa works with her undergraduate and graduate student researchers in the Self-Organizing Particle Systems Lab. The lab team will explore the distributed paradigms at the core of algorithmic matter for the five-year MURI award project. Photo by Erika Gronek/ASU

Multidisciplinary team makes this research possible

Just as emergent behavior is about the whole being more than the sum of its parts, so is the MURI project team Richa works with. Each researcher brings a unique combination of skills that is instrumental in solving the challenges of understanding, predicting and synthesizing emergent behavior.

“I don’t think any one of us could do it separately because the questions we propose in this project cannot be answered within any one of our disciplines alone and will require extensive collaboration involving vast expertise,” Richa said.

Richa’s expertise lies in the theoretical foundations of distributed algorithms and computing, broadly speaking, with a recent emphasis on self-organizing particle systems. In this MURI project, Richa and her research team at ASU will explore the distributed paradigms at the core of algorithmic matter.

Dana Randall, ADVANCE Professor of Computing at Georgia Tech and principal investigator of the MURI project, brings expertise in theoretical computer science and stochastic and randomized algorithms. Her research bridges computer science, discrete mathematics and statistical physics.    

Together, Richa and Randall will investigate what the minimal computational capabilities at the individual level are in order to enable a desired emergent behavior.

Daniel Goldman, the Dunn Family Professor of Physics at Georgia Tech, will work on the experimental physics of emergent behavior and will also utilize his experience with swarm robotics. For the MURI project research, Goldman can build robotic systems to mimic physical behavior that exists in nature. This will provide a hands-on experimental platform for testing the team’s algorithms and ideas.

“Dan is a good match for the project in that he doesn’t just work in physics but also in robotics, and that kind of expertise is hard to find,” Richa said.

Jeremy England, Thomas D. & Virginia W. Cabot Career Development Associate Professor of Physics at MIT, contributes to the project his theoretical physics expertise, particularly in emergent behavior away from thermal equilibrium.

Michael Strano, Carbon P. Dubbs Professor in Chemical Engineering at MIT, is responsible for the nanomaterials aspects of the project. Building on his strengths in chemical engineering and materials science, Strano is developing “synthetic cells,” nanotechnology units that mimic cell behavior. He will help miniaturize the concepts seen in Goldman’s robotic systems to the micro- or nanoscale, which will be useful for future applications.

Todd Murphey, professor of mechanical engineering at Northwestern University, covers computational methods in dynamics and control, with applications in neuroscience, health science, robotics and automation.

“The more we worked on it, the more excited we all got about the project and the collaboration,” Richa said. “This research is going to be challenging but very exciting.”

Building on past research

Richa has conducted research into programmable matter, or a smart network of tiny sensors that monitor and respond to the environment — for example, fixing fractures or defects on bridge components automatically, which is closely related to the MURI project research.

Some of this work she conducted over the past few years with Randall and Goldman with funding from the National Science Foundation.

At the ASU Biodesign Institute, Richa is a faculty associate in Professor Stephanie Forrest's Center for Biocomputing, Security and Society. There Richa conducts research inspired by natural systems. For example, her research into concepts of programmable matter is inspired by the behavior of ants, honey bees and schools of fish.

“There will be a lot of collaboration and venues for enrichment for the things we’re doing in the MURI project with the Biodesign Institute,” Richa said.

Top photo: Professor Andrea Richa and her undergraduate and graduate researcher team members from the Self-Organizing Particle Systems Lab. Richa’s research into self-organizing particles, like the pingpong ball model she holds, and expertise into distributed algorithms are instrumental in achieving fundamental research advances into emergent behavior conducted as part of a U.S. Department of Defense Multidisciplinary University Research Initiative award project.  Photo by Erika Gronek/ASU