Artificial Intelligence Designs Ultimate Road Trip
Drive to 48 state capitols in just over a week using the mapping power of machine learning and genetic algorithms.
Loyal readers will recall that last spring we conspired with artificial intelligence expert Randal Olson to develop the ultimate U.S. road trip. The map Olson came up with -- he did all the work, really -- optimized the best way to drive by car to 50 major U.S. landmarks, using machine learning algorithms and Google Maps.
We're happy to report that Olson is back at it, just in time for summer road tripping. His new project maps out the most efficient route for visiting all 48 state capitols in the continental United States.
By leveraging the power of genetic algorithms and other artificial intelligence technology, Olsen's optimized loop route will get you across the country and back in a little over eight days -- starting in Concord, N.H., and dropping you back in Boston, Mass.
How did Olson generate his road trip map? Well, if you're interested in the heavy-duty technical details, you can read Olson's latest blog post on the project. But here's the basic gist:
Using the free Google Maps API, Olson acquired a rather massive chunk of raw data -- the point-to-point driving directions between all 48 state capitols. That's 2,256 individual sets of directions. Armed with these, Olson set his algorithms to work solving the traveling salesman problem: Given 48 different destinations, what is the optimal sequence so that total distance traveled is as short as possible?
WATCH: THE CANDOURIST: Back On The Road
"With 48 landmarks to put in order, we would have to exhaustively evaluate 1.24 x 1061 possible routes to find the shortest one," Olson writes on the project page. "To provide some context: If you started computing this problem on your home computer right now, you'd find the optimal route in about 3.98 x 1049 years -- long after the Sun has entered its red giant phase and devoured the Earth."
That seemed a tad long, so Olson unleashed his genetic algorithms. Based on concepts of biological evolution, genetic algorithms use a kind of natural selection process to get results. In this case, they delivered optimal driving directions for hitting 48 state capitols in about a week.
"Instead of exhaustively looking at every possible solution, genetic algorithms start with a handful of random solutions and continually tinker with these solutions -- always trying something slightly different from the current solutions and keeping the best ones -- until they can't find a better solution any more," Olson writes.
So there you have it: Better road-tripping through technology. The state capitol trip is designed so that you can start anywhere along the route, follow the loop, and end up back home secure in the knowledge that you were as efficient as possible. As an added bonus, Olson even threw in a quick jaunt to Washington, D.C., without adding any extra miles.
Have fun! Take pictures!