Vault

ECS170-L6

4 min read

πŸ“— -> 04/11/25: ECS170-L6

Files

🎀 Vocab

❗ Unit and Larger Context

Heuristic (Informed) Search (AIMA 3.5, 3.6)

  • Heuristic Search (AIMA 3.5, 3.6)
    • What is a heuristic?
    • How to define good heuristics?
  • Greedy Best First (AIMA 3.5)
  • A* (pronounced A-star) (AIMA 3.5)

Heuristic search relies on selection of good heuristics

  • Find heuristics through relaxed versions of the problem
  • Two criteria for good heuristics: admissibility, consistency
  • Can prune the search space by many orders of magnitude
    Greedy Best First: 𝑓(𝑛) = β„Ž(𝑛)
  • Same as Best First with the evaluation function equal to the heuristic function
  • Not complete, therefore not optimal
    A* Search: 𝑓(𝑛) = 𝑔(𝑛) + β„Ž(𝑛)
  • Best known of Best First methods
  • Optimal if heuristic is consistent, therefore complete

βœ’οΈ -> Scratch Notes

Compares to uninformed search
Improves by using heuristics, improves upon Uniform-Cost Search (UCS)

  • UCS uses priority queue ordered by an evaluation funct
  • is path cost function on path from start node to current node

However, we’re interested in path from start to goal, not start to current node

  • Replace 𝑓(𝑛) with a new function 𝑓(𝑛) = 𝑔(𝑛) + β„Ž(𝑛)
  • 𝑔(𝑛): path cost so far to the current node n
  • β„Ž(𝑛): estimated cost from the current node 𝑛 to goal
    • computation of β„Ž(𝑛) uses heuristic knowledge to get
      a good estimate
  • 𝑓(𝑛): estimated total cost of path through 𝑛 to goal

Relaxed Problems and Heuristics
A problem with fewer restrictions on the actions than the original is called a relaxed problem

The solution to a relaxed problem is a heuristic for the original problem

Criteria for Good Heuristic Functions

Admissibility - An admissible heuristic never overestimates the distance to the goal
Consistency - A heuristic is consistent if, for every node and its successor , cost function , action , and goal state , we have , similar as the triangle inequality in geometry

Dominance as a metric
Intuition: Pick an optimistic heuristic that is as accurate as possible
If for all (both admissible)

  • Then dominates , or is more accurate than
  • is therefore better for search than h1

For the 8-tile puzzle:

  • number of out of place tiles
  • total Manhattan distance (i.e. number number of moves from desired location of each tile)
    dominates

Given a cost function: 𝑓(𝑛) = 𝑔(𝑛) + β„Ž(𝑛)

  • is path cost so far to n
  • is heuristic estimate for n to goal

Greedy Best First ignores , so

Evaluation:

Completeness? - No, can get stuck in loops when using tree search
Cost Optimality? - No, just finds node n with lowest path to goal

Complexities:

  • Time - , worst case like DFS
  • Space - , priority queue keeping all unexpanded nodes in memory

Best known form of best-first search

  • Avoid expanding expensive paths
  • Expand most promising first
  • Uses the classic 𝑓(𝑛) = 𝑔(𝑛) + β„Ž(𝑛)
  • Implementation: Frontier with a PQ
Evaluation

Completeness? - Yes, if heuristic is consistent
Cost Optimality? - Yes, if heuristic is consistent

πŸ§ͺ -> Refresh the Info

Did you generally find the overall content understandable or compelling or relevant or not, and why, or which aspects of the reading were most novel or challenging for you and which aspects were most familiar or straightforward?)

Did a specific aspect of the reading raise questions for you or relate to other ideas and findings you’ve encountered, or are there other related issues you wish had been covered?)

πŸ”— -> Links

Resources

  • Put useful links here

Connections

  • Link all related words

Graph View

Backlinks