The boxer has his hand, well, up his butt. He has
just thrown a punch, a hard one—too hard because the forward momentum
nearly threw him flat on his face. He saved himself by pulling his
right arm back behind him as a counterbalance, a tactic that worked,
except for one thing: as that arm came around front again, it grazed
his posterior, causing his hand to stick where the sun don’t shine.
Leah Fasten
Computer Science Professor Chad Jenkins works on designing robots that we can teach to do our bidding. His amazing vision of the future starts with the push of a joystick.
Now
the fighter’s opponent should be able to clobber him. But these
fighters are characters in a video game, one in the earliest stages of
development. The game still has glitches, so the opponent is standing
on the opposite side of the computer screen solipsistically shadow
boxing. He shows no signs of wanting to engage in combat. In fact, both
fighters bear little resemblance to real people. They are stick
figures, made up of small orange rectangles attached where we humans
have joints.
Don’t expect these boxers to be showing up on an
Xbox any time soon. But once its creators, computer science professor
Odest “Chad” Jenkins and his former student Pawel Wrotek ’05, further
develop it, the game might help you not with boxing but with housework.
Why? It’s all about artificial intelligence. Eventually, Jenkins and
Wrotek plan to invite an actual heavyweight boxer to come into the lab,
don a body suit studded with sensors, and teach the computer how to
move and fight. If all goes as expected, the pixilated boxer on the
computer screen will start to learn how to literally think like a
champ, with the same instincts, acumen, and prowess.
Now take the same software and put it inside a
robot. This time, you’re the one with the sensor-studded body suit.
Pick up a broom or fire up the vacuum and start cleaning the house. The
robot will first learn to imitate you, then grasp your preferences and
patterns of behavior, and will even detect how you react when the
telephone rings or the baby cries. “It’s too hard to program a computer
to do what you want it to do,” Jenkins says. “It’s much easier to
demonstrate and have the robot follow.”
So that boxer with his hand up his rear? In the
not too far off future, you may be having him answer your doorbell, put
away the dishes, and fold your laundry.
If it’s true that learning should be fun, the twenty-seven members
of Brown’s computer science faculty are doing a lot of learning. Most
of these professors work in highly esoteric and complicated areas of
research. They are well acquainted with such things as stochastic
optimization, cryptography, and natural language processing.
You will also find, though, that many of these
scientists spend a great deal of time designing and playing games.
Games are where the rubber meets the road, so to speak, where
theoretical ideas get transformed into practical applications that may
one day transform our everyday lives.
Leah Fasten
This souped-up robotic dog programmed by Brown researchers is in training to become the computer world’s next Pelé. His software may one day be put in androids capable of beating the World Cup champions.
Take
Amy Greenwald, for instance. Greenwald, one of the department’s star
junior faculty members, specializes in devising optimal decision-making
algorithms and artificial-intelligence heuristic search techniques. But
day-to-day, she spends a significant amount of time preparing for a
tournament called the Trading Agent Competition, in which teams of
pretend travel agents take part in twenty-eight simultaneous
competitions, eight for hotel rooms, eight for flights, and twelve for
concert and entertainment tickets. The real competitors, however, are
not the human beings but their computer software. Balancing forecasts
of supply and demand, assessments of customer preferences, and
judgments of what the other players will bid based on their behavior at
previous auctions, the software places bids on behalf of each team. The
winner is the one whose travel agency makes the wisest bids and
therefore earns the highest profit.
Leah Fasten
Our whole economic system is just one big game to Amy Greenwald, who designs software that can be used to bid—and triumph—in internet auctions. Imagine being able to participate in dozens of eBay auctions at the same time and win.
Think
of what such a computer program could accomplish on eBay. After you
told the computer your preferences and needs, it would find the
auctions that satisfy these criteria and enter simultaneous bids in all
of them. Because the program would also be analyzing the habits of
other bidders, its final bid would be just high enough to beat the
competition, and not one cent more. And if such a program could do this
on eBay, just think of the impact more sophisticated versions might
have in other areas—Wall Street or international finance, for
example—where game theory really matters. Greenwald, a rare female in a
male-dominated field, calls her software RoxyBot. In this year’s
tournament, it trounced the competition.
Chad Jenkins began playing video games after his
father, a warden at a federal prison, brought home an Atari console.
Jenkins was eight years old. “It was like this magic black box,” he
recalls. “I was just fascinated.” Twenty years later, for all his
ambition to push the outer limits of his academic specialty, artificial
intelligence, Jenkins just wants to develop the perfect video game.
What holds back such games is their limited ability to learn. Right now
the range of actions you can take as a player depends on the number of
maneuvers programmed into the game’s software. Kick, punch, jump, duck,
and shoot are pretty much all you can do. But imagine the action if the
game’s software can learn new moves from human players. That such a
breakthrough in the world of gaming could lead to the development of
robots capable of being educated by humans can seem beside the point to
Jenkins, who seems not to have shed completely the perspective of an
eight-year-old boy. “Ever since I was a kid playing those video games,”
he says, “I’ve known I could do it better.”
In other words, if you really want to know what
the future of computer technology will look like, skip the journal
articles and the academic conferences. Sit down with these professors
and play games with them. That’s where the seeds of technological
breakthroughs are being sown.
I am a troll scurrying around the labyrinthine ground floor of a medieval
castle. I head up a cobblestone ramp into an atrium and fire off a few
blasts at the dozens of other trolls running around. This video game,
known as the Cube, presents me with formidable foes. They have rocket
launchers; I have a handgun. Within seconds, one of them fires off a
burst. “You are fragged,” the computer screen reads. Translation: I am
dead.
I challenge computer science grad student Yanif
Ahmad ScM ’04 to do better. He finds a way to replace the handgun with
a rocket launcher, which I consider unfair. Then again, he has spent
the last several years of his life developing this program. Not that it
makes much difference, anyway. He manages to kill a few enemy trolls,
but then one of his foes sneaks up behind him and blows him away. He
didn’t last much longer than I did. “Right now, there are too many
trolls in too small a space,” Ahmad explains. “Even I can’t cope in
there.”
What’s different about this game is the level of
complexity Ahmad is striving for. He is trying to write code that will
let hundreds of thousands of users all across the globe battle one
another simultaneously.
To achieve such a real-time gaming environment,
the slightest move by one player must register instantly on individual
computers all over the world. The technology for doing that today
requires an individual player’s computer to relay a command to a
central computer server, which in turn sends it out to everyone else’s
computer. This takes time—too much time, in fact, for the Cube to work.
Having a player in Beijing beam a request for data to a server in
Providence and then wait to get an answer back wastes milliseconds,
time you simply do not have if you want the Cube to achieve its full
potential. Besides, hundreds of thousands of users asking for updates
on other players’ maneuvers every few milliseconds would overload the
entire system.
How quickly information moves among computers is
a fundamental problem of our age. As Ahmad’s adviser, assistant
professor Ugur Cetintemel, describes it, “We have reached the point
where no computer, no matter how powerful, will ever be able to keep up
with all the information out there.” This is why the Cube experiment is
so critical to the future of computing. It’s not just the Cube that
needs to relay massive amounts of information in real time; computers
on Wall Street must constantly update the market data they send to
investment companies. News sites can update their Web sites every few
minutes at most; more frequent updates would crash their servers.
Getting information out faster in such businesses can give them a huge
competitive advantage.
Leah Fasten
Ugur Cetinitemel is building computer networks that can transmit data at close to the speed of light.
There
are more mundane advantages as well. Supermarkets may soon be attaching
sensors to every item they sell to help them continually track and
update their inventories. They are looking at scenarios that would
allow them to track the precise whereabouts of their products, so that
the act of putting one product in your grocery cart would trigger price
adjustments to items you haven’t reached yet. If you were stocking up
on celery sticks, for example, the market might immediately drop the
price of dip to encourage you to spend the extra money. Right now no
computer server out there has the processing power to handle so much
data quickly enough. But if only Ahmad could get that Cube working
right.
Cetintemel’s solution is what he calls an
“overlay network.” Instead of a centralized server, the Cube will use
every computer in the game as a kind of mini server sharing the
responsibility for moving data. If Player A moves his troll forward,
his own computer will send this information to several other computers,
each of which relays it to several other computers, and so on and so
on. Every computer becomes in effect a server. Similarly, if you want
updates of news beamed to you by CNN every second, you will have to
give over some of your computing power to serve the larger needs of the
network.
The problem is that every computer—hundreds of
thousands of them in this example—will have to think like a server,
making split-second decisions about the most efficient way to route
data. If, for example, Player A’s computer in the Cube senses that
Player B’s computer has a slow processor, it will send a signal out to
the other computers to make sure that Player B’s computer is pushed to
the fringes of the network. Player B’s computer will also need to be
able to tell if Player A turns his machine off, and then send out a
message informing the network that A is AWOL and a new replacement
needs to be found immediately. What you wind up with is a highly
dynamic, supremely powerful, Borg-like network that is constantly
reconfiguring itself to deliver information at a rate approaching the
speed of light. “No one has ever achieved speeds like this before,”
says Ahmad. “Whether this is feasible at all, I don’t know, but we’re
going to give it a shot.”
It’s spring break, and the campus is deserted. Even athletes aretaking
a week off. But holed up in a computer lab, Dan Grollman ScM ’05 and
three other grad students are at work training a dog. Grollman, the
group’s captain, presses a button on a store-bought Logitech joystick.
A few feet away, a five-inch-high robotic poodle rises to attention.
Its platinum head, complete with two purely decorative plastic ears,
mechanically turns back and forth. It seems to be sensing something.
Grollman pushes the joystick, and the robot moves forward, its legs
motoring in little circles as it walks in a motion more ducklike than
doglike. It reaches a plastic pink ball, then swings its front right
leg forward. The ball moves. The poodle swings its leg forward again.
The ball moves again.
Leah Fasten
Ethan Leland ‘05 and team captain Dan Grollman ‘05 ScM created a team of robotic dogs able to play soccer. For now, these computerized canines can only run after the ball and kick, but in the long-term they could pass and play out complicated strategies.
In
a few weeks, Grollman and his team will travel to Atlanta for the
RoboCup competition, where four of their reprogrammed robotic dogs will
face off in a soccer game against canine squads from other universities
around the country (They wound up losing all sixteen matches). For now,
the game is basically what Grollman calls a “canine free for all”—the
dogs are programmed to sense the location of the ball, go toward it,
and then kick it. With luck the ball will move in the direction of the
opponent’s goal. In an example of the level of optimism that drives
scientific researchers, RoboCup’s organizers believe that in fifty
years similar androids will be able to compete with that year’s World
Cup champions—and beat them.
Before that’s possible, Grollman says he will
need to perfect “a dog that can learn new tricks.” As with a real dog,
this means repeating a lot of actions over and over so that the robot
can gather and collect data on what its sensors detect. The data it
records while racing toward the ball, for example, form what might be
called Snapshot 1. By recording such things as the amount of light
overhead, the rotation of its legs, and the distance between it and the
ball, and by joining that data with the information it took in response
to these stimuli, the dog will be able to react the same way when it
encounters another constellation of stimuli similar to Snapshot 1. Over
time the dog will have created so many snapshots it will have the
ability to parse the data and “reason” its way to reacting to its
environment. This constant analyzing and reanalyzing of snapshots will
eventually give the dog a kind of intelligence that will let it
improvise even when its opponent plays out a maneuver that’s totally
unexpected.
The work is similar to what Chad Jenkins is doing
with his boxers. Through their games, both are trying to achieve the
same serious goal: to bridge the gap between robots and humans. Both
Grollman’s dog and Jenkin’s boxer think like any other computer, in
binary combinations of 0’s and 1’s. Because humans don’t think that
way, they are trying to write software that translates human reasoning
patterns into 0’s and 1’s, the vocabulary of computer code. In the case
of the dog and boxer, this happens through a process known as
“dimensionality reduction.” The software sifts through all the data the
robot or boxer has collected from the environment and picks out the
information that was the basis for its human master’s decision.
When Grollman tells his dog to advance on the
ball, the machine actually collects more than 20,000 pieces of data
about its position and environment at that precise moment. Assuming
Grollman succeeds in his quest, the dog will then be able to select out
the half dozen or so stimuli that most likely motivated the human being
in the first place. The pooch will ignore, for example, that it was
three feet away from a wall or that the light was dim overhead.
Instead, it will know that the information pertaining to its distance
from the ball, the goal, and its closest opponent was pertinent to its
human master and therefore must be the most important data.
Jenkins sees this kind of learning, however
stilted, as the only way machines can become fully integrated into our
everyday lives. What good is a housecleaning android that tidies up
your house according to information preprogrammed into its software by
its manufacturer? It needs to be able to internalize your preferences
and, even more important, to react as you would in situations it hasn’t
encountered before. “Right now,” Jenkins says, “we have programmers
that sit down and manually program what they think a robot should do,
but it takes a lot of time.You can get a really big advantage in
programming a robot by letting humans be humans and having computers
just observe and learn from them.”
This may all be a pipe dream. It might even
create robot Frankensteins. One thing is for certain, though: Jenkins,
Grollman, and their colleagues will have a lot of fun trying to achieve
it.
Lawrence Goodman is the BAM’s staff writer.
