Wolfram Student Podcast Episode 3: Traffic Light Algorithms to Optimize Traffic Flow

Hello, everyone, and welcome to the third episode of the Wolfram Student Podcast. I'm Sam.

And I'm Roshank.

And we're your hosts.

This is the Wolfram Student Podcast, where every fortnight we dive into a new innovative project done by high schoolers using wood from language.

For our third episode, let's welcome Henry Gustafsson, who will be discussing his project on creating traffic light algorithms to optimize traffic flow. Hello, Henry.

Hello. Thanks for having me.

Of course. Can you tell us a little bit about yourself to start off?

Yeah. My name is Henry. I'm a junior in high school, and I'm really interested in math and computer science and physics and the Wolfram language in particular. Great.

And what Wolfram experience do you have? Have you attended any camp in the past or one of the other programs?

Yeah, so the first. The first camp that I did was in the summer of 2021. And then I. The year. During the school year after that, I did well, which is like an opportunity to do group projects. And then I just did the summer camp in 2022 this year as well.

So you've worked with Wolfram for a long time. Cool. What's your favorite Wolfram function?

I mean, my favorite function is probably a pretty popular one, but it has to be cellular automata. I used it in my project, as you'll see.

Oh, well, that's interesting. Traffic light algorithms using cellular automata. That's.

I can also share a little more obscure one. I think it's a resource function called. I think it's called probabilistic cellular automaton, and it allows for, like, as the name implies, a stochastic telluratomaton, where instead of having the same rule every time, you have a certain probability of doing each rule.

Interesting.

Yeah, it sounds pretty cool. I guess, getting into your project. Why don't you share with us?

Yeah. So the goal of my project was optimizing traffic light timing in simulated cities. So given some city with, you know, a grade of streets and a certain density of cars and some traffic lights, trying to come up with an algorithm to control the traffic lights so that cars could move through it as quickly as possible.

Pretty cool. So I guess go ahead and explain.

Yeah. So the first step of what I did was to try to, like, create a model of a city using a cellular automaton. Cellular automaton, like, most basically are a grid of cells, and each cell can be in any number of states. So a lot of times it'll just be two states. Like, just. It'll be black or white. And then every generation, the cells will all follow some very simple rule where it looks at the surrounding cells and then changes to a new state based on that. So, for example, like the most simple cellular automata are elementary cellular automata where it's only one dimensional, like one single row of cells and every cell is either black or white. And. And the rule only depends on like the cell itself and the two cells on either side of it. Which means there's only 256 possible rules. And one of those rules, Rule 184, happens to be really good at modeling what traffic does. So here's an animation of what it looks like. But what it's basically doing is every black cell represents a car, and every generation, the car will only move forward if it has white space in front of it. So which is a pretty good representation of what it looks like when you have a single lane of cars moving forward.

Yeah, this, this is actually yearly accurate, you know, so I'm wondering, how did you land upon this specific cellular top down? Did you, you know, did you try a lot of those and see which one worked best or was there some other process?

Yeah, so, so Rule 184 was like the first thing I came up with just researching, like how can you model traffic flow? It's a pretty common thing that people have done in other research. But what I actually wanted to do is I came up with a sort of two dimensional version of it where it does a similar idea, but instead of just having a single lane, it's a two dimensional cellular automaton, which means it's a two dimensional grid of cells and it uses like a three by three neighborhood where it looks at the cells all around it. So basically the way it works is the cells, every cell, like every car is moving either horizontally or vertically, and that move horizontally move first they'll follow the same rules. Basically they move forward if they can, and then the, in the same generation, the cars moving vertically move down if they can move. So it's basically a two dimensional generalization.

I like how you can see certain dense spots that like slowly move across the board as traffic flows.

Which is pretty cool. Yeah, exactly. When you have like a really big animation, you can start to really see those, those patterns as cars move across.

Wow, that is very accurate to traffic these days.

Yeah, so, but since my project was really about traffic light algorithms, I also had to like build into my cellular automaton traffic lights. So. Which is actually a little bit more difficult than you might think. So I Had to come up with, like, states to represent empty, like, blocks where cars can't drive. And then I had to come up with states to represent, like, all the different configurations that a traffic light would be, like, green in one direction or red in the other direction moving through it or not. So I actually came up with not 10 total states for the cellular automaton, which makes it actually pretty complicated.

Would you mind going through each one of these states?

