Road traffic optimization

Motivation

Large road traffic congestion is a serious civillization and commercial issue. It causes huge delays, wasted time and energy, noise and larger emission of greenhause gases which may have a negative impact on the environment and our health. Therefore, it is important to analyze and manage traffic properly. There are very good ideas to reduce the demand for using private cars by introducing public transport, carpooling/vanpooling services. However, the pandemic crisis showed the the shared mobility is not a perfect solution. There are also ideas to build more bicycle paths which are great as well but we can't travel everywhere with bikes, some people can't use them or can use them only for short distances. There are also ideas to ban using private cars in some areas (e.g., city centers) or collect tolls for driving in city centers or for parking. It also helps but we don't like bans and too large costs of parking. Sometimes we just have to use private cars so they will stay with us in the future, at least for some time. However, they may become more and more autonomous and connected with each other and with the road infrastructure, so that it will be more and more easier to acquire the information about traffic conditions and future route of vehicles. Therefore, we should already think on how to take advantage of the growing amount of traffic data and availability of computational power. The answer may lie in new technologies, such as AI or quantum computing, and designing the best possible future traffic management systems leveraging the power of those new technologies is one of the goals of the TensorCell research group. 

Traffic jam in Delhi. Source: https://en.wikipedia.org/wiki/Traffic_congestion 

Our approach

Traffic optimization was the first application of the methods developed in the TensorCell team (and it is still the major research area of our group). In fact, the earlier research on traffic optimization conducted by one of our members (Paweł Gora) was one of the reason why the TensorCell group was established! 

Everything started in 2008 with an idea to use metaheuristics (e.g., genetic algorithms) and traffic simulations using the Traffic Simulation Framework software [1] to find heuristically optimal settings of traffic signals. This approach assumes that we have a detailed information about the current traffic conditions (which can be acquired from detectors such as inductive loops, cameras, or (preferrably) vehicle-to-infrastructure communication) which can be an input to traffic simulation model able to estimate the traffic quality (e.g., the total time of waiting on red signals) for different traffic signal settings. Thanks to that, it is possible to assess the quality of various traffic signal settings and find the good one. However, the number of settings is astronomical (e.g., in case of Warsaw it is more than 120800, much more than the number of possible games in Go (~10700) and more than the number of atoms in the visible Universe (~1080)), so we can't evaluate all possible settings. Can we find the best setting without it? Well, it was proven the that Traffic Signal Setting problem is NP-hard even for very simple mathematical traffic models [2], so most probably, we will not be able to find the best possible settings in a reasonable time (in addition, it doesn't make sense to look for optimality - the best solution according to the mathematical model doesn't have to be optimal in case of real traffic - the model is just a simplification of the real world). In such cases, the good approach is to use metaheuristics (e.g., genetic algorithms) which are able to search through the large space of possible signal settings and find heuristically optimal solutions [3]. 

This approach gives very good results (which were summarized in a Master thesis [4] and an article published at ISMIS conference [5]) but one of the issues is a large time of computations (e.g., simulating 10 minutes of traffic in the entire Warsaw takes many seconds, while metaheuristics require running hundreds or thousands of such simulations). One can think about distributing computations on many machines and we also tried it [6], but it is not well scalable and has its limitations. The new idea which we came up with in 2015 is to build so called metamodels (or surrogate models) able to give approximate outcomes of computations. However, simpler traffic models don't give sufficient accuracy of approximation [6], so we decided to employ machine learning. We train neural networks and LightGBM models to approximate outcomes (e.g., times of waiting on a red signal) of traffic simulations for various traffic signal settings (mostly offsets, i.e., times from the beginning of simulation to the first switch from the red signal phase to the green signal phase) based on the outcomes of traffic simulator.

It turns out that neural networks and LightGBM are able to approximate traffic simulation outcomes with a very good accuracy (the mean average percentage error at the level of 1-2% on a test set) and return results a few orders of magnitude faster than traffic simulation, which gives opportunity to evaluate much larger number of traffic signal settings and test many optimization algorithms. The results and their new extensions were summarized in our papers published at NIPS 2016 [7] and later at MT-ITS 2017 [8], NeurIPS 2018 [9] and TFML 2019 [10].

We are now extending these methods  further and testing even more optimization algorithms: genetic algorithms, memetic algorithms, particle swarm optimization, gradient descent, CMA-ES, simulated annealing and tabu search [11]. We are now also designing new architectures of neural networks which may give even better results for this particular use case. For example, we are testing graph neural networks in which the topology of connections between neurons is built based on a topology of the road network with traffic signals [12].

Another interesting approach we are testing is based on reinforcement learning: the goal is to learn the optimal policy of traffic signal setting adaptation to a given traffic conditions. We are also developing the TensorTraffic Online project - its goal is to visualize our methods in a browser and let the users play with traffic signal control strategies!

Why our approach may be better than existing traffic management systems?

The existing systems have several drawbacks:

Bibliography

[1] Gora P., "Traffic Simulation Framework - a Cellular Automaton based tool for simulating and investigating real city traffic", in "Recent Advances in Intelligent Information Systems", 2009, pp. 641-653, ISBN: 978-83-60434-59-8. 

[2] Yang, C.B., Yeh, Y.J.: The model and properties of the traffic light problem. In: Proc. of International Conference on Algorithms, Kaohsiung, Taiwan, pp. 19–26 (December 1996).

[3] Luke S., "Essentials of Metaheuristics", 2013.

[4] Gora P., "Adaptive planning of vehicular traffic", M.Sc. thesis in Computer Science, 2010.

[5] Gora P., "A genetic algorithm approach to optimization of vehicular trafficc in cities by means of configuring traffic lights", in "Emergent Intelligent Technologies in the Industry", 2011, pp. 1-10.

[6] Gora P., Pardel P., "Application of genetic algorithms and high-performance computing to the Traffic Signal Setting problem"", in "24th International Workshop, CS&P 2015, Vol. 1", Rzeszów, 2015, pp. 146-157.

[7] Gora P., Kurach K. "Approximating Traffic Simulation using Neural Networks and its Application in Traffic Optimization", in "NIPS 2016 Workshop on Nonconvex Optimization for Machine Learning: Theory and Practice."

[8] Gora P., Bardoński M., "Training neural networks to approximate traffic simulation outcomes", in "2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), IEEE", pp. 889–894. 

[9] Gora P., Możejko M., Brzeski M., Klemenko A., Kochański A., "Investigating performance of neural networks and gradient boosting models approximating microscopic traffic simulations in traffic optimization tasks", presented at NeurIPS 2018 Workshop "Machine Learning for Intelligent Transportation Systems". 

[10] Możejko M., Brzeski M., Mądry Ł., Skowronek Ł., Gora P., "Traffic Signal Settings Optimization Using Gradient Descent", in "Schedae Informaticae", Vol. 27, 2018, pp. 19–30.

[11] Gora P. et al., "Solving Traffic Signal Setting Problem Using Machine Learning", 2019 6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), Cracow, Poland, 2019, pp. 1-10.

[12] Skowronek Ł., Gora P., Możejko M., Klemenko A., "Graph-based Sparse Neural Networks for Traffic Signal Optimization", Proceedings of the 29th International Workshop on Concurrency, Specification and Programming (CS&P 2021), 2021.