Week 2c - Informed Search

Source: Lecture Video

Outline & Objectives

• Learn about two different informed search algorithms
  • Greedy Best-First Search
  • A* Search
• Understand the role that heuristic plays in these algorithms
• Being able to use Greedy Best-First Search and A* Search to solve a search problem

Improvement to Uniform Cost Search

• UCS: Expand unexpanded node n with the lowest path cost g(n). Formally, this is via an evaluation function f(n) = g(n).
• UCS Implementation: Use a priority queue ordered by path cost g(n).
• Evaluation function f(n)
  • For UCS, path cost measures how far a node is from the initial state
  • Is this effective? Does a shorter path from the initial state mean we're nearer to the goal state?
  • Path cost ignores direction. This might lead to a lot of redundant searches.

Heuristics

Definition: A rule of thumb, simplification, or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood.

Heuristic function h(n)

• The heuristic function h(n) is an estimate of how close a state n is to the goal state.
• Informed search algorithms use heuristics to solve the search problem.
• There are good and bad heuristics

In the Romania Holiday example, the straight line distances to the Goal state could be used as the heuristic function.

Greedy Best-First Search

• General Idea: Expand the node n with the lowest heuristic h(n)
• Implementation: use a PQ ordered by heuristic h(n).
  • Evaluation function f(n) = h(n)

Steps

1. The initial state (Arad). Queue: A
2. After expanding Arad: Queue: Sibiu, Timisoara, Zerind, Arad (lowest heuristic first)
3. After expanding Sibiu: Queue: F,R,S,T,A,Z,O,A. Since A is already in the queue, it will not be added anymore.
   …

Properties

• Completeness: No (can get stuck in the loop, unless the repeated states are kept track of)
• Optimality: No (GBFS uses heuristic instead of real path cost rather than metrics)
• Time complexity:
  $O(b^m)$ (Similar to DFS but a good heuristic can improve the performance greatly)
• Space complexity:
  $O(b^m)$ (keeps all nodes in memory)

Exercise: UCS vs GBFS

• What are the issues with UCS in contrast to greedy search?
  • Complete and optimal but may "waste" search in the wrong direction.
• What are the issues with GBFS, in contrast to UCS?
  • Search generally in the "right" direction but not complete or optimal
• Is there a way to combine the two and address each's shortcomings?
  • UCS: f(n) = g(n)
  • Greedy: f(n) = h(n)
  • Combined: f(n) = g(n)+h(n)

A* Search

• General idea: Expand the node n that has incurred the least cost and is nearest to the goal state.
• Implementation: using a priority queue ordered by evaluation function f(n)
  • Evaluation function f(n) = g(n)+h(n)
  • Path cost g(n) = total path cost from start node to node n
  • Heuristic h(n) = estimated distance from node n to goal state.

Property

• Completeness: Yes
• Optimality: Yes (if heuristics are admissible/consistent)
• Time complexity: Same as UCS
• Space complexity: Same as UCS