Hello.

I am reading Artificial Intelligence: The Modern Approach and can't understand one thing in the Recursive Best First Search (RBFS) algorithm. Here is a code of the algorithm from 3-d edition:

  function RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution, or failure
      return RBFS(problem, MAKE-NODE(problem.INITIAL-STATE), infinity)

  function RBFS(problem, node, f_limit) returns a solution, or failure and a new f-cost limit
    if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
    successors <- []
    for each action in problem.ACTION(node.STATE) do
        add CHILD-NODE(problem, node, action) into successors
    if successors is empty then return failure, infinity
    for each s in successors do // update f with value from previous search, if any
      s.f <- max(s.g + s.h, node.f)
    repeat
      best <- the lowest f-value node in successors
      if best.f > f_limit then return failure, best.f
      alternative <- the second-lowest f-value among successors
      result, best.f <- RBFS(problem, best, min(f_limit, alternative))
      if result != failure then return result

Two lines are confusing me:

for each s in successors do // update f with value from previous search, if any
   s.f <- max(s.g + s.h, node.f)

Here for all successors for the current node we calculate their f-value, but why if parent's f value is greater than it's successor's f-value we assign parent's f-value? If new s.g + s.h is less then node.f this mean that heuristic estimation for a successor node is better than for a parent node, why should we ignore it and assign parent node's heuristic estimation to a successor's node?

Thank you in advance.

asked Jun 25 '11 at 04:16

proger's gravatar image

proger
16114

edited Jun 25 '11 at 04:19


One Answer:

RBFS is a variation of A-star algorithm that using linear space. A-star algorithm, to be complete and optimal has several requirements for a heuristic function. Heuristic function should be:

  1. by nature optimistic (never overestimate the cost to reach the goal). This means that f(n) = g(n) + h(n) <= C, where C is the cost of the optimal path from initial state to the goal state.
  2. monotonic: h(n) <= c(n, a, n') + h(n'). Where c(n, a, n') - cost of performing an action a that is performed in node n to reach node n'.

This two requirements makes situation when f(parent_node) > f(successor_node) impossible.

Heuristic function should be monotonic, to make possible to use GraphSearch in A* (GraphSearch is an implementation of a Dijkstra’s algorithm to find solution in state space where same states can appear several times). For more information you can read AIMA(Chpt 4 - Informed Search and Exploration) and Dijkstra’s algorithm

answered Jun 26 '11 at 07:02

proger's gravatar image

proger
16114

edited Jun 26 '11 at 07:05

Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.