AI_Chapter3

Posted on | In |

Chapter3. Solvinig Problems by Search

3.5 INFORMED(HEURISTIC)SEARCH STRATEGIES

  1. Minimizing the totoal estimated solution cost

  • $f(n) = g(n) + h(n)$
    • h(n) is the estimated cost of the cheapest path from n to the goal
    • g(n) the cost to reach the node

  1. Conditions for optimality: Admissibility and consistency

  • $h(n)$ be an admissible heuristic
    • an admissible heuristic is one that never overestimates the cost to reach the goal.
    • an example of admissible heuristics is the straight-line distance $h_{SLD}$
  • $h(n)$ be an consistency(monotonicity)
    • required only for applications of A* to graph search
    • A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n’$ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to $n’$
      $h(n) <= c(n,a,n’) + h(n’)$
    • every consistent heuristic is also admissible

  1. Optimality of A*

    • tree-search version of $A$ is optimal if $h(n)$ is admissible
    • graph-search versioin is optimal if $h(n)$ is consistent
      • fisrt establish: if $h(n)$ is consistent, then the values of f(n) along any path are nondecreasing
      • second prove: whenever $A$ selects a node n for expansion, the optimal path to that node has been found.*
      • A* search is complete, optimal, optimally efficient
      • prunning, optimally efficient, absolute error, relative error
      • There can be exponetially many states with $f(n) < C*$ even if the absolute error is bounded by a constant.

3.6 HEURISTIC FUNCTIONS

3.6.1 The effect of heuristic accuracy on performance

  • effective branching factor
  • why $h_2$ is better than $h_1$?

    3.6.2 Generating admissible heuristics from relaxed problems

  • relaxed problem
    A problem with fewer restrictions on the action
    the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem

    3.6.3 Generating admissible heuristic from subproblems:Pattern databases

  • patern databases, subproblem, disjoint pattern databases
  • Admissible heuristic can also be derived from the solution cost of a subproblem of a given problem.

    3.6.4 Learning heuristic from experience

    feature
  • to construct a heuristic function?
    • devise relaxed problems
    • learn from experience