Overbranching Hunting
The intent of this page is to illustrate how to use the OTP visualizer to investigate scenarios that give rise to an inefficient amount of branching during the execution of the route planning algorithm.
First, generate a graph of about medium size. Portland Oregon including Trimet's GTFS is about the right size.
Next, start up the visualizer using a debugger. Eclipse's debugger works great.
The basic layout of the visualizer is a little messy. You should see three tabs at the top, a pane on the right, several panes on the left, and a map in the middle.
Zoom in with your mouse scrollwheel, then left click a part of the map. All nearby nodes will show up in the "Vertices" pane on the left.
Click on one with a node name starting with "osm:node:", and then click the "set source" button at the top left of the visualizer. Click on another part of the map, and select a different node from the "Vertices" pane, and then click "set sink". Finally, click the button labeled "path search".
After a short animation, you should see something similar to this.
There's a lot going on here, so let's simplify the map a little. Click on the tab at the top labeled "Prefs". Unselect the checkboxes labeled "show transit", "show highlighted", and "show multistate vertices".
Click on the Main tab to go back to the map. Then maybe zoom in a little. It should look like this.
This is still pretty cluttered, but it's worth explaining what's going on. This is a visual depiction of the shortest path tree, where the width of each branch shows the total sum of the weight of all states up-branch. Because a vertex can have multiple states, several branches can overlap on a single point on the map. Each branch is colored according to the "height" of the tree branch. The algorithm is sort of complicated but the idea is to give a quick visual indication of where different fanning SPT regions overlie the same area, and it didn't really work out super great.
A little more to the tour before we start going debugging. Click on a part of the map that looks busy, and a bunch of entries will appear in the "Paths" list box in the left. This is what it looks like after I clicked in Portland's "Hollywood" neighborhood.
Click on any of the entries in this list and the relevant route will appear on the map. In order to actually see the route, you might want to go over to the "Prefs" tab and deselect the "show SPT" checkbox. If you do you might see something like this.
Note on in a pane on the right is a list of "path states". If you click on any of the path states it will highlight the edge that leads to that path state on the map.
Also if you click on one of the path state list items, and then use tab navigation on the righthand pane to move to the "metadata" tab you can see a dump of all information about that state.
The vertex I selected on the map happens to have ten different SPT states, each with a its own path leading back to the origin. It's common for many of the states to have essentially identical paths, which is inefficient.
The basic idea is:
- Find a place with a lot of similar paths
- Find two redundant paths
- Identify where they should have merged
- Run the debugger to investigate why the paths branched instead of merged.
To style the map according to the number of states at each vertex, go to the Prefs panel and turn on "show multistate vertices". Here's the resulting map.
Large circles represent intersections with lots of codominant states. Click on an intersection with a big circle to see all the paths leading to that vertex listed in the "Paths" list box on the left. Here I've selected a vertex with eight states. The first two states have nearly identical paths, and the final path states have a weight difference of 0.002%.
Next, we want to compare the two paths and identify where they improperly branched. Right click on the first path in the "Paths" window and select "compare" from the context menu.
Do the same for the second (nearly identical) path. Then click on the "Diff" tab at the top of the screen. You should see the path diff tab.
The two lists show a list of each state for each path. All the blue-colored list items represent the initial portion of the two paths before they diverge. All red-colored list items represent the portion of the path at the end when the paths have converged onto a string of identical vertices. If you select an item in either list some information will be printed in the box below.
Here's where things get fun. Upon clicking the "traverse" button, the traverse method of the backedge of the most recently selected state will be executed. If you click the "dominates" button, MultiShortestPathTree#dominates will be called on the lefthand and righthand selected states. Each button won't initiate any visible behavior, but if you set a breakpoint on either of those functions, you get to see them spring into action with the offending input.
In this arbitrary instance it turns out that s1 has a route sequence subset of s2, any epsilon comparison are waived, and since s1.getElapsedTimeSeconds() is 1 second larger than s2.getElapsedTimeSeconds(), it does not dominate.
Likewise s2 does not dominate s1 because s2 has a backedge that is a street with no turn restrictions and it does not have the same backedge as s1. Which for some reason means that s2 cannot dominate s1.
Since neither state dominates the other they are codominant and result in a planning branch. Since they are in fact nearly identical, they should not be allowed to produce peer branches of the trip planner.