Advanced Traffic Light Control

[pschichtel]

During my university time @jonasdann and I worked on optimization of traffic light control systems and I think it would be nice if there was a way to test the system we developed in abstreet. So I was wondering if there are any plans to have some kind of advanced traffic light control mechanism based on sensors on lanes and some control component. Our approach would dynamically calculate the phases and their duration for a given intersection and tries to estimate incoming traffic per lane based on surrounding intersections to inform the phase calculations. I had a look at the game and it seems there is neither sensors nor a dynamic way to control traffic lights. I could only find the manual phase configuration.

I assume there are two big challenges here:

1. Getting data for existing lane sensors (with various types possibly covering several lanes at once) and some kind of UI to add a sensor to a lane
2. Having a way to specify an automatic traffic light controller. I could imagine something like "convert to automatic traffic light" next to "convert to traffic signal" which could link to an external system of some kind for control

[dabreegster]

Actuated controllers would be amazing! Poor signal heuristics are currently preventing most of the larger maps from being simulated without unrealistic gridlock, so if we could come up with a solution here, maybe we could initially seed those maps with a configuration that works. I haven't explored the idea in much depth, but some initial thoughts/pointers:

• Historic counts per hour at the granularity of entire roads (all lanes, both directions) is currently tracked at https://github.com/dabreegster/abstreet/blob/626636ece77ebc8c77fdc42e5a19b1b2eca80fc1/sim/src/analytics.rs#L13

• Getting the current count on an incoming lane is easy; it'd be the length of https://github.com/dabreegster/abstreet/blob/626636ece77ebc8c77fdc42e5a19b1b2eca80fc1/sim/src/mechanics/queue.rs#L11, or for pedestrians, the number of pedestrians in https://github.com/dabreegster/abstreet/blob/626636ece77ebc8c77fdc42e5a19b1b2eca80fc1/sim/src/mechanics/intersection.rs#L37.

• For the purposes of the simulation, do the sensors need to be in a particular place along the road, or could they just magically count everything? If placement isn't key, then the first cut of a UI could literally just be a button in https://github.com/dabreegster/abstreet/blob/master/game/src/edit/traffic_signals.rs.

• How often does the control component need to run? A/B Street uses a discrete event model, which makes some things a little tricky. At worst, we can fallback to mimicking 0.1 second (or whatever) timesteps by scheduling events that far in the future, but it wrecks performance. But hopefully it'd be reasonable to decide a phase ought to be at least X seconds, and not need to recompute anything until then.

• The list of phases lives currently in the map model layer at https://github.com/dabreegster/abstreet/blob/626636ece77ebc8c77fdc42e5a19b1b2eca80fc1/map_model/src/traffic_signals.rs#L13, and generally the map is immutable once built. Player edits are a bit nontrivial to apply. But I think the map model phases are only used for rendering, editing, and in sim/src/mechanics/intersection. So as a first step, we could leave the map model layer alone, and just have dynamic phasing in the sim layer. I can work out a clean way to update the map model later.

• Is there an easy way to initially come up with groups of non-conflicting protected movements and possibly conflicting permitted movements? That's what all of the heuristics in https://github.com/dabreegster/abstreet/blob/master/map_model/src/make/traffic_signals.rs try to do now. They fail for many intersections, and that's causing lots of gridlock currently. Do the algorithms you have in mind need this as input, or do they figure out the grouping automatically?

[pschichtel]

For the purposes of the simulation, do the sensors need to be in a particular place along the road, or could they just magically count everything? If placement isn't key, then the first cut of a UI could literally just be a button in https://github.com/dabreegster/abstreet/blob/master/game/src/edit/traffic_signals.rs.

It would be perfectly fine to start of with "magic sensors" everywhere, but one of the goals of our approach was to helper with incomplete sensor coverage without adding more sensors, driving down deployment cost. So in a perfect simulation, I could place like coils on lanes and cameras and stuff, but magic sensors everywhere would still be a good start for sure!

