Dynamically change lanes if alternative lane is on the same road and available

[matkoniecz]

Everyone wants to use right lane, even ones changing lane after crossing to middle one!

Scene from Kraków map, unmodified anything, robot proletariat traffic model.

Drivers in a real-life Kraków could be better, but they are not so bad :)

[matkoniecz]

In extreme cases it is one of reasons for deadlocks

[dabreegster]

Attempting to reproduce this kind of problem in a smaller setting, to make it easier to iterate on a fix and prevent regressions. You can reproduce this by editing tests/src/main.rs, going to test_lane_changing, doing map.save(); scenario.save();, then cargo run --bin game -- --dev data/system/oneshot/scenarios/lane_selection/lane_changing.bin. As you can tell, the lane selection actually looks half-reasonable in the test case, except for everyone insisting on using the rightmost lane to vanish at the border. Any ideas how to force a map and set of trips to reproduce the weird choices? Maybe that small road just before the traffic signal is important, because everybody waits to not block the box, but settles into their lane choice too early?

[matkoniecz]

Maybe that small road just before the traffic signal is important

I think so. Looking at https://user-images.githubusercontent.com/899988/98115670-78345780-1ea7-11eb-9cde-a3ac15a059ca.gif again: note that next vehicle enters only after both first crossing is empty AND small road is empty.

If car would be able to enter center/left lane then it would not wait until small road is completely empty, right? It should result in doubling (maybe even trippling) capacity.

Not sure whatever it would also fix problem with passing crossing one by one (is it possible to have multiple vehicles at crossing at the same time if all are going without conflict between them)

[matkoniecz]

editing tests/src/main.rs, going to test_lane_changing doing map.save(); scenario.save();

What

doing map.save(); scenario.save();

means here?

[dabreegster]

To try out the synthetic map and scenario used in the test:

1. Change https://github.com/dabreegster/abstreet/blob/7854823c28a2a7728eb1d7d3dc60607a76f772e6/tests/src/main.rs#L216 to true
2. cargo run --bin tests
3. You can stop the test process almost immediately after it starts; the lane-changing test code gets run first, and the other tests take a few minutes
4. You should then be able to run it: cargo run --bin game -- --dev data/system/oneshot/scenarios/lane_selection/lane_changing.bin

If car would be able to enter center/left lane then it would not wait until small road is completely empty, right? It should result in doubling (maybe even trippling) capacity.

Correct. The main issue here is really bad choice of lane. The secondary issue is the rules for not blocking the intersection. I think I'll try allowing blocking the intersection for these "degenerate" cases where there's just a crosswalk. Pedestrians may suffer, but this is a little closer to reality. And in most cases, there's probably not even a crosswalk there anyway.

My experience hand-crafting the synthetic map and trying to specify a traffic pattern that approximates this setup was tedious, and the result still doesn't match. I wonder if there's something more direct we could do. Maybe a way to specify a small test area from an existing map, record the exact timing of vehicles passing through there, and replay it.

[matkoniecz]

Maybe a way to specify a small test area from an existing map, record the exact timing of vehicles passing through there, and replay it.

If that is possible without spending an extremely long time on that - it would be an ideal solution. Not sure is there some sane way to record blocked outflow (what is some cases may be important, but not here so it is not some blocker)

[dabreegster]

Alright, after a few false starts, I finally have a recorded scenario that reproduces lots of silly behavior here. I've yet to cleanly make this a test case that can last forever and survive binary map format changes, but at least I can iterate on the LC behavior now.

[matkoniecz]

Not sure if it would be useful, but I can record video how this crossing behaves with a real traffic.

(with potato-level camera, from ground, without a proper stabilization but cars behavior should be visible)

[dabreegster]

Not sure if it would be useful, but I can record video how this crossing behaves with a real traffic.

Hmm, I think I have intuition for how things flow here, but if it's not much trouble, sure! It'd be a neat experiment to see how closely we can get the simulation to look like a sample of real behavior.

[michaelkirk]

I've been poking at this and wanted to check in and verify my understanding @dabreegster.

I think what's happening is:

A car's route is a list of lane IDs (and their connections) that will be traversed.

A lane ID identifies one segment of road between two particular intersections - so if you pass through an intersection, even if you stay in the right most lane, the Lane ID changes. This is important for later.

When a car crosses an intersection, provided the intersection is clear^[1], we allow the crossing car to opportunistically switch lanes while crossing the intersection.

