Computer science doctoral students Joshua Daymude (left) and Zahra Derakhshandeh (right) play key roles in professor Andrea Richa’s work to boost the performance of self-organizing particle systems that could provide solutions to many technical challenges. Photo by Pete Zrioka/ASU
Download Full Image
Given the many interconnected components of modern bridges, some of which can be difficult to access, the labor is likely to be time-consuming and expensive.
Now, says Andrea Richa, imagine the work could instead be done by a “smart” material, composed of many tiny sensors capable of detecting and measuring such things as temperature, traffic, and structural cracks and stresses.
This “smart” network of tiny sensors would be achieved through the use of “programmable material” — material that can monitor and respond to its environment — consisting of “self-organizing” particles that could coat the surface of bridge components or any other objects.
And in addition to its sensing abilities, the material might also be able to fix small fractures and other defects.
Similar types of repairs could also be made on things such as aircraft, space shuttle components, nuclear reactors — or even within the human body.
Exploring plethora of uses for programmable matter
Turning that concept into reality is the focus of research by Richa, a professor of computer science in Arizona State University’s Ira A. Fulton Schools of Engineering, in collaboration with colleagues at the Georgia Institute of Technology and the University of Paderborn in Germany.
Her role is to develop the computer science theory and distributed algorithms necessary to explore and broaden the possibilities of using programmable matter.
Distributed algorithms are those designed to run concurrently on several independent, interconnected computational devices that cooperate via local interactions, without centralized control. They’re used in many applications in computing, from telecommunications and networking to information processing and process control.
“We try to answer the question of exactly what kinds of problems programmable matter would be able to solve, given certain constraints on its computational power or the movement of its individual sensors,” Richa explained.
In using programmable matter, she added, “It’s important that the distributed system is able to self-organize, so that it does not require any central control or human intervention, and that it achieves the desired behavior by means of local interactions of the computationally limited sensors.”
Some of the more significant recent findings made by her Self-Organizing Particle Systems research group were reported on in the prominent research publication MIT Technology Review and in a computation theory blog that’s popular in the field.
A series of snapshots illustrate a particle system performing compression. There are 100 particles, which were initially in a straight line. Snapshots (a) through (e) were taken at regular intervals, showing the system’s steady progress toward a tightly gathered (compressed) state.
'Amoebot' model provides the framework
Those articles detail her group’s theory for a system of self-organizing particles that can perform “universal coating” and “compression” with only local communication and limited information about the environment. For example, the particles are able to perform these processes without having to rely on a global coordinate system, or any global orientation that they all share.
Universal coating involves layering a given object with material as evenly as possible, as in the aforementioned bridge. Compression, in this context, refers to gathering the material together as tightly as possible.
The findings were based on work with professor Christian Scheideler and doctoral students Robert Gmyr and Thim Strothmann at the University of Paderborn to develop a framework to describe programmable matter systems, which they call the “amoebot model” (the name is inspired loosely by the way amoebas move).
Using the model, Richa and her associates addressed the problem of coating surfaces of any shape through their universal coating algorithm for programmable material that “is indifferent to the shape or size of the surface that it must coat,” she said.
Applying the amoebot model to the challenges of compression, they took a cue from collective systems in nature and in some man-made systems, in which elements need to be as close as possible to each other to optimize their overall effectiveness,
“Think of army ants forming floating rafts to cross bodies of water, or ants exploring for food sources and then gathering around a source once it’s found, or a swarm of robots doing similar explore-and-gather operations,” she said.
Daymude, Richa and Derakhshandeh view a computer simulation they developed to depict how their self-organizing particles can act together to form a coating over large surfaces. Photo by Pete Zrioka/ASU
Algorithms for finding and fixing problems
Through collaborations with Georgia Tech professor Dana Randall and doctoral student Sarah Cannon, Richa’s group has constructed and analyzed a new compression algorithm that enables system behavior similar to that of ants and other insects when they swarm to collectively carry out tasks.
Improved compression would likely help tiny particulate sensors not only perform better at gathering information but also improve their communication with each other, enabling them to work faster in some cases.
Such progress in developing self-organizing particle systems is likely to have myriad applications beyond monitoring and maintaining structures. They could also be used to form nanoscale devices for use in surgery and molecular-scale electronic structures.
Programmable matter with improved abilities to alter its physical properties — such as shape, density, electrical conductivity and optical properties — opens the door to even more practical uses, particularly for increasing the kinds of technical operations that could be performed remotely, such as finding and sealing leaks in a nuclear reactor.
Coordinating the performance of 'particle friends'
Richa is providing Fulton Schools students valuable computer science experience through her research endeavors.
Doctoral students Zahra Derakhshandeh and Joshua Daymude, along with undergraduate Alexandra Porter, have been involved in the development of the universal coating algorithm. Daymude has also contributed to work to improve compression of programmable matter.
“What excites me the most,” Daymude said, “is that these individual particles, which know almost nothing about the world around them — which way is north, how many particle friends they have to work with, or even what time it is — and are armed with only a little memory and some rules to follow, can perform coordinated, large-scale behavior.”
It’s “a very human idea,” he added. “We can do things together that are impossible for us to do alone. All it takes is some coordination. The communication necessary to make that happen tends to be the hard part. But if tiny particles can do it, I think we can, too.”