I am working on an implementation of the Anytime Dynamic A* algorithm as described here. I am ~50% of the way through an initial, basic implementation but am stuck at the following line:

In the procedure ComputePath, on line 19 it says

if s′ was not visited before then

This is the only line that I can find mentioning "visiting" a node. What does "visited" mean? Do I need to add a visited boolean to each node, if so, when do I make a node visited or unvisited?

I'm sure it doesn't matter, but I'm writing this implementation in Java 21

I am working on an implementation of the Anytime Dynamic A* algorithm as described here. I am ~50% of the way through an initial, basic implementation but am stuck at the following line:

In the procedure ComputePath, on line 19 it says

if s′ was not visited before then

This is the only line that I can find mentioning "visiting" a node. What does "visited" mean? Do I need to add a visited boolean to each node, if so, when do I make a node visited or unvisited?

I'm sure it doesn't matter, but I'm writing this implementation in Java 21

• graph-theory
• path-finding

1 Answer 1

In graph search algorithms, 'visitation' typically means calculating properties for, children of, or otherwise evaluating some node. The question being asked is, "Have I looked at this before?" A bit earlier in the paper you referenced (in section 2) it says:

To make the following proofs easier to read we assume that the min operation on an empty set returns ∞, arg min operation on the set consisting of only infinite values returns null and any state s with undefined values (in other words, a state that has not been visited yet) has v(s) = g(s) = ∞ and bp(s) = null.

It looks like the values of v(s), g(s), and bp(s) are all guaranteed to be set by the code after line 15, so I would mark s as 'visited' there and ensure that all nodes start out as unvisited. In terms of how to mark a node as visited, a boolean is probably the easiest way to do it, but there's plenty of options.

However:

More pragmatically, it seems to me the only reason for checking if a node has been visited before is to ensure that the values of v(s), g(s), and bp(s) are all initialized to some starting values, so if you're representing your states as objects, you could probably just set those values in the constructor and ignore the 'visitation' nonsense altogether.

The only two if statements that check if a node has been visited both just initialize those values, so as long as you set them in the constructor whenever you create a new state you should be able to safely remove those if statements.