Research project: Traffic lights that learn

Controlling the traffic lights on a network of roads and junctions is an optimal switching problem. In 1995 computational complexity theorist Christos Papidimitriou proved, that this problem is "EXP time complete'" meaning that it is intractable in practical terms. Consequently traffic light control algorithms are developed using approximate optimisation methods.

The research carried out on this project has shown that in some scenarios a human controller can outperform currently deployed traffic light control systems, albeit for a limited time period before fatigue sets in. It has also shown that by asking the human controller to play a “traffic light control computer game” it is possible to capture their control strategies using pattern recognition. Thus machine learning junction controllers have been developed that can match human performance.

To investigate whether human performance was generally superior to approximate optimisation on this task we developed a temporal difference learning controller designed to act on exactly the same state-space and function approximator used in the machine learning controller. In theory this could find the same strategy as the machine learning controller. After running for a month on a high-end PC the optimiser had found a good strategy, capable of outperforming current systems but not humans, or the machine learning controller trained by the humans.

Work is continuing to develop machine learning junction controllers and we are also investigating how the work can be generalised to other transportation scenarios.