Yeah, sure. So the first state that any one cell in the grid could be is just empty, meaning there's no car, but it is like a place where a car could be. Then I have two states to represent a horizontally moving car. And I have another state to represent a vertically moving car. Then I have four states for traffic lights. So one is a. The first one is a green light for horizontally moving cars and a red light for vertically moving cars. The next one is just the reverse of that. And then the next two are the. Those same two, but also with a car in the intersection. Because the way cellular automata work is they only look at the surrounding cells. So you have to actually represent when there's a car, like when there is a car there moving through the intersection. And then the last state that it could be is just an empty block with. With no cars, no lights that, like a house might be there, for example. Cool.

And, yeah, you can continue moving on.

To the next part. Yeah. Okay, so I'll just play an animation of what it looks like with cars moving through the traffic lights as they randomly change. It looks pretty accurate to what a city looks like with traffic light. So then I started to think of different ways that the light could be controlled, different possible algorithms. So I came up with three, like, very simple, general ideas for an algorithm. So the first one is just randomly changing the lights all independent of each other. It's like the most, like, naive version. You're just randomly changing all the lights, and you wouldn't expect it to be very successful. The lights don't respond at all to surrounding cars or to each other. The next idea I had was a system where the lights still are, like, dependent of each other, but they do respond to nearby cars. So the most simple version of this would be just like you imagine, there's a sensor, whereas as soon as a car reaches the light, it turns green for a car in that direction. And there could also be slightly more complicated versions of it where, like, it'll only allow a car through if it has room on the other side of the light to go through, because otherwise it would be pretty pointless to turn green. And then the last, like, class of algorithms is what I called rotation. So it'll have, like, all green in one direction and then all red in another, and allows cars for some time to travel, like, east to west. And then for some period of time, cars travel, are able to travel from north to south. And there's all different ways that you could decide how long it should spend in each direction. But my first idea was just proportional to the amount of cars that are traveling in each direction. So, for example, if twice as many cars are traveling east to west, it should stay green for them twice as long as it stays green for the cars that are traveling north to south.

That makes sense. And going back to the second algorithm for a bit, I was wondering just a question that popped into my mind. If, for example, there are two cars to a traffic light, and one of them is going east to west, and the other is going north to south, then what direction would the traffic light turn to?

Yeah, so I think if both cars get to the light at the exact same time and they both have room to go through the light, it. It kind of. It's symmetrical. It doesn't really matter. In this case, it allows the ones going from, like, horizontally east to west to go through. Got it. But it's completely arbitrary.

And as your algorithms got more complex, how did you manage to balance the cars that were going east to west and north to south?

Yeah, like, for this one, where I just spend some time allowing the cars to go one way and then sometimes allowing the cars to go the other way. I'll get to it later. My first idea of what would work best would just be to have the lights on in proportion Exactly. To how many cars are. Are traveling in that direction. But as maybe this is revealing what I found out later, but that's actually not the case. There's actually a better way to determine how long to spend in each direction.

Interesting, because I thought there would be, you know, at least when you explained it to me, that was, you know, logical. Like, I was like, yeah, that makes sense. That. Yeah, I'm excited to see what you found out after that. So go ahead.

Yeah. Okay. So the next part was to try to come up with some, like, numerical metric to quantify the efficiency of these different algorithms. So I came up with two different ones. One is just the average speed of a car. So this is basically just measuring what's the total change in cells every generation. So, like, does a car, on average, the maximum that it could be, is Move a single cell every single time. That would be like perfect. Cars never have to stop. And the worst, it could possibly be a zero if cars never are able to move at all.

I'm curious about how exactly you measured this average speed.

Yeah, so I basically just this function here, car movements, it counts how many cars moved every generation. And then the frame average speed just divides how many cars moved by how many cars there are, and it averages that over all of the frames. So my other metric to sort of quantify the efficiency was, I think this is pretty cool. It's the maximum density without gridlock. So what I often noticed was happening with these cellular automata is that you could sort of have a fast traffic flow with cars not having to stop too often, but then all of a sudden you would just increase the density slightly, and it would all of a sudden create like this phase change where it all of a sudden the speed of the cars goes down drastically. So you can see that in this, this graph, the cars as the densities is like less than about 0.4. They move relatively quickly, but all of a sudden, when you increase the density to above 0.4, they move much slowly. Much more slowly. So this metric is measuring at what point does that sort of transition happen. So then the next obvious thing to do is to compare the three different algorithms. So interestingly, the different one, the. The random one, was pretty much always the worst algorithm, as you might expect, because it's not really doing anything intelligent. But the other two did depend on the amount of density that there was. So at lower densities, the quickest algorithm was the one that just immediately responded, like, with. As if there was a sensor as soon as the. Which kind of makes sense, like you don't want cars to be waiting at the intersection as soon as there's a car there, if there's not too many other cars, it would make sense to just let that car go. But at higher densities, the. The quicker option was definitely the one where it spends a longer period of time allowing cars to travel vertically and a longer period of time allowing cars to travel horizontally, which, again, makes sense that that would work better because it's more like optimizing for a more unified system where instead of just for individual cards. Does that make sense? Yeah.

