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, and student presentations.

For at least the first part of the course, the lectures will be delivered online over Zoom. Attendance is strongly encouraged, though lectures will also be recorded and posted on D2L.

Evaluation

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 best three are worth 5% each of your final grade (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%.

There will be a 25% penalty per day for any assignment handed in late. The same penalty will apply for the project proposal and final report. Paper reflections that are handed in late will get a mark of 0. The final presentation much be completed during the last class, though accommodations will be made for extenuating circumstances.

Tentative Schedule of Course Topics

Week 1: Introduction, Dijkstra's Search, and Best-First Search
Week 2: The A* Algorithm
Week 3: Abstraction-Based Heuristics
Week 4: Bounded Suboptimal Search
Week 5: Focal Search, GBFS, and Exploration
Week 6: Linear-Space Search
Week 7: Embedding-Based Heuristics
Week 8: Learning-Based Heuristics
Week 9: Bidirectional Search
Week 10: Monte Carlo Tree Search
Week 11: TBD
Week 12: Student Project Presentations