How often does the control component need to run? A/B Street uses a discrete event model, which makes some things a little tricky. At worst, we can fallback to mimicking 0.1 second (or whatever) timesteps by scheduling events that far in the future, but it wrecks performance. But hopefully it'd be reasonable to decide a phase ought to be at least X seconds, and not need to recompute anything until then.

yes, we do have a minimum phase duration in our approach, at least a couple of seconds. possible phases are calculated upfront for all intersections, phase switching is done every n seconds to the phase with the most waiting vehicles with the most combined waiting time (which might be the same phase again)

Is there an easy way to initially come up with groups of non-conflicting protected movements and possibly conflicting permitted movements? That's what all of the heuristics in https://github.com/dabreegster/abstreet/blob/master/map_model/src/make/traffic_signals.rs try to do now. They fail for many intersections, and that's causing lots of gridlock currently. Do the algorithms you have in mind need this as input, or do they figure out the grouping automatically?

For the research I calculated all possible constellations of green lights for a given intersection using roughly this algorithm:

1. calculate power set of all signals and their attached lanes (matsim has a signal per lane) (all possible groups)
2. remove all groups that either have intersecting lanes or lanes that merge within a certain distance (all "non-conflicting" groups)
3. remove all groups that are a subset of another group (largest "non-conflicting" groups)

(see impl)

These groups obviously overlap, so there might be phase changes, which could leave certain lights unchanged. This ignores possible conflicting movements, which could be beneficial to throughput.

I don't think you can realistically come up with a perfect set of heuristics, because what can be considered safe depends on so many things in the real world. Movements that are safe in one location might be a disaster at the next one. At some point you'll need a manual way to correct the heuristics, maybe like a list of constraints in the form of "if light A is green, light B may never be green" or "if light A is green, light B can be green too", that users can configure in the intersection properties.

[dabreegster]

I started attempting a brute-force grouping of non-conflicting movements here, but your implementation is much cleaner! I'll dig in later. It's nice that the problem of grouping movements into phases is orthogonal to the adaptive timing part.

It sounds like the phase switching every n seconds will work fine with the discrete event model. Is there anything I can do to unblock you from starting on the approach of just changing the sim layer? I'll work on changing map_model and game to surface dynamic phases properly in the UI. And I can also mock up the UI for placing sensors. How should a single coil or camera be specified? As a line across a single lane?

Oh yeah, and the lane-changing model might be confusing or cause problems. TurnGroup is the abstraction that traffic signals see, so you can hopefully ignore it.

[pschichtel]

Is there anything I can do to unblock you from starting on the approach of just changing the sim layer?

Well... can you cover for me in my full time job? :laughing: I'm following this project for quite a while, because I'm still very interested in the whole topic of traffic flow optimization (it's a mess in many german cities too, that inspired the research back then), but little time to actually work on something. Yesterday I finally took the time to play around with it and write up this issue. So don't feel the need for immediate action. I'll have a longer free period later this year (september - october), that would probably be a good time frame for me to dive into this. So if some degree of infrastructure is done by then, that would be awesome, but I'll look into it either way.

How should a single coil or camera be specified? As a line across a single lane?

coils as a line marking the point of measurement would probably be a good enough estimate for most things. If we'd want to go fancy, coils could have a size to allow detecting different kinds of vehicles, but most of that can also be approximated by multiple coils and neither is really relevant for signal control. For cameras a 2d-view-cone would be nice, but not sure how that would fit in the model. So the camera would be a point, a direction and a viewing angle. Interesting would also be the linking between intersections and sensors. Usually one sensor can only be measured by one intersection.

We also played with the idea of inter-intersection-communication, so that intersections could "gossip" to neighboring intersection to signal, e.g. backpressure situations, which would eventually propagate through an entire area. The goal was to have green waves automatically emerge from traffic changes (e.g. large sport events). Our matsim customization already contains the concept of an intersection network, but time ran out before we could actually invest time into experimenting with that idea.

[dabreegster]

Great, I can definitely have more infrastructure in place by autumn. I just did the first step of handling variable timing in general, with a really unrealistic policy (that I realize is probably misnamed -- I keep mixing up "adaptive" and "actuated"). Smarter movement grouping is probably my next priority for signals.