Best heuristic function for fastest route using A*

Jirka Jirout · 12-09-2008, 11:49 AM

We have a navigation module for our software, which is very good at finding the shortest route. However, finding the fastest route takes ages. From what I can tell, it appears the problem is in the heuristic estimation of the cost of the remainder of the route.

At the moment, we use the time it takes to travel from a selected node to the destination in a direct line at speed of 300km/h, but this does not work very well. Any ideas on what to try?

Enforcer · 12-09-2008, 12:14 PM

Quote: Originally Posted by Jirka Jirout

At the moment, we use the time it takes to travel from a selected node to the destination in a direct line at speed of 300km/h, but this does not work very well. Any ideas on what to try?

What is this navigation software for a plane?

300Km/h is a tad fast.

Jirka Jirout · 12-09-2008, 12:34 PM

Not really, although we already have one installation in an ultralight (which we call a half-plane here :-) ).

The reason for using this speed that the heuristic function in A* must never overestimate the cost of the remaining part of the route. Speeds around 200km/h are legal and rather common on German highways (and not quite unheard of on the Dutch and Czech ones :-) ) so we have used 300km/h to be on the safe side.

Bugbyte · 12-09-2008, 01:17 PM

Why does the algorithm have to be different from finding the shortest route? Couldn't you have the program substitute a time estimation for each path in the network rather than the distance?

The cost function would be expressed in time rather than miles.

Jirka Jirout · 12-09-2008, 01:57 PM

The algorithm is the same. The difference is just the heuristic function. And that needs to be different, because when you calculate shortest route, the vertices of the graph have value expressed as their length and when you search for the fastest route, the values of the vertices are in minutes.

So when looking for the shortest route, you need to get an estimation of remaining distance from a node to the destionation and the beeline seems to be working fine for that. But when you are looking for the fastest route, you need to somehow estimate the remaining time. Time to travel the beeline at some speed (higher than real, because of the A* requirements) seemed to be an obvious choice, but the actual results are pretty poor :-(

Sicarius · 12-09-2008, 03:23 PM

It's likely that your time estimate is too optimistic. From what I've been able to dig up, the worse your estimate, the worse the A* algorithm's performance gets.

How feasible would it be to search all vertices within a circle with a radius of the remaining distance to the destination centered on the destination to find speed limits? You'll never be able to get to the destination faster than the highest limit found and it's a much better estimate than an assumed 300km/h.

Enforcer · 12-09-2008, 03:38 PM

It's no good trying to work out the fastest route if you are assuming a high speed of travel.

You should use the speed limit of the road and probably reduce that by 10% to allow for traffic problems.

I'm not sure if their is anywhere that publishing actual average speed of roads against time but that again could help make it more accurate.

I know in the real world people travel above the speed limit but if your algolrithm is based on that you could be accused of encouraging speeding, so if this is a commercial app that might be a legal issue.

Jirka Jirout · 12-09-2008, 04:34 PM

Quote: Originally Posted by Enforcer

I know in the real world people travel above the speed limit but if your algolrithm is based on that you could be accused of encouraging speeding, so if this is a commercial app that might be a legal issue.

The function we are talking about is only used internally during the route finding to estimate the cost of the remaining route segment and determine the order in which the following nodes are examined and how much the search is expanded within the graph. The elapsed time for visited vertices as well as the travel time for the itinerary (after a path has been found) is always calculated using realistic times from the map database or standard 50/90/130 speed limits.

The speed in the heuristic function has nothing to do with the actual speed when travelling or even the optimization of the route for particular speed. It is mathematically necessary for the function to never ever overestimate the cost of the remaining part of the route, that's all.

http://en.wikipedia.org/wiki/A*_search_algorithm

Jirka Jirout · 12-09-2008, 04:40 PM

Quote: Originally Posted by Sicarius

It's likely that your time estimate is too optimistic. From what I've been able to dig up, the worse your estimate, the worse the A* algorithm's performance gets.

Yes, it is definitely very optimistic, because we wanted to be on the safe side and to make sure we never overestimate the time cost.

Quote:

How feasible would it be to search all vertices within a circle with a radius of the remaining distance to the destination centered on the destination to find speed limits? You'll never be able to get to the destination faster than the highest limit found and it's a much better estimate than an assumed 300km/h.

That should not be too hard I guess. Thanks for the idea, I will definitely give it a try! We might actually retrieve the highest speed in the whole graph as we build it in memory and then simply use it throughout the search

User Name		Remember Me?
Password