Informed Search


CSE 440: Introduction to Artificial Intelligence

Vishnu Boddeti


Content Credits: CMU AI, http://ai.berkeley.edu

Today

  • Informed Search Methods
    • Heuristics
    • Greedy Search
    • $A^*$ Search
  • Reading
    • Today's Lecture: RN Chapter 3.5-3.7, 4.1-4.2
    • Next Lecture: RN Chapter 6

Search Problems

Uninformed Search
  • Methods we saw:
    • DFS
    • BFS
    • UCS
  • Searching with your EYES CLOSED

Example: Pancake Problem

Heuristics

Search Heuristics

  • A heuristic is:
    • A function that estimates how close a state is to a goal
    • Designed for a particular search problem
    • Examples: Manhattan distance, Euclidean distance

Example: Heuristic Function

Example: Heuristic Function

  • Eg: index of the largest pancake that is still out of place

Greedy Search

Example: Heuristic Function

Greedy Search: Romania

  • Expand the node that seems closest...
  • What can go wrong?

Greedy Search

  • Strategy: expand a node that you think is closest to a goal state
    • Heuristic: distance estimate 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

Greedy Demo

$A^*$ Search

Key Idea: Combine UCS and Greedy

Combining UCS and Greedy

  • 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?

  • What went wrong?
  • Actual bad goal cost $\leq$ estimated good goal cost
  • We need estimates to be less than actual costs

Admissibility

  • Inadmissible (pessimistic) heuristics break optimality by trapping good plans on the fringe.
  • Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs

Admissible Heuristics

  • A heuristic $h$ is admissible (optimistic) if:
    • $$0 \leq h(n) \leq h^*(n)$$
  • where $h^*(n)$ is the true cost to a nearest goal
  • Example:
  • In practice, coming up with an admissible heuristic is most of what is involved in using $A^*$.

Optimality of $A^*$ Tree Search

  • Assume:
    • A is an optimal goal node
    • B is a suboptimal goal node
    • h is admissible
  • Claim:
    • A will exit the fringe before B

Optimality of $A^*$ Tree Search

Proof:
  • Imagine $B$ is on the fringe
  • Some ancestor $n$ of $A$ is on the fringe too
  • Claim: $n$ will be expanded before $B$
    • $f(n)$ is less or equal to $f(A)$
    • $f(A)$ is less than $f(B)$
    • $n$ expands before $B$
  • All ancestors of $A$ expand before $B$
  • A expands before B
  • $A^*$ search is optimal
    $$ \begin{eqnarray} f(n) &=& g(n) + h(n) \nonumber \\ f(n) &\leq& g(A) \mbox{ admissibility of } h \nonumber \\ g(A) &=& f(A) \mbox{ } h=0 \mbox{ at goal} \nonumber \end{eqnarray} $$ $$ \begin{eqnarray} g(A) &\leq& g(B) \mbox{ } B \mbox{ is suboptimal} \nonumber \\ f(A) &\leq& f(B) \mbox{ } h=0 \mbox{ at goal} \nonumber \end{eqnarray} $$ $$ \begin{eqnarray} f(n) \leq f(A) < f(B) \nonumber \end{eqnarray} $$

UCS vs $A^*$ Contours

  • Uniform-cost expands equally in all "directions"
  • $A^*$ expands mainly toward the goal, but does hedge its bets to ensure optimality

$A^*$ Demo

$A^*$ Applications

  • Video games
  • Pathing / routing problems
  • Resource planning problems
  • Robot motion planning
  • Language analysis
  • Machine translation
  • Speech recognition
  • ...

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 can often be useful too.

Example: 8 Puzzle

  • What are the states?
  • How many states?
  • What are the actions?
  • How many successors from the start state?
  • What should the costs be?

8 Puzzle: Heuristic III

$$ \begin{bmatrix} 7 & 2 & 4 \\ 5 & \times & 6 \\ 8 & 3 & 1 \end{bmatrix} $$
  • How about using the actual cost as a heuristic?
    • Would it be admissible?
    • Would we save on nodes expanded?
    • What is wrong with it?
  • With $A^*$: a trade-off between quality of estimate and work done 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

Graph Search

Tree Search: Extra Work !!

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 or why not?
  • How about optimality?

$A^*$ Graph Search Gone Wrong?

State Space Graph
Search Tree

Consistency of Heuristics

  • Main Idea: estimated heuristic costs $\leq$ actual costs
    • Admissibility: heuristic cost $\leq$ actual cost to goal
      • $h(A) \leq$ actual cost from A to G
    • Consistency: heuristic "arc" cost $\leq$ actual cost for each arc
      • $h(A) - h(C) \leq$ cost(A to C)
  • Consequences of consistency:
    • The $f$ value along a path never decreases
      • $h(A) \leq$ cost(A to C) $+$ h(C)
    • $A^*$ graph search is optimal

Tree-Search Pseudo-Code

Graph Search Pseudo-Code

$A^*$ Summary

  • $A^*$ uses both backward costs and (estimates of) forward costs
  • $A^*$ is optimal with admissible heuristics
  • Heuristic design is key: often use relaxed problems

Q & A

XKCD