01/04/2011 08:00:00

Prepare Ye the Way of the Droid

Noon: a crowded cafeteria. You drift past the salad bar, glumly eyeing the line at the pizza counter. But what's this rolling toward you? It's a little robot—vaguely reminiscent of the movie 'droid WALL-E—and the two of you are moments from a head-on collision.

Do you halt in your tracks? Jump back? Veer away? Feint left and dodge right? Perhaps you just tromp right across the motorized monstrosity—your little act of revenge against every insane robot in every B movie you ever watched as a kid.

These questions aren't merely academic, because the situation isn't at all hypothetical. Over the past several months, a little wheeled gizmo sporting stereo camera "eyes" has occasionally been spied lurking in Caltech's Chandler Dining Hall around lunchtime. Its creator, graduate student in control and dynamical systems Peter Trautman, has been using it to study interactions between humans and machines. His project, to be presented at next week's TEDxCaltech conference, is teaching robots how to behave—and survive—in crowded environments.

Nor is this just for his own amusement. Robots, he says, won't become common in hospitals, stores, and museums until, like teenaged drivers, they've learned to maneuver safely and quickly through crowds. But how? By sauntering forth in a straight line? That's dangerous, overaggressive—and frankly obnoxious. Taking wide, evasive detours? Too inefficient. Waiting for gaps in traffic? That risks perpetual immobility: what roboticists call the Frozen Robot Problem (FRP).

Teenagers thronging a mall, rush-hour drivers, skiers on a crowded slope: all exhibit movement in response to the movements of others. It's one thing to observe all this from afar, but the moment a robot sets foot into a crowd, the observer becomes the observed.

Modeling these convoluted feedback loops is mathematically intractable; that's why most roboticists to date have relied on either intuition and psychology (what do humans "expect" of our little mechanical mascots?) or artificial intelligence (letting the robot itself discover by trial and error what works and what doesn't).

Neither of those strategies addresses the Frozen Robot Problem (FRP), says Trautman, cheerfully quoting Caltech Nobelist Richard Feynman: "What I cannot create, I do not understand." A human pedestrian constantly makes small speed and direction adjustments, and any automaton hoping to navigate, say, a mall on Thanksgiving weekend cannot emulate this behavior without first comprehending it. This, in fact, was his breakthrough: the realization that solving the FRP would require not merely implementing cooperative collision avoidance, but also forecasting it in others. Fortunately, although the logic of crowds is complex and largely subconscious, he discovered that he only needed to model a few of its characteristics (intentionality, contact avoidance, and some basic dynamics of the human body), all of which could be measured by filming pedestrians. The result: a probabilistic algorithm that produces natural, brisk motion and also chooses shorter, safer trajectories than most humans do.

Along the way, he found some surprises. For instance, it turns out that a robot moving with purpose is generally ignored by passersby. But once it pauses, individuals start harassing it; a crowd may gather; and when the machine tries to move again, it can't. "Sometimes," Trautman marvels, "people will even try to force it into a corner."

In other words, in a schoolyard full of bullies, the robots are having to learn the same lesson we once learned:

"Head down; avoid eye contact; keep walking."

Written by Dave Zobel