CP8207/8315: Heuristic Search

Heuristic search is a popular Artificial Intelligence approach that has been used in a variety of applications including robotics, combinatorial optimization, route pathfinding, and automated planning. In this course, we will investigate algorithms for solving single-agent search problems, and introduce methods for automatically generating heuristic functions. Topics will include optimal algorithms, abstraction and graph embedding-based methods for generating heuristic functions, bounded suboptimal algorithms, and Monte Carlo Tree Search-based algorithms.

Below is a truncated version of the course outline. For the full outline, please see the course website on D2L.

Course Learning Outcomes

At the end of the course, students should

1. Be able to identify if a problem can be suitably solved using heuristic search techniques, and understand how to represent such problems to do so

2. Understand the fundamentals behind various heuristic search algorithms

3. Understand a variety of methods for constructing heuristic functions

4. Implement and evaluate a heuristic search-based system for applicable problems

5. Improve their ability to read, understand, and explain research papers in the field

Teaching Methods

The course will be organized around the three lecture hours per week. This time will be used for a combination of instructor lectures, discussions on paper readings, in-class coding/analysis activities, and student presentations.


The course assessments will consist of three main components: assignments, paper reflections, and a final project. There will be three assignments, each worth 15% of the final grade, for a total of 45%. There will be five paper reflections, such that your mark is given by the average of your highest four marked reflections (for a total of 15%). The final project will consist of a project proposal worth 5%, presentation worth 10%, and report worth 25%, for a total of 40%.

Tentative Schedule of Topics

Week 1: An Introduction to Heuristic Search Problems and Methods
Week 2: Best-First Search and the A* Algorithm
Week 3: Abstraction-Based Heuristics
Week 4: Bounded Suboptimal Search and WA*
Week 5: Modeling
Week 6: Linear-Space Search
Week 7: Satisficing Search and Random Exploration
Week 8: Embedding-Based Heuristics
Week 9: Learning-Based Heuristics
Week 10: Bidirectional Search
Week 11: TBD
Week 12: Student Project Presentations