The car chooses the best lane to switch to based on a scoring of all possible lanes: backed up traffic, a bike in the lane, and changing lanes all count against a lane.

A little example: Imagine a one-way road with two lanes and three segments.

[----1a--->][----1b--->][----1c--->]
[----2a--->][----2b--->][----2c--->]

Let's say my original planned route is:

• 1a
• 1b
• 1c

However, when I reach the end of 1a, and am about to cross, I see a cyclist in 1b, so I opportunistically decide to change lanes to 2b. So now my planned route is

• 1a
• 1b 2b
• 1c

Notably, I made no updates to the third step — 1c is still currently on my planned route.

Fortunately, normally when we reach the end of 2b, we'll have another opportunity to update our trip plan, and be biased for updating to 2c since it avoids the lane change penalty. But there's one final caveat, if the intersection is part of an uber turn^[2], we don't even consider an opportunistic lane change. So if 2b were part of an uber turn, while we're in that lane, we can make no further updates to our trip plan, and end up switching back to 1c.

https://user-images.githubusercontent.com/899988/98115670-78345780-1ea7-11eb-9cde-a3ac15a059ca.gif

So looking back at our Krakow scenario, the lane that everyone is changing too is indeed part of an uber turn and part of their original travel route. What's happening is drivers approaching the intersection have opportunistically changed lanes before the uber turn. But then once they're in the uber turn, they're prevented from further updating their original plan, which forces them to switch back to their original lane.

Does that sound correct and plausible @dabreegster ?

If so, some possible solutions might be:

1. allow opportunistic lane updates in an uber turn.

I naively tried this and hit a cascade of asserts - it seems like you had specific and thorough reasons for preventing this.

2. cascade opportunistic lane changes

When changing lanes - update more than just the next step - update the entire trip plan (or some forward looking portion of it).

3. change trip plans to not be LaneID based

