I was on I-70 in Maryland on Sunday, going to Alexandria, Virginia, along with a lot of others. I was using Google Maps for navigation. When I could look down, the route was looking red, indicating congestion and delay. Eventually, Google said, "We have an alternate route that will save you a half hour. Want to take it?"
Of course I said yes. So I took the next exit, went down some rural highways, through a small town and almost down someone's driveway, it seemed, and back onto I-70. I called it a win.
The Friday after, on my way home, it rained all the way through Maryland, West Virginia, Pennsylvania and Ohio, and well into Indiana. It occasionally rained hard enough that I started seeing other drivers turning on their hazard lights for others to see them, and I followed suit.
A truck had crashed in western Ohio, closing westbound lanes, and Google told me it would add an hour delay, but when it routed me through five miles of county roads to the next on-ramp, it was closed. I knew it -- I saw the chain across the road -- but Google didn't, so I alone, without a line of other vehicles, bird-dogged a route to the next on-ramp with Google urging me to make a u-turn every few hundred feet.
This made me think about what's actually going on inside the navigation feature of Google Maps. It starts in graph theory, establishing the US road system as a directed graph with weighted edges, showing Interstates as preferable to highways to county roads and side streets, and using Dijykstra's shortest path algorithm to find the best route.
In graph theory, everything is either a node or an edge. In this case, a node could be the intersection of 6th and Main, or the fork where I-70 splits off to I-270. The edges would be the road between 5th and 6th on Main St., or the long path between exits on the Interstate. In other uses of graph theory, the nodes are most important -- Facebook Users being nodes and their friendships being edges in Facebook's Social Graph -- but here, the information about the edges is the important part.
This is similar to how we used to do it, looking at a paper map and preferring Interstate for long-haul routes, judging this road or that road as preferable due to scenery or a hundred other criteria, dropping to surface streets only to get through the final few miles. But, Google knows this road gets gridlocked at rush hour and that one is under construction, which you can't tell from your ten-year-old road atlas, and has a huge body of historical data that allows it to present alternate routes and the estimated time difference between.
The increasing amount of data helps it properly weigh edges and make connections. Early in my time with Maps, it suggested I go from Lafayette to Ft Wayne through Indianapolis, which would actually add an hour to the trip, because it had weighted the Interstate so highly. Now, it properly suggests two east-west routes and avoids the southern detour entirely. Similarly, an intersection near work is right-turn only, and it took some time for Maps to not suggest a left turn.
Maps re-calculates the route often, which is why, after a time off its path, it still says "fastest way is behind you; turn around and go back". When you're just stopping for gas, it's a little annoying, but when you see that the highway department has blocked the suggested route, you wish it would just shut up and get with the program. I'd have to take more trips where I'm not the driver to really tell, but I would guess it re-runs shortest-path several times a minute. My guess is there are waypoints, places along the route between here and there, so Maps tries to find the shortest path between them, rather than rethinking every turn in your 600-mile journey, which makes this faster and more predictable.
Maps has a lot of data for each section of road, showing how many drivers use it and their average speed, as well as the posted speed limit. If the drivers are going slower than average and slower than the speed limit, that indicates there is a problem. In the Ohio case, the Department of Transportation must have reported that the reason was an accident, but to paraphrase Scream, causes are incidental. What's important is knowing where things get back to normal, and if cars aren't there, then Maps has no way of knowing where that is and what on-ramp is open. This is guesswork of the highest order, but in a week where my every movement was guided by Maps' algorithms, this was the only point of failure.
When I took that detour in Maryland, I was not alone; I counted at least eight vehicles taking that route along with me. Google offered me the choice, but this can't have been an option for every driver on a backed-up highway. I think there must have been a process of A-B testing, where some were rerouted and some were kept on the main road, and it used this information to decide where to send drivers later.
I don't often take these long drives, so it may be a year or two before I'm so fully in the hands of Google Maps and on such a dynamic journey, but I expect the experience to be even better.
No comments:
Post a Comment