[pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation

Stephen_V_Mather · April 13, 2013, 1:07am

Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com

Tao_Romera_Martinez · April 13, 2013, 2:21am

Hi Stephen,

About finding a route from a point close to the network that is not one of the nodes, here is how we are doing it.
I don’t think it is the most “clean” way of proceeding, because we did it when we started using PostGIS for the first time, so we were complete beginners. This procedure splits the closest way on the network to the starting point from which you want your route at the orthogonal projection of this starting point to the closest way.
The programming language is Ruby, but I think you will understand it easily and adapt it to your programming language.

Construct Point: route starting point
→ start_pt = “ST_GeometryFromText(‘POINT(#{point.lon} #{point.lat})’, 4326)”
Find closest road on the network to the starting point
closest_road = Map.connection.execute(“WITH index_query AS (
SELECT ST_Distance(geom_way, #{start_pt}) AS distance, id, geom_way, x1, y1, x2, y2, source, target FROM #{self.table_name} ORDER BY geom_way <#> #{start_pt} limit 10)
SELECT id, ST_AsText(geom_way), x1, y1, x2, y2, source, target FROM index_query ORDER BY distance LIMIT 1”)

closest_road_geom = “ST_GeometryFromText(‘#{closest_road.getvalue(0,1)}’, 4326)”

Find closest point lying on closest way from starting point
closest_pt_on_closest_way = Map.connection.execute(“SELECT ST_AsText(ST_ClosestPoint(#{closest_road_geom}, #{start_pt})) AS point;”).getvalue(0,0)
closest_pt = “ST_GeometryFromText(‘#{closest_pt_on_closest_road}’, 4326)”
Get points of the closest way to the starting point
points = Map.connection.execute(“SELECT ST_AsText((point.gdump).geom) FROM (SELECT ST_DumpPoints(#{closest_road_geom}) AS gdump) AS point;”).column_values(0)
Iterate through all the points of the closest way to find what 2 points of the closest way the orthogonal projection of the starting points is in between
points2 = points[1…-1]
index = 0

Would be much better if we could calculate it directly here, not accessing the DB, but it is not an easy calculation…could not manage to find the correct formulas

points2.each_with_index do |pt2_raw, idx|

Get distance

pt1 = “ST_GeometryFromText(‘#{points[idx]}’, 4326)”
pt2 = “ST_GeometryFromText(‘#{points2[idx]}’, 4326)”

dist = Map.connection.execute(“SELECT ST_Distance(#{closest_pt},(SELECT ST_MakeLine(#{pt1}, #{pt2})));”).getvalue(0,0)
if dist.to_f < 0.0000000001
index = idx
break
end
end

Now we can split the road into 2

Split the road into 2

road1 = “”
points[0…index].each_with_index do |pt, idx|
if idx == 0
road1 = “ST_GeometryFromText(‘#{pt}’, 4326)”
else
road1 = “#{road1}, ST_GeometryFromText(‘#{pt}’, 4326)”
end
end
road1 = “#{road1}, #{closest_pt}”

road2 = closest_pt
points[index+1…-1].each do |pt|
road2 = “#{road2}, ST_GeometryFromText(‘#{pt}’, 4326)”
end

Finally, you have to insert “road1” and “road2” into your database, so that pgrouting uses them when finding the route (no need to delete the original way), and delete them when the routing calculations are over. Something like:

buffer variables

geom_buf = “road1 AS (SELECT ST_MakeLine(ARRAY[#{road}]) AS geom)”

Insert road into network table

insert = Map.connection.execute(“WITH #{geom_buf}, #{length} INSERT INTO #{self.table_name} VALUES (#{id_r1},0,0,0,0,#{clazz},1,#{source},#{target},#{km},1,#{cost},#{cost},#{x1},#{y1},#{x2},#{y2},#{geom_r1},#{cost_car});”)

Tao

···

2013/4/13 Stephen V. Mather <svm@clevelandmetroparks.com>

Hi All,

I’m curious about efficiency of A* vs Dijkstra in large networks. If A* tends to follow the straight line nodes until/unless it finds an obstacle, for really large networks, under what conditions is A* a better choice than Dijkstra?

Also, regarding A* implementation, is it strict, or is there any way to relax the admissibility criterion as currently implemented?

Finally, in using pgRouting for turn by turn, we have pre-chopped our network into short segments to ensure the nearest search node is close to the point we are searching so the directions start from a nearby point, not the nearest network intersection.

For datasets as large as the one we are working with, this seems to result in a pretty high random IO tax. I wondered if anyone has some boilerplate modifying the returned route, slicing the nearest ways to the beginning and end points with ST_ClosestPoint or similar?

Thanks,
Best,
Steve

Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Tao Romera Martínez

Tel: 080-6805-0945

Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn

Stephen_Woodbridge1 · April 13, 2013, 2:33am

On 4/12/2013 9:07 PM, Stephen V. Mather wrote:

Hi All,

I'm curious about efficiency of A* vs Dijkstra in large networks. If A*
tends to follow the straight line nodes until/unless it finds an
obstacle, for really large networks, under what conditions is A* a
better choice than Dijkstra?

In general, A* is much more efficient because it does not have to solve the whole network as Dijkstra has to. Take the simple case of the start node in a center of a square region with a uniform distribution of nodes and edges over the square. If you route from the center to one of the corners, A* only needs to look at enough edges to get to the destination node and it can stop. While Dijkstra will solve the whole network.

But for large networks, the overwhelming cost might to be build the graph in the first place. I don't have hard numbers handy about I think that fetching the edges and building the graph cost more than solving it.

Also, regarding A* implementation, is it strict, or is there any way to
relax the admissibility criterion as currently implemented?

There are not any controls that I am aware of.

Finally, in using pgRouting for turn by turn, we have pre-chopped our
network into short segments to ensure the nearest search node is close
to the point we are searching so the directions start from a nearby
point, not the nearest network intersection.

You might want to look at TRSP. This is going to replace shooting star which is seriously broken and noone know how it is supposed to work. TRSP allow you to select an edge and an offset along that edge as the start and end point. This is critical is you want your start or end point to be on a segment that is a one way street. For ample it is possible to have both the start and the end on the same segment like:

---o-->--E--->--------S----o----

In this case to get from S to E you have to exit right and find a route back around to the E coming from the left. TRSP (Turn restricted shortest path) is a little slower (not much) than dijkstra. You don't have to give it turn restriction but if you have them they can be supplied. There is a trivial test(s) in the sew-devel-2_0 branch for trsp. It was developed under contract by a UK client and has been used with restrictions and Navteq data. The test use the same graph with and with out turn restriction. There is an image of the graph in doc/static/images/

Let me know if your need more information.

For datasets as large as the one we are working with, this seems to
result in a pretty high random IO tax. I wondered if anyone has some
boilerplate modifying the returned route, slicing the nearest ways to
the beginning and end points with ST_ClosestPoint or similar?

I have done this, it is not that hard.

-Steve

Thanks,
Best,
Steve

http://sig.cmparks.net/cmp-ms-90x122.png Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com <http://www.clemetparks.com>

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

dkastl · April 13, 2013, 3:16am

For datasets as large as the one we are working with, this seems to

result in a pretty high random IO tax. I wondered if anyone has some
boilerplate modifying the returned route, slicing the nearest ways to
the beginning and end points with ST_ClosestPoint or similar?

I have done this, it is not that hard.

As Steve said, this is not so hard. You can select the closest point on the
nearest road segment and PostGIS has all the function to gibe you a
substring from that point.
There is an example how to do this with Shooting Star, which has some
problems at the moment, but just to get an idea:
https://github.com/pgRouting/pgrouting/blob/sew-devel-2_0/src/common/sql/pgrouting_network_check.sql
Shooting Star routes from road segment to road segment, so the logic is
slightly different. For other algorithms such as TRSP you probably need to
create a temporary node.
So in short, I wouldn't modify the returned route but start from new points.

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_V_Mather · April 15, 2013, 4:12pm

Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com

Stephen_V_Mather · April 15, 2013, 6:48pm

In general, A* is much more efficient because it does not have to solve
the whole network as Dijkstra has to. Take the simple case of the start
node in a center of a square region with a uniform distribution of nodes
and edges over the square. If you route from the center to one of the
corners, A* only needs to look at enough edges to get to the destination
node and it can stop. While Dijkstra will solve the whole network.

Cool. That was my interpretation.

But for large networks, the overwhelming cost might to be build the
graph in the first place. I don't have hard numbers handy about I think
that fetching the edges and building the graph cost more than solving it.

My hunch was that building the graph for our case is the more expensive operation due to io.

> Also, regarding A* implementation, is it strict, or is there any way to
> relax the admissibility criterion as currently implemented?

There are not any controls that I am aware of.

Cool.

You might want to look at TRSP. This is going to replace shooting star
which is seriously broken and noone know how it is supposed to work.
TRSP allow you to select an edge and an offset along that edge as the
start and end point. This is critical is you want your start or end
point to be on a segment that is a one way street. For ample it is
possible to have both the start and the end on the same segment like:

---o-->--E--->--------S----o----

Ah, so I wouldn't have to create a temporary node because I'm dealing with ways?

Let me know if your need more information.

Will do. More homework for me... .

Best,
Steve

Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com

Stephen_V_Mather · April 15, 2013, 6:50pm

Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com