Results from prebaked scenario are different from the same scenario in a blank proposal

[lucasccdias]

Hi, @dabreegster

I told you about this issue on Discord, and I finally found out how to reproduce it.

1. Build A/B Street from Git.
2. Open "São Miguel Paulista" map.
3. Choose the "Full" scenario, which is the prebaked one.
4. Edit map: make some random edit and run the scenario. The visualizations show that the trips' results changed (as expected, since the map changed).
5. Create a new, blank proposal and make no edits (0 roads, 0 intersections changed) in the map and run the scenario again "Finish & resume".
6. Open the visualizations and see that the results are different from the baseline, prebaked scenario. But they should not be since the map was not edited.

[dabreegster]

Thanks! I can reproduce this. After step 3 if you run the scenario, the travel time dataviz shows 0 changes as expected. But indeed, making an edit, then clearing it out, winds up with a diff.

A variation also fails -- edit a lane in the map, immediately undo, and then launch the scenario. There's a diff when there shouldn't be!

I'm not sure what's going on, but this is a majorly unexpected bug, I'll look into it...

[dabreegster]

We have individual level A/B testing for a reason. :) For some random agent that changed, their path before/after the nonexistent edit has changed. I'm now suspicious of recalculate_pathfinding_after_edits.

[dabreegster]

It's not looking great -- I've found at least 3 bugs.

Problem 1: not short-circuiting

https://github.com/a-b-street/abstreet/blob/460c03e75cd83f3b9c948aaf52850678486415c2/apps/game/src/edit/mod.rs#L73

When we exit edit mode, we sometimes short-circuit and leave the traffic simulation exactly as it was, without needing to reset. This only happens if the map edits when we exit are exactly the same as when we enter. This comparison is overly conservative -- if we edit one lane then undo the edit, we won't short-circuit, but we should. Consider compressing edits.

Problem 2: undoing edits isn't idempotent

If I modify one lane, then immediately press revert, the net result should be nothing. But in reality, both of those edits cause us to re-snap building paths. The result is a slight difference in dist_along, which can crash the simulation if it's running:

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `SidewalkSpot { connection: Building(BuildingID(906)), sidewalk_pos: Position { lane: LaneID { road: RoadID(218), offset: 0 }, dist_along: Distance(65.8684) } }`,
 right: `SidewalkSpot { connection: Building(BuildingID(906)), sidewalk_pos: Position { lane: LaneID { road: RoadID(218), offset: 0 }, dist_along: Distance(65.8683) } }`', sim/src/trips.rs:1339:17

Not sure why this is happening yet.

Problem 3: the pathfinding graph changes spuriously

This is causing the main problem reported, and the changed paths in the screenshot above demonstrate the problem. I dumped the entire pathfinder object before and after https://github.com/a-b-street/abstreet/blob/460c03e75cd83f3b9c948aaf52850678486415c2/map_model/src/edits/mod.rs#L963 for these no-op edits, and the file has a bunch of diffs internally:

There are two possibilities:

