improving a* search for finding path in a triangulated environment

Question

I have an area which is represented by constrained delaunay triangulations. I am playing around with the problem of finding a path among two points. I am using the paper provided by Marcelo Kallmann as a reference point to approach this problem. However, instead of using the Chazelle funnel algorithm as proposed by Kallmann paper link, I am planning to use the A* search algorithm which plans the path in a grid environment pretty efficiently.

For the heuristic cost function, I am using the Euclidean distance from the current node to the goal node and for selecting the neighbor nodes, I am drawing a line segment from the current point p to the mid-point of the edge of triangle. [This idea was proposed by kallmann] The cost to a neighbor node is also given by the Euclidean distance among them.

Here is the figure from the Kallmann demonstrating the use of the mid-point of the edge technique to generate various paths to the triangle containing the goal node.

Now this technique works fine when the triangle density is not large enough in an area. But say if the generated triangulation for a set of points looks like this

I was wondering whether there is a way to improve the efficiency of the algorithm by using some other technique like IDA* or ID-DFS? A Triangulation Reduction A* (TRA*) has been proposed,but I could not understand it since it was too formally defined. The details of the TRA* method can be found in section 5 of this thesis by Demyen.

I would appreciate some thoughts on it. If some code is required to be shared, I will edit this post.

Answer 1

Note that the ID algorithms trade off the cost of bookkeeping incurred by A* by repeating work, thus potentially making them slower (but hopefully not much slower). So what measure you're trying to improve the efficiency of will affect how useful these will be.