Intelligent Navigation System to minimize Traffic jams due to Second-Order Chaos
An improvement of Google Maps by Ayush, Jai, Pratham, and Riyaan
You get into your car and punch in your destination into Google Maps. A central server proceeds to compute your travel - accounting distances, speed limits, and current traffic on various routes - and then pings back optimal routes for you to take. Two routes show up - one taking the freeway, and the other a longer suburban road.
You set off on your journey, heading uptown via the faster freeway, but alas! You find yourself in a massive congestion riddled with Google Maps users who inadvertently created a traffic jam. You sigh, pondering if you could have avoided this, had you left 10 mins later - after Maps knew about the traffic. You sigh again, now enviously looking down as cars cruise below via the longer suburban route - knowing they'll probably reach long before you.
But what if it didn't have to be this way? What if the massive clientele of Google Maps users had instead been intelligently directed to prevent a jam from forming in the first place? And what if a few people were made to sacrifice a few minutes of extra travel to create a shorter journey for all commuters as a whole?
This is where Giggle Maps steps in.
What it does
Giggle Maps (trademark pending) is an intelligent navigation service that supplies not just the optimal path for individual users, but optimal paths for the entire real-time user-base to minimize everyone's travel times. It does so by taking into account not just existing congestions, but perceiving traffic jams that it might inadvertently cause by prescribing overlapping routes to many users This would mean that people who travel before others may get stuck in a traffic jam, even if people who travel later get a route that now avoids the newly formed congestion.
In the example described in the Inspiration above, had some users chosen to take the slightly longer suburban route, the freeway would not have been over capacitated, and more people would have arrived earlier. To do so, Giggle Maps runs not just a traditional Dijkstra's algorithm to search for paths, but a "Distributed Dijkstra's Algorithm" which can track road traffic that its own directional prescriptions would cause, thus creating an optimal navigation experience for all users.
Currently, we're taking the increase in the weight of an edge to be linear to the number of users on the street. However, this can be replaced with any monotonic function that best represents a road's ability to hold cars (width, car limits, etc.).
Challenges we ran into
Computational complexity was something that was difficult to optimize. Our current implementation is a simplified but scalable version that runs in O(T⋅N⋅[V +E⋅log V] ) where (E, V) is the graph and N is the number of users and T is the time taken for all users to reach their destination. However, we do believe that by implementing a more advanced state-space A* search algorithm with a good heuristic (involving summed Euclidean distances and regional user-density), the complexity can be reduced significantly.
Check out our algorithm!
What we learned
In a short span of time, we managed to learn Dijkstra's and implement a version with dynamic edges. Although the implementation we've currently hacked together is not immediately scalable, it can easily handle thousands of clients with a fairly complex graph (analyzing hundreds of possible Google Maps routes). We've also planned to implement more computationally efficient alternatives to our algorithm.
What's next for GiggleMaps
Integration with Google Maps, and porting the algorithm onto an app are the next steps. For the app to indeed prescribe efficient paths, a critical number of users must be reached such that the app can truly optimize traffic flow. Until then, the algorithm will assume that the edges are subject to regular traffic (based on Maps data).
Another addition to the algorithm would be to prioritize users with urgent needs (ambulances, premium GiggleMaps Gold users, etc.). Tweaks can be made to the existing algorithm to do so.
Accomplishments we're proud of
What we're most proud of is that we were able to implement a considerably complicated algorithm while being spread across multiple continents and timezones. Being rookies, we had to navigate (without help from our own navigation service) the hackathon's themes, Github collaboration, brainstorming on Zoom, and countless other problems for the first time.