1. The input graph is different
2. The assumption about reusing node ordering (https://github.com/a-b-street/abstreet/blob/460c03e75cd83f3b9c948aaf52850678486415c2/map_model/src/pathfind/vehicles.rs#L145) is false

@easbar, regarding the second, what do you think about this sequence of events:

1. an InputGraph is built
2. That graph is used to prepare a CH, using custom parameters
3. We build a new CH using the original CH's node ordering, feeding in exactly the same InputGraph, and some parameters. The one parameter in common between Params and ParamsWithOrder matchs -- for both, max_settled_nodes_contraction = 100`

Would you expect the two CHs to be exactly equal (JSON dump matches)? Or functionally equivalent, producing the same results for all possible queries?

Edit: https://github.com/dabreegster/fast_paths/commit/567695cb1cbbc3547e2838cb11c74c896fd995d4, answer to the first question appears to be no, unless I've written the test incorrectly somehow

[Robinlovelace]

Heads-up: discussing the with @lucasccdias today.

[Robinlovelace]

Follow-up question on this from @fred-r-ramos: could this bug be local to certain places that have unusual OSM data? I guess not but thought it worth asking. I guess a good way to test would be to find the simplest situation in which the bug can be reproduced, e.g. in the default map view in Seattle.

[dabreegster]

could this bug be local to certain places that have unusual OSM data?

Nope, I can reproduce outside of A/B Street just at the graph routing level: https://github.com/dabreegster/fast_paths/commit/567695cb1cbbc3547e2838cb11c74c896fd995d4 The root problem comes from an assumption I had about how contraction hierarchies work. I thought these two processes would produce equivalent results:

1. Prepare a CH from some input graph

and

1. Prepare a CH from some input graph
2. Modify some edge weights (representing road closures, changing speed limits, etc)
3. Prepare a new CH, but re-use the node ordering from the 1st CH. This is much faster than preparing from scratch.
4. Reset the edge weights to their original form
5. Prepare a CH reusing node ordering again

I don't know enough theory about how CHs work to diagnose further. Possibly the routes that're changed spuriously have nearly equal weights to the alternatives? That's a theory I could test.

A blunt hammer to fix this problem is to always prepare the CH from scratch. Slow, but I'd expect less problems.

I don't anticipate having time to look at this before AI:UK, sorry. :\

[Robinlovelace]

A blunt hammer to fix this problem is to always prepare the CH from scratch. Slow, but I'd expect less problems.

Sounds like a plan. I would expect the contraction hierarchy (CH) needs to be rebuilt after each edit. Another advantage: would mean that new links (if/when that functionality is added) will be picked up in the routing with minimal change? Also editing the road network is not super common for many users and waiting for the CH to rebuild will be a small cost relative to the huge benefits of before/after analysis.

[dabreegster]

would mean that new links (if/when that functionality is added) will be picked up in the routing with minimal change?

Correct, one of the blockers for creating entirely new roads is dealing with the CH changing completely.

Also editing the road network is not super common for many users and waiting for the CH to rebuild will be a small cost relative to the huge benefits of before/after analysis.

What I might do is only enable the slower full rebuild if we do have prebaked data, because only then do the comparisons matter so much.

[dabreegster]

I figured out at least one of the main problems. Tracing my steps:

1. Make an innocuous edit (like adding a stop sign, which shouldn't even affect any pathfinding weights)
2. Use the A/B test and find an agent whose route changed
3. Get very suspicious
4. Dump the InputGraph to JSON while importing the map originally, and again after the map edit
5. Diff, notice many changes. For a particular changed edge, dig into why the cost changed

The smoking gun:

      - orig: 0->622 has round(3.6s). from DirectedRoadID(0, forwards) to DirectedRoadID(311, forwards)
        - t1 3.5s + t2 0.2s
        - final cost 1 * 3.6s + 0s

      - live: 0->622 has round(0s). from DirectedRoadID(0, forwards) to DirectedRoadID(311, forwards)
        - t1 3.5s + t2 0.2s
        - multiplier 1 getting modified by main_road_penalty 0
        - final cost 0 * 3.6s + 0s

The bug is happening because vehicle_cost is returning bad results while editing the map live. Why? Because of the main_road_penalty added months ago for the LTN tool. When this is != to 1, we multiply the cost by it, to simulate heavy traffic on main roads.

The problem: while building the map initially, this is correctly set to 1. But when we save the map, we don't serialize this field -- https://github.com/a-b-street/abstreet/blob/eff3d8323183e0ce5946a44dca9b1179adbc6915/map_model/src/pathfind/mod.rs#L189 -- and so it gets set to a default 0, and thus breaks vehicle_cost when recalculating things later. Skipping serialization like that is my quick trick for adding new fields to the map without breaking binary compatibility and having to rebuild all maps. I made this change during a hackathon and forgot to clean it up for 4 months.

Actions:

• Start serializing this parameter so it'll properly be 1
• Audit rest of codebase for skip_serialize
• Regenerate all maps
• Verify spurious changed routes stop happening
• Write an integration test to make a no-op edit like this and verify prebaked results don't differ, to prevent this nonsense from happening again

Apologies it took so long to actually get to working on this

[Robinlovelace]

Great diagnosis, many thanks for the clear description of what's going on that does not require deep knowledge of Rust to understand. Look forward to pumping out updated results from A/B Street soon!

[fred-r-ramos]

Many thanks, Dustin. No need for apologies! Great work! Are the corrections already available at the online Play on the web version? Curious to see the simulations for Sao Paulo running.

[dabreegster]

@fred-r-ramos, they're not on the web version yet. I can expedite a release before Sunday if it's useful, though I might have more fixes coming soon, because...

There are still unexplained changes in pathfinding caused by seemingly unrelated map edits: The cyan and red line show before/after of someone driving in the area. The only change is the modal filter introduced far to the south. The edge weights shouldn't change and affect the shortest path so far north. I'm looking into why.

[dabreegster]

The problem is that the alternative path chosen has exactly the same cost as the original path. This is what's happening:

1. Given the same map and travel demand input, running the simulation and measuring things like which roads get used, where people experience delay, etc is all totally deterministic.
2. When you edit the map, we repeat the simulation and measure everything again. We want any differences in measured output to be caused by the edit to the map.
3. But some paths have alternatives with the exact same cost, and it looks like the graph search methods we're using can fluctuate when we make a change to the graph far away.

I can work around this in a simple case unrelated to the traffic sim, by ignoring changes from routes that have the same cost before and after edits. But in the simulation this won't be straightforward.

I'll have a discussion with @easbar about a way to keep the chosen paths "stable" across edits that shouldn't affect anything.

[fred-r-ramos]

I see. Many thanks for the explanation. Very interesting to follow it.

[dabreegster]

I added the test to guard against the first problem (reverting edits must be equivalent to an unedited map). But still seeing spurious changes with benign edits. If I edit a sidewalk's width in São Miguel Paulista, there are a bunch of agents experiencing different trip times. The first one that I spotted happens to walk over the widened sidewalk and hit a traffic light they didn't before. But the length of the sidewalk (and time needed to cross it) didn't change. I need to dig in more to figure out what's happening. On the call the other day, I speculated this is because some paths are changing spuriously because they have equal predicted cost. But this may not be the only problem.