CMPUT 651 - Real-time Heuristic Search

Overview

Heuristic search is a core area of Artificial Intelligence with applications to planning, scheduling and game playing. Realtime heuristic search is critical in search problems where plan execution needs to start before a complete plan can be computed. Since the inception of real-time heuristic search in the early 90s, a great number of algorithms have been proposed and evaluated. We will work through both seminal and contemporary heuristic search algorithms covering: key concepts in heuristic search, lookahead techniques, heuristic learning rules, automatic state abstraction, heuristic generation, subgoal generation, state space pre-processing, moving target search, non-stationary environments, automatic parameter tuning, performance prediction, distributed search, and search with computational errors (e.g., on robots) and possibly other topics. The course will host a real-time heuristic search competition (e.g., real-time pathfinding on video-game maps from BioWare's Dragon Age, Blizzard's StarCraft) and the students' algorithms will compete in it.

CMPUT 651 Syllabus (PDF, 144kb)

Objectives

• Gain understanding of the fundamentals of heuristic search
• Learn a wide range of real-time heuristic search techniques and algorithms
• Become familiar with practical issues in deploying real-time heuristic-search algorithms in the field
• Get hands-on experience in designing, implementing, evaluating and applying real-time heuristic search algorithms

Course Work

• Paper synopses
• Paper presentations
• Project, proposals and reports