I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my misunderstanding of the cost evaluation of the re-generated nodes.
Can there be some memory saved by not fully expanding a node immediately?
The third paragraph of section 4:
Unlike SMA*, SMA*+ fully expands a node each iteration, instead of adding only one successor to the open list every iteration. While adding one successor at a time may seem more efficient, the overhead required to determine which successor to add, adds unnecessary complexity and decreases performance with minimal memory advantage.
Maybe in this context "minimal" is a euphemism to mean "none" and I'm just arguing semantics here. But if taken literally, I actually don't see a case with a memory gain in adding one successor at a time.
I mean, if the heuristics is admissible, then every successor $n_i$ of a node $b$ has a higher $f$-cost: $f(b) \le f(n_i)$. And since we're expanding $b$, we know it already has the lowest $f$-cost of all the open nodes. Therefore we won't switch to expanding another node, and thus SMA* will always fully expand a node once it started, no matter what.
Or did I miss something that might make the progressive expansion worth it in some cases?
Does SMA* store its children when they are removed?
The SMA*+ paper says in section 4:
The original SMA* makes similar progress by keeping removed nodes in memory, until their parent is removed.
Which is think is surprising. When I read the algorithm in the SMA* paper section 3.1 I see:
Procedure BACKUP(n):
if n is completed and has a parent then
f(n) <- least f-cost of all its successors
if f(n) changed, BACKUP(parent(n)).
I think it means that it stores only the least $f$-cost of all its successors. Not the successor nodes, not even one $f$-cost per successor.
Do I misunderstand the way SMA* recomputes the $f$-cost of the regenerated successor nodes?
Why do we need to set $f(n) \leftarrow max(f(b), g(n) + h(n))$?
In SMA* I thought this was needed because we forgot the actual value of $f(n)$ when pruning it. Therefore we underestimate its value by using $f(b)$ (the cost of its predecessor) which is either set to the minimum $f$-cost of all its pruned successors or its natural value which is also less than the $f$-score of its successors if the heuristic is admissible. Then we use $max$ to ensure the $f$-cost is non-decreasing along the way, which I guess would mean that the heuristic was non-admissible.
But here, in SMA*+, we store the $f$-cost of all the children, so why do we still need this $max$?
