The road to better path-finding

Posted by Barry Brumitt, Software Engineer

Way back at the end of 2005, Google Maps' driving directions were on par with other sites, providing basic driving directions in a few seconds. But the nature of the existing system made it nigh impossible to make it faster, add new features, or improve the quality of the routes. And better directions can yield tangible real-world benefits by saving people time and fuel, alleviating frustration, and making travel more pleasant. For all these reasons, it made sense to take a fresh look at the problem and to try to reinvent things such that we could provide a service markedly superior to the status quo.

It's important to us to solve big problems. Automatically finding routes quickly is a hard problem -- especially at a global scale (there are several hundred million road segments worldwide). Even if a routing program is needed to only look at 10% of the map and only examine each segment for a microsecond, it would take tens of seconds to compute a path. Route-finding has to be done automatically because it would be impossibly time-consuming to compute the best routes between all pairs of locations by hand.

Fortunately, we have the tools, technologies, and expertise that make it easier to tackle such hard problems and to build systems for searching large data sets quickly. A small group of engineers (of which I was a part) created the Google Maps route-finding project in Kirkland, WA with the hope of building a world-class system for route-finding. This is the first project I've worked on at Google, and it has given me the opportunity to learn all about the infrastructure we have to build and launch products and features.

We started with the geographic data sets already in use by other groups at Google. Then we designed, built, tested, and deployed a complete route-finding solution in under 12 months. Commutes across the 520 Bridge from Seattle became a favorite test query. As someone with a background in path planning and robotics, it's been great to work on a problem with such substantial theoretical and practical aspects. It took 10 months of hard work, thousands of MapReduce passes, and an uncountable number of lattes to complete.

And 'complete' doesn't really capture it. Our new route-finding system is hundreds of times faster: it can find and describe a cross-continental shortest path in well under a second. Shorter paths can be found proportionately faster.

As evidenced by our 'draggable directions' launch earlier this year, this kind of performance fundamentally changes your Maps experience. It's now possible for you to change your route by simply dragging it or its endpoints. (Here's an example of the above route adjusted to use I-90 instead of WA-520.) No other planning service provides this feature, and it would have been impossible to ship without the massive speedup provided by the system we created.

In the last few months, we've also added other features, like 'avoid highways' and 'estimated time-in-traffic.' Plus, we now cover about 50 countries worldwide. We've raised the bar for what a route-finding system can and should provide. We're pleased with what we've built, and you can expect further improvements in the coming months.

Just recently, the Google Maps route-finding team moved to our new Fremont Engineering office. I'm happy to report we don't have to commute across Lake Washington at all anymore. In fact, nearly half the team cycles in every day! And we're always looking for great people, so if any of this sounds like the kind of challenge you'd be up for, we'd love to hear from you.