Project: A* algorithm on google maps to find shortest path (googlemapsastar)

Data:

• Data has been extracted from OSM.
  
• It contains ~27k nodes and ~63k edges
  
• Bounded by :- min: (40.4961000, -74.5015000); max: (40.5333000, -74.4143000)
  
• More on data:
  • Data provided by OSM is in .osm format, which is nothing but the XML file.
  • Converted this file to lighter XML (.graphml) file, which can be parsed easily as compared to .osm. Code
    
  • Used OSMNX for this -> OSMNX Documentation
    
  • This .graphml file will be used for rest of the tasks.
    
  • convertJSON.py is helper class which contains all the methods which we will be needed to achieve the task.
    
    • getLatLon - to get latitude and longitude of a node by passing its OSMId.
      
    • getOSMId - to get OSMId of the node from its latitude and longitude.
      
    • calculateHeuristic - gives heuristic value from the given node to destination.
      
      • Heuristic used:- Haversine (also called as "As crow flies" distance.)
        
    • getNeighbours - it generates all the neighbours of the given node(given its OSMId).
    • getNeighbourInfo - helper function to extract informtation of the particular neighbour while implementing A*.
    • getKNN - it finds K-Nearest Neighbour(s) of particular node (given its coordinates).
      • Why do we need it?:-
        • Application allows users to select any marker on map. So, there might be case that marker selected by user is not present in nodes of our .graphml file. So, in order to make algorithm work - I have used KD Tree library from sklearn
          
        • The first index of the output given by KDTree is the most nearest node to the given node.
          for example: if we were to find nearest neighbour of the point (40.48834484237183,-74.4464808486693), which is not there in our .osm file. Then output will be [0.00662018 0.00676685 0.00680585] and first index of the output is nearest and corresponding node is (40.492516, -74.4413367).
    • getResponsePathDict - helper function in order to get the final path from source to destination.

Algorithm: A*

UI:

• Used Google Maps API to render the map. Also map is bounded by the co-ordinates using which OSM map data was generated.
• You can click anywhere on the map. The first mouse event recorded will be treated as Source and second will be Destination.
• In order to generate output - click anywhere on the map. It will call the API developed using Flask.
• Path will be displayed by marker with "drop" animation.

Output:

• Due to larger number of nodes present in a map-snippet, A* becomes really slow. As it highly depends on branching factor : O(b^d)
• Hence, it works really well when source and destination are placed nearby.
• Consider below example:
  • Source: (40.49840455168209, -74.44476100847496)
  • Destination: (40.49923169717668,-74.4478649066509)
    • Output generated by Google Maps: Cost:- 0.4828 km (0.3 mi)
    • Output generated by A*: Cost:- 0.337249 km

• Time taken: ~9 seconds. Pretty Good.

P.S. : Hit me up if you have any doubt.