[인공지능] Chapter 3. Informed Search

Heuristic

• 특정 state가 얼마나 goal state에 가까운지 평가하는 함수
• 특정 Search problem을 위해 고안됨

Greedy Search

• goal state에 가장 가까워 보이는 노드로 확장
• Strategy
  • expand a node that you think is closest to a goal state
  • Heuristic 활용: 각각의 state에서 가장 가까운 goal까지의 거리 계산
• A common case
  • Best-first takes you straight to the goal
• Worst-case
  • kike a badly-guided DFS

A* Search

• UCS + 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
  • Only stop when we dequeue a goal
• Is A* optimal
  • yes!

Admissible Heuristics

• 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 Heuristic
  • A heuristic h is admissible (optimistic) if:where h*(n) is the true cost to a nearest goal
  • 0 ≤ h(n) ≤ h*(n)
  • Coming up with admissible heuristics is most of what’s involved in using A* in practice

UCS vs A*

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

Creating Admissible Heuristics

• 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

Combining heuristics

• Trivial heuristics
  • The zero heuristic is bad
  • The exact heuristic is good but usually too expensive
• Dominance
  • 모든 n에 대해 ha(n) ≥ hc(n)이라면,(Roughly speaking, larger is better as long as both are admissible)
  • ha ≥ hc
  • What if we have two heuristics, neither dominates the other?
    • from a new heuristic by taking the max of both
    • h(n) = max(ha(n), hb(n))
    • Max of admissible heuristics is admissible and dominates both

Graph Search

• Idea
  • never expand a state twice
• Implement
  • Tree search + set of expanded states (closed set)
  • Expand the search tree node-by-node
  • 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
• Store the closed set as a set, not a list

Consistency of Heuristics

• Main idea
  • estimated heuristic costs ≤ actual costs
  • Admissibility
    • heuristic cost ≤ actual cost to goal
    • h(A) ≤ actual cost from A to G
  • Consistency
    • heuristic ‘arc’ cost ≤ actual cost
    • h(A) - h(C) ≤ cost(A to C)
• Consequences of consistency
  • The f value along a path never decreases
  • h(a) ≤ cost(A to C) + h(C)
  • A* graph search is optimal

Optimality

• Tree search
  • A* is optimal if heuristic is admissible
  • UCS is a special case (h=0)
• Graph search
  • A* is optimal if heuristic is consistent
  • UCS optimal (h=0 is consistent)
• Consistency implies admissibilty
• In general, most natural admissible heuristics tend to be consistent, especially if from relaxed problems
• Optimality of A* graph search
  • consider what A* does with a consistent heuristic
    • Fact1: In tree search, A* expands nodes in increasing total f value
    • Fact2: For every state s, nodes that reach s optimally are expanded before nodes that reach s suboptimally
    • Result: A* graph search is optimal

A* Summary

• A* uses both backward costs and forward costs
• A* is optimal with admissible, consistent heuristics
• Heurisitc design is key: often use relaxed problems

Search and Models

• Search operates over models of the world
  • The agent doesn’t actually try all the plans out in the real world!
  • Planning is all ‘in simulation’
  • Your search is only as good as your models