shootingstar (#18) - shooting*: unusual routes compared with Dijkstra. (#180) - Message List

shooting*: unusual routes compared with Dijkstra.

Hi

I've been experimenting with this shooting star algorithm because I need to model turn restrictions in my application. I love the functionality, but have experienced some unusual results.

My edge cost table includes 'cost', 'reverse_cost', 'to_cost' and 'rule' for every edge. When I calculate a route from edgeA to edgeB using shooting star, the routes are very poor when compared to Dijkstra (from corresponding vertexA to vertexB). The main concern is that whilst Dijkstra correctly follows major roads (with relatively low costs), shooting* returns routes which often deviate onto minor roads with relatively high costs. This happens even if I leave to_cost empty for all edges, so the effect should not be caused by the influence of turn restrictions.

I am unable to find out if the cause is due to: 1. Shooting* not taking account of edge costs. 2. shooting* is a *directed* shortest path algorithm, and so gives low priority to edges that are not directly aligned with the target.

In a perfect world I'd like to see Dijkstra with turn restrictions: are there plans for this?

I'd appreciate advise if possible. I can submit examples if required.

Thx to all for work on pgRouting. This is a great package David

the_nerdling
10/13/08 22:03:26 (2 years ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #614

    Hi David,

    You're right - Shooting* is directed (or else turn restrictions make no sense), which means that if your graph is directed *without* reverse cost, it will never pass through any edge against its direction. If your graph is directed *with* reverse cost, it should be OK.

    I guess you call the function with 'has_reverse_cost' parameter set to false. So, my suggestion is to call with two last parameters set to 'true'.

    Unfortunately, Dijkstra with turn restriction is impossible to implement. Dijkstra and A* are vertex based, which means that each vertex can be visited only once, which makes some turn restriction cases invalid (for example P-turns).

    Shooting* is well tested algorithm and its result doesn't differ so much from Dijkstra or A*. Believe me or not, but it uses the same cost evaluation function as Dijkstra and A*.

    anton
    10/14/08 11:21:31 (2 years ago)
    • Message #615

      Hi Anton

      Thx for fast response. It looks like shooting star is what I need so I'm keen to get these problems fixed. I've got some more information and would appreciate it if you can help diagnose.

      1. My graph has reverse_cost and I call the shooting star algorithm with 'has_reverse_cost' set to true. The line of php where I define the sql is copied below ($edge1 and $edge2 are set from user clicks and db queries). Not sure if there is some other problem in there?

      ... select edge_id,cost from shortest_path_shooting_star('SELECT gid AS id, source::int4, target::int4, cost::float8, reverse_cost::float8, x(node1) as x1, y(node1) as y1, x(node2) as x2, y(node2) as y2, rule, to_cost from edgecosts order by id',".$edge1.", ".$edge2.", true, true)

      2. The routes returned by Dijkstra and shooting star are very different. Compare  http://www.soi.city.ac.uk/~dmm/temp/dijkstra.png and  http://www.soi.city.ac.uk/~dmm/temp/shootstar.png: Dijkstra sticks to main roads as expected. Shooting* deviates from them. The resulting costs show shooting* is returning poor routes: 2456secs cost vs 1488secs for Dijkstra. Something isn't right here.

      3. Shooting * appears to be cost-aware: compare  http://www.soi.city.ac.uk/~dmm/temp/shootstarHiCost.png and  http://www.soi.city.ac.uk/~dmm/temp/shootstarRegCost.png. When I set an edge to have very high cost and reverse_cost, an alternative route avoiding that edge is returned.

      Again any advice you can offer is greatly appreciated.

      Many thanks David

      the_nerdling
      10/14/08 18:47:22 (2 years ago)
      • Message #616

        Hi David,

        Hmmm... It really looks different.

        Can you please also post the string where you call Dijkstra? Are you using plain cost value? 'Cause for me it looks like weighted shortest path search.

        It would be also nice if you can share your data - just a small piece were the behavior of Shooting* differs.

        Can you also run A* with your data? If a result would be the same as for Shooting*, I can tell you the reason.

        About cost awareness - I didn't really understand you. Of course it is cost-aware! It is exactly what shortest path algorithms were made for :)

        anton
        10/14/08 19:14:09 (2 years ago)
        • Message #621

          Hi Anton

          Can you please also post the string where you call Dijkstra? Are you using plain cost value? 'Cause for me it looks like weighted shortest path search.

          PHP sample for shortest_path "select vertex_id,cost from shortest_path('SELECT gid AS id, source::int4, target::int4, cost::double precision, reverse_cost::double precision from edgecosts',".$node1.", ".$node2.", true, true)"

          In my edgecost table, units for the cost values are seconds, calculated from a speed estimate for class of road and edge length. Given your later post, I suspect this might be the problem? I want my routes to reflect fastest routes, so wish to retain a cost based on time, rather than spatial distance.

          It would be also nice if you can share your data - just a small piece were the behavior of Shooting* differs.

          I've extracted about 200 edges from the DB which demonstrate the diff between shooting * and Dijkstra. You can download from (pls do not distribute)  http://www.soi.city.ac.uk/~dmm/temp/edgecostsample.csv

          The first surprise is that using this subset of edges as the src for shooting* gives a different route than for when using shooting* with the complete table of edges. In both cases however, the path is suboptimal, compared to Dijkstra. I can post examples for this (images and start / end nodes/edges used).

          Can you also run A* with your data? If a result would be the same as for Shooting*, I can tell you the reason.

          I have experienced similar problems in the past with A Star, and can reimplement for this edgecost table is this helps.

          Let me know if you need further diagnostics, and thx for your help. David

          the_nerdling
          10/16/08 19:53:32 (2 years ago)
      • Message #617

        Hi David,

        You didn't reply with your results, so I decided to give you one more hint. Your Shooting* path shows that heuristic function value for each edge are higher than cost value. The most probable reason is using different units for cost and coordinates. I guess that you reprojected your data (from degrees to meters or way around), but forgot about length.

        So, please check it.

        anton
        10/15/08 17:17:41 (2 years ago)
        • Message #622

          Hi Anton

          I think using alternative units for cost and coordinates is the issue.

          I have changed my cost units from seconds to millisecs, and the routes returned by shooting* are now very similar to those that I would expect from Dijkstra.

          David

          the_nerdling
          10/16/08 21:26:16 (2 years ago)
          • Message #625

            Hi David,

            So, it's what I thought.

            If you don't want to bother with heuristics, you can change heuristic function of distance_heuristic class (shooting_star_boost_wrapper.cpp) and make it return constant value (let's say 0).

            anton
            10/16/08 22:58:42 (2 years ago)
Tree View Flat View (newer first) Flat View (older first)