Why is pgrouting astar not consistent?

Question

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.

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?

-

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.