e.g maybe road based, or "index of lane" based rather than LaneId based (obviously we'd have to handle changing the number of lanes - maybe it could be a float... drive 25% from the right edge 🙃, just throwing stuff at the wall really.

Any inclinations?

---

[1]

provided the intersection is clear[1], we allow the crossing car to opportunistically switch

More specifically - when laggy_head.is_none() - I'm not sure why this matters though. Removing this restriction triggers an assert.

[2]

uber turn

I'm not completely sure what this is - it seems to be used in a couple of related but slightly different contexts. One context is surfaced in the UI as a visual tool to visualize arbitrary combinations of turns through intersection. The other context is that an individual intersection can be "in an uber turn". My intuition is that this just happens when a bunch of turns are close together, but I haven't yet verified that.

[dabreegster]

More specifically - when laggy_head.is_none() - I'm not sure why this matters though. Removing this restriction triggers an assert.

For reference, this is a call in mechanics/driving.rs before calling car.router.opportunistically_lanechange. If there is a laggy head, it means the current car isn't actually at the front of the lane yet; somebody in front of them is partly in the intersection, partly still in the lane. The car will stay in the Queued state, and once the laggy head clears the lane, they'll wakeup their follower (the car), putting them back into a Crossing state.

If you remove this check, the crash happens because the laggy head clears the lane, tries to wake up its follower, but it's already WaitingToAdvance, not Crossing. That's here: https://github.com/dabreegster/abstreet/blob/4690ea36cdeaa2849b8a9d7ad60c18fd09cafbf1/sim/src/mechanics/driving.rs#L359

Does that sound correct and plausible @dabreegster ?
I'm not completely sure what this is - it seems to be used in a couple of related but slightly different contexts.

Ah, yes! The traffic signal intersection in question is just north of another traffic signal, and that proximity causes uber-turns to be created there. There's a second case forcing uber-turns: turn restrictions -- but there are none defined here.

allow opportunistic lane updates in an uber turn.

There is/was a reason, but I need to think about it again to explain it; I'll followup shortly.

cascade opportunistic lane changes

This could work, but it's likely just a performance issue. Also, the number of vehicles in a future lane could change by the time we get there, so waiting to decide seems nice. Plus, I'm not sure changing the plan ahead of time would even help in this case -- there's still some reason why lane-changing in the middle of an uber-turn is tricky.

change trip plans to not be LaneID based

This is a possibility. Also need to think about it a bit more.

I'll think through 2 of these ideas more and reply soon.

[dabreegster]

Uber-turns and lane-changing

Background

UT=uber-turn
LC=lane-changing

An UT is a sequence of lane->turn->lane->turn...->lane. They get created for two reasons:

1. Some traffic signals are within 25 meters of each other. In reality, humans would probably treat this area as one intersection. Creating UTs between the cluster of close signals is an attempt to make sure vehicles don't get stuck "in the middle" of two lights.

2. OSM has turn restrictions with via as a road segment. An example is:
   
   If the pathfinding layer operated purely at the level of road segments, then it might return a path including this movement. At the graph search level, we have to instead stick in special nodes and edges to represent only the legal movements.

For reference, there's another unsolved bug involving editing a lane in/near the end of an UT: #259

Why can't we LC during an UT?

I introduced this restriction during the handle_uber_turns experiment. This bool is enabled by default right now. It has a few effects:

1. prevent LCing right before or during an UT
2. inside mechanics/intersection.rs: if we started an UT successfully but hit a red light in the middle of the UT, plow right through it
3. also in that file: before we start the first turn in an UT, check that right now we could successfully make it through the entire UT, ignoring red lights. aka, make sure another vehicle isn't blocking some future turn. if everything passes, "lock" the entire UT by inserting a reserved request in those future intersections.

I started this experiment roughly around #114 (comment). But I don't think it was successful -- I didn't really make progress on the south_seattle map there. And since then, one of the problems -- dealing with unsynchronized traffic signals -- has gotten easier to manually edit, and there's very primitive "autotuning" to line up pairs of signals. In retrospect, handle_uber_turns is one of the things making the intersection code really complicated -- it's especially weird to think about the cycle detection in context of reserving an entire UT.

Solutions

Ideally we would delete this experiment. I think first you can try your repro scenario passing --disable_handle_uber_turns. If that helps, run cargo run --release --bin game -- --prebake --disable_handle_uber_turns and make sure both scenarios finish without gridlock. (Or maybe more usefully, run the full weekday scenario in the UI in both montlake and lakeslice.) If this works, let's just delete this entire experiment; it's making things worse here, it's complicated, and I don't have evidence it helps.

If this doesn't work, then maybe we still need to reserve an UT, but we can relax and allow LCing inside an UT, removing the restriction from router.rs. I think the only thing that might go wrong is the reserved code in intersections.

A third option is to allow LCing near an UT in a specific case: when the UT is actually just a single turn. That's the case in this situation; all of the UTs along Aleja Juliusza Słowackiego are just single turns. So the reservation logic wouldn't do anything funny. We could either detect this one-step case in router.rs, or maybe even more simply, go update pathfind/driving.rs to not push onto the list of uber_turns there when it's a one-stepper.

I'm thinking through your third proposal, will write it up too

[dabreegster]

Can a vehicle path be a list of roads?

Only focusing on paths for vehicles here; for pedestrians, "go from intersection1 to i2" is ambiguous because side of the road isn't clear.

The idea is to make a HighLevelPath (with a better name) that's just a list of DirectedRoadIDs. (Or equivalently, IntersectionIDs or RoadIDs, with a little bit of logic to figure out the direction along the roads.) As needed, Router would pick a specific lane to use.

Side effects

First the easy implications of this kind of change:

• the contraction hierarchy would be smaller and cheaper to compute, because the graph of roads is smaller than the graph of lanes
• We'd have to adapt how we draw routes. When we're previewing a route and we only know roads, we could draw a thick fuzzy band or along centerlines or something. When we're drawing the route that a vehicle has followed so far or in the past, we might want to continue showing exactly their lane changes -- or maybe not, if it's not useful to see that.

Why would this change be hard?

Imagine we're a car pulling out of the driveway of the red house. Right now, the driving_pos connection is the rightmost lane, so if our path ideally starts by turning left onto Louisa, we have to follow the green route and loop around the block to get into the proper lane. This is because we can't lane-change in the middle of a lane, only at an intersection.

If we routed by roads, then the first step of the path might say to immediately turn left, following the blue route. If we keep spawning cars in the rightmost lane only, then that wouldn't work. We could maybe try to workaround this by starting the routing from a road that we definitely can reach from the rightmost lane, but there are a few arbitrary choices, and running several pathfinding queries and picking the cheapest feels like a possible performance problem.

So, should we change the model to allow spawning a car on any lane? In many situations, this probably matches reality better, and would compensate for the lack of realistic LCing. How should we do it? We could cheat and just call start_car_on_lane with the left lane, and just ghost through stuff in the right lane. Or maybe we could do the safety check on all lanes in the way, and only go once they're all clear.

If we go this route, should we also allow cars to start from a building or parking lot by turning left, across the road center line? If we could do all the safety checks reasonably, this would fix some "parking blackhole" problems along borders like this:

These houses can't be used for parking, and most trips can't start here, because if the driveway only lets you turn right, then all you can do is vanish off the border. If we more realistically allowed turning left from a driveway, I think lots of the blackhole cases would go away -- but not all.

Are there situations where it's impossible in reality to turn left out of a driveway? Yes, and OSM captures that -- as a divided one-way pair. No issue.

If we manage all of this, then it's also worth asking if we can make vehicles end their route by turning left into a driveway, across opposing traffic. We'd have to bake in a new CarState to represent this and figure out how to make the safety checks work with the discrete event system, but it would increase realism. It might also hurt gridlock -- we might need some amount of dynamic replanning to give up on turning left across a busy street, and just do the loop-around-the-block thing.

Will this help the current problem?

I'm not convinced pathing at the coarser granularity of roads would help here. It depends how the router chooses the exact lane to use, and if UTs are still a complication. Since intersection reservations for handle_uber_turns are at the level of TurnID, I think we'd have the same issue.

So, I think to fix this particular bug, we should still try nuking handle_uber_turns. BUT I would also love to support left turns to/from driveways, and then simplify the pathing layer to return roads.

[dabreegster]

One last thing that came up:

When do we lock in the Turn we want?

As soon as a vehicle hits WaitingToAdvance, they call opportunistically_lanechange just once, and then forever wait for that one particular turn. I've observed situations before where a car picks a clear lane, but while the light is red for them. By the time they can go, actually a bike has picked that lane. But the car's fate is already set, so they follow the bike into the right most lane, with the left lane being nice and clear.

I'm losing steam, but I think it's worth revisiting the protocol that agents use to communicate with intersections. Should vehicles submit all possible turns they want to do? Should the request they submit be coarser and just at the level of a destination road? Then the "opportunistic LCing" can be lazily evaluated inside mechanics/intersection.rs, when the most recent information is available. This complicates things inside there like blocked_by, though -- potentially we'd have to say a car waiting to turn is waiting on the last vehicle in every possible lane.

[michaelkirk]

Thank you for all this excellent feedback! I will consider over night and respond in the AM - I'd like to keep working on this.

[michaelkirk]

Thanks for the clarity around how doing lane-based pathfinding avoids certain unsupported scenarios (e.g. mid-segment lane changing). I see why it would be complicated to switch to a road-based route.

With --disable_handle_uber_turns (and commenting out a couple asserts) the situation is improved a bit:

I'm currently running through some other scenarios to see what the impact is...

Honestly though, now that you've explained it more, special handling of compound turns ("uber turns") makes sense to me. And I'm a little hesitant to just completely rip it out.

Instead, maybe we could take it a bit further:

cascade opportunistic lane changes

This could work, but it's likely just a performance issue.

Why can't we LC during an UT?

I'm wondering if there's a compromise here, where we could opportunistically cascade updates to the path, not for the entire trip, but for entire uber turn, and still require that it all be "locked in" before the car enters the intersection.

Since it's (hopefully/usually) only a handful of segments making up the uber turn, it should be more tractable vs. updating their entire trip plan.

And since it's locked in at the point of entry, I'm hoping we could keep the bulk of uberturn logic untouched like the "don't get locked in the middle of an uber turn" behavior from #114

[dabreegster]

With --disable_handle_uber_turns (and commenting out a couple asserts) the situation is improved a bit:

It looks much better! But all but one of the cars in the video are going straight, so it's still far from realistic -- all 3 lanes should be advancing at the same time, without any switching around...

I'm wondering if there's a compromise here, where we could opportunistically cascade updates to the path, not for the entire trip, but for entire uber turn, and still require that it all be "locked in" before the car enters the intersection.

This is a nice idea! The performance should be fine, and the code complexity shouldn't blow up too much. I am not sure it'll help this specific situation, though -- the uber-turn is only across the traffic signal, not the two little stop signs before and after:

I never finished the process of playing around with how to automatically group UTs. Maybe we can take away checks like https://github.com/dabreegster/abstreet/blob/308eb90956be7d963f308957168bf0e91a1c504c/map_model/src/pathfind/uber_turns.rs#L181 and just go by distance. I think I saw some pretty unintuitively large groups when I did that.

[michaelkirk]

It looks much better! But all but one of the cars in the video are going straight, so it's still far from realistic -- all 3 lanes should be advancing at the same time, without any switching around...

Tweaking the costing function helps this. Currently we'll lane change if there's even just one car in front of us, which is probably not very realistic. If we combine the "number of cars ahead of us" and "number of lanes" into a single score component, we can get more realistic behavior.

Note there are still one or two lane changes in the intersection, but from what I can tell they represent reasonable choices for the car - i.e. they eventually need to be in that lane.

There is a comment about a desire to "keep it simple" and avoid linear combinations of the score function, but this does seem more realistic. WDYT?

@@ -407,7 +407,7 @@ impl Router {
                 } else {
                     slow_lane = 0;
                 }
-                let cost = (lt, bike, slow_lane, vehicles, lc);
+                let cost = (lt, bike, slow_lane, vehicles + lc);
 
                 (cost, turn1, l, turn2)
             })

