More realistic static routing

[dabreegster]

A/B Street's cost functions for driving/biking and walking are laughably simple. They're used to pathfind for agents and to determine walksheds in the 15 min tool. This issue will focus on improving these cost functions for the static case; not going to worry about dynamic conditions like traffic delays or congestion charges yet.

Some thoughts/questions:

• Do we express the cost just as an estimated time, subject to constraints? That's easier to communicate with people and matches the 15 min neighborhood intuition, but it doesn't directly express quietness / safety / pleasantness.
• Multiple factors will influence a single cost. Should we use linear combination with parameters we have to somehow tune? Or a lexicographic comparison of each factor, arbitrarily choosing that a slight safety benefit warrants any increase in expected time?
• Bucket list of factors:
  • For driving: speed limit and road length, waiting at traffic signals (could use actual fixed timing, or at least cycle length), unprotected left/right turns onto a bigger road
  • For biking: road length, elevation (don't have data yet), biking on/adjacent to a higher speed limit road, bike lanes in the door zone of parking, preferring totally separated trails, some OSM-based measure of road beauty (tree cover?) or quietness
  • For walking: same as biking, except the door zone factor doesn't matter
• Individual people's preferences differ
  • Biking examples: fearless and fastest route possible, wanting hills for training, wanting safe/quiet routes
  • Do we need to support any arbitrary set of parameters, or just make up a few fixed profiles? Implementation-wise, since we're using contraction hierarchies, a few profiles is more reasonable.
• Parameter tuning and testing
  • How do we verify resulting paths for different preferences are reasonable? I could manually audit some examples around Seattle that I'm intimately familiar with.
  • Should we set up goldenfile unit tests, or is this likely to be super brittle as we get new upstream OSM data?
• Using the cost functions for reporting
  • Today, the main metric used as a score in the game is trip time savings
  • We can measure anything we simulate. It's a matter of how to report it -- total cyclist miles spent in a door zone?

Some initial tasks

• [ ] Research how CycleStreets, Valhalla, GraphHopper and other open source routing engines solve these problems. (We're going to end up doing something way simpler of course, but at least get ideas)
• [ ] Make a new RoutingProfile enum that subsumes PathConstraints, pass it in a limited number of places
• [ ] Refactor internal CH / Dijkstra impls to work off the profile enum
• [x] Make a new debug UI to specify a start/end. Automatically show the route for all profiles.
• [x] Add sliders for the parameters to the UI and allow changing live. (Maybe for pathfinding, that always winds up calling the Dijkstra impl instead of rebuilding the CH)
• [ ] Investigate using routing tables from CycleStreets directly (is https://github.com/cyipt/actdev/blob/main/data-small/great-kneighton/routes-fast.geojson an example?)

@Robinlovelace , @mvl22 as FYI -- I'm going to start some amount of this to improve the routes taken for actdev.

[Robinlovelace]

Very excited to see movement on this.

[mvl22]

Writing a routing cost function for bicycles is a massive can of worms, as your own initial (but very incomplete) list shows. We've spent years trying to do it properly and still have a massive list of future things we want to implement. Look at other routing engine development trackers and, where you find people that actually care about bicycle routing, you will find lots of discussion, which you risk having to replicate.

My strong suggestion to you is that you simply add support for routing profile file/function formats used by another engine and delegate the problem there. That means there are off-the-shelf profiles that meet the 'good enough' test and can just be pulled in, for multiple different mode choices. Creating yet another forum for complex debate about how to score bicycle routing, in another format, and trying to solve that problem, is not really the core value A/B Street brings, and will become a distraction.

For instance, OSRM uses a Lua-based profile system: https://github.com/Project-OSRM/osrm-backend/tree/master/profiles

You essentially would just need to provide a function prototype that reads any such functions that a profile writer has defined, adding support progressively for each type.

Things like junction modelling will be complex to implement and may not be worth bothering too much with until you have a lot more time.

(The CycleStreets cost profiles are significantly more detailed than OSRM's, incidentally.)

PS Yes, also provide the ability to provide a simple wayId/cost lookup. This won't handle junctions of course but will add much flexibility.

[dabreegster]

Thanks for the insights! I certainly don't aim to repeat the efforts of proper routing engines, just improve what abst is doing.

The idea of directly reusing existing profiles is interesting. The architectural requirements may not be that bad; abst can continue building contraction hierarchies as it does already, and just use a profile as a black-box to provide costs. Lua support specifically is a reasonable option; there are well-maintained Rust/Lua bindings for running natively. One complication is that abst rebuilds the contraction hierarchies and needs to reevaluate costs when the player edits the map. For this to continue working in web browsers, there'd need to be a WASM Lua implementation, likely in the form of a Lua interpreter in pure Rust. At a glance, a few projects exist to do this, but look unmaintained and incomplete.

Another possible complication with OSRM profiles is that abst maps don't retain key/values for OSM nodes. We do for ways, so maybe we just start with just process_way.

I dug into graphhopper a bit and found some nice info on how they combine multiple factors. I haven't actually found the profile definitions in the repo yet, just some example customizations, but I'll keep looking.

Anyway, I'll start with some of the architectural changes for more flexible routing and setting up a UI to quickly tune / understand the effects of cost functions. Still not sure how to write those functions, but directly calling into another project's profiles is a good possible option.

[mvl22]

For this to continue working in web browsers, there'd need to be a WASM Lua implementation, likely in the form of a Lua interpreter in pure Rust.

I'd have thought that writing a basic Lua string parser that can then open up a whole range of off-the-shelf templates that others have already argued over, would be more productive than introducing the friction involved with a whole new syntax and requiring the same debates having to be rehashed.

[dabreegster]

Here's a simple tool to live-tune routing params and see how they affect a single route. The north/south arterial shown at the beginning has bike lanes, and the existing cost function adds a penalty for using car/bus/bike lanes. So as I fiddle with those values, you can see the chosen route jump back and forth.

Next up is #237 -- the same thing, but instead of one handpicked start/goal, use any abst scenario (like real Seattle Soundcast data or the disaggregated actdev ODs) to get lots of ODs, pathfind for all of them, and color all roads based on more/less/same traffic. So intuitively, a quick way to visualize how tuning a parameter would influence overall system behavior, without running a simulation.

Still undecided how to write the cost function. I might try some very simple additions to what's existing. With regards to the Lua profile idea:

I'd have thought that writing a basic Lua string parser that can then open up...

I'm in agreement here about wanting to reuse existing work and not repeat the process of tuning a profile. I'll dig more into the idea of using OSRM Lua specifically. I don't think a simple parser would suffice; the OSRM example uses includes and does arithmetic. I don't intend to go write a Lua interpreter for Rust if there isn't one already. But luckily, the Rust gamedev community loves Lua integration, and I bet at least somebody has WASM compatibility in mind. I'll look around more.

Yes, also provide the ability to provide a simple wayId/cost lookup.

This is one of the simplest directions forward, and would leverage all of your effort. Are you willing to export a CSV file (or any other format) with OSM way ID and a cost for the actdev integration?

[dabreegster]

Summary of directly using OSRM Lua profiles: feasible, but complicated and would likely incur some heavy dependencies, at a time when we're trying to slim down the web version of abst.

As I mentioned earlier, if abst only ran on native or if map edits didn't affect routing at all, this would be pretty easy. But we'd have to execute Lua both natively and on web. The easiest way to do this in Rust is if there's a Rust implementation of a Lua interpreter (or VM, technically), because Rust can turn into wasm just fine. All I found here was https://github.com/kyren/luster, which is abandoned and may be missing many features that the OSRM profiles use.

There are pure Rust parsers for Lua, like https://github.com/Kampfkarren/full-moon, but we'd then have to write an interpreter operating off the AST.

There are a number of ways to compile Lua into wasm: https://github.com/ceifa/wasmoon, https://github.com/vvanders/wasm_lua, and more at https://github.com/LewisJEllis/awesome-lua#implementations-interpreters-and-bindings. We could use rlua (the C bindings to native Lua) on native, and glue one of these Lua WASM impls to the web version. Or maybe for slightly less difference between environments, always use Lua WASM and run a WASM runtime (https://github.com/wasmerio/wasmer) on native or in the browser.

I haven't checked to see how many dependencies these options would bring in, but my guess is that they'd be substantial. As part of #377, we've been trying to slim down the startup cost of web abst. Lua integration is likely to harm that effort. It might wind up being worth it to pursue one of these options, to gain the benefit of reusing OSRM's effort, but it doesn't strike me as a priority.

I'll keep researching other OSM routers to see how they define profiles. Maybe one of them uses a different config format with simple logic to apply this to an OSM way's key/values, and we could just implement that logic and directly use the config file with the tuned params.

[dabreegster]

Valhalla uses some mix of lua and C++ -- even less easy to directly integrate.

[dabreegster]

BRouter uses a custom format

[Robinlovelace]

Here's a simple tool to live-tune routing params and see how they affect a single route.

This is very cool! To me it emphasises a key strength of the abstr approach: maximise playability. I think you can go a long way using simple profiles. After that there will be diminishing returns. On the note of simplistic 'get started' profiles, here's another from the routino project imported into the R package dodgr.

[Robinlovelace]

library(dplyr)
#> 
#> Attaching package: 'dplyr'
#> The following objects are masked from 'package:stats':
#> 
#>     filter, lag
#> The following objects are masked from 'package:base':
#> 
#>     intersect, setdiff, setequal, union
dodgr::weighting_profiles$weighting_profiles %>% 
  filter(name == "bicycle")
#>       name            way value max_speed
#> 1  bicycle       motorway  0.00        NA
#> 2  bicycle          trunk  0.30        NA
#> 3  bicycle        primary  0.70        15
#> 4  bicycle      secondary  0.80        15
#> 5  bicycle       tertiary  0.90        15
#> 6  bicycle   unclassified  0.90        15
#> 7  bicycle    residential  0.90        15
#> 8  bicycle        service  0.90        15
#> 9  bicycle          track  0.90        12
#> 10 bicycle       cycleway  1.00        15
#> 11 bicycle           path  0.90        12
#> 12 bicycle          steps  0.50         4
#> 13 bicycle          ferry  0.20        15
#> 14 bicycle  living_street  0.95        15
#> 15 bicycle      bridleway  0.70         8
#> 16 bicycle        footway  0.90         4
#> 17 bicycle     pedestrian  0.80         4
#> 18 bicycle  motorway_link  0.00        NA
#> 19 bicycle     trunk_link  0.30        NA
#> 20 bicycle   primary_link  0.70        15
#> 21 bicycle secondary_link  0.80        15
#> 22 bicycle  tertiary_link  0.90        15
dodgr::weighting_profiles$surface_speeds
#>        name     key                 value max_speed
#> 1  motorcar surface                cement        80
#> 2  motorcar surface             compacted        80
#> 3  motorcar surface           fine_gravel        80
#> 4  motorcar surface         paving_stones        60
#> 5  motorcar surface                 metal        60
#> 6  motorcar surface                bricks        60
#> 7  motorcar surface                 grass        40
#> 8  motorcar surface                  wood        40
#> 9  motorcar surface                  sett        40
#> 10 motorcar surface           grass_paver        40
#> 11 motorcar surface                gravel        40
#> 12 motorcar surface               unpaved        40
#> 13 motorcar surface                ground        40
#> 14 motorcar surface                  dirt        40
#> 15 motorcar surface           pebblestone        40
#> 16 motorcar surface                tartan        40
#> 17 motorcar surface           cobblestone        30
#> 18 motorcar surface                  clay        30
#> 19 motorcar surface                 earth        20
#> 20 motorcar surface                 stone        20
#> 21 motorcar surface                 rocky        20
#> 22 motorcar surface                  sand        20
#> 23 motorcar surface                   mud        10
#> 24  bicycle surface cobblestone:flattened        10
#> 25  bicycle surface         paving_stones        10
#> 26  bicycle surface             compacted        10
#> 27  bicycle surface           cobblestone         6
#> 28  bicycle surface               unpaved         6
#> 29  bicycle surface           fine_gravel         6
#> 30  bicycle surface                gravel         6
#> 31  bicycle surface           pebblestone         6
#> 32  bicycle surface                ground         6
#> 33  bicycle surface                  dirt         6
#> 34  bicycle surface                 earth         6
#> 35  bicycle surface                 grass         6
#> 36  bicycle surface                   mud         3
#> 37  bicycle surface                  sand         3
#> 38  bicycle surface                  sett        10
#> 39     foot surface           fine_gravel         4
#> 40     foot surface                gravel         4
#> 41     foot surface           pebblestone         4
#> 42     foot surface                   mud         2
#> 43     foot surface                  sand         2
dodgr::weighting_profiles$penalties
#>          name traffic_lights turn
#> 1        foot              2  0.0
#> 2       horse              8  0.0
#> 3  wheelchair              2  7.5
#> 4     bicycle              2  6.0
#> 5       moped              8  7.5
#> 6  motorcycle              8  7.5
#> 7    motorcar              8  7.5
#> 8       goods              8  7.5
#> 9         hgv              8  7.5
#> 10        psv              8  7.5

^{Created on 2021-02-03 by the reprex package (v1.0.0)}

[dabreegster]

Thanks @Robinlovelace for the routino tip; that should be very easy to copy as a cost function!

I made a similar UI for seeing how the routing params affect all trips on a map. For every OD pair, it calculates how many paths cross every road. Then after you fiddle with the params, it does the same thing, and shows the diff. So here's where some bike lanes are: And here's what happens if I change the params to more strongly prefer cycle lanes: Red means more traffic, green is less.

This general tool/technique can also be used to show the player the effects of editing the map to build new cycle lanes, or make any other kind of comparison. It's faster / more reliable than running a simulation and comparing the count-per-road data from the simulations.

The visualization still needs some work to adjust the color scales. At first I tried https://github.com/a-b-street/abstreet/blob/7855d26a6a81ae2339bcff5a12d43aa98b398d2c/map_gui/src/tools/colors.rs#L189, which calculates a ratio count_after / count_before and can not draw anything for a range like [0.99, 1.01] (to not show roads with a small diff). But since bike traffic is a tiny percentage of most roads in the first place, most of the ratios are too close to 1.

So I switched to https://github.com/a-b-street/abstreet/blob/7855d26a6a81ae2339bcff5a12d43aa98b398d2c/game/src/debug/routes.rs#L340, shown above. This finds the biggest difference of (before - after).abs() from all changes, then uses a red or green scale and linearly interpolates by a percentage of the particular difference divided by the biggest diff.

I'm pretty sure I've spotted some before/after count comparisons in the PCT tool and your Geocomputation book before, so I'll poke around and see if there's a better method for coloring this kind of diff.

[Robinlovelace]

Impressive progress on this @dabreegster, great work!

[michaelkirk]

This is neat!

[dabreegster]

I'll revive work here soon. Just noting a need for discouraging multi-step U-turn maneuvers like this:

[dabreegster]

@mvl22 We've got some decent elevation/incline data wired up now, and are going to start adjusting bike and pedestrian speeds based on percent incline. Happen to know any references for this? So far, we've unearthed http://bikecalculator.com/what.html and https://en.wikipedia.org/wiki/Tobler%27s_hiking_function (for walking).