When it comes to working together, schools in the water have plenty to teach about control theory.
By Alan S. Brown, Associate Editor
Naomi Ehrich Leonard grew up in Marblehead, Mass., a small town that juts out into the Atlantic Ocean 18 miles north of Boston. Perhaps this is why she starts nearly all her invited talks—and there are many—with a video of a school of fish.
The video is as ordinary as it is mesmerizing. The fish rise, forming a tight spiral that morphs into a school heading down towards the ocean floor. There is no visible leader. Each fish senses, makes decisions, and moves independently. Yet the school moves as one.
For most of the past decade, Leonard, the Edwin Wilsey Professor of Mechanical and Aerospace Engineering at Princeton University, has studied how to apply the rules underlying cooperative animal group behavior to control theory. Her work on cooperative robots helped earn her a MacArthur Foundation “genius grant” in 2004.
According to Leonard, animal groups as diverse as schools of fish, flocks of birds, and herds of zebras synchronize their movements to find the densest source of food, reduce the stress of migration, and minimize predation. They do this consistently, despite uncertainty in their decisions and noise in the form of environmental interferences.
Leonard made the connection to engineering at a lecture at the Center for Information Technology Research in the Interest of Society at the University of California, Berkeley last November. “We have these great examples of groups doing the types of things we want to do,” she said. “We want to forage for information; they forage for food. Of course, the catch is that while we can observe what the group is doing, we don’t know what the individuals are doing in terms of making decisions or passing information that lead to these remarkable behaviors.”
Understanding how a school of fish moves as one provides insights into controlling
teams of autonomous robots.
Working with biologists who specialize in animal group behavior, Leonard has been identifying some of these behaviors. The rules are often simple. Individuals seek food, maintain optimal distances from others, and follow neighboring fish. Yet those simple rules produce complex group patterns.
Biologists, like Princeton’s Simon Levin and Iain Couzin, study these behaviors by building complex models and by exploring their possible evolutionary advantages.
“We have the same kinds of questions, but bring different perspectives and tools,” Leonard said. “I come from a feedback-centric perspective that considers how systems gain robustness through feedback.”
Control theory often stumbles when it encounters complex systems. Leonard hopes to apply her field’s systematic approach to biological insights in order to create high-performance designs. “We’re not trying to copy nature exactly,” she said. “We’re looking for key mechanisms and principles in animal group behavior that we can use to design better mechanisms for cooperative robots.”
Systems of rules could enable teams of robots to work with one another or with humans. Robotic groups could remediate a toxic chemical spill, search for survivors amid wreckage, and help workers manufacture complex components. Or they could scout enemy outposts, patrol a harbor for terrorists, and enable drones to operate in formations.
Leonard’s first robot teams have already helped oceanographers monitor and map Monterey Bay.
Leonard graduated Princeton as a mechanical engineer in 1985 and worked in the electric power industry for four years. She earned a Ph.D. at the University of Maryland in 1994 and joined the Princeton faculty.
By the late 1990s, she was investigating underwater gliders, propeller-less craft that looked like torpedoes but moved by changing their weight and redistributing their mass. Let water into the bow and the front-heavy vehicles dive. Push out the water and they glide upwards. Shift weight from side to side and they veer to port or starboard.
In 1998, Leonard and her graduate students built an 18-inch-long glider with modular wings and four servo-driven syringes inside. Depending on whether the syringes filled with water or air, the glider could perform maneuvers—slow and limited, but controlled and purposeful nonetheless—inside a large test tank at the university. Her team authored the expected papers that sought to understand the tradeoffs between gravity and buoyancy, and the dynamics and control of winged buoyancy-driven gliders.
Gliders were cheap (as far as autonomous robots go) and used little power. They could remain at sea for weeks at a time. Yet they were slow and hard to maneuver. Leonard envisioned using a fleet of gliders as a mobile sensor array, slowly gathering data as they traversed the roiling ocean.
Unpowered robotic gliders can use simple rules to maintain their formation,
even in choppy waters.
There was one very large obstacle to realizing this vision. Ordinarily, oceanographers would sample an area by powering a boat or submersible along a planned path. Since gliders were unpowered and easily swept off course by tides and currents, Leonard could not expect them to follow a predefined route very closely. Instead, she needed another way to make best use of their movements.
This led her to biologists interested in cooperative behavior, including Julia Parrish and Danny Grünbaum of the University of Washington, as well as Levin and Couzin at Princeton.
She quickly saw parallels between their studies and her coordination problems. “I realized how the rules could do so much more than create interesting patterns,” she recalled. “We could turn it around, reverse engineer these rules to create collective motion patterns for mobile sensor networks that were consistent with the part of the ocean I wanted to measure.
According to Leonard, “I got lucky. In 2002, Tom Curtin, a visionary program manager at the Office of Naval Research, suggested that he could fund me to put together research on gliders with research on collective behavior.”
The grant he lined up enabled Leonard to team with physical oceanographers and marine biologists to launch a fleet of gliders to sample the ocean and map temperature gradients in Monterey Bay in 2003.
Located just south of California’s Silicon Valley, the bay drops sharply to form one of the world’s largest underwater canyons. Complex currents and upwellings of cold water race through its depths, thousands of feet below the surface, dispersing nutrients throughout the bay.
Ecologists wanted to study the bay’s salinity, plankton concentrations, and temperature gradients. They were especially interested in how the cold water dispersed nutrients and where plankton gathered.
The ecologists were used to snapshots of data sampled by a single craft. Leonard proposed using a fleet of three gliders as a reconfigurable sensor array to provide richer measurements of dynamic gradients.
Leonard had an ambitious agenda for the autonomous gliders. They would coordinate their motion on their own, using the feedback control algorithms that she and her team had designed. Each glider measured its local environment frequently, but communicated with its fellows only every two hours.
Leonard expected them to maintain a triangular formation and move in formation. They would also vary the triangle’s size, demonstrating the potential of the three-glider sensor array to adjust its resolution to minimize errors in its estimates of the measured field’s gradients. With accurate gradient estimates, the glider group would have the means to find and track features in the ocean.
The gliders performed as expected. They maintained their formation, despite currents that tended to push them together. The triangle would change its orientation, spinning around as its gliders sought out target data. Over time, the gliders closed their formation to 3 kilometers, from 6 kilometers, as they sought the most accurate gradient estimates.
“Fish do this incredibly well,” Leonard noted, referring to the ability of fish to find food even in turbulent water. In this sense, her gliders attempted to emulate them.
“I stood there in our control room and said, ‘Look, the gliders are telling us the cold water’s over here,’ ” she recalled. “The oceanographers looked at me and told me, ‘We know that, Naomi.’ But the whole point was that they didn’t have to be standing there to tell me where the cold water was. These vehicles were figuring it out on their own, and they could have headed for the cold water if that had been their mission.”
Setting the Patterns
The goal of the 2003 demonstration showed that the gliders could stay in formation while responding to their environment. Leonard returned in 2006 with a very different agenda. This time, she wanted the gliders to cruise in predefined patterns, distributing themselves evenly to collect the most information.
Leonard and her oceanographic collaborators wanted her fleet of ten gliders to move around three or more nearly rectangular tracks in a 20 km by 40 km region, maintaining even spacing from one another so that the group did not miss any interesting environmental changes. They also wanted to be able to change those patterns on the fly. “Instead of thinking about gradients, we were asking, ‘How do we cover an area and know we’re not missing anything?’ “ Leonard said.
This involved some reverse engineering. “We turned this into a design problem. We knew that in animals, feedback rules led to patterns. But as engineers, we could go the other way and say, ‘We want this pattern,’ and then find the rule that would yield it,” Leonard explained. In other words, she wanted to create a cookbook, a list of recipes that contained the rules needed to create the patterns she wanted.
This was more difficult than it sounded. In the past, researchers hadn’t tried to coordinate groups of gliders. Instead, they used rules and feedback about flow and position to keep each glider on track.
Since the first Monterey Bay experiment, Leonard had been looking at ways to apply what she calls “local rules” about how animals make decisions based on the movements of group members closest to them. Leonard then looked for ways to turn those biological rules into algorithms that produced similar patterns. The best algorithms, developed with former graduate student Derek Paley and collaborator Rodolphe Sepulchre of University of Liège in Belgium, had simple parameters and depended only on relative headings and the relative positions of neighbors. Leonard’s team could change patterns easily by switching a small number of parameters.
In theory, a glider tracing a rectangle evenly spaced from its fellows was not that different from a school of fish moving in a helix. “We don’t want to program where each vehicle should be at every moment in time. Instead, we want motion patterns to emerge. We build in feedback that gives the gliders the ability to do what animals do well, which is to be super flexible and super robust,” Leonard explained.
Six green gliders patrol three stacked boxes. Four purple
gliders cruise the perimeter of the rectangle formed by
The gliders use simple rules to maintain their patterns.
By communicating their position, they try to remain equidistant
from one another.
In the 2006 field experiment in Monterey Bay, Leonard’s team and her collaborators successfully demonstrated the autonomous coordinated motion control methodology. Six of the ten gliders carried out 14 different coordinated motion patterns on their own for 24 days straight. The gliders adapted to the ocean, its currents, and new requests from the team. For example, the gliders tightened their rectangles when asked to provide higher resolution data about the head of the canyon.
Questions Run Deep
Leonard’s research continues to raise profound questions about nature and control theory. Sometimes her work produces counterintuitive answers. This is especially true about group leadership.
Leonard imagines a school of fish moving in a horizontal plane. Their role is to keep track of their neighbors’ headings and stick together as they move forward.
“But what if five of these individuals think the food is at 2 o’clock. They don’t want to lose the group, but they have this extra pull in the direction of 2 o’clock. The other fish don’t know that they have this information. Can leadership emerge? Will they entrain the other guys and move to 2 o’clock? Even more interesting, what if five of the other fish saw something at 10 o’clock. They want to move in that direction, while the other 90 fish have no preference at all.”
Leonard wanted to use dynamical systems analysis to understand how the group makes the right decisions, how it uses feedback to correct poor decisions, and whether such rules would work with robots.
Using analytic methods, she looked at how the two informed groups of fish battled it out to lead the naive fish, which made up the vast majority of the school. Leonard drew on work by Levin and Couzin and their collaborators, which showed that if there were two groups of leaders with equally strong pull, the entire school of fish would split small differences. In other words, if one group wanted to go to 11 o’clock and the other to 1 o’clock, the school would head to 12 o’clock.
When the differences grew larger, say 2 versus 10 o’clock, one of the two groups would ultimately win. Couzin and his collaborators used numerical methods tried to understand the dynamics and to show that it was possible for leadership to emerge without identified leaders or explicit communication.
Leonard and former graduate student Benjamin Nabet sought to model this phenomenon with dynamical equations and to look at how strong the pull needed to be in order to change behavior.
“We don’t have to mimic the biological system to learn from it,” Leonard said. Emergent leadership could be important to a group of gliders or robots, she noted. The robots may not all have the same sensors, and some may even be able to turn their sensors off to conserve power.
“Suppose we have a whole bunch of mobile sensing platforms,” she said. “When a few sense something interesting, we want them to head for it. How do we design how many other individuals they should entrain with them? Maybe it’s just a few. Maybe it’s so important, everyone needs to go.”
Leonard and Nabet’s first dynamic models and analytic studies included only the informed individuals. Through their collaboration with Couzin and Levin, they found that naive individuals played an important role in improving the outcome of the decision. According to Leonard, “They’re the subtle glue. They’re not just going along for the ride, but by passing information, they are enforcing a signal to make decisions more accurate.”
Leonard has seen the glue improve decision making in schools of fish in Couzin’s lab as well as in her own models: “The dynamics of trying to stick with your neighbors when you have a preference is an interesting way to understand how the preference gets passed along,” she explained.
In a related problem, she has turned her analytical approaches towards how neighborhoods are defined in animal groups and how best to define neighborhoods for robotic groups. In other words, how many others or which others should an individual pay attention to in determining its reactive behavior? What types of interconnections produce the most cohesive yet responsive collective, despite uncertainty in individual decisions and noise in measurements? This is a problem that runs through feedback control theory of multi-agent systems, from animal groups to mobile sensor networks to automated factories to corporate networks.
For example, every fish could watch every other fish (all-to-all), but such dense connections eat up too many resources. Another approach is the star interconnection, where all the fish follow a leader. That works as long as the leader never fails. Leonard’s preliminary results, informed by data about fish and also the flight of starlings in Rome, show that the robustness and speed of consensus dynamics of the all-to-all case can be matched with far fewer direct interconnections.
Further, Leonard has shown how sensitive group patterns can be to who is sensing whom. “For example, if everyone is only sensing their next-door neighbors on either side, moving uniformly around in a circle is a stable solution. As soon as everyone starts sensing everyone else, the only stable solution is the whole group moving in a straight line direction.”
Of course, there is no straight line in Leonard’s research. It continues to morph, just as she evolved from her work in the power industry to one of today’s most profound thinkers about the control solutions that may one day govern tomorrow’s robotic teams.
Naomi Leonard’s work is widely available on the Web. Among the best:
>> “Collective Motion and Sensing Networks in Nature and Robotics,” a lecture at University of California, Berkeley’s Center for Information Technology Research in the Interest of Society. www.citris-uc.org/events/Collective_Motion or tinyurl.com/2uanyly
>> “Flocks and Fleets: Collective Motion in Nature and Robotics,” a President’s Lecture at Priceton University outlining Leonard’s work for a general audience.
www.princeton.edu/WebMedia/flash/lectures/20091022_preslect_leonard.shtml or tinyurl.com/237fu7o
>> Adaptive Sampling and Prediction. This Web site explains the Monterey Bay glider project, and how to use autonomous vehicles to sample the ocean, gather data for numerical models, and predict future conditions. www.princeton.edu/~dcsl/asap/ or tinyurl.com/5nkg42
>> Naomi Leonard’s faculty profile. www.princeton.edu/mae/people/faculty/leonard/ or tinyurl.com/36sde3l