by Vas Mylko
Intro
Most our friends asked for some viz of the concept, and most geeky ones asked about AI role. In this post we’ll briefly answer those two questions.
There are more than a dozen definitions of value from travel. We are going to multiply your individual value by 10x, maybe by 100x. It’s an opportunity for us to build something good and cool. It’s an opportunity for people to travel better, despite [always] scarce time or budget or both.
To automatically assemble a trip in specific geographical area, starting and ending in specific cities, with proper collections of POIs in each city, with proper routing between the cities and within each city, for specific trip duration and budget, we have to solve one of the hardest optimization problems in the world. It’s what we are working on right now.
Example
2 Tourists asked for 24 day trip within $6000–6500 budget in Switzerland, Liechtenstein, Austria geo region [identified by cities and destinations]; by good car from Geneva to Vienna via Bern, Zermatt, Lugano, Vaduz and Graz waypoints, without specifying any POI within those waypoints or start/end locations; tourists wanted good comfort at the cities and destinations of stay, good food during the trip. The algorithm assembles the rest of cities and destinations automatically, fills them with POIs, routes between them; all this within requested time and budget.
Zurich, Meyrin, Salzburg, Innsbruck were added automatically, and entire route was arranged for optimal ride. If you take each proposed POI, sum the time required to experience it, admission, routing and time and cost to move between all POIs within each city/destination, time and cost between cities/destinations, cost of good sleep, cost of good food, cost of car rent — you will come up with 24 days and ~$6000–6500. And there will be no other better route between Geneva and Vienna under those conditions. Furthermore, there will be no other better collections of POI in each waypoint. There could be similar (as good) alternative routes and POI collections though. We are going to give you alternatives for each trip search.
Complexity
The most notable characteristic of NP-complete problems is that no fast solution to them is known. There is no known efficient way to locate a solution in the first place [as of today]. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. Determining whether it is possible to solve these problems quickly, called the P versus NP problem, is itself one fundamental unsolved problem in computer science [as of today]. In NP-Complete case P=NP, in other words each sub-problem of NP problem is NP itself.
The decision version of TSP is NP-complete problems itself. It’s possible that the worst-case running time for any algorithm creeps superpolynomially with the number of nodes. The decision for specific list of nodes is another problem over optimization problem between the given nodes. Optimization of the overal trip by multiple objectives is additional big problem, a CSP. Altogether — discovery of the trip route, optimized by time and budget simultaneously — is NP-complete problem.
Approach
We envision that it is possible to attack and solve this problem with AI; with vertical AI, specifically bred for the travel domain. We’ll have to create a whole new technology that could work good enough, especially quick enough. Architecturally, we have to build a Knowledge Graph, Geo Engine, and Intelligence on top of KG and Geo. We described some deeper details in previous posts It Starts From Data and Geo Engine. Inter-city and intra-city transportation and routing was described in Touristportation After 2020. In this post we will describe some details on Intelligence. The approach for building Intelligence consists of two strategies: reverse engineering of existing knowledge and building new knowledge.
Future
“Most of the knowledge in the world in the future is going to be extracted by machines and will reside in machines.”
— Yann LeCun, Director of AI Research, Facebook
For our mission it’s not enough to only extract the knowledge and store it. It’s only first half of the mission, that we must do, to make what we want to do — to build new knowledge. It’s a second half, and it is more like what Stephen Wolfram calls the computational universe, computational mining. It’s going to be an AI plant, generating AI, like power plants generating electricity. The AI plant takes data and creates intelligence. The AI plant looks like a data center. At least one rack is needed. En face one rack looks very much like a black monolith from Space Odyssey 2001, check What’s in the Name. We will have to build the AI plant, and will generate AI from it. Also it worth to augment LeCun’s statement with knowledge generation.
“Most of the knowledge in the world in the future is going to be extracted by machines, will be built by machines and will reside in machines.”
— Ingeenee
Reverse Engineering
The cities, destinations, POIs data is poorly structured or semi-structured, so we make it structured, to be included into the knowledge graph. Machine Learning, Statistics and Fuzzy Logic are used for data classification. We need raw POI properties, such as type, time, cost, geo, i.e. travel atoms, to be able to build something bigger from those travel atoms. Preliminary results are encouraging, with F1 scores 85+ percent, for several properties that we are working on. So far we don’t use NLP, but we periodically consider it. Most probably we will start applying NLP for cracking POI availabilities: seasonality, working days, open hours.
New Intelligence
Intelligence is ability to see the future. The more firmly and further intelligence sees the future, the stronger it is. Could we see how the travel could possibly work, more optimally than today, based on raw properties of the travel atoms? This is discovery problem. This knowledge could be unlocked by Evolutionary Computation. We believe that complexity is built from simple rules. Like simple rules encoded into our DNA defines synthetis of more complicated things (proteins), which adapt to the environment (fold), and participate in creation of nano-machines, which unite together and adapt to the environment, to create even bigger complex entities, such as a human body. Adaptation allows complex systems to keep together, to be alive, to be intelligent. Travel environment consists of rules, domain rules. That’s why it’s important to verticalize AI — to make it adaptable, to create a universe for intelligence to evolve and spread in it as a CAS.
Testing
How to ensure that proposed trip is good? How to validate nice look, aesthetics, routing to the scenery edges (land-water, land-mountains, rivers, canyons)? The shape of the route, density of waypoints, routing through relevant geo areas, and other humane properties of the trip could be tested by ConvNets. Human efforts required to label the data for training. That’s why Amazon built Mechanical Turk — specifically for manual labeling tasks…
Scaling
In travel startups scaling of content and geo coverage is top priority. In other words, the critical mass of the content is big. It could be more than 20,000 cities worldwide, according to research in the industry. If the critical mass is 20K, then average is higher, and relevant is even higher. The relevant number could be 200,000 cities and destination, all with POIs, experiences, and other attributes. The cap could be even bigger, ~400,000 or so. There are ~50 cities with over 10M population, ~500 cities with 1M population, 1000+ cities with 0.5M population, all full of POIs and experiences.
How the algorithm and machines could tame the scale? What’s next in the directed graph, learnt from similar directed graphs? Could new knowledge be discovered via cheaper computation than the critical mass of new foundational travel intelligence? We think so, we’ll apply Markov Chains, Recurrent Nets and Reinforcement Learning (whatever performs better on our graphs) to scale intelligence by orders of magnitude — to all 400,000 cities, destinations, towns on our entire planet. And Probabilistic Computing considered as promising approach for scaling problem.
Vertical
Why travel? Well, it is possible to apply this approach to another domain, e.g. take healthcare as a silo, i.e. enforce different environment for AI, and get different CAS in the end. But health data is not open. Health market is very regulated. While travel data is out there, except availability, and data quality is good enough to start from. Travel is harder to commercialize than healthcare in short term (see Scale section), but B2B deals work well. Big businesses with established userbases push on enriching their offers. Their global promise shifts from distribution to experiences, and everything is getting digital. We fit there.
AI will deliver core value. We are not taking travel and bring AI there. It’s vice versa — we are building AI and silo it for travel. It’s a vertical technology, it’s a full stack product. From user problem from the interface that solves for the need all the way down the stack to the functionality, models, proprietary data and special infrastructure, that powers the user interface. Best explanation of importance of Vertical AI by DCVC Bradford Cross here, especially for startups.
Sanity Check
Our mission is very ambitious. It’s high-tech. It’s not pop in AI yet. But it will be in several years. We love our mission. Is it sane? Could this technology be built in Lviv? Will we need scientists in residence? Is talent present? The answers are yes, yes, yes, yes. We will have to participate in education of AI and CS students, to contribute into our future with cutting edge stuff. It’s already started in two universities, though episodical. Will be started in third university. And will be continued in all three regularly.
One more thing. Once upon a time, not long ago, in late evening in NYC, R&D guys Vasyl and Alex occasionally met one of the greatest minds on our planet Peter Norvig, Research Director at Google. We walked together for a while, that stood and continued to talk, about many aspects of AI, current and future. We talked about the man without brain with low normal IQ, about the man with seven seconds memory, elephant and bird brains, Elon Musk’s cocktail meetings with Larry Page and unknown somebody else at some secret appartnment in Palo Alto, The Master Algorithm, quantum chips, the present and the future of intelligence. Peter is very practical, like true engineer. If something works and solves some problem, then use it. We asked him, what he dreams about. It happend to be next OS like HER. He asked us what we’d like to do next, and we described the problem we want to solve, with this approach. Peter blessed us around midnight. So let’s build the Thing.
