4

I am reading the book "Artificial Intelligence: A Modern Approach" by Stuart and Norvig. I'm having trouble understanding a step of the recursive best-first search (RBFS) algorithm.

Here's the pseudocode.

enter image description here

What does the line s.f <- max(s.g + s.h, node.f) do?

Here's a diagram of the execution of RBFS.

enter image description here

nbro
  • 39,006
  • 12
  • 98
  • 176
Just_Alex
  • 151
  • 4
  • You don't understand only the line `s.f <- max(s.g + s.h, node.f)` or all the algorithm? – nbro Mar 20 '20 at 02:07
  • Only the specific line. – Just_Alex Mar 20 '20 at 02:39
  • I've edited your post to make it clearer then. Make sure that's still consistent with your original intent. – nbro Mar 20 '20 at 03:02
  • It is computing the cost for the successors, it will be max of the current incurred cost (node.f) or sum of s.g and s.h (as far as I remember, it is the edge cost+estimate cost to goal, I am not sure, the book might have used a similar notation before) – SajanGohil Mar 20 '20 at 11:46

1 Answers1

1

This is probably more easily understood as the collapse/restore macro. The idea is that the previously explored state was collapsed and only the minimum f-cost from the sub-tree was stored. This represents the best unexpanded state in the subtree that was collapsed.

When restoring the portion of the collapsed tree, the f-cost of the restored node could either be the original f-cost (g+h), or it could be the stored f-cost if it is larger. By taking the max, the code ensures that states that are restored maintain at least the cost of the previously best unexpanded state. (If the g+h cost is larger, then we know the state wasn't previously expanded and it wasn't previously the state on the fringe with the minimum edge cost.)

The linked paper gives several examples where similar ideas are used during search.

Nathan S.
  • 371
  • 2
  • 9