Gridlock due to tiny roads

[belt-drive]

Not sure if this is a feature or a bug, but reporting here because the behavior seems unexpected, or at least undesired. Working in the sandbox with the South Seattle map.

Roads with medians, like 1st Ave S in downtown Seattle, can cause permanent backups. These are roads that are treated as two separate one-way streets that run parallel. These backups seem to result from the very closely-spaced intersections that occur with cross streets where there is only space for one car in the space between the intersections with the respective sides of the street.

Seems like there are two primary reasons (possibly more) why these persistent, unresolvable backups occur at these locations:

1. If the signals on the two sides of the road, i.e. the two one-way streets, are out of sync, there is capacity for only one car to move through the intersection per light cycle because of the one-car holding zone in the median intersection. Oh well, poor light timing is maybe one of the challenges of the game that the player needs to fix, so not necessarily a bug here. One car per cycle is better than no cars per cycle.
2. This seems to be a bigger issue, though: a long car can stick out from the median holding area to block a tiny portion of the main intersection, effectively shutting down that intersection. If one car sticks out from the median holding area after every light cycle, the intersection is effectively closed permanently. Seems like cars will never try to pass through an intersection if any portion of another car from a different light cycle is still in the intersection.

See attached screenshot. There is a car turning left from South Main St to go north on 1st Ave S. This car is in the small "holding area" in the median of 1st Ave S. The tail of this car sticks out a bit into the intersection of 1st Ave S heading south and S Main St. The two cars that are trying to go south on 1st Ave S through this intersection have been waiting more than an hour because there is a always a small section of a car sticking out into the intersection at the end of every light cycle, preventing them from going forwards. They're stuck forever, and that permanent backup eventually ripples out through the rest of the street grid.

So, maybe this is a feature and not a bug, but it's annoying. Likely also a known issue. A few possible ways to fix it:

1. From the dev standpoint, allow cars to go around partial blockages to traverse a partially-blocked intersection. That sounds like a complex can of worms, though. If you can solve that problem, you're most of the way to being the first AV billionaire.
2. Somehow enforce that every interstitial intersection space can accommodate at least one car. Not very elegant or in keeping with the idea of a realistic streetscape. Plus, big cars causing problems when trying to use small streets is a real issue on streets like 1st Ave S in Seattle, though I think most of the median spaces on 1st Ave S and other streets with similar configurations (Beacon Ave S, for example) can accommodate at least one car.
3. As a user, close all those tiny problematic between-intersection spaces. Close for construction or turn them into the world's most useless bike or bus lanes; anything to keep cars from trying to use them.

[dabreegster]

It's a bug, perhaps the most infamous one: gridlock. I've been fighting in some form since ~2011, when I was a lowly undergrad working on a different simulator. :)

It has many causes, but you've hit upon two of the big ones. For the traffic signals, there's an attempt at dealing with this, but it's incomplete. If you press ctrl+S in game to activate dev mode, then click one of these pairs of signals, there's a button to explore uber-turns. I'm trying to make the traffic signal editor understand movements across pairs of intersection that people think of as logically one intersection.

Long cars getting stuck in short roads has a bunch of causes. I have some hacks that I've hardcoded for some intersections that sort of help; they may help with Main and 1st, but may not.

Anyway, this is a hard problem always on my radar. I'm working on a comprehensive presentation of the modelling assumptions in A/B Street, which will definitely cover this topic. I'll link that here when it's ready.

[dabreegster]

I made some progress in #8 on synchronizing pairs of traffic lights. It'll be in the build tomorrow (along with a few other fixes I've been slow at getting in)

[belt-drive]

Not sure if this is the right place for this convo, but I'm curious about the gridlock that came up here (I don't see any way to comment on the "project" page for gridlock). Is there anything that I can do to contribute to this issue? I'm doing a lot of spot fixes to try to fight gridlock on the South Seattle map, but I still can't get it to run past about 8 a.m. without a meltdown. Some spot fixes are easy, like around Boeing Access Rd and SR 99 ramps, but Yesler and Jackson remain the dynamic duo of throughput destruction. Downtown is where all the gridlock issues seem to come together and I can't find an easy spot-fix solution.

[dabreegster]

Issues are the easiest place to track conversation, and I don't think Github has a way to change permissions for projects. You can definitely help!

1. If there's a traffic light that's particularly dumb and you fix it, or you know the real timings, then enable dev mode (ctrl+S), hit export in the signal editor, and send the files in traffic_signal_data. Or if you have a bunch in the whole map, send the edits .json. I can add these as hand-mapped defaults.