Alternatively, we could try explicitly penalizing "short lanes" and add that as an explicit cost in our function to exclude lane-changing. (language is tricky here! by exclude lane-changing I mean that in the context of allowing changing the trip plan to avoid changing lanes.)

[dabreegster]

There is a comment about a desire to "keep it simple" and avoid linear combinations of the score function, but this does seem more realistic. WDYT?

Switching to a sum here SGTM. The preference for the lexicographic ordering is understandability. Maybe we shouldn't switch 1 lane over until there's a 2 or 3 vehicle advantage, to add a bit more hysteresis. I'm allergic to parameter tuning, especially when we don't have a convenient way of trying different parameters against a representative sample of traffic loads. But since this little change improves things so much and feels more realistic, seems worth it.

Alternatively, we could try explicitly penalizing "short lanes" and add that as an explicit cost

That's also pretty intuitive -- getting stuck behind a slow vehicle for very short distance doesn't matter so much. Where would it get prioritized in this tuple?

[michaelkirk]

That's also pretty intuitive -- getting stuck behind a slow vehicle for very short distance doesn't matter so much. Where would it get prioritized in this tuple?

If we went that route, I'd guess pretty early on, something like: (lt, short_lane, bike, slow_lane, vehicles, lc).

I kind of prefer the combination score though - it seems like it would effectively accomplish the same thing (you can't have more than one car in the lane if it's very short) plus it seems like it handles some other real world cases (I think people don't usually lane change to get around just one car).

Plus it's easier to implement. ;)

[dabreegster]

SGTM! So IIUC, the immediate plan is to:

• keep handle_uber_turns
• make opportunistically_lc adjust ahead the entire uber-turn
• update the cost function to use vehicles + lc

And the criteria for success are:

• keep montlake and lakeslice running for a full day without breaking
• make visible improvement in this krakow case

[michaelkirk]

Sounds right, yes!

[michaelkirk]

As an update, I'm still working on this.

My work in progress (https://github.com/dabreegster/abstreet/compare/master...michaelkirk:mkirk/lane-change-2?expand=1) attempts to update router.rs so that an entire uber turn can be optimized just before the agent enters the turn.

However, this has introduced some failures that I'm trying to track down. Here are two that I'm seeing:

thread 'main' panicked at 'Queue has spillover on Traversable::Lane(2027) at 00:01:30.5 -- can't draw Car #2, bound is -4.7508m. Laggy head is None. This is usually a geometry bug; check for duplicate roads going between the same intersections.', sim/src/mechanics/queue.rs:156:17
stack backtrace:
   0: rust_begin_unwind
             at /rustc/8256379832b5ecb7f71e8c5e2018446482223c12/library/std/src/panicking.rs:493:5
   1: std::panicking::begin_panic_fmt
             at /rustc/8256379832b5ecb7f71e8c5e2018446482223c12/library/std/src/panicking.rs:435:5
   2: sim::mechanics::queue::Queue::inner_get_last_car_position
             at ./sim/src/mechanics/queue.rs:156:17
   3: sim::mechanics::queue::Queue::get_car_positions
             at ./sim/src/mechanics/queue.rs:59:9
   4: sim::mechanics::driving::DrivingSimState::get_unzoomed_agents
             at ./sim/src/mechanics/driving.rs:908:30
   5: sim::sim::queries::<impl sim::sim::Sim>::get_unzoomed_agents
             at ./sim/src/sim/queries.rs:468:26
   6: map_gui::render::agents::AgentCache::calculate_unzoomed_agents

Another one like:

thread 'main' panicked at 'invalid reserved length: Distance(-6.8051), car: Car { vehicle: Vehicle { id: CarID(9924, Car), owner: Some(PersonID(11505)), vehicle_type: Car, length: Distance(5.9454), max_speed: None }, state: Crossing(TimeInterval { start: Time(10837.0747), end: Time(10837.6318) }, DistanceInterval { start: Distance(0.0), end: Distance(7.4713) }), router: Router { path: Path { steps: [Turn(TurnID { parent: IntersectionID(16), src: LaneID(2349), dst: LaneID(2027) }), Lane(LaneID(2027)), Turn(TurnID { parent: IntersectionID(342), src: LaneID(2027), dst: LaneID(2039) }), Lane(LaneID(2039)), Turn(TurnID { parent: IntersectionID(341), src: LaneID(2039), dst: LaneID(2036) }), Lane(LaneID(2036)), Turn(TurnID { parent: IntersectionID(340), src: LaneID(2036), dst: LaneID(2033) }), Lane(LaneID(2033)), Turn(TurnID { parent: IntersectionID(339), src: LaneID(2033), dst: LaneID(2811) }), Lane(LaneID(2811)), Turn(TurnID { parent: IntersectionID(338), src: LaneID(2811), dst: LaneID(2030) }), Lane(LaneID(2030)), Turn(TurnID { parent: IntersectionID(337), src: LaneID(2030), dst: LaneID(2814) }), Lane(LaneID(2814)), Turn(TurnID { parent: IntersectionID(336), src: LaneID(2814), dst: LaneID(1619) }), Lane(LaneID(1619)), Turn(TurnID { parent: IntersectionID(182), src: LaneID(1619), dst: LaneID(1610) }), Lane(LaneID(1610)), Turn(TurnID { parent: IntersectionID(87), src: LaneID(1610), dst: LaneID(1604) }), Lane(LaneID(1604)), Turn(TurnID { parent: IntersectionID(220), src: LaneID(1604), dst: LaneID(1616) }), Lane(LaneID(1616)), Turn(TurnID { parent: IntersectionID(207), src: LaneID(1616), dst: LaneID(2841) }), Lane(LaneID(2841)), Turn(TurnID { parent: IntersectionID(64), src: LaneID(2841), dst: LaneID(2282) }), Lane(LaneID(2282)), Turn(TurnID { parent: IntersectionID(367), src: LaneID(2282), dst: LaneID(2312) }), Lane(LaneID(2312)), Turn(TurnID { parent: IntersectionID(219), src: LaneID(2312), dst: LaneID(2300) }), Lane(LaneID(2300)), Turn(TurnID { parent: IntersectionID(354), src: LaneID(2300), dst: LaneID(2306) }), Lane(LaneID(2306)), Turn(TurnID { parent: IntersectionID(214), src: LaneID(2306), dst: LaneID(2288) }), Lane(LaneID(2288)), Turn(TurnID { parent: IntersectionID(217), src: LaneID(2288), dst: LaneID(2294) }), Lane(LaneID(2294)), Turn(TurnID { parent: IntersectionID(400), src: LaneID(2294), dst: LaneID(2225) }), Lane(LaneID(2225)), Turn(TurnID { parent: IntersectionID(70), src: LaneID(2225), dst: LaneID(2232) }), Lane(LaneID(2232)), Turn(TurnID { parent: IntersectionID(399), src: LaneID(2232), dst: LaneID(2244) }), Lane(LaneID(2244)), Turn(TurnID { parent: IntersectionID(289), src: LaneID(2244), dst: LaneID(1749) }), Lane(LaneID(1749)), Turn(TurnID { parent: IntersectionID(351), src: LaneID(1749), dst: LaneID(2615) }), Lane(LaneID(2615)), Turn(TurnID { parent: IntersectionID(234), src: LaneID(2615), dst: LaneID(2609) }), Lane(LaneID(2609)), Turn(TurnID { parent: IntersectionID(148), src: LaneID(2609), dst: LaneID(659) }), Lane(LaneID(659))], end_dist: Distance(0.0), total_length: Distance(2128.6857), crossed_so_far: Distance(519.3439), total_lanes: 34, uber_turns: [UberTurn { path: [TurnID { parent: IntersectionID(338), src: LaneID(2811), dst: LaneID(2030) }] }], currently_inside_ut: Some(UberTurn { path: [TurnID { parent: IntersectionID(10), src: LaneID(2331), dst: LaneID(2349) }, TurnID { parent: IntersectionID(16), src: LaneID(2349), dst: LaneID(2027) }, TurnID { parent: IntersectionID(342), src: LaneID(2027), dst: LaneID(2039) }] }) }, goal: ParkNearBuilding { target: BuildingID(2378), spot: None, stuck_end_dist: None, started_looking: false }, owner: CarID(9924, Car) }, trip_and_person: Some((TripID(32535), PersonID(11505))), started_at: Time(10805.0), total_blocked_time: Duration(5.7794), last_steps: [] }', sim/src/mechanics/queue.rs:261:9
stack backtrace:
   0: rust_begin_unwind
             at /rustc/8256379832b5ecb7f71e8c5e2018446482223c12/library/std/src/panicking.rs:493:5
   1: std::panicking::begin_panic_fmt
             at /rustc/8256379832b5ecb7f71e8c5e2018446482223c12/library/std/src/panicking.rs:435:5
   2: sim::mechanics::queue::Queue::free_reserved_space
             at ./sim/src/mechanics/queue.rs:261:9
   3: sim::mechanics::driving::DrivingSimState::trim_last_steps
             at ./sim/src/mechanics/driving.rs:801:21
   4: sim::mechanics::driving::DrivingSimState::update_laggy_head
             at ./sim/src/mechanics/driving.rs:745:13
   5: sim::sim::Sim::do_step
             at ./sim/src/sim/mod.rs:601:17

Current theory is that something about my change is preventing queues from releasing their reserved length properly. I don't immediately understand why, but still looking.

[dabreegster]

Can I repro that on the south_seattle map? I read through your change and it all looks correct to me, not sure what's wrong either.

[dabreegster]

south seattle crashes almost immediately for me. I see you added some debugging to the analytics demand bit. I'm confused how your changes could affect this... it must mean the rewritten path picks different road1->road2 pairs. The indexing in there based off segment is a little confusing to me; I'll read through the debug output more carefully for one of the changed paths.

[dabreegster]

Steps changed. Before:
[Lane(LaneID(29096)), Turn(TurnID { parent: IntersectionID(6278), src: LaneID(29096), dst: LaneID(40201) })

vs After:
:[Lane(LaneID(29096)), Turn(TurnID { parent: IntersectionID(3989), src: LaneID(40201), dst: LaneID(22642) })

Path has a hidden validate_continuity method; it might be useful to temporarily expose this and call it after you do the rewrite. For this crashing case, something _very_wrong is happening; that first turn warps.

[dabreegster]

Ah, your bug is self.path.modify_step(1, 2, 3...) -- the number is an exact index into the steps. Since you're modifying into the future, need to add segment * 2 to all of these

[michaelkirk]

ah!! thank you!!

[BruceBrown]

--disable_handle_uber_turns no longer works. This is one of the likely crashes you'll run into:
thread 'main' panicked at 'assertion failed: self.currently_inside_ut.is_none()', map_model/src/pathfind/mod.rs:276:9

[dabreegster]

Whoops! I don't regularly test that flag. Do you think it's worth keeping around? Are we likely to want to try simulating without reserving UTs, to see if it helps some particular map? Keeping around all of the optional flags definitely increases code complexity, but we might regret it later if we remove them.

[BruceBrown]

I think we want to reduce UT via merge, but I don’t believe they will completely go away. One way to find good merge candidates might be to remove UT and watch for jams. If that’s the case, then I think we might want to fix some things. I’m guessing, but I suspect it’s a hand full of asserts or unwraps that need additional filtering.

I started to look at how to provide the flag and not crash, but wasn't able to find a clean, clear, way to do it. Instead, I found more "danger ahead" signs, like this in map_model/src/pathfind/mod.rs:

        if self.steps.len() == 1 {
            // TODO When handle_uber_turns experiment is turned off, this will crash
            assert!(self.uber_turns.is_empty());
            assert!(self.currently_inside_ut.is_none());
        }

[dabreegster]

Visualizing the dynamic "ghosts" for better debugging