2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.