More control over Astar heuristic function

[justjkk]

The current implementation of Astar core function accepts a table generating SQL statement as first parameter and the table has four columns x1, y1, x2, y2. Then the heuristic is computed as (|x1 - x2| + |y1 - y2|) / 2. Tying down the heuristic reduces reusability of the Astar function.

The solution can be to pass the string containing a call to some psql function(Eg: ST_Distance) that can be evaluated inside the operator definition of AStarHeuristic's subclass. This means that astar_boost_wrapper.c will contain some SPI code.

Example call of Proposed Astar core function:

SELECT * FROM shortest_path_astar('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost,
                        FROM ways',
                605, 359, false, false,
                'SELECT ST_Distance(src.the_point, tgt.the_point) 
                        FROM nodes src, nodes tgt
                        WHERE src.id = ?0 AND tgt.id = ?1'
);

[dkastl]

Yes, that's interesting. Also heuristic itself could be calculated different for different use cases. Right now it needs to be recompiled when you want to change it. So this is some good point when reviewing the functions for (hopefully) 2.0.

[antonpa]

Great idea in general, but heuristic function calculates a value for each (current) vertex and target vertex, not only for source and target. It means that we need a query which returns kind of distance (or whatever) values for each vertex in graph and target, than store it somewhere and refer to it every time we calculate heuristic value for current vertex. I see some memory and performance drawback here, while this way increases flexibility of course.

[dkastl]

Well, what about making this "optional" then? If not used it will take a default one.

[antonpa]

I'm not completely against that, but first, I see no strong reasons to change heuristic function often. Second, people will be confused with result in case their heuristic function has stronger value than cost. Third, it requires some additional implementation. Also for big graphs creating and storing a matrix might be a problem.

[justjkk]

It means that we need a query which returns kind of distance (or whatever) values for each vertex in graph and target, than store it somewhere and refer to it every time we calculate heuristic value for current vertex.

True. But, the existing code defines distance_heuristic with the definition of heuristic function which gets evaluated every time heuristic value is calculated.

I see some memory and performance drawback here, while this way increases flexibility of course.

True, calling the sql function is costlier than evaluating c++. I am thinking of using A-star algorithm with custom heuristics and custom f() too for solving the scheduled routing problem.

[dkastl]

Anton, I think we should leave it up to the users if they want to make use of their own heuristic definition or not. If it's documented, is optional and has a good default setting, it's not confusing but might be an interesting option for some. For everyone using packages rather than compiling themselves, it's a lot more comfortable to read settings from some table or pass it as parameters.

[justjkk]

heuristic function calculates a value for each (current) vertex and target vertex, not only for source and target.

Why not let the user construct a table/view like:

CREATE VIEW heuristic_map(
    node_id          int4,
    heuristic_cost   double precision
)
AS
SELECT curr.id, ST_Distance(curr.the_point, target.the_point)
       FROM nodes curr, nodes target
       WHERE target.id = 359;

Then we can accept the two column 'heuristic map' table instead of the heuristic function as the extra argument, use the heuristic values which the user gave when implementing distance_heuristic.

[antonpa]

Well, OK then. We should add one optional query attribute which returns heuristic values for each vertex and the target.

[cvvergara]

solution mentioned of having a SPI, within the C++ code its not possible at the moment. (on all my experimenting, I haven't even being able to use the very simple pfree in the c++ code) So passing a postgres function I can not do currently. But: there are options in the of possible heuristics So, 1 or even maybe 3 extra parameters might be useful:

• which heuristic
• factor to that heuristic (for units conversion)
• epsilon

h(v) = 0 would give the pgr_dijkstra same results

Weighted A/Static Weighting.[8] If ha(n) is an admissible heuristic function, in the weighted version of the A search one uses hw(n) = ε ha(n), ε > 1 as the heuristic function, and perform the A* search as usual (which eventually happens faster than using ha since fewer nodes are expanded). The path hence found by the search algorithm can have a cost of at most ε times that of the least cost path in the graph.[9]

Quote from wikipedia

So, as a start:

0. h(u) = 0
1. h(u) = max(dx, dy)
2. h(u) = dx * dx + dy * dy
3. h(u) = sqrt(dx * dx + dy * dy)
4. h(u) = fabs(dx)+fabs(dy)

Factor > 0: Default 1

epsilon >= 1: Default 1

so the final heuristic would be: H(u) = factor * epsilon * h(u) I can see that factor * epsilon is a constant value, but the concept they have behind is different, so keep the concepts apart on the parameters I feel is best, instead of having just one parameter.

Why the factor for units conversion, Ill put some examples:

Example 1) working with cost/reverse_cost as length in degrees, x/y in lat/lon: Factor = 1 (no need to change units)

Example 2) working with cost/reverse_cost as length in meters, x/y in lat/lon: Factor = would depend on the location of the points:

latitude	conversion	Factor
45	1 longitude degree is 78846.81 m	78846
0	1 longitude degree is 111319.46 m	111319.46

Example 3) working with cost/reverse_cost as time in seconds, x/y in lat/lon: Factor: would depend on the location of the points and on the average speed say 25m/s is the speed.

latitude	conversion	Factor
45	1 longitude degree is (78846.81m)/(25m/s)	3153.8724s
0	1 longitude degree is (111319.46 m)/(25m/s)	4452.7784s

[cvvergara]

Modifications to Astar are in develop

[esdras-kid]

I have a question about the factor parameter in the documentation example it's said that the factor would depend on the location of the points is there a way to set the parameters dynamically depending on tag on the edge table (value in a column) ?