Thursday, June 20, 2013

Traffic Light Coordination, Genetics, and Machine Learning

Assuming that everyone always drives at the speed limit, we should be able to time the traffic lights down a stretch of road so that nobody ever hits more than one red light. Just make the lights change at a difference in time equal to the distance between the lights divided by the speed limit.

I don't know why this road has so many lights,
but at least they're all green.

Well, its not really that simple. What about the cars going in the opposite direction? What about the cars driving on the perpendicular roads? Is there a way that we could time the lights so that nobody ever has to hit them more than once? Maybe. Not for most roads, though. Can we optimize the timing? Maybe. Some roads have more traffic than others, which must be taken into account.  It turns out to be a very difficult optimization problem with many local minimums. A genetic algorithm may work well, nonetheless.

What if we don't assume that everyone is traveling at the speed limit all the time? People do take some time to accelerate before and after hitting lights. Also, different people drive at different speeds at different times of day and in different weather. Some roads have more cars at different times and on different days. In addition, it is almost impossible to predict how people will change their driving in response to changes in the light timing. These things make the problem essentially impossible to solve on a computer alone.

Try calculating that!

Maybe we need to use some machine learning. Have a camera installed on each light that can count the number of cars waiting. Then, change the timing of the lights every so often and see what works the best. Done. Well, not really. There is a concept in machine learning called "Exploration vs Exploitation" and it plays a crucial roll here.

Like I said, this is a problem with many local minimums. Finding an optimum solution by merely watching the effects of the timing on the traffic could take years. We would be wasting valuable time with bad systems just to find the absolute minimum.

We could combine the genetic algorithm with the learning technique. Start by calculating some optimum solutions with the genetic algorithm that assumes speed limit driving. Apply the best solution and then watch the flow of traffic. Learn where the calculations have gone wrong and why. Update the genetic algorithm. Continue to use the best solution from the algorithm, but continue to improve it via machine learning.

This is much easier said than done, but many smart people are currently working on this problem. Maybe one of them will figure it out. Until then, take the highway.