cs188 lecture3

Abstract

Informed Search:

• Heuristics
• Greedy Search
• A* Search

Graph Search

General Tree Search

lec3-1

We call it "general" because we can change the strategy depending on the search algorithm we use.

Search Heuristics

A heuristic is:

• A function tat estimates how close a state is to a goal
• Designed for a particular search problem

Need to find a heuristic function.

A good selection of heuristic function maybe cost less in algorithms.

Greedy Search

Expand the node that seems closest…

• Strategy: expand a node that you think is closest to a goal state
  • Heuristic: estimate of distance to nearest goal for each state
• A common case:
  • Best-first takes you straight to the (wrong) goal
• Worst-case: like a badly-guided DFS

A* Search

• Uniform-cost orders by path cost, or backward cost \(g(n)\)
• Greedy orders by goal proximity, or forward cost \(h(n)\)
• A* search orders by the sum: \(f(n) = g(n) + h(n)\)

When should A* terminate

• Should we stop when we enqueue a goal?

• No: only stop when we dequeue a goal

Is A* optimal

A* is not generally optimal.

Actual bad cost < estimated good goal cost.

We need estimates to be less than actual costs.

Idea: Admissibility

If heuristics satisfy the property, then it's optimistic, then A* is optimal.

Admissible Heuristics

A heuristic \(h\) is admissible (optimisitic) if: \[ 0 \leq h(n) \leq h^*(n) \] where \(h^*(n)\) is the true cost to a nearest goal.

Coming up with admissible heuristics is most of what’s involved in using A* in practice.

Creating Admissible Heuristics

• Most of the work in solving hard search problems optimally is in coming up with admissible heuristics
• Often, admissible heuristics are solutions to relaxed problems, where new actions are available
• Inadmissible heuristics are often useful too

Semi-Lattice of Heuristics

• With A*: a trade-off between quality of estimate and work per node
  • As heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself

Trivial Heuristics, Dominance

• Dominance: \(h_a \geq h_c\) if

\[ \forall n:h_a(n) \geq h_c(n) \]

• Heuristics form a semi-lattice:

  • Max of admissible heuristics is admissible \[ h(n) = max(h_a(n),h_b(n)) \]

• Trivial heuristics

  • Bottom of lattice is zero heuristic
  • Top of lattice is the exact heuristic

Graph Search

• Idea: never expand a state twice
• How to implement:
  • Tree search + set of expanded states (“closed set”)
  • Expand the search tree node-by-node, but…
  • Before expanding a node, check to make sure its state has never been expanded before
  • If not new, skip it, if new add to closed set
• Important: store the closed set as a set, not a list
• Can graph search wreck completeness? Why/Why not?
• Optimality?

Consistency of Heuristics

• Main idea: estimated heuristic costs \(\leq\) actual costs
  • Admissibility: heuristic cost \(\leq\) actual cost to goal
  • Consistency: heuristic "arc" cost \(\leq\) actual cost for each arc
• Consequences of consistency:
  • The f value along path never decreases
  • A* graph search is optimal