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

[Stephen V. Mather]

Hi Tao,
      In spite of my ruby inexperience, that looks pretty readable.  Now just an (uncool :) PHP port.

Thanks!
Steve


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



________________________________
From: pgrouting-users-bounces at lists.osgeo.org [pgrouting-users-bounces at lists.osgeo.org] on behalf of Tao Romera Martinez [taoromera at gmail.com]
Sent: Friday, April 12, 2013 10:21 PM
To: pgRouting users mailing list
Subject: Re: [pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation

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.

1. Construct Point: route starting point
    ->  start_pt = "ST_GeometryFromText('POINT(#{point.lon} #{point.lat})', 4326)"

2. 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)"

3. 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)"

4. 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)

5. 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

6. 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

7. 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 at clevelandmetroparks.com<mailto:svm at 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


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


_______________________________________________
Pgrouting-users mailing list
Pgrouting-users at lists.osgeo.org<mailto:Pgrouting-users at 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
---------------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130415/081a91d3/attachment.html>