Heuristic for an A* Path Finding GPS

Question

I'm developing a GPS system and to do that I'd like to use the A* algorithm. I have a graph where the vertex are the source / target and the edges are the streets. For that I have a database with following info:

id;"Street Name";source;target;GeoCoordinateX1;GeoCoordinateY1;GeoCoordinateX2;GeoCoordinateY2

Each of these lines represent an edge. Using the coordinates the aim is using one path finding algorithm get the shortest and fastest path. I already developed djikstra algorithm but now I'm trying to find a really good heuristic.

I'd like to know if there's an heuristic that is more accurate or efficient. I read that I could use Manhattan, Euclidian or Diagonal distance. I think Euclidian would be a good choice but then the cost of the g funciton wouldnt be the same of the heuristic funcion h. I'd get the shortest path but it'd take longer. Is there any way to get the good and the profit?

Best regards

You neither develop a GPS System (probably a GPS app, or tracking or navigation system), nor do you want to find GPS . Probably you want to match a "geographical coordinate" received by GPS to a street graph and then calculate some shortest path from the point to a destination point (graph element), etc. You should express better what you want. Especially between the second and third sentence there is much information missing. You could assign to each link the geoghraphic length, in advance!, and use that as distance metric. No need for Manhattan (useless). — AlexWien, Apr 26 '16 at 21:02
Thanks for the update. Shortest path algos use a cost function for each street (node / or link in the graph). Your question is which metric to use as cost? Manhattan distance, euclidean distance (does not work well since it is geographic distance). (Navigation systems use the average number of seconds needed to drive through the street, as cost) — AlexWien, Apr 27 '16 at 15:01

score 1 · Answer 1 · edited May 23 '17 at 11:59

For most coordinate based pathfinding, the cost function used in A* is 'distance'. Each vertex in your graph is a gps coordinate along a street, so the distance between each vertex is calculated like this using the Haversine formula:

function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) {
    var R = 6371; // Radius of the earth in km
    var dLat = deg2rad(lat2-lat1);  // deg2rad below
    var dLon = deg2rad(lon2-lon1); 
    var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
            Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * 
            Math.sin(dLon/2) * Math.sin(dLon/2)
    ; 
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    var d = R * c; // Distance in km
    return d;
}

function deg2rad(deg) {
    return deg * (Math.PI/180)
}

In order to find the fastest path, the cost function will be 'estimated travel time'. In order to calculate this, you need the 'speed limit' for each edge between vertices (street), as well as the distance calculated above.

The cost function is very simple: cost in hours = distance / speed = km / (km/h)

Google maps has an API to find the shortest/fastest paths for many different modes of transportation, and it will save you a lot of effort. It also takes into account traffic, bus schedules and other factors that would be difficult to consider in your project.

If this is a hobby project, continue and you'll learn a lot about pathfinding. Feel free to learn from my favourite A* guide on Amit Patel's website. If you'd like to learn about all the cool options you have for pathfinding, I have an in-depth guide that I wrote for this answer. People in academia commonly write tutorials on the essential algorithms and google searches can find research papers about variants on these algorithms.

Heuristic for an A* Path Finding GPS

1 Answers1