# SMA*+: f-cost estimation of re-generated nodes

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$$?