The Science of Swarms

Dry Clean Only?

Berkeley Engineers: Changing Our World

Dean's Digest

Lab Notes Update

Printer-friendly version

Professor Tarek I. Zohdi's swarm mechanics research also has long-term applications in medicine, specifically aiding in the design of new drugs that employ swarm behavior to collectively attack cancer cells. (David Pescovitz photo)

To become intimately acquainted with the research of UC Berkeley professor Tarek I. Zohdi all one needs to do is yell "fire" in a crowded theater. More than likely, the audience will stampede toward the emergency exits, bumping and bouncing off each other as they push to safety. If you had a bird's eye view, the chaos might resemble a laboratory physics experiment with hundreds of magnetic particles attracting and repelling one another. Ironically, Zohdi explains, there isn't much difference between the two scenarios. In both, the interacting objects--people or particles--exhibit what's known as swarm behavior. And understanding its mechanisms could impact everything from building design to robotics.

"We would like to control groups of individuals simultaneously so that their collective behavior achieves the particular goal that we have in mind," Zohdi says.

The individuals Zohdi refers to are not necessarily biological entities, although they could be. Essentially, he says, the aggregate motion of a large group of individuals--flocks of birds or crowds of human beings--does not come from a top-down plan directing the emergent behavior but from the simple one-to-one interactions between the individuals.

Zohdi's aim is to computationally tease out the simple laws of one-to-one interactions that affect the motion of an entire group so that the swarm behavior can be modified for the better. For example, he explains, accurate models of panic behavior could help architects design stairwells and exits that reduce dangerous bottlenecks during emergency situations.

The key to modeling swarm behavior on a computer, Zohdi says, is mathematically treating each individual in a swarm as a simple particle governed by very specific physical laws. For instance, he explains, a particle representing a human may be restricted by a law saying that "people in our culture don't like their personal space invaded within two feet."

This video depicts an optimized swarm of particles that after twenty generations learned to navigate a three-dimensional obstacle course in a minimum amount of time. The swarm's ultimate objective is to land within a pre-specified distance of a target (the white dot on the far left) while following certain rules: the swarm members could not make physical contact with one another or get too close to an obstacle. "Initial swarm members would impale themselves on the obstacles," Zohdi says. "However, later generations have 'learned' by adjusting their interaction laws to bunch up and squeeze through the obstacle course." (courtesy the researcher)

"The whole ball of wax boils down to what is the correct description of forces between individuals?" Zohdi says. "If you can map the characteristics of an individual into some kind of force, you can start to design the behavior you want. For example, you might say, I want a team of robots to swarm around one object and avoid another."

Indeed, instilling a bit of swarm intelligence into robots is one of Zohdi's ongoing efforts. In a project for the Office of Naval Research's UC Berkeley-based Center for Collaborative Control of Unmanned Vehicles, Zohdi is collaborating with professors Karl Hedrick and Raja Sengupta on the design of unmanned robotic vehicles that can avoid obstacles and fly in swarm-like formations. Similar technology could also be employed by self-driving vehicle systems like those pioneered by researchers in Berkeley's Partners for Advanced Transit and Highways (PATH) program.

When Zohdi begins a computer simulation, he seeds the virtual swarm with a series of laws based on his own educated guesses. The beauty though is that the moment he first unleashes the swarm to tackle whatever task he's simulating--an obstacle course, for instance--the particles begin to learn from experience.

"I use genetic algorithms," Zohdi says. "Just like with living creatures, the swarms store and rate previous experience."

What applications would you like to see developed by swarm mechanics research? We want to hear from you...

After each simulation, the swarm undergoes the software equivalent of "biological mutation." For example, a law describing how closely particles should remain together when maneuvering an obstacle course may be randomly tweaked between a simulation. If the slightly changed law leads to better swarm performance, it gets passed down to the next strain of particles. The evolution continues with each simulation until a set of laws emerge that is best suited for the task at hand.

"Approximately, 20 separate laws are all I've ever needed to predict any kind of complex movement," Zohdi says. "My focus is on designing the laws so that they match physical reality."

Professor Tarek I. Zohdi's home page

"Ultimate Auto-Pilot" by David Pescovitz (Lab Notes, October 2003)

Partners for Advanced Transit and Highways (PATH)

Lab Notes is published online by the Public Affairs Office of the UC Berkeley College of Engineering. The Lab Notes mission is to illuminate groundbreaking research underway today at the College of Engineering that will dramatically change our lives tomorrow.

Media contact: Teresa Moore, Lab Notes editor, Director of Public Affairs
Writer, Researcher: David Pescovitz
Web Manager: Michele Foley

Subscribe or send comments to the Engineering Public Affairs Office: lab-notes@coe.berkeley.edu.

© 2004 UC Regents. Updated 2/19/04.