Anyone has implemented SMA* search algorithm?

Question

I find the algorithm description in AIMA (Artificial Intelligence: A Modern Approach) is not correct at all. What does 'necessary' mean? What is the memory limit? The queue size or processed nodes? What if the current node has no children at all?

I am wondering if this algorithm itself is correct or not. Because I searched the Internet and nobody has implemented it yet.

Thanks.

Answer 1

I believe this PDF is the SMA* section from AIMA, for those that don't have the book.

I first note the pseudocode from Wikipedia has a rather obvious error in the line:

parent.successors.remove(parent);

It should be

parent.successors.remove(badNode);

(How could a parent be its own successor?)

What does 'necessary' mean?

If its parent is not already in the queue, then we have to add it to the queue. Otherwise, we'll end up searching this node again.

What is the memory limit? The queue size or processed nodes?

The queue will take up all available memory. There is no queue for processed nodes. This is precisely why SMA* can re-traverse nodes and potentially get stuck.

What if the current node has no children at all?

If a node has no children, then it's a leaf node. And if it's a leaf node, then it's a terminal node. In that case, if it's not the goal node, we set its f-cost to infinity, and propagate that information to its parent.