The University of MichiganNews Services
The University Record Online
Updated 12:00 PM June 23, 2005




view events

submit events

UM employment

police beat
regents round-up
research reporter


Advertise with Record

contact us
meet the staff
contact us
contact us

Come out and play—fictitiously

Imagine cruising home from work through heavy rush hour traffic, your windows down and hair blowing in the wind because—gasp—your car actually is moving.

The reason it's moving is because the optimal, real-time traffic patterns already have been worked out and applied using fictitious play, a mathematical concept that U-M researchers apply in a novel way to solve complex system problems including traffic congestion.

Robert Smith—the Altarum/ERIM Russell D. O'Neal Professor of Engineering and co-author with Marina Epleman of "A Fictitious Play Approach to Large-Scale Optimization," to appear this month in the journal Operations Research—says that using the fictitious play method to seek the best solution is similar to how people problem solve in real life.

In this method, every player has the same goal—to reach the optimal result, whether it is the quickest route from work to home, or the most efficient manufacturing production line. Doctoral student Ted Lambert also worked on the paper.

"It's what meetings are all about; you arrive at a joint consensus," Smith says. The learning model of fictitious play is related to the work of John Nash, the subject of the movie, "A Beautiful Mind." Fictitious play models how people might interact to discover a Nash equilibrium, which seeks the best joint strategies for games with two or more players that reach an outcome to mutual advantage.

Using computer modeling, U-M engineers used fictitious play to simulate the traffic conditions through 75 traffic lights in Troy, Mich. Smith says the result was at least a 20 percent savings in travel time, just by adjusting the traffic signals.

"These traffic signals are just finding out how to cooperate with each other as they play for the common interest," he says. "Weeding out all but the best options, they are all doing micro-improvements jointly and simultaneously, which makes the whole system better and better. This game can be played in parallel, all (traffic lights) can have their own little Central Processing Unit."

The method also is much faster than the brute-force method of computer number crunching, Smith says. For example, it would take the world's most powerful computer more than 300 years to test all possible options on an eight-mile trip with 64 intersections, to determine the fastest route.

"You can't do this thing with simple-minded crunching alternatives through computers," Smith says. "This is a problem we have to solve intelligently."

By applying the concept of fictitious play, decisions about which direction to turn are anticipated in parallel at every intersection, and the previous outcomes fuel the next until all but the best options are weeded out.

The challenge now is to wed communication technology with computational technology to understand the traffic network in real time, Smith says. Instead of a what-if analysis, the hope is to use intelligent vehicles as statistical probes that report on prevailing congestion, thus providing real-time updates on evolving traffic conditions, he says.

More Stories