2. If the number or type of lanes in a certain area is wrong, either make a note of it in an issue or fix it in OpenStreetMap directly. I'd like to make more tools to fix OSM problems directly, but for now, you'd have to use the existing editors. (The exception to "wrong lanes" is sidewalks -- I'm not using OSM for these at all yet.)

If you're interested in the south seattle map but the stuff near downtown is causing problems, we could cheat and adjust the boundary to start at King or Dearborn or so.

Also, I haven't looked at the Boeing Access Rd area closely before; this is horrendous. I'll see if there's some obvious bugs here. At least one is that I'm sticking sidewalks on roads that OSM labels as "trunk".

[belt-drive]

Excellent, thanks for the suggestions. I'll export some simple signal timing issues that cause big problems. I'll also work on fixing some lane issues in OpenStreetMap. I know there are some problems on MLK where OSM indicates one travel lane where there are actually two, and I'm sure there are others. Ultimately, I'd like to be able to work with the entire Seattle map to do some more meaningful simulation work, so while changing the map boundary might be helpful in the short term, I'm willing to put up with the annoyance for the sake of working towards solving the underlying gridlock issue. Thanks again.

…

On Sun, Jul 5, 2020 at 7:29 PM Dustin Carlino ***@***.***> wrote: Issues are the easiest place to track conversation, and I don't think Github has a way to change permissions for projects. You can definitely help! 1. If there's a traffic light that's particularly dumb and you fix it, or you know the real timings, then enable dev mode (*ctrl+S*), hit export in the signal editor, and send the files in traffic_signal_data. Or if you have a bunch in the whole map, send the edits .json. I can add these as hand-mapped defaults <https://github.com/dabreegster/seattle_traffic_signals>. 2. If the number of type of lanes in a certain area is wrong, either make a note of it in an issue or fix it in OpenStreetMap directly. I'd like to make more tools to fix OSM problems directly, but for now, you'd have to use the existing editors <https://learnosm.org/en/>. (The exception to "wrong lanes" is sidewalks -- I'm not using OSM for these at all yet.) If you're interested in the south seattle map but the stuff near downtown is causing problems, we could cheat and adjust the boundary to start at King or Dearborn or so. Also, I haven't looked at the Boeing Access Rd area closely before; this is horrendous. I'll see if there's some obvious bugs here. At least one is that I'm sticking sidewalks on roads that OSM labels as "trunk". — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#114 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AQEDTNAVZQUK62K37AGREB3R2EZKBANCNFSM4OOP3T5Q> .

[dabreegster]

Next steps here, all confusingly co-dependent:

• Once a vehicle starts an uber-turn, prevent others from starting conflicting turns on nearby intersections. Until groups of traffic signals are configured as one, this is necessary to prevent somebody from making it halfway through a sequence then getting blocked.
• Disable the "don't block the box" policy during uber-turns. Or maybe make it just look at the final target queue, not the little intermediate steps.
• Group both stop sign and traffic signal intersections when looking for uber-turns. Even a single traffic signal surrounded by tiny roads with stop signs is causing problems. The hardcoded list of overrides can be generalized.
• Related: it's always fine to block the box at degenerate intersections

[dabreegster]

Just organizing some thoughts.

Causes/problems:

• short roads, weird geometry
• unrealistic traffic patterns caused by everyone trying to park in one big garage (downtown) or take some tiny road (the UW soundcast issue)
• bad individual signals
• bad groups of signals long a corridor

Attempted solutions:

• synchronizing pairs of signals
• uber-turns (for synchronizing larger groups of signals or for locking turn sequences)
• cycle detector
• block-the-box protection (and the manual list of overrides to allow it)
• hacks to allow conflicting turns at really broken intersections
• upstreaming turn restrictions into OSM to prevent invalid U-turns and other crazy movements
• upstreaming lane count fixes into OSM to improve geometry
• manually timing signals

[dabreegster]

I went back to spot-fixing problems. Using the "modify traffic patterns" tool, cancelling 90% of all trips makes the downtown map complete. Took it down to 80, it was easier to spot specific problems. I made a flurry of OSM fixes, for example Lenora and Westlake went from

to

Still need to make the code more generally robust, but I had somehow forgot that it's much easier to make progress by tackling individual issues.

[matkoniecz]

One more ingredient: false positive in collision detection. Selected car should be able to enter the crossing and help in unblocking it.

[dabreegster]

Another problem came up in the SLU map due to one of these, prompting discussion again about merging the short "road" between these two "intersections" into one.

I haven't dug through the history to find the commit deleting it, but there used to be a merge_short_road method at the RawMap layer to try to deal with problems like this. It's been a while, but some of the complications from doing this were:

