by Vas Mylko
In this post we will describe the complexity of the problem, that we are solving, with some details and visualization. Let’s recall the problem statement first.
Problem Statement
We like the wording by famous traveler — Artemy Lebedev. He traveled a lot, and he continues to travel. Below is his Facebook post, translated to English.
“Composer. I want this service — I enter places in a city, it makes a plan. Or I enter cities that I want to visit, and it builds a route for me. Or I name the countries, and it tells how to better and faster visit them. This service must do it all within time and budget constraints, these are two main parameters. There is nothing even close to this out there. Many could show [as maximum] options from point to point. But the future is in organization of relations between N points.”
He is rich enough to travel a lot. If you want to know how people will travel in the future — look how rich travel today. In the years to come, more people will be able to travel more. It’s normal evolution of technology and society — what was possible today for rich, will be possible in the future for others.
Traveling Salesman Problem
Traveling Salesman Problem aka TSP asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. Vehicle Routing Problem is generalization of TSP.
Dr. Randy Olson, Lead Data Scientist at Life Epigenetics, is doing advanced data science and machine learning technology to the life insurance industry. Besides that, he is running experiments in travel. In one experiment he takes a list of “50 Places In Europe You Need To Visit In Your Lifetime”, put’s them on the map, and finds the fastest route between them all. Here are links to few his experiments; make sure you click them to read how he does it.
Computing the optimal road trip across the U.S.
Computing the optimal road trip across Europe
Computing the optimal road trip across South America
Recently, Chevrolet teamed up with him to compute an epic family road trip, to visit family-favorite attractions in 48 states in US. So far we are dealing only with time optimization between fixed list of points. We will address budget optimization, and uncertainty with points soon; let’s elaborate more on time optimization, it worth it.
Google Maps & Google Trips
Ever wondered why Google Maps don’t calculate more than 10 waypoints? It’s because of complexity and too high cost of computing. With 50 waypoints the number of possible routes is bigger than 10⁶⁴, which is more than 10⁵⁰ years of computing on desktop chip to evaluate and compare them all. Server chips [cores] are usually slower than desktop ones, so it’s even longer in the data center. Check out details on search strategy, with cool ballparks how crazy long it is.
There are free and commercial services allowing to compute up to 20 waypoints, and more. E.g. https://www.routexl.com is free to 20 points or less, but is pricey for more. This computing handles time optimization only.
Getting More Complicated
We deal with countries and geo regions, cities and POIs. First complication happens to TSP — there is no list of points known in advance. Second problem is budget optimization. Geofencing is a third problem. Here we could name it Constraint Satisfaction Problem aka CSP. Altogether, it’s time and budget simultaneous optimization with unknown list of points in geofenced area of irregular shape…
The challenge is real, it keeps us [mentally] fit. We, as researches, know how to approach hardest problems. We, as engineers, know how to make it work. We have to tame complexity. It’s difficult, it’s expensive, but it’s doable. In the years to come it will be more affordable. Our tech must be ready by then.
There is good progress, check out our recent recordings from the lab. Below is one of those recordings: simultaneous optimization in irregular geo region by time and budget, with desired travel through points, unknown all waypoints, and unknown POIs per waypoint.
Strategy for Complexity
Artificial Intelligence or Artificial Smartness is possible, if it is built with multiple layers, layer by layer, until breakthrough moment, when it becomes smart. Check out the Scale of Everything. It’s a foundation law, how complexity increases at next scale, based on the simpler previous scale.
Inspiration comes from evolution of biological complexity. Living organisms are Complex Adaptive Systems aka CASs. Although complexity is hard to quantify in biology, evolution has produced some remarkably complex organisms. At the low level the genetic information is encoded as DNA (sometimes RNA) in cell Nucleus and Mitochondria. There are strict rules how big molucules bond to each other. There are nanorobots (Ribosomes), that read genetic information, and build other things, that sometimes become nanorobots themselves. Check out Kinesin robot. Check out ATP synthase. Those tiny robots build bigger entities, machines and resources for machines, adapt to the contraints (environment), until they build a human body. OK here, we are building a CAS for travel; travel intelligence will emerge from it.
Complexity from Simplicity
How such complex visual structure appears on the shell of the widespread cone snail species Conus textile? What kind of behavior in nature makes it? There is no symmetry. It’s hard to predict. But there is obvious recognizable pattern from triangles of different sizes with same orientation.
This complex pattern could be created by evolution from simple rules. If direct ancestor was dark, and two cells around it were dark, then the offspring will be light. If all three ancestors where light, then we offspring will be light. There are six more simple rules. All eight rules are shown below:
This was researched by Sephen Wolfram, and is known as Rule 30.
There are other cellular automata, demonstrating complexity from simplicity, added during evolution. I’d like to mention Rule 110.
Rule 110 is famous not because of those triangles. Rule 110 is famous by its ability to build a cyclic tag system, which is Turing complete. That cyclic tag system can encode and run any calculation, or computer program can be simulated using this cellular automaton. Below is snapshot after more evolutions, at different orders of magnitude: simplicity created complexity.
Check out what Rule 110 builds from 3,228,176,000 cells. There is initialization, construction, reading, erasing of elements, all encoded into the cyclic tag graph. It’s possible to construct NAND (inverted AND) or NOR (inverted OR) gates on those cycles. With NAND (or NOR) it’s possible to construct all other logical gates. Having all logical gates we got a computer. Recall that’s all started from the simple rules, and went through evolution.
Conclusion
We strongly believe that it’s possible to create smarter and smarter intelligence, with each added order of magnitude, by evolving from the simple first rules. With several added orders of magnitude, the emerged intelligence is noticable. With more orders of magnitude you start to respect that intelligence. This is amazing and thrilling.
This is also cool, because it’s applied to travel. What would you do if you got everything? You would travel. Think of this. With our AI tech you could travel much more, and travel much better. This AI is benevolent, good.
