‘Ants’ go marching on to optimize traffic lights

Tiny and industrious, ants are models of teamwork and efficiency. The picnic-wrecking insects could also teach city planners a thing or two about how to optimize the timing of traffic signals, according to students at the Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS).

For their final project in “Advanced Optimization” (AM 221), taught by Yaron Singer, assistant professor of computer science, applied math concentrators Robert Chen, A.B. ’17, and Alex Wang, A.B. ’17, used a heuristic technique called “ant colony optimization” (ACO) to find the most efficient time settings for traffic signals on a grid of city streets.

“Efficiently controlling traffic light cycles could have major benefits for the public, since people spend more and more time sitting in traffic,” Wang said. “Optimization could reduce wait times at intersections across an entire city, saving time and money for a lot of people.”

Traffic systems have often been the target of different modeling techniques, but the inherent complexity of traffic flow, which becomes even more complicated when additional intersections and light cycles are added, makes it difficult to optimize mathematically, Chen explained.

So Wang and Chen took a page from Mother Nature’s book. In ACO, simulated “ants” traverse a graph that maps all possible solutions to the problem—in this case, all possible light cycle combinations on a square grid of city streets.

“These simulated ants deposit pheromone chemicals on the paths that they take. They will deposit more pheromones on solutions that are better—more efficient—and this encourages more ants to follow that path and converge on the optimal solution,” Wang explained.

The ants traverse all the edges and vertices of the graph, but they travel over the edges with the highest pheromone values more often. In this case, these well-traveled edges represented the optimal timings for each traffic light, and were more likely to be used in future iterations as the simulation progressed.

The large number of possible traffic light settings initially made this approach computationally unfeasible. Chen and Wang developed a novel solution: they adjusted the graph so that pairs of vertices shared the edges, reducing the total number possibilities that needed to be explored in each round of simulation. They further enhanced their study by taking into account the relative ranking of ants, as opposed to evaluating the ants on an absolute scale, which is typical in ACO. In each round of the simulation, how much pheromone the ants deposited compared to other ants determined the optimal solutions used in the next round of simulation.

“The adjustments we’ve made to ACO are actually reminiscent of several machine learning techniques, so it would be interesting to apply this ACO method to other problems that are generally tackled with machine learning and see if there are any differences,” Chen said.

In the end, their modified ACO system led to a 7 percent decrease in mean travel time over standard baselines used in some cities. In practice, rather than simply timing each green light for an arbitrary 30 seconds, the ACO model might lead city planners to time a green light at one intersection for 20 seconds, while another would stay green for 40 seconds. With this theoretical model, the next step would be to apply the techniques to real-world city data to see how it works with a dynamic traffic system, said Wang.

For Wang and Chen, the biggest lesson they learned from the project—aside from the power of mathematics to solve real-world problems—is that experimentation doesn’t always lead to expected results. At the start of their research, they thought the ACO method would be too complex to effectively solve their problem.

“So often in research projects, the intuitive methods are the ones that perform better, but you never truly know what you are going to find,” said Chen. “Whatever avenues you start exploring, it is critical to put your assumptions aside and consider your next steps based on what you see from the results.”