Heuristic Search:

• What is Heuristic Search? Heristic Search is an informed search, which use problem-specific Knowledge beyond the defination of the problem itself - often more fficient than uniformed search stratedy.

• Best first search Very similar to Normal Graph Search algorithm (uniformed), BUT, at steps each node is selected for expansion based on an evalution function f(n).

• heristic function, often denoted by h(n): is the estimated cost of the cheapest path from node n to a goal node.

• Beam Search Breadth First Search where each step you prune all but the n best nodes, as decided by your heuristic. Prevents fringe from being too enourmous, but sucks lots when heuristic sucks (sometimes not finding a path at all)

• A* what is A*? A* is a special form of best first search. Its evaluation function f(n) is g(n) + h(n), where g(n) = the cost to reach the node, and h(n) = the cost to get from the node to the goal. Hence, at steps we use f(n) with smallest value.

  • Optimality proof
    • Is optimality useful
    • Admissibility
      A* is optimal if h(n) is admissible. What is admissible huristic? h(n) doesnot overestimate the cost to reach the goal
    • Monotoniciticy Monotone: h(n) is said to be monotonic 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' plus the estimated cost of reaching the goal from n'
  • Non-optimality mods
    • Delta-min in queue
    • Non-admissible heuristics
  • Dominance of heuristics
• Heuristics
  • Steps to Goal
  • Cost to Goal
  • Heuristic quality/search time tradeoff

• Implementation

  • Non-mutable lists
  • Back-pointers
  • Links into A* heap

• Invention of heuristics through relaxation

  • Relation to abstraction