City-Navigation-AI

Implemented a Google Maps prototype that provides the shortest route in terms of distance, the fastest route, the route with the fewest turns, and a scenic route that avoids roads when provided a source and destination. The algorithms used were DFS, BFS, A*, and Iterative Depth First Search.

Approach to Road trip!

Abstraction:

1. Segments:The cost for this is uniform 1 since we have only one edge from city1 to city2.
2. Distance: The cost for this is the distance between city1 and city2 which is specified in road-segments file.
3. Time: The cost for this is the time taken to travel from city1 to city2 which is evaluated by distance divided by speed_limit provided in road-segmensts file.
4. Delivery: The cost for this is the time taken to deliver a product from city1 to city2. This will be evaluated by following conditions.
   • If the speed_limit is above 50 then there is 5% chance of falling out of the truck and the product gets damaged. So, while using this the probability of mistake is calculated as tanh(distance/1000)
   • So the time taken would incrase by two times because he has to go back to start city and pick the product.
   • If the speed_limit is less than 50 then there is no extra time_taken to deliver the product.

1. Intially by using pandas module loading all the data from specified files to get road-segments and gps details and converting them to lists for better accessing. As mentioned, including the bidirectional condition as well.
2. Calculating the time taken for all segments and mistakes for delivery cost function and adding to the list.
3. Adding the start city into the frontier(fringe)
4. Maintaing explored routes which is empty at the initial point.
5. Looping till the frontier is not empty:
1. Pop the latest city using heappop method in heapq module which gives the minheap board which has less f_score.
2. Checking whether the board popped is the destination city. If yes, the return and print the segments, distance travelled, time taken and delivery.
3. Otherwise, add this segment to explored list
4. Generate all the successors segments for this current_city.
1. For each successor route, calculates the F_score which is the sum of heuristic score and cost function based on cost_attribute.
2. If the successor route is not in explored and not in frontier, then heappush the board into frontier with f_score of travelled route.