Rerouting: mechanism and policy

Early in the development of AORTA, I encountered many issues with gridlock, where drivers would collectively reach a state where none of them could move. Eventually I came up with two behaviors that prevent many forms of the gridlock, and I baked these into the code. Today I finally separated these policies (because that’s what they are — there’s more conservative and more risky versions of them that could exist) from the mechanisms of rerouting. Now ReroutePolicy, a component each driver has, two new methods that can be overriden:

  1. pick_alt_turn: given an existing turn request, cancel it and try to reroute if gridlock is detected starting at the turn
  2. pick_next_turn: If the next road in our path is congested, try to reroute.

Deprecated code removed

I’m studying for my last final exam ever, so I didn’t do much today. I just removed code I’ve judged to be useless in hindsight:

  1. Lots of old routers (ways of giving A* a score) that used lexicographic tuples of (toll, time) per road. There were some wacky ideas in there, like (sum toll, sum time), meaning a driver would choose a route with cost (toll $10, time 9000) over a route with cost (toll $10.01, time 60). In general, lexicographic comparisons, where one feature strictly dominates another, aren’t a good choice. Instead, linear combinations (or some other function) of toll and time are the way to go.
  2. Zones. This was an idea I tried a few years ago too. Basically, zones are a partitioning of roads. It could be used for hierarchical pathfinding, avoiding an entire region for general congestedness, and pricing a larger unit of the map. Unfortunately, I never got zones to be connected components of the road graph. And empirically, the other ideas didn’t work too well.
  3. Road agents. These were wacky little agents associated with each road, analogous to the intersection agent. They contained various ways of labeling a road as congested or not, based on reporting current state or some sort of moving window of conditions. I’ve long since moved away from congestion as a binary state. Basically, these aren’t used by anything anymore.

Still more cleanup planned. And if for some reason, this code would be useful in the future, then hey, that’s what git is for.

Spring cleaning

I guess it went a bit quiet around here. I’ve been working on a data mining project using AORTA (it identifies OSM roads likely to have the wrong label, which leads to weird numbers of lanes or incorrect speed limits). It’s done; I may write about it eventually,or at least put up the report. I’ve also been working on experiments with toll roads. My main project has been non-traffic related.

I’ve made some logistic and code changes, to make things easier for other people to use AORTA:

  1. I moved from Google Code to Github. Github is a more popular platform these days. All new code will be pushed to the Github repository. The main catalyst for the switch, though, was the massive size of the repository. I made the mistake of committing OSM maps and converted maps, leading to a 600MB repository. Absolute madness for somebody trying to download the project. So now, the git repo will just have code. I added a script grab_maps.sh that pulls down some .osm’s and .map’s from this web server. The Usage page has been updated to reflect this. If you already use AORTA and you need help transitioning, let me know.
  2. Lots of the toll-related code has been ripped out and replaced with something simpler. It’s still in flux, till we get good results, though.
  3. Driver priorities are finally floats in the range [0, 1] rather than integers {1, 2, …, 500}. Old scenario files won’t parse.
  4. You can now draw a polygon around roads in the GUI, export the list of OSM road IDs to a file, then use that as a whitelist when converting the OSM map. In other words, you can select a polygon out of a larger city.
  5. I wrote an untuned intersection policy called Batch that tries to clump drivers together. It needs lots of work still.

I have more cleanup tasks planned. I’ll be starting full-time work in August, so my primary objectives are to make this code totally solid for future people to use. Of course, I’ll always be available to help out with it.

Scala Macros for Serialization

A few days ago, I decided to play with Scala macros in order to reduce boilerplate code for serialization. Macros are regular Scala code that runs at compile-time in order to generate more code. These aren’t just text replacement-type preprocessor macros; using quasiquoting, you write Scala code that’s fully-typed abstract syntax trees. There’s quite a learning curve to using them, but the end result is pretty simple for my case. I would normally use this post to talk about them, but I’ve decided not to push the commit to the master branch yet. Some people are using AORTA through Eclipse now, and I don’t even want to begin to fight to get an IDE to handle macros (sbt requires a sub-project for the macros). Additionally, although I got rid of the boilerplate for Scenario-related serialization, doing the same for maps or savestating will be harder. I can’t just look at all fields of a case class and write/read them. I’m still thinking of ways to be clever, succinct, and bug-free here. (The motivating problem, for background, is that savestating is probably broken right now, because it requires annoying maintenance when relevant fields change.)

Anyway, the code so far is in the macros branch, but it’s not in master.

Heatmaps and road layers

Screenshot - 030714 - 14:25:45

Some new toys spurred by the GUI refactoring yesterday. I often observe drivers using only major roads, and very rarely touching residential roads to cut through and avoid jams. To confirm this, I started collecting road usage data (the RoadUsageMetric class) — the total number of drivers and the sum of driver priorities (a proxy for tolls) along each road. Then I plugged the data into a heatmap coloring scheme to get the results above. Darker colors mean a road with more high-priority drivers.

Since there’s a few heatmaps to display (different runs, different notions of road usage), I made a simple layer system, controllable by the menu shown in the screenshot. You can select and display one layer at a time.

I hope this sort of thing will help me more quickly qualitatively gauge problems with various routing schemes that’re supposed to make drivers spread out more.

UI refactoring

The UI code has long been horrible. I’ve never put much effort into it, and have readily tacked on new things. (It’s the lowest priority, after all.) Today my frustration with it peaked, so I spent a few hours eliminating dead code (about 200 lines worth) and rearranging everything. The result still isn’t awesome, but it’s much better. The organization is now (by file):

  • Coloring – driver and road color schemes
  • Controls – most responses to keyboard/menu events
  • Drawing – used to be called Content, now has stuff to draw intersections too
  • GUI – still the same as before, sets up the status bar and menus
  • MapCanvas – drastically slimmed down, but it still is begging to be split into some traits (such as one for running the simulation at a certain frame-rate). GuiState is still the context object passed around to all code to do rendering.
  • ScrollingCanvas – mostly unchanged, still a generic Swing canvas that knows how to pan left/right/up/down and zoom in/out

I had some grand ideas for what controls should look like (hint: autogenerating a little reference table of keys), but I’m not there yet. For now, this is big progress, but it was low-hanging fruit.

Pathfinding optimizations

I took a day to profile and optimize A*, since my recent experiments make more calls to pathfinding than ever. I tried out JProfiler and loved it — it can draw pieces of the call graph, centered around a problematic method, and you can trace things that bottleneck calls and who calls it. I also drew on Amit’s A* page, which has always been invaluable.

The changes were simple, and each made a measurable speedup.

  • The CurrentCongestion road agent now caches the congestion state, rather than look at a number of lanes each time the query happens.
  • Scala’s mutable priority queue is much slower than Java’s priority queue, and it’s simple to use the Java one instead.
  • Cache next_turns from a lane and the successors of a road, query methods that are called often and never change answer. It’s as easy as changing ‘def’ to ‘lazy val’.
  • The A* implementation in common.algorithms was previously generic over any node type, but since all code only uses it over Roads, I specialized things in order to investigate hashing roads. I don’t think the generic causes any slowdown, but I also don’t see a reason to make it generic again.
  • Specialized the A* call to only support one goal road rather than a set of them. The set of them is only used by zone assignment (which is itself an unused feature), and incurs a small performance penalty.
  • Specialized the A* call to only return the table of costs when requested, which is only done by the UI to draw a heatmap.
  • Rewrote the inner loop of A* to use while instead of a foreach. Foreach’s are implemented as closures and make profiling a bit harder to trace out.
  • The heuristic that guesses freeflow time was under-estimating too much, because I forgot to convert mph to m/s.

In the end, there’s nothing obvious left to optimize. In Baton Rouge, an average call expands 6,000 roads (about 1/3 of the roads). This is the source of any remaining delay. Getting rid of this means sacrificing optimal paths by using an inadmissible heuristic. I tested this by using just Euclidean distance to goal (rather than Euclid dist divided by max possible speed limit) and saw a vast improvement of 10,000 calls done in about 7 seconds, each call expanding only about 100-200 roads. For now, I’ll accept this as a trade-off: optimal paths are more important than simulation speed. There’s a trade-off triangle between optimal paths, fast routing, and dynamic edge weights — you can pick only 2 at a time. (If you forgo dynamic edge weights, you can use preprocessing techniques like contraction hierarchies, which I was doing for a while.)

So how much did the micro-optimizations help?

  • Before optimizations: 10,000 paths in 1,000s, aka .1 s/path, or 10 paths/s
  • After optimizations: 10,000 paths in 200s, aka .02 s/path, or 50 paths/s

The optimizations made the code simpler, if anything, by specializing, so a 5x speedup is totally worth it.

Eclipse finally works

Check out the Usage guide; the Eclipse instructions finally work! I’ve been requiring Scala 2.11 (a beta version) for some REPL features, but it turns out, everything seems to work just fine with 2.10.3 (the current stable) with some small mods for the REPL. It’ll be easier to keep AORTA using the current stable version, since IDEs like Eclipse support it better.

Rerouting overhaul

I don’t often batch 15 commits locally before pushing, but for the past few days, I’ve been overhauling some of the fiddliest code in order to add what I thought would be a simple feature: reroute some drivers regularly, or upon triggers beyond congestion. Notes and changes below:

  • Added a new component to each agent — a ReroutePolicy. These get to react every tick, see when the agent last rerouted, see if the state of roads has changed significantly, etc, then request an optional reroute.
  • Rerouting is split into two cases: mandatory and optional.
    • Mandatory occurs when the driver is forced to pick a turn and can’t reach the next road. It starts from a road that can definitely be reached from the current lane, and it doesn’t necessarily avoid looping back on roads at the very beginning of the path in hopes of lane-changing. As a result, it could produce long, loopy paths, but it’s guaranteed to find a path, since the graph of roads is guaranteed connected by the map making process.
    • Optional occurs anytime — when gridlock is detected, when the next road is too congested, when the agent’s ReroutePolicy wants to. It starts from the current lane and limits the successors in the first round of A* to roads reachable from that lane, and it bans revisiting roads earlier in the path. This avoids funky loopy paths (I need to draw a picture of this) where the driver loops around to visit the same road in quick succession trying to lane-change. But since the whole graph of roads isn’t available to A*, it may fail, which is why it’s optional.
  • The call to algorithms.AStar.path was a mess, with about a dozen parameters, most optional. I fixed this with a form of the command pattern and builder pattern. A Scala case class now encodes defaults for all the optional params. The advantage here is that different functions/places in the code can build up the call to A*.
  • Changing the lookahead code to rely on route.pick_turn’s idempotence less. Since pick_turn has potential side-effects of doing mandatory rerouting, it’s confusing to call it in many places and not know which is causing a reroute. Instead, in all cases, lookahead can actually look at requested tickets to figure out the path a driver will immediately take.

Along the way for my current project, I’ve improved the results/plotting system, since I’m not a fan of R, and made fixes to debugging (when you run a scenario that crashes, it drops into a REPL shell where you can interact with anything in memory). I’ll write about that after a bit more work.