Triangulation A* (TA*) pathfinding algorithm

Question

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81.

He describes how to adapt the regular A* algorithm for triangulation, to search for other possibly more optimal paths, even after the final node is reached/expanded. Regular A* stops when the final node is expanded, but this is not always the best path when used in a triangulated graph. This is exactly the problem I'm having.

The problem is illustrated on page 78, Figure 5.4:

I understand how to calculate the g and h values presented in the paper (page 80).

And I think the search stop condition is:

if (currentNode.fCost > shortestDistanceFound)
{
    // stop
    break;
}

where currentNode is the search node popped from the open list (priority queue), which has the lowest f-score. shortestDistanceFound is the actual distance of the shortest path found so far.

But how do I exclude the previously found paths from future searches? Because if I do the search again, it will obviously find the same path. Do I reset the closed list? I need to modify something, but I don't know what it is I need to change. The paper lacks pseudocode, so that would be helpful.

Answer 1

I haven't implemented this, but as I read it, I think you'd do something like this:

shortestDistance = infinity
do A* with modified g cost
    if node.fCost > shortestDistance (section 5.5)
        don't open node
    if node.isGoal()
        run funnel algorithm (string pulling)
        update shortestDistance

The difference is that even if you find a path to the goal, it's not necessarily the shortest path. But you'll keep improving the upper bounds on the shortest path, meaning that you won't have to open all nodes. Eventually your open set should be empty, and the best path you've found so far should be the shortest.

The modified g cost that he describes seems like a big underestimate, so I'm skeptical about how well it works in practice.