Miami is the land for tourists. We are stormed with hundreds of places to visit once we are in Miami. So an idea stuck us to why not use a computational graph problem to find us the places and recommend us few places to visit while we are in the certain area.
What it does
Our project takes the city name and number of places to visit as input and gives out the itinerary with optimal time to cover all the places. We fed the itinerary to Alexa to speak up for us!
How I built it
We first brainstormed various graph problems to solve this idea. Starting with Dijkstra shortest path, Minimal spanning tree and we ended up with TSP. We solved the TSP approximation algorithm in python using dummy data. After all the bugs from algorithm are taken care of, we took data from google places API to give us the edge weights for each edge in the graph. The whole implementation happens on AWS lambda whose output is fed to Alexa for speaking with us.
Challenges I ran into
Narrowing down our problem to a TSP was our first hurdle. We came across the journals that solve TSP with various variations. We came up to solve Hamiltonian approximation to TSP would give a 3/2 approximate solution to NP-hard problem. We implemented TSP with python and a 2D matrix as our graph representation as this will be a fully connected graph. After solving TSP for a dummy data we used Google map API to get real-time data. Integrating google's API with AWS cost us a lot of time as the access to API would expire with less than 20 tries.
Accomplishments that I'm proud of
None of us had prior experience working with Alexa or Google API. Coding a graph is a place we were comfortable with. We were proud to get graph algorithm running and feeding it to Alexa using Google's API is something we can boast about.
What I learned
We learned how to get an Alexa skill up and running using its rival's API.
What's next for Na'viGator
In the 36 hours time frame we got, we were not able to touch an users interest, his current location. Recommending places near to him is na'vi's next goal. Graph weights could be adjusted with the person's interest also. That would be a good machine learning problem to solve.We were also limited by our knowledge working with Alexa skill. Exploring more with Alexa and lex API from AWS would get na'vi to its full potential usage. Solving TSP's in different places and integrating them with a greedy choice can be used to solve world TSP although may not be optimal.