20120814 BBC
Contributor: Christopher Mims
As the largest city in southern China, with a population of around 13 million, Guangzhou has traffic so bad it's legendary. One way to alleviate it would be to increase the intelligence of traffic lights – converting them from dumb beasts that beat out the same rhythm all day long into dynamic managers of vehicle flow.
And now two Chinese researchers have proved, at least theoretically, that insights borrowed from the lowly bacterium E. coli could markedly increase the throughput of a real-world traffic light in Guangzhou. No one knows what effect this could have if it were applied to an entire city, but it's fitting that a solution from a class of algorithms that seek to mimic the collective behaviour of organisms should be applied to the teeming masses of Guangzhou's trucks and automobiles.
Traffic lights around the world, from Guangzhou to Geneva, are managed by computerised systems housed in a metal cabinet at the side of the road, which regulate the cycle of changes from red to green to red either through fixed time periods, or through sensors in the road that can detect when a car is stationary. Both options work well when traffic is low, less so during rush hour, as any driver will tell you.
The solution Qin Liu and Jianmin Xu have proposed for improving flow during high traffic periods is what's known as a Bacterial Foraging Optimisation (BFO) algorithm. The algorithm varies when and for how long a given light is red or green. So, for example, the algorithm has an almost traffic cop-like sense for which road at an intersection has a higher volume of traffic, and when to strategically deprioritise traffic that may be waiting on a less-used road. Simulations of a Guangzhou intersection showed that BFO-regulated lights reduce the average delay of vehicles by over 28% compared with those regulated by a fixed time cycle.
Behaviour code
It's part of a surprisingly rich history of applying algorithms inspired by nature to traffic light timing – researchers have applied everything from genetic algorithms to models of ant behaviour to the problem. And it's not just traffic lights – BFO can be used on just about any engineering problem, from tuning the behaviour of simple automated control systems, such as those used to regulate the level of water in water towers, to determining the lightest and strongest configuration of structural elements in a building.
BFO was invented in 2002 by Ohio State professor of electrical and computer engineering Kevin Passino. As is the case with many discoveries, Passino wasn't searching for a better mousetrap when he stumbled into one. Instead, he was merely trying to create a faithful simulation of the food-seeking behaviour of E. coli.
Like many bacteria, E. coli swims more or less randomly, but it will spend more time swimming in the direction of food and less time swimming away from it. This incredibly simple behaviour allows the bacterium to move up a chemical gradient, from areas of lower concentration to areas of higher concentration. Once Passino expressed this behaviour in code, he had his eureka moment.
"I realised that it could solve engineering problems, because what it was doing was performing an optimisation," says Passino. Many engineering problems like design, quality control and maintenance of buildings and devices can be expressed as "optimisation problems", in which a single number, known as a performance index, quantifies how good any particular solution is. A good algorithm will find the best possible combination of all the parameters in a system to make it perform as well as possible according to this one measurement of quality.
Follow the swarm
Individually, E. coli aren't very smart. Yet according to Passino, making them more intelligent about their environment doesn't improve the performance of his algorithm. In part, that's because BFO finds the optimal solution to any problem by letting multiple virtual E. coli loose, one after another. After a hundred or so have run the simulation, generally at least one has found a pretty good solution.
Running the algorithm over and over again turns it into a classic case of parallel processing, which is exactly the trick our (relatively slow, at the neuronal level) brains employ to outwit computers on most tasks. It's also the very definition of "swarm intelligence", in which groups of animals operating according to simple rules can solve very tough problems.
Other biomimetic algorithms exist, some of which simulate ants, bees or swarms of insects. Further afield, there are algorithms that simulate genes and natural selection, and even primitive nervous systems. They're all part of a much broader class of solutions that seek the best possible solution to any particular optimisation problem.
Knowing that these solutions can operate on real-world problems doesn't mean they've been incorporated, yet. At this stage, the research by Qin Liu and Jianmin Xu has yet to go beyond the modelling stage. But it's reasonable to expect that as the components of cities become ever more interconnected, centralised traffic systems will incorporate whichever combination of optimisation algorithms – out of the thousands available – will be best at reducing urban China's infamous traffic.