Yeah, that makes a lot of sense. And would you like to maybe go back to those graphs you showed and maybe. Because I think those looked kind of interesting, and I was wondering if.

Yeah, for sure. Okay. So the way I generated these is I basically just experimentally did 100 simulations of each algorithm changing whatever, like the necessary variable to change were. So this is the first graph here. So these three graphs are for the three different algorithms. So this is the one for the random one. This is the one where the lights respond to nearby cars, and this is the one where the lights are coordinated. So as you would expect at first, for all of the algorithms, the mean speed and density are pretty directly correlated. As you increase the density, the cars move slower. But as I was talking about before, you get to this, like, transition point where all of a sudden, like, it doesn't really matter how dense it is, the cars are just in gridlock and they're going to move really slowly. Like, even adding more cars, it's still gonna, it's gonna be, it's not gonna actually make it slower because you're already basically as slow as you can get. And the difference between these different algorithms was the ability to, like, delay when that happens. So you can see that the latest it ever happens. Like, the longest slope you get where they are correlated is in the one where you coordinate all the lights, which makes sense. If you coordinate all the lights, you can handle, like, a greater density of cars before you, you get into the gridlock situation, but it's not necessarily the fastest at the lower density. So this one might have a little bit of a deeper slope at first, but when you get to higher densities, it performs work. So then next I graphed, like, the average flow versus the rate of density, which might seem similar, but what flow is measuring is just the total number of cars that, that leave the city every generation. So it's actually, it's interesting. It's, it's related to the average speed, but it also, like, is higher, higher densities as well. And maybe this is what you should really optimize for in a city. You don't just want cars to be able to go fast. You want as many cars as possible to be able to go through your city. So these are, at first they're directly correlated between flow and density. As you add more cars, more cars are making it through the city. But eventually you get to, like, a point where adding more cars doesn't actually allow more cars to travel through the city in any amount of time because you're only slowing down other cars. And it gets to a point where it, like, cancels out. And this is not too different between the three algorithms, but it's definitely true that no matter what algorithm you have, like, you're going to get to a point where you can, you can Only handle so many cars. Like, adding more cars is just going to end up slowing down everyone else. The last one is mean speed versus flow. So this is. This is comparing, like, how fast cars are going versus how many cars are making it through. So in the random case, and even in the one where the lights are all coordinated, these are pretty directly related. But in the one where you're responding to nearby, the lights are responding to, like, nearby cars, it starts off where it's much less correlated. Like, you can. You can increase the amount of cars that are going through and they can maintain a pretty quick speed, but then it quickly, like, drops off and they become correlated again. And then what I was doing here was I create. This is a little bit harder to visualize, but these are 3D plots of vertical density, horizontal density versus flow. And with the random algorithm, you can see that, like, it's pretty symmetric. So adding more cars traveling east to west versus more cars traveling north to south. Like, it doesn't really matter which direction you add the cars. It's going to slow people down regardless. And. But what's interesting is when you compare that to the. To the third algorithm where the lights are more coordinated, you can actually handle a lot more cars in one direction. And that doesn't actually decrease the flow rate very much, which makes sense. If you're in, like, a bigger city where, like, you imagine, like, everyone's moving in one direction for the most part, like, going from know where they live to downtown or whatever, then you're going to want to have an algorithm where the lights can be coordinated that you can allow those cars going in the, like, most popular direction to travel that way for the longest amount of time. So then the last part of the project, which is, I think, the most exciting, but it was definitely also the most difficult part was of these three different algorithms sort of optimizing for the best version of each one. So the way I did that was just like running them all a bunch of times at different densities of cars and then trying to use. So Wolfram language has a really great function called findminimum, which allows you to pass in any function. So this isn't really a mathematical function, but it's just a function that takes the density of cars and returns the average speed and that sort of, like, point where the transition to gridlock happened. And it tries to minimize that, those metrics of efficiency. So this is where I found some interesting results about what was best. So, for example, in this case, when the densities are both 0.1, so that's like 10% of the cell horizontally are filled and 10% of the car filled vertically were filled. The best version of the third algorithm was to spend one like unit of time allowing cars to travel vertically and then one unit of time to allowing cars to travel horizontally. Which made sense. But when I changed the density to like a 5 to 1 ratio, so like 10% of the cells horizontally filled and 50% of the cells vertically filled, the ratio of the amount of time to space then allowing cars to travel in each direction was actually 2 to 7, not 1 to 5. So there's a pretty complicated relationship between the density in each direction and the amount of time that you should spend in each direction.

