Share Button

ghrist_portrait

Unconventional mathematician Robert Ghrist rejects his field’s “hippie aesthetic” in favor of suits and ties, loves medieval literature, reversed the usual way of teaching calculus in his popular MOOC, and is using one of mathematics’ most abstract disciplines—algebraic topology—to solve real-world problems in robotics and sensor networks.

BY KEVIN HARTNETT | Illustration by Jeff Koegel

Last March seven researchers from the University of Pennsylvania landed in Dayton, Ohio for two days of meetings at the Air Force Research Laboratory. The lab, housed on Wright-Patterson Air Force Base, has been home over the years to breakthroughs in everything from lasers to propulsion technology, and the agenda for these meetings was no less forward-looking: to consider ways of engineering fully autonomous flying robots able to work together to search buildings, track targets, and gather information about areas that are too dangerous for US soldiers to enter.

Among the representatives from Penn was Andrea Mitchell University Professor Robert Ghrist, a Penn Integrates Knowledge (PIK) professor with appointments in the departments of mathematics and electrical/systems engineering. Not long ago, the presence of an applied mathematician like Ghrist at this kind of meeting would have been surprising. His specialty is algebraic topology, an abstract branch of mathematics that studies the properties of different kinds of spaces and has existed as a purely academic pursuit for most of its history.

Yet over the last decade, Ghrist has found a number of innovative ways to use algebraic topology to solve real-world problems in robotics and sensor networks. These discoveries have helped make him one of the best-funded mathematicians in the world. Over the last decade he’s been a principal investigator on more than $20 million in grants from military organizations including the Defense Advanced Research Projects Agency, the Department of Defense, and the Office of Naval Research.

The first day of talks in Dayton focused on the problem of getting large teams of robots to work together without any human intervention. On the second day, Ghrist, who coincidentally grew up in nearby Cleveland, took the floor. He gave a presentation on advances he and his collaborators in the School of Engineering and Applied Science had recently made applying a subfield of topology called sheaf theory to the problem of isolating and tracking a target given a huge and often “noisy” set of data collected by automatic sensors like cameras and radar.

“When I gave my talk I told a story, something like a fairy tale,” Ghrist says, in which “Department of Defense investments in ostensibly basic or pure research led to techniques that were then able to be applied to a problem they clearly do care about.”

In a follow-up call after Ghrist had returned to campus, Air Force scientists quizzed him on his ideas, wanting to know more about how the system he’d designed would translate from the laboratory to the real world. He likens the interaction to deal-making. “They have specific problems with specific needs they’re working on and we have specific tools with specific hypotheses we’re working on,” he says. “It’s almost like a business negotiation [where each side says], ‘Hey, are you willing to give on that?’”

