PopSci's Brilliant 10

Lydia Kavraki: How can the robot know how to move through the ever-changing human world?

Photograph by Brent Humphreys

Computers must serve the social good: "My sister and I were always taught to put humans first in whatever we do." -- Lydia KavrakiPhotograph by Brent Humphreys

LYDIA KAVRAKI
Computer Science, Rice University

Lydia Kavraki credits her parents with instilling in her a desire to understand how the world works when she was still a schoolgirl on the Greek isle of Crete. They didn't want her to think only mechanically, however; they also taught her that "technology should serve humans, and in the best possible way."

Kavraki was exposed to computers from an early age because of her father's work in the airline industry. By 18, she'd heard the siren song of computer science. But as a graduate student at Stanford University, in the heart of Silicon Valley, she looked beyond theory and code to the world in which humans and computers coexist. Computers alone were too remote, impersonal. No stereotypical computer geek, this Greek; Kavraki can cite the ancients, and defers to Heraclitus on the constant nature of change.

"I like interactions with the physical world, I love geometry," Kavraki says. "I like physical things." Thus she turned to practical challenges. She started to think about how robots are programmed to navigate. The problem is a tricky one. Say you want a robot to travel from point A to B, and the robot has 10 moving parts. There are a vast number of combinations in which it could use those parts to mount steps, turn corners, and so on-a number so large even a powerful computer would have trouble finding the optimal solution. Kavraki's answer was to randomly sample the range of poses open to the robot, create snapshots of the machine in motion at various stages along its path, and then connect those snapshots as efficiently as possible into a kind of road map. The computer does not search every possible combination, and may miss the best solution every now and then. But the process is fast and reliable, and that's crucial for operating robots in real time.

Kavraki's work is rapidly becoming the stuff of textbooks; meanwhile, several major companies, including General Motors, are interested in applying her method to industrial problems. But creating smarter robots for the assembly line is just a stepping stone, as far as Kavraki is concerned. Ultimately, she says, "I would like to see a robot that would help an elderly person get out of bed safely, or help the disabled to get around."

Kavraki, 35 and an associate professor at Rice University, is now looking for ways to model biological molecules to aid in the hunt for new medicines. Chemicals rotate, waggle, stretch, and flex-much like articulated robots. Instead of navigating through corridors, a drug often needs to wedge itself snugly into the groove on a protein molecule. Kavraki hopes that her technique will help search through drug candidates more rapidly. "I like to work on problems that will generally improve the quality of our life," Kavraki says.

What's your earliest memory of scientific interest or achievement?: Getting a
microscope from my parents at age 6 or 7.

Favorite place to go: Crete

What are you like when you're totally immersed in your work?:
Like a master chess player. I like to get as close to the goal as possible
and explore all the interesting aspects along the way.

Make an out-on-a-limb prediction for your field: When I'm elderly, I expect
robots to be around to help me, and better drugs and disease control.

What's the thing you love most about science?:
Working with students and interacting with people from diverse intellectual
backgrounds. Discovery and the challenge of solving a tough problem,
especially when it can really affect the quality of our lives. I find the
whole process energizing.

What do you do in your spare time?: Travel, read, listen to music.

As a kid, what did you want to be when you grew up?: At first I considered a
career in the life sciences or medicine, but CS won out.