CP8326: 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.

Evaluation

The course assessments will consist of four main components: assignments, paper reflections, in-class activities, and a final project.

·      There will be 3 assignments, each worth 14% of the final grade, for a total of 36%.

·      There will be 4 paper reflections, each worth 3% of your final grade (for a total of 12%).

·      There will be six in-class activities, such that your mark will be given by the average of your highest four marked activities (for a total of 6%)

·      The final project will consist of a project proposal worth 5%, presentation worth 10%, and report worth 25%, for a total of 40%.

Prerequisites

Students should have some knowledge of standard data structures (queues, heaps, etc.), be comfortable with the basics of graph theory and logic, and have some experience writing formal proofs.

The assignments will use C++ code, but students will make only small changes to the given code base. Having some comfort coding in a object-oriented language is most important.

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: Linear-Space Search
Week 5: Bounded Suboptimal Search
Week 6: Greedy Best-First Search and Exploration
Week 7: Embedding-Based Heuristics
Week 8: Learning-Based Heuristics
Week 9: Bidirectional Search
Week 10: TBD
Week 11: TBD
Week 12: Project Presentations