Results 1 to 9 of 9

Thread: Best heuristic function for fastest route using A*

  1. #1
    QCar Creator Jirka Jirout's Avatar
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    590

    Best heuristic function for fastest route using A*

    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?

  2. #2
    Confusion Master
    Auto Apps:loading...
    Enforcer's Avatar
    Join Date
    Sep 2003
    Location
    If you go down to the woods today, You're sure of
    Posts
    14,585
    Quote Originally Posted by Jirka Jirout View Post
    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.

  3. #3
    QCar Creator Jirka Jirout's Avatar
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    590
    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.

  4. #4
    Admin. Linux loser.
    Auto Apps:loading...
    Bugbyte's Avatar
    Join Date
    Sep 2004
    Location
    Corning, NY
    Posts
    7,359
    Blog Entries
    2
    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.
    Quote Originally Posted by ghettocruzer View Post
    I was gung ho on building a PC [until] just recently. However, between my new phone having internet and GPS and all...and this kit...Im starting to have trouble justfiying it haha.
    Want to:
    -Find out about the new iBug iPad install?
    -Find out about carPC's in just 5 minutes? View the Car PC 101 video

  5. #5
    QCar Creator Jirka Jirout's Avatar
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    590
    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 :-(

  6. #6
    Constant Bitrate
    Join Date
    May 2008
    Posts
    223
    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.

  7. #7
    Confusion Master
    Auto Apps:loading...
    Enforcer's Avatar
    Join Date
    Sep 2003
    Location
    If you go down to the woods today, You're sure of
    Posts
    14,585
    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.

  8. #8
    QCar Creator Jirka Jirout's Avatar
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    590
    Quote Originally Posted by Enforcer View Post
    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

  9. #9
    QCar Creator Jirka Jirout's Avatar
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    590
    Quote Originally Posted by Sicarius View Post
    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.

    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

Similar Threads

  1. Is it me or is Route Buddy awful?
    By Bugbyte in forum MacCar
    Replies: 22
    Last Post: 09-03-2009, 11:39 PM
  2. Why do people think RR is hard to setup?
    By 2k1Toaster in forum Software & Software Development
    Replies: 53
    Last Post: 05-18-2008, 12:38 AM
  3. pc reboot on sd startup
    By duanes7 in forum StreetDeck
    Replies: 3
    Last Post: 12-14-2007, 08:55 AM
  4. Replies: 6
    Last Post: 07-19-2007, 11:35 AM
  5. Autodimming monitor after 2 seconds of inactivity. (Solution inside)
    By justintime in forum Software & Software Development
    Replies: 54
    Last Post: 02-01-2006, 01:48 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •