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've managed to implement graph search with it in C#, using the PDF.

I've used 3 lists - frontier (open list), leaf list and "tree branch" list.

• Frontier is the Queue, mentioned in the PDF, it is a common priority queue sorted from best to worst.

• Leaf list keeps only leaves, sorted from worst to best, we will need it when we'll decide what leaf to forget. SMA forgets only leaves, not whole branches.

• Tree branch list keeps fully expanded nodes, whose children are all in memory. We'll need it to test state intersection.

I've used fast binary heaps for frontier and leaf list, and hash table for tree branch list.

Nodes should keep the following additional info:

• Successors iterator with position (position is needed for pointing in successors list). We absolutely must not reset our successor enumeration to zero if we forget as we go, cause it is possible, that we forget the node we just added. I use IEnumerator, int for position and bool for "finished" flag.

• Successors list. We unevitably need this for f-cost upwards propagation. Also I keep simple successor states list - like [blocked, forgotten, exists]. It is needed for keeping track of forgotten and blocked nodes. (blocked - in graph - by some node, which expanded faster)

• Two F's, mentioned in the PDF, our current F, and best forgotten successor F.

• Node depth

Sorting of nodes in both frontier and leaf list should be done like this: "if we have "finished" enumeration flag, pick best forgotten successor F, else pick current F, if equals, pick deepest". Leaf list is sorted in reverse order using the exact same condition.

Basic algorithm outline is like this (similar to PDFs):

• We pick best node from frontier, if it has "finished" flag - we know we'll be remembering, reset the iterator, and we must reset best forgotten successor F in this case (for complicated reasons).

• If we don't have this successor in list already (can be, when we're remembering) - we generate it and set it's F as described in PDF.

• Then follows the most complex thing - we test if the node with the same state exists in frontier or tree branch list. If it does - I'll describe what to do later. If not we just add child to frontier (and remove parent from leaf list).

• In all cases when enumeration of successors ends - we do the so-called backup of f-costs, and if we don't have any forgotten nodes (and have some successors), we remove current node from the frontier and add it to tree branch list.

How to forget: we pick first leaf from leaf list (the worst leaf), remove it from the frontier, remove it from parent's successors list, update (decrease) parent's best forgotten successor's F, if needed, and if parent is not on frontier - we remove it from tree branch list and add it to frontier and also add it to leaf list, if it's now a leaf (doesn't have successors anymore).

What to do, if we generated a successor, that is already in frontier or tree branch list. First, we'll need to test it's better - we compare PathCost + H (the "original" F) of the two nodes. Note, that we can't compare backed-up F's at all - this will not work. If it's not better - we just set the successor state to blocked. If it is - there could be the case, that the worse node is a root of a huge subtree (too complicated to explain again). In this only case we cut the subtree completely and SMA forgets a bunch of nodes at once. After replacing the worse node with the better node, we remove worse node from it's parent successor list, from frontier, leaf list, or even tree branch list (it could be even there!), set successor state to blocked for it's parent and don't forget to check if worse node's parent have all nodes blocked now - we'll need to set it's F to infinity, cause it became the terminal node.

Maybe I've got not the simplest implementation, but it's the only, that works for me. I've used 8-puzzles for tests - solving n-steps with a minimum of (n+1)-memory (counting starting node), and checking the solution optimality with conventional a-star. I've spent like 20-30 hours trying to figure out all the details - the main problem was in the complexity of the fail test cases - I've got the "replacing with better node" logic bugs only on 20+ steps with an extensive testing of thousands random seeds. Also watch out for priority queues - I had to reinsert the item in so much cases, cause any change in F, best forgotten F, or "finished" flag - changes the sort order. I ended up checking my binary heaps consistency on every dequeue. And the main idea of getting rid of the most complicated to understand bug of endless cycling is to check, that you do not decrease F's in all cases. This way the F's will keep to increase.

I'm going to share the working implementation source in a couple of weeks.

Answer 2

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.