CSCE 420 Lecture 6

« previous | Thursday, January 31, 2013 | next »

A* Search

A* uses heuristic $h(n)$ to "estimate the distance to the goal" / "closeness to being solved"

• Sort frontier on $f(n)=g(n)+h(n)$, the "estimated total path length"
• Optimal if $h(n)$ is admissible (never overestimates the true distance to the goal)
• Efficiency depends on accuracy of $h(n)$: worst-case $h_{0}(n)=0$, best-case $h^{*}(n)$.

Proof of Optimality

f(G2) < f(G) since G2 is suboptimal

f(G2) > g(G2) from above
h(n) <= h*(n) since h is admissible
g(n) + h(n) <= g(n) + h*(n)
f(n) <= f(G)


f(n) = g(n) + h(n)
f(n) <= f(G) since h is admissible
f(G) = g(G) + \cancel{h(G)}
...
f(G) <= f(G2)

Efficiency Analysis

${\begin{aligned}{\text{err}}_{\text{abs}}&=\left|h(n)-h^{*}(n)\right|=\Delta \\{\text{err}}_{\text{rel}}&=\left|{\frac {h(n)-h^{*}(n)}{h^{*}(n)}}\right|\end{aligned}}$

Err from root to goal

Time complexity of A* (in certain cases) is $O(b^{\delta })$

For most heuristics, $h(n)$ grows with path length $\Delta \propto c\,d$

A* is sub-exponential if $\Delta \in O(\log {(h^{*}(n))})$

Heuristics

• Navigation: straight-line distance
• Rubik's Cube: "closer to being solved" (number of 8 face cubes that match color of center cube) ^?
• Tile Puzzle:
  • number of tiles in incorrect position
  • weight tiles by manhattan distance out of place (example of "relaxed constraints")
  • quadrants
  • swaps
  • look by rows and columns
• Block-Stacking
  • blocks out of place
  • sum of whether block b is on x, where on(b,x) is in goal.
  • number of base blocks not on table

Designing a good heuristic:

1. try to relax constraints
2. extract features (having tiles in increasing order in a row; perhaps a weighted linear combination)
3. look for patterns
4. learning

Local Search

Skip section 3.5.3 in textbook

Rather than finding a goal with least path cost, try to maximize a score associated with each state (quality, objective function)

Discrete optizmization

• optimizing numeric function (gradient descent)
• optimizing linear equations (linear programming)

Hill-climbing

def hill_climb(init, &oper, &score)
  current = init
  loop do
    children = oper(current)
    return current if children.all{|c| score(c) <= score(current)}
    current = children.max_by &score
  end
end

Four Queens

Goal: for $n$ queens, a $n\times n$ boards in which no queen can attack the other

Start with all queens on a row, incrementally move queens to minimize the number of queens being attacked