[quote align=”center” color=”#999999″]

“Topology is the mathematics of the qualitative as opposed to the quantitative,” Ghrist says. “Most people are used to mathematics as expressly quantitative, as numerical, but there are lots of phenomena where a qualitative understanding is sufficient.

[/quote]

For most of its history, topology has had very little to do with flying robots. The field was first developed in the late-19th century by, among others, the legendary French polymath Henri Poincaré. In mathematics, topology considers the properties of familiar kinds of spaces, like the circle, but also much more complicated spaces that can exist in infinitely many dimensions.

Topologists think of spaces in terms of their essential properties, and they don’t worry about characteristics like length or angle measurement. Instead, topologists classify spaces in terms of their ability to be smoothly deformed into each other, without any cutting or gluing. For example, a hexagon is topologically equivalent to a circle, because you can turn one into the other by inflating the hexagon and smoothing out its edges. It’s said that a topologist can’t tell a donut from a coffee cup: They’re both two-dimensional spaces (considering just their surfaces) with a single hole.

“Topology is the mathematics of the qualitative as opposed to the quantitative,” is the way Ghrist explains it. “Most people are used to mathematics as expressly quantitative, as numerical, but there are lots of phenomena where a qualitative understanding is sufficient.”

Topology grew quickly as a field during the 20th century, but didn’t spill over into other areas. During this period many other branches of pure mathematics found important practical applications: linear algebra became arguably the essential tool of modern engineering; and matrices, which had formerly been regarded as hopelessly esoteric, became indispensable in computer graphics.

Though it can take a long time, it’s common for abstract mathematical discoveries to eventually give rise to important practical application, Ghrist says. “Most applications of mathematics undergo certain transitions, phase transitions like the changing of water from ice to liquid to gas,” he explains. “What starts off as very pure and known only to mathematicians eventually crosses over into what I’d call applicable mathematics, where one sees what the application could be.” Eventually, a concept progresses “from the pure to the applicable to the applied to finally [being] implemented and adopted, where people outside of mathematics are really using it.”

For some branches of mathematics, like arithmetic and calculus, that translation took place long ago. For others, like topology, it is just getting under way. A decade ago topology had reached the applicable stage—it was clear that topology had a role to play in solving some important problems, especially in engineering, but the actual applications hadn’t been worked out.

Back in 1998, Ghrist was involved in one such application, which would later play a role in bringing him to Penn. At the time, Ghrist was an instructor at the University of Texas, Austin, having finished his PhD at Cornell three years earlier. At Cornell, he’d studied under Philip Holmes, one of the most important dynamical-systems researchers of the past century (who’s since moved on to Princeton). That experience, along with his undergraduate degree in mechanical engineering,made him a logical person for Daniel Koditschek—then at the University of Michigan, now the Alfred Fitler Moore professor of electrical and systems engineering—to cold-call when he found himself confronted by a problem that involved issues that come up when robots patrol a warehouse floor.

In the scenarios Koditschek was working on, the robots moved based on a method called optical path navigation, in which they used cameras to follow lines painted on the floor. Koditschek wanted to find a way to program the robots so that they’d never collide. This could be thought of as a complicated scheduling problem, or, Koditschek realized, it could be considered in a more subtle topological way.

In this view, you imagine all the possible positions of the robots as a “configuration space,” in which each robot moves in a different dimension. Within that multi-dimensional space, there are some coordinates that should be considered off-limits because they are where the collisions would occur.

“Those spaces are not the traditional spaces of Euclidean mathematics that the Greeks taught us about,” Koditschek says. “Those are more abstract spaces, so finding your way around those spaces really needs a collaboration between a person like Rob and me.”

Koditschek and Ghrist came up with a solution that uses vector fields toallow robots who meet at an intersection to reason about which one should go through first. The vector fields perform a kind of instantaneous arbitration, nudging the robots toward a cooperative solution to the problem. They published their work in 2002; six years later, Ghrist’s relationship with Koditschek helped lure him to Penn. Ghrist was drawn to the cutting-edge work Penn engineers were doing in robotics, and by the cross-disciplinary work he’d be able to do as a PIK Professor. “We would not have gotten Rob to Penn without that ability to be intimately connected to both schools at the same time,” Koditschek says.

Ghrist explains his decision to come to West Philadelphia in similar terms. “This is one of the things that really attracted me to Penn, that I get to live fully in two departments, and I get to ping-pong my brain back and forth across 33rd Street,” he says. “That really helps me think about what I’m doing in novel ways.”

 

When he gave his presentation at the Air Force Research Laboratory, Ghrist was wearing a suit and tie—but the formality wasn’t for the benefit of the military brass and scientists in attendance. He dresses the same way for his classes. One reason, he says, is to make an impression on his four school-age children about the importance of professionalism and hard work. And he also does it, he admits, as a kind of statement among his peers. “The mathematics culture in which I’m embedded has a proclivity for the dress-down—one might also say, the hippie aesthetic,” he says. “I’m expressing my cultural rebellion.”

This kind of against-the-grain thinking crops up in many areas of Ghrist’s life. While a lot of his work may conjure visions out of futuristic science fiction, in his leisure reading he gravitates toward medieval literature because, he says, he likes living in that world. He loves the Divine Comedy most of all, and also the Decameron by Boccaccio and Boethius’s Consolation of Philosophy. When asked why the period has such a hold over him, he starts to seem a little embarrassed. “It’s kind of like talking about how much I love my wife. I certainly do, and I guess I’m happy to tell everyone on earth about it, but it’s awfully personal,” he says.

That affection for old works and worlds hasn’t stopped Ghrist from embracing the new when it comes to educational methods. In 2013 he brought his unconventional thinking about math to a free online calculus course presented through Coursera [“MOOC U,” Mar|Apr 2013]. The 13-week course, which has since attracted more than 100,000students, includes many hand-drawn animations that provide a novel take on familiar concepts, like functions and integrals.

Ghrist says that the calculus course provides a glimpse of the way mathematics appear in his mind’s eye. “When I’m teaching calculus or topology, my head is full of images. What I’ve striven to do in this calculus course is really show off the mathematics visually and in motion.”

Vijay Kumar, the former UPS Foundation Professor of mechanical engineering and applied mechanics who was recently appointed dean of the School of Engineering and Applied Science [“Gazetteer,” May|June], also thinks that Ghrist’s take on calculus is indicative of how he approaches math in general. “He’s taking a subject that’s been taught for hundreds of years, and the way he teaches it is completely different,” he says.

In an introductory video to the course, Ghrist emphasizes his decision to upend the standard sequence in which calculus concepts are taught. The beginning of the class focuses on the Taylor series, a way of representing functions that’s usually taught toward the end of single variable calculus. It also places more emphasis than usual on asymptotics. Both choices, Ghrist explains in the video in a lilting voice, are meant to make calculus more conceptual and intuitive. This ability to see how familiar ideas could fit together in unexpected ways has also played a big role in Ghrist’s success finding applications for mathematical tools.

“At some level everybody knows very similar things,” Kumar says, “but it’s how you architect those pieces of knowledge in your head and how you organize it, how you connect it, that differentiates you. I think [Rob] is very unique in what he does.”

 

Since coming to Penn, Ghrist has spent a lot of time collaborating with engineers in the General Robotics, Automation, Sensing & Perception, or GRASP, Laboratory. Much of his work there has focused on technology for autonomous vehicles, which, rather than taking commands from a remote human operator, as many drones do, are able navigate an environment completely on their own. This ability is especially useful in places where good maps are lacking and GPS signals are unreliable, like the interior of a building or beneath the ocean.

The challenge robots face in these environments is akin to groping around an unfamiliar building in the dark. You don’t know anything about the master layout and you can only gather small pieces of information: here’s a door, here’s a wall, here’s what seems to be a column in the middle of a room. The key is to find a way to collect these local pieces of information and stitch them together to produce global knowledge about the properties of a space.

Local pieces of information, if combined correctly, can sum to an understanding that’s greater than its parts. One way to see this is with a kids’ brain-teaser. Imagine that someone draws a complicated curve on a piece of paper. The curve bends, twists, and doubles back, but never crosses itself, producing a very complicated-looking maze. Now imagine a person standing on the inside of the maze, who wants to know whether she’s stuck on the inside of a closed loop or has a path to get out. The answer won’t be immediately obvious, but there’s an easy way to find out: Draw a straight line from the person to the outside of the maze and count the number of times the line crosses walls in the maze; if the number is odd, she’s stuck in the maze, and if it’s even, she has a way out.

This calculation begins to get at the idea behind a tool topologists use called an invariant. Invariants come in many different forms, but altogether they are a way of probing the structure of spaces using an algebraic test. And what the maze example shows is that these kinds of simple tests can yield important knowledge about a space that might otherwise be too complicated to study.

“You’re looking at just a couple bits of localized information, yet you’re able to infer something global about [the maze],” Ghrist says. “Small pieces of local data can give you a global inference.”

In some of the real-world problems Ghrist works on, these local pieces of information are gathered by swarms of robots. In February 2012 Kumar gave a widely viewed TED talk in which he demonstrated the capabilities of the autonomous flying robots developed in the GRASP lab [“Drone’s Day Scenarios,” Nov|Dec 2012]. In a video he showed during the talk, the palm-size quadrotors assemble in tight, agile formations and dart nimbly through obstacles completely on their own.

The robots in the 2012 video were not yet programmed with the ability to reason topologically. Those ideas were developed over the next several years, in collaborations between Kumar, Ghrist, and a post-doctoral fellow, Subhrajit Bhattacharya. Kumar says the move to topologically based algorithms has helped him create robots that are smaller, smarter, faster, and cheaper. Balancing these priorities means doing away with expensive sensors, like GPS devices, which create bulk and consume battery power.

“How do you make something small, with crappier sensors, and make them smarter?” Kumar says. “That means you have to make them better at representing information and reasoning about it, and that’s where algebraic topology comes in.”

Algebraic topology provides engineers with a programmable language for describing a space without having to resort to metric measurements. Instead of talking about the length of a hallway or the angle of a turn, it’s enough to know that the hallway exists and how many branches come off of it. This is intuitive enough for human beings feeling their way around an unknown space, but it’s an unnatural way of thinking for robots, which work best with precise commands. One of Ghrist, Kumar, and Bhattacharya’s major contributions has been to find ways to take qualitative topological descriptions of spaces and translate them into terms a robot can understand.

“You put [algebra and topology] together and focus on making it computable, focus on algorithms for it,” Ghrist says. “Then you stand a chance to have some really big wins in terms of being able to solve large scale qualitative problems.”

The problem is even more difficult because the robots need to do more than collect information topologically—they need to be able to share it with each other, too. “So nobody knows the entire floor plan, nobody knows everything, everyone knows a little bit of something and they have to work together to look around, explore, but then plan to do things in as optimal a manner as possible,” Ghrist says.

To see how this might work, imagine a pair of quadrotors arriving at a T-junction in an unmapped building. One goes left, the other goes right, and each keeps a sensor trained on the wall as it flies down its branch of the hallway. This approach is similar to how two people might go about the mapping problem if they wanted to be absolutely sure they were not going to miss any important features of the space. We’d split up; I’d run my left hand along the outer wall and you’d run your right hand along the outer wall. If, when we met back up, we were each able to report that we’d never lifted our hands and had never encountered a break in the wall, we could be fairly confident that we’d completely mapped a closed loop.

Robots can’t talk to each other in such plain terms, but there are mathematical calculations that allow them to convey the same idea. As they fly down their respective branches of the hallway, they continuously take an integral measure of the surface of the wall they’re following. When they reunite, they share their integral measurements. If the first robot’s number and the negative of the second robot’s integral number sum to zero, the robots known they’ve traced a loop that doesn’t encircle anything interesting, like another hallway. If the sum of the numbers is non-zero, they know there are additional features to be mapped.

This same kind of approach can be used to map a whole building, provided you have enough robots. Given a room with only a single obstacle, like a column, you’d need two robots in order to establish the room’s topology. In a more complicated space, with many rooms, many obstacles, and lots of hallways, you’d need more robots that, working in tandem, could take on pieces of the terrain and establish they haven’t missed anything between them. The resulting map would show the space boiled down to its essential features. It would lack the precise measurements of an architect’s drawing, but it also has several advantages over a quantitative mapping approach. It takes far fewer robots to create a topological map than it takes to sweep every square inch of a space. And, a topological map created in this way ends up being much more reliable than a map built from remote metric measurements, which are often inaccurate.

“The story of topology is that one can convert that very qualitative visual problem into something algebraic, that can be vigorously characterized, checked, classified, certified, and you can say without a doubt, this area is safe,” Ghrist says.

 

The nature of the military’s interest in autonomous swarming robots is plain, and it’s not something that particularly bothers Ghrist.

“I think about it from a historical perspective,” Ghrist says. “If you look back at the kinds of research the military has funded over the years and what it has led to, on the whole I feel really good about participating in that collective endeavor.”

He cites the research that led to the internet and GPS, among other military projects that have substantial positive spillover effects. And then there are lasers. “We don’t have hand-held laser blasters, but what we do have are lasers in Blu-Ray players,” Ghrist observes.

With algebraic topology, the directions for future applications are just beginning to emerge. One immediate place to look, says Ghrist, is with the development of driverless cars, which are expected to hit the roads sooner than not. Those cars will navigate primarily according to GPS, but Ghrist thinks that engineering them with the ability to reason topologically is an important backup. “What do you do when the GPS system fails because you are in an urban canyon between skyscrapers?” Ghrist asks. “That’s a good time for a topological failsafe.”

Topological thinking has begun to seep into other fields as well. Ghrist is collaborating with MacArthur “genius” grant award-winner Danielle Bassett, the Skirkanich Assistant Professor of Innovation Bioengineering, to use algebraic topology to understand the way neurons are wired in the brain. Topological thinking is also increasingly influential in big data analysis, where it’s used to probe for patterns in huge data sets.

 

And Ghrist is continuing to work on finding ways to use algebraic topology to improve sensor networks—but without military backing, so far. A month after his trip to Ohio, funding talks with the Air Force Research Laboratory broke down. As Ghrist characterizes the discussion, the AFRL was more interested in seeing proof of the immediate advantages of Ghrist’s methods. “That’s the way it goes in this business,” he says. “You have to go to half-a-dozen of these types of meetings in order to find one person who cares about breakthrough research as opposed to number-crunching.”

Ghrist first hit on the idea of using sheaf theory to improve the performance of sensor networks eight years ago, and the theory itself has been around since the 1940s. He hopes one day to make it indispensable for solving real problems, but he’s philosophical about the long road it takes to get there.

“Part of my professional mission is to excavate some of these useful, beautiful ideas and show how they can be put to work,” he says. “My goal is to take tools and perspectives of algebraic topology and drag them, kicking and screaming, over the line from pure to applied.”


Kevin Hartnett, a freelance journalist in Columbia, SC, writes the Brainiac column for the Boston Globe’s Ideas section and is a contributing writer for Quanta Magazine. His work has been collected in the “Best Writing on Mathematics” series.
Share Button

    Leave a Reply