So just to be clear, I suppose so you're saying if there's a higher density going east to west compared to north to south, then you would want to spend more time with cars going east to west. But what would happen if these like, were exactly equal? Would that just be the same amount of time or is there a different way to handle that?

Yeah, so when it's exactly equal that, that's this year, like 10% of the cars in, in each direction build it is what you would expect. You should spend an equal amount of time allowing cars to travel east to west as you do cars traveling north to south. But what was more interesting to me was when there's like an unequal ratio, the ratio that you should spend allow travel in each direction is not the same as the actual density in each direction. And it's a much more complicated relationship.

Would you want to play the animation for us? I feel like that can be a great little bit on cell griddle works.

Yeah, sure. So this is the animation for what it looks like at the. The 10% and 10% density. You can see what the lights do is they just switch every generation. And that allows for the best times to clear the board, the best average speed of the car. Yeah. And then this is an animation of what it looks like at the more complicated like 10% versus 50% density. And you can see that the cars have to spend a different amount of time in each direction. And this is what it looks like to clear the board as quick as possible.

Cool. And I'm curious what would happen if you added more traffic lights as opposed to more cars?

Yeah, so that would be a really great extension of my project. I didn't really explore that very much, but yeah. So I think that's something that would be super interesting. And you could totally model that with cellular automaton. There's all sorts of extensions that you could do. So like you could have different types of intersections as well. Like, you know, in some cities you'll see like all of these different arrows for the different having protected turn for different lane and things like that. You could have like roundabout, you could, you could allow right turns on red light. There's all sorts of different intersections that might optimize things. But I was just focusing on like if you already have a city built with lights in certain places, like what's the best algorithm in that case?

Yeah, that makes sense. And wow, this, this was pre project. I'm surprised you were able to model so much and get so many results out of what seems like a pretty simple simulation, but is, you know, on the surface, but it turns out to be incredibly hard to accurately model. So I'm interested in, you know, you had so much complex code here. Each of those algorithms looked like it was pretty complex to implement. And especially as someone who has worked a lot with Ultron, but not worked too much with cylinder automata, you know, it looks like it, it needed a lot of work to get right. So I was wondering, given all those parts, which one did you think was the most difficult to cause?

Yeah, I mean the most difficult part for me was definitely the part of the end where I was kind of trying to find like the most optimal version of each algorithm. What I wanted to do originally was do like a more advanced like reinforcement learning where like you like sort of respond to like, you test it at one point and then you change the variable slightly and you see like which direction is best to travel and you, you try to. I was going to try to implement some like more complicated to try to optimize each algorithm, but Wolfram does have this like built in find minimum function which might not be perfect because it's not really supposed to be used in this in this case, but it worked pretty well. So that's kind of what I ended up doing.

Cool. So overall your project has seemed really interesting. But what do you want to try next? I guess other than expanding on traffic lights. Are there other projects you're interested in doing with the Wolfram language?

Yeah, so I would be interested in all of these extensions that you could do to the project, but I would also be interested in like related projects as well because the Wolfram language is really great at like using things like cellular automata to model the real world systems. So something I would be interested in doing is to like find a different cellular automaton that models some other real Life system? I don't know exactly, but there's all sorts of systems like, you know, in chemistry and physics, in biology, like, you know, even like higher level like that feel even more applicable to the real world. So I think it would be really cool to like, find a different cellular automaton that can model something like that and just explore the results that I can get from there.

Yeah, that would be pretty cool. And as someone who's quite interested in biological and biology and stuff, I think, you know, this is sort of an off the cuff thought, but this kind of reminds me of, you know, potentially modeling the movement of honeybees in a hive, for example, because those traffic lights do kind of remind me of flowers and then those yellow arrows are similar to bees, so. Yeah, but you, you're definitely right about the potential of cellular automata and how they can be used to model so many complex phenomena.

Yeah, the honeybees, I'm sure that's something that you could model with automaton. That seems like something that seems like a behavior that could definitely be modeled with. Yeah. Yeah.

Work to do for our listeners out there. Am I right?

Yeah.

Cool. So thank you so much, Henry, for coming on for this episode and we wish you luck on your future endeavors.

Yeah, thank you so much for having me.

Thank you and good luck. Thanks for listening to this episode of the Wolfram Student Podcast. We hope you learned something new and took away insights from today's discussion. If you want to be featured in a future episode, fill out the form@tinyurl.com WSP interest form and be sure to.

Tune in in two weeks time when we discuss with Anthony Lee about his project regarding whether planes near airports tend to fly over green space. Once again, thanks for listening.