• intersection geometry was sometimes strange
• the traffic signal heuristics sometimes performed much worse on merged intersections
• deciding which roads/intersections to merge was brittle -- only do it between traffic signals? guarantee length is at least MAX_BUS_LENGTH + FOLLOWING_DISTANCE so nobody can partly get stuck in intersections?
• preserving turn restrictions after deleting inner roads was complicated

I think it's time to attempt merging short roads again, though, after doing a bit of archaeology and recalling why the last try failed.

One thought is that #255 could be a way to manually annotate in OSM which "roads" are really just parts of an intersection and would be good candidates for merging.

[dabreegster]

Starting to look into this, one issue at a time. First, how do we calculate the intersection geometry? One idea I haven't tried before is to just generate all the polygons as usual for each individual intersection, then take the convex hull of all of them. Some results:





Decent in some cases, covers way too much area in others. This is a problem especially when the merged shape cuts across an incoming road at a non-90 degree angle.

[dabreegster]

Concave hull helps a bit in some cases, hurts in others.

[dabreegster]

Trying this out again at the RawMap layer.

Brief history to record: Back in ~May, there was a way to merge short roads at the RawMap layer. Doing the work on a simple representation was nice, because we didn't have to fix up things like buildings that got snapped to a short merged road. But all of my attempts to automatically pick which roads to merge had problems, so I expressed the transformation manually as part of the old MapFixes system. That was basically a way to apply manual "edits" to the OSM input, the idea being that complicated areas could just be manually redrawn in a way that was easier for abst to deal with. But that idea proved unmaintainable -- the edits referenced OSM IDs, so any benign upstream edit would blow up the edits. Making the edits survive upstream changes would be very hard.

So the new idea is:

• Try merging short roads at the RawMap layer again
• Manually tag the short roads in OSM upstream, using the tagging scheme described in Consider tagging "intersection" ways in OSM #255. It's a reasonable thing to put in OSM.

Getting the merge to actually work will require improvements to things like the intersection geometry algorithm and signal heuristics, but all of that is probably doable.

[dabreegster]

From a few test cases, fixing the intersection geometry wasn't hard at all. :D Testing a fix more rigorously, then blazing forward. No short roads shall survive into 2021.

[dabreegster]

Progress, but also hitting more complications. Preserving turn restrictions is not hard in some of the common cases. But we also have to preserve reachable roads from one-ways:

Otherwise we'll wind up with U-turns, depending on the (arbitrary/unpredictable) order that these junction ways get merged:

[dabreegster]

Not sure how to properly handle the one-way problem. For now, the simple workaround is to detect U-turns that get generated in merged intersections, and just filter them out. Sometimes they're legal, but usually not.

Other thoughts on more sanely preserving turn restrictions:

1. Just keep handling case-by-case
2. Convert a chunk of the RawMap into the final form, remember all of the possible turns there, do the merges at the RawMap layer, then filter the final form based on the unmerged version's turns.
3. Similar, but come up with a more abstract RawRoad->RawRoad connection set at the raw layer only, use to filter

And for handling one-ways: can we turn the constraint into a bunch of turn restrictions? Sometimes, yes, but in the example above, not safely, because there might be other paths to get between the off- and on-ramp.

[dabreegster]

@matkoniecz, just an update in case you wanted to try out the new merging. Right now, any ways with junction=intersection will get merged. This often requires splitting a way to isolate the section that belongs in the intersection; if you leave the tag on a long way, likely the A/B Street import will botch it in some exciting way. The merging process tries to preserve information about turn restrictions and one-ways, but there are lots of cases, so let me know if you see some result that looks wrong.

You can just run the importer on a .osm to get the new behavior. If you want a convenient way to experiment locally, you could manually edit your .osm file. But another method is:

1. Open the UI, go edit a lane
2. Press m to edit multiple lanes
3. Select all short roads you want to try merging (it also works with just one)
4. Click "export list of roads" to create osm_ways.json
5. Move that file to the root directory
6. Change https://github.com/dabreegster/abstreet/blob/bc3c3dfd6ce925492ebf2822426f85c20c262bc0/convert_osm/src/extract.rs#L32 to if true
7. Run ./import.sh --raw --map --city=krakow (with osm_ways.json in the current directory)
   This adds a fixed key/value to the list of way IDs, so you can "test" the change before upstreaming in OSM.

I don't think the definition in #436 should be determined by what A/B Street does, of course -- that's like tagging for a particular renderer or router. So there may be cases where intersection=junction makes sense, but abst shouldn't merge, and vice versa. I'm still planning to try heuristics to detect when it should happen, regardless of how things are tagged.