DRMacIver's Notebook
Adaptive planning and grid systems
Adaptive planning and grid systems
Consider, if you will, a perfectly flat city laid out in a perfectly even grid, aligned with the compass directions.
Suppose you are at grid reference (0, 0) and want to be at grid reference (10, 10). You ask Google maps for a plan. What does it say?
It will probably tell you something like “Go East 10 blocks, then go North ten blocks”.
This is somewhat unintuitive but correct. You naturally think that the shortest path between two points is a straight line and want to do a sort of diagonal where you go East, then North, then East, then North, then East, etc. or something like that, but on a grid system this doesn’t buy you anything because each time you go North or East you travel exactly one block, so every route you take must be exactly 20 blocks long. There is no route to your destination shorter than 20 blocks.
Also, a human ignoring Google maps will get there sooner than one following it.
Here is the correct fastest algorithm for getting to your destination: Every time you are at an intersection, if there is a green light for going either North or East, and that is a useful direction for you to take (i.e. if you’re still South of destination and there’s a North light, or if you’re still West of your destination and there’s an East light), take it.
Following this algorithm doesn’t reduce your travel distance. It doesn’t even significantly reduce the amount of time you spend actually driving. But it significantly shortens your wait times along the way.An interesting feature of this algorithm that I can’t decide if it is a coincidence or not is that the resulting path will look a lot closer to the straight line that you might have intuitively drawn.
The thing about this algorithm is that it’s completely outside of Google Maps’s ability to give you this plan. It’s not just that it’s not a thing it considers, it’s not a thing that it can consider, because there’s too much variability to predict exactly when the lights are going to change on your journey, even if it had precise timing data. This is however no problem for following the algorithm, because it is adaptive - it takes into account the information that you have access to at the time of making the decision but do not have in advance.
Planning in advance is very useful, but it will always lack access to this sort of on the ground information, and you can often improve on purely up front plans by introducing an adaptive element to it like this..
The flipside of course is that we were able to do this here because the decisions we confront in navigating a grid are easy. Trying to make hard decisions adaptively introduces a significant cost to executing the plan. One of the most important things to decide in advance is how you are going to make decisions on the fly.