Studied and Applied advanced heuristics to a basic version of Google Maps, which improved direction suggestions for the application users. This included changing suggested path based on traffic, type of road and time of the day amongst other features. All the features of the project are detailed below :-

a) Although side-streets often provide the shortest path based on distance, we rarely use them because speed limits are usually lower than the speed limit on major roads. In this extension, We try to pull in speed limit data from another source OR use "roadType" to make assumptions about speed limits. Then modify our Dijkstra and A* algorithms to use a trip duration rather than distance in finding the shortest path. We even further and then make predictions about traffic based on road type and time of day (which might again make side-streets a good choice over arterials.)

b) When multiple people search Google Maps, it's likely to have some commonality in the searches. For example, if there's a concert in downtown San Diego on Friday night, there will be a number of people searching for directions to the concert venue on Friday afternoon. Each person probably has a unique starting address, but there is a likely commonalities in the paths (e.g., multiple paths to get to the main freeway to downtown, followed by the same path from the freeway to downtown). Rather than redoing the entire search every time, we store previously found shortest paths between vertices. As a result, the first search downtown may take a while, but when the next person searches, they'll use part of the previous solution in the solution.

Share this project:
×

Updates