A* Search

Informed Search and Heuristic Design

AI, Artificial and Computational Intelligence
AI, ACI, Informed Search, Heuristics, Greedy Best-First Search, A* Search

Informed Search and Heuristic Design #

Informed search uses additional knowledge to estimate which states are most promising. A good heuristic can greatly reduce unnecessary exploration while preserving solution quality.

  • Notion of Heuristics
  • Informed Search Algorithms : Greedy best first search, A* search
  • Optimality of A*
  • Heuristic Functions
  • Heuristic Accuracy & Algorithm performance
  • Admissible heuristics from relaxed problems, pattern databases. Experience.
  • Use case : Learning Heuristics using Supervised Learning

Learning Objectives #

  • explain the purpose of a heuristic function
  • compare Greedy Best-First Search and A* Search
  • trace A* using OPEN and CLOSED lists
  • test heuristics for admissibility and consistency
  • explain heuristic dominance and effective branching factor
  • derive heuristics from relaxed problems and subproblems
  • describe pattern databases, landmarks and learned heuristics

1. What Is Informed Search? ☆ #

Uninformed search knows only how to generate successors and recognise a goal. Informed search additionally estimates whether one non-goal state is more promising than another.