How would you test Google Maps "Get Directions" feature?

Question

(I imagine this would be a good interview question, but in my case it's more pragmatic than that.)

We have a large & complex application that models an extremely long and sophisticated chemical reaction process between dozens of chemical components. We are at the stage of designing Acceptance Tests for the application, but we are somewhat daunted by the intractable number of possible paths to test. It occurred to me that our situation is very much like what the Google Maps dev team must have faced when it came time to test the route-planning algorithm in their "Get Directions" feature. Obviously they couldn't test (verify and validate) every possible route. So how did they get confidence that their application would work in every situation?

And since I don't expect to find out how they did it, let me ask you: How would you go about designing a test suite with adequate code coverage, to satisfy yourself that a given application is robust -- when it is literally impossible to probe every potential path through the system?

What I'm looking for are the principles that you would use to break down an intractable problem into smaller, tractable pieces, the sum of which provide a satisfactory estimate of the whole: "I can't test everything, but I can test this, this and this -- and that's enough." I'm not looking for an approach that is "provably correct", but rather one that is prudent, given real-world budget/time constraints.

(I'm using the Google maps example as something of a foil to solicit answers that are as specific as possible.)

Answer 1

I worked in the car navigation field over a decade ago.

Step A) Use a reference package and select a large sample set, run A/B tests. Not looking for exactness, looking for outliers - The reference set showed Reroute 1234 as 10.34km, and we calculated 123.5km.

Step B) - Refine our software and the reference software - Add more samples and reduce the tolerances.

Step C) - In house testing using local knowledge across global data sets.

Step D) UAT... "User Acceptance Test" As in "Sell this stuff and see what the customers complain about the most"

If you ever used mapping products circa Mid 1990's - 2000, you know what I mean, those of us that did still check the turn by turn directions every time.

Back to you example question. What you are being asked is how to prove that a piece of software is correct. If you want mathematical proof, it's been shown it can be done - for simple software at a price that exceeds any realistic budgets, for a complex software package, well, that is still research.... NASA has models for writing highly reliable software within economically manageable prices, as do DoD and the aviation industry - although still much higher than most are willing to pay. In the end, it comes down to how much are you prepared to pay.....

Edit : I just re-read you OP. It seems what you are looking for is a quick and cheap way to Test the quality of a complex piece of software. You cannot test in quality. You need to have a robust process so you know that what is built works correctly. If you have got to thinking about how to prove it's correct and you already have a the "large and complex application", you are too late.

Answer 2

We're one of Google's competitors. Our answer? Basically two.

First, we do calculate the complete address-to-address solution. Yup, that's a big matrix. Even worse, we do so for all times of day, all days of the week. There's sufficient similarity in the input domain to cache intermediate results, which makes the problem tractable. Still, try to get a bulk rate on harddisks.

Note that this offline calculation is done using a different algorithm. It uses far more memory than the algorithm we intend to test, but not linearly more (i.e. it uses less than 1000 times more memory when calulating a thousand routes).

Secondly, participating users provide us with real-world results. We validate millions of routes driven. Are the actual routes as fast as predicted?

And sure, you do find bugs that way. All the times. E.g. a stretch of road that's bounded on both sides by a "local traffic only zone" *. There's only one way ;) that you're going to find that in testing, and that's when you plan a route to that particular road.

_{* A "local traffic only zone" may only be used when you're starting or ending a route in such a zone. The stretch in the middle is therefore disconnected from the main roadnetwork. This is either a zoning or a map fault.}

Answer 3

It's not like google writes separate code for every pair of addresses in the world. With the exception of heuristics that kick in at a larger scale, the algorithm for a 3-leg journey is exactly the same as for a 3000-leg. You thoroughly test the shorter paths and use induction to show the testing applies to longer paths as well.

You pick a healthy sample of real-world routes, and check it against what a human comes up with. You pay a lot of attention to end user feedback in your first releases, and make it easy for them to provide it. You test the boundary conditions, like if the best route actually requires traveling away from the destination for a while, or if the shortest route by distance has 18 turns compared to a more direct route that's slightly longer. You do negative testing, like if you're trying to drive from California to Hawaii, and make sure clever easter eggs are in place.