Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I route from 1 end of a circular route to the opposite end. Visually it is obvious that going clockwise is shorter, however shortest_path_astar sometimes picks clockwise and sometimes anti-clockwise.

astar messing up

I narrowed down the amount of edges it may route on and it seems that the order in which the selected edges appear in the result set make a difference in the outcome of astar (which should not happen in my opinion).

Set1:

SELECT e.id, e.source_id::integer as source,    e.target_id::integer as target, (SELECT SUM(n.shape_leng::float) FROM netwerk n    WHERE e.source_id = n.source_id    AND e.target_id = n.target_id) as cost,    ST_X(source.the_geom) as x1, ST_Y(source.the_geom) as y1, ST_X(target.the_geom) as x2, ST_Y(target.the_geom) as y2 FROM edges e JOIN knooppunten source    ON source.gid = e.source_id JOIN knooppunten target ON target.gid = e.target_id where e.id in (127,757,471,286,579,601,760) or not exists (SELECT * FROM netwerk n    WHERE e.source_id = n.source_id    AND e.target_id = n.target_id);

Result1:

 id  | source | target |       cost       |        x1        |        y1        |        x2        |        y2        
 -----+--------+--------+------------------+------------------+------------------+------------------+------------------
 127 |    459 |    460 | 1166.62881971498 | 178418.026099999 |      593089.0845 | 179488.144699998 | 592656.112100001
 286 |    457 |    373 | 2701.89635124091 | 177301.707899999 |      593119.0339 | 177093.187399998 | 590500.850200001
 471 |    457 |    458 | 229.123075139216 | 177301.707899999 |      593119.0339 | 177516.643399999 | 593197.757599998
 579 |    371 |    373 | 1291.71083699618 | 178363.840300001 |      590548.6774 | 177093.187399998 | 590500.850200001
 601 |    460 |    371 | 2456.81983676712 | 179488.144699998 | 592656.112100001 | 178363.840300001 |      590548.6774
 757 |    459 |    458 | 919.539772037522 | 178418.026099999 |      593089.0845 | 177516.643399999 | 593197.757599998
 760 |    372 |    373 | 805.921542501888 |      176324.6664 | 590358.514199998 | 177093.187399998 | 590500.850200001
 (7 rows)

Set2:

SELECT e.id, e.source_id::integer as source,    e.target_id::integer as target, (SELECT SUM(n.shape_leng::float) FROM netwerk n    WHERE e.source_id = n.source_id    AND e.target_id = n.target_id) as cost,    ST_X(source.the_geom) as x1, ST_Y(source.the_geom) as y1, ST_X(target.the_geom) as x2, ST_Y(target.the_geom) as y2 FROM edges e JOIN knooppunten source    ON source.gid = e.source_id JOIN knooppunten target ON target.gid = e.target_id where e.id in (127,757,471,286,579,601,760);

Result2:

 id  | source | target |       cost       |        x1        |        y1        |        x2        |        y2        
 -----+--------+--------+------------------+------------------+------------------+------------------+------------------
 579 |    371 |    373 | 1291.71083699618 | 178363.840300001 |      590548.6774 | 177093.187399998 | 590500.850200001
 760 |    372 |    373 | 805.921542501888 |      176324.6664 | 590358.514199998 | 177093.187399998 | 590500.850200001
 471 |    457 |    458 | 229.123075139216 | 177301.707899999 |      593119.0339 | 177516.643399999 | 593197.757599998
 286 |    457 |    373 | 2701.89635124091 | 177301.707899999 |      593119.0339 | 177093.187399998 | 590500.850200001
 127 |    459 |    460 | 1166.62881971498 | 178418.026099999 |      593089.0845 | 179488.144699998 | 592656.112100001
 757 |    459 |    458 | 919.539772037522 | 178418.026099999 |      593089.0845 | 177516.643399999 | 593197.757599998
 601 |    460 |    371 | 2456.81983676712 | 179488.144699998 | 592656.112100001 | 178363.840300001 |      590548.6774
 (7 rows)

Above 2 result sets are identical apart from the ordering of the rows. When i use shortest_path_astar on these 2 result sets i get different results:

select * from shortest_path_astar('<select Set1>', 460, 373, false, false) astar;
 vertex_id | edge_id |       cost       
-----------+---------+------------------
       460 |     127 | 1166.62881971498
       459 |     757 | 919.539772037522
       458 |     471 | 229.123075139216
       457 |     286 | 2701.89635124091
       373 |      -1 |                0

select * from shortest_path_astar('<select Set2>', 460, 373, false, false)      vertex_id | edge_id |       cost       
-----------+---------+------------------
       460 |     601 | 2456.81983676712
       371 |     579 | 1291.71083699618
       373 |      -1 |                0

In this example Astar gives different results for an identical set of rows.

Other things i noticed:

  • If i route from endpoint to startpoint (373 -> 460) shortest_path_astar gives the correct answer.
  • If i use shortest_path instead of shortest_path_astar this particular problem does not occur.
  • If i change the type of x1,x2,y1 and y2 to double precision or float8 (what it should be according to docs) shortest_path_astar still is incorrect
  • If i change the type of x1,x2,y1 and y2 to int or bigint shortest_path_astar gives the correct answer

My best guess is that the heuristic function in the underlying Boost library is messing up because of how it interprets the incoming x1,x2,y1 and y2. Chances that the boost library is wrong seem slim so it might be the transfer of the data i feed it.

Does any of you have experience with this behaviour of shortes_path_astar or knows what/if i am doing wrong?

    -
share|improve this question
    
Looking at your x,y values it seems your data is in a meter projection. Is this correct? Could you try to route in WGS84 (EPSG:4326) for example? –  dkastl Nov 29 '12 at 10:19
    
I am using EPSG:28992 (RDNEW). This is in meters. Let me try 4326. If i transform the x's and y's into 4326 before astar it gives the correct answer. –  mrg Nov 29 '12 at 10:24
    
Any idea why that works? The difference i see is that the numbers in EPSG4326 are much smaller. –  mrg Nov 29 '12 at 10:43
    
Could it be that the order i feed astar the rows determines which vertices he will examine first. Anticlockwise (see image) all vertices will be closer by than the first one clockwise. And once he discovers the target he doesn't test other shorter routes anymore? –  mrg Nov 29 '12 at 11:55
    
Astar will always keep testing nodes until the heuristic says the current best solution can no longer be improved upon. –  flup Jan 15 '13 at 23:37
show 1 more comment

1 Answer 1

Your guess with the heuristics function was correct, I think. A-star's heuristics settings are (badly) defined assuming a projection in degree. With a meter projection as in your case they might have to be configured with different values.

share|improve this answer
    
Checking the boost library the default heuristic function seems to be (dx+dy)/2. –  mrg Nov 30 '12 at 7:42
1  
It is an [admissible heuristic] (en.wikipedia.org/wiki/Admissible_heuristic) so this cannot be the cause. –  flup Jan 15 '13 at 23:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.