- Background and Fundamental Algorithms. This section will discuss the core algorithms in the eld of heuristic search, including the use of heuristics and constraints in search, with live online demos of each of the algorithms. Speaker: Nathan Sturtevant
- Preprocessing and Heuristics This section will discuss many different ways in which preprocessing can be used to speedup search. Speaker: Sven Koenig and Daniel Harabor
- Any-angle Search. This section will discuss how to perform path nding between locations on a grid where movement is not restricted to the grid itself. Speaker: Sven Koenig and Daniel Harabor

**Title**: Heuristic Search

**Date**: Tuesday, May 14

**Time**: 2:00pm - 6:00pm

**Location**: MB 3.445

**Schedule**: 2:00-3:30pm Parts I and II. 4:00-6:00pm Parts III-V

**Part I: Brief Introduction and Overvew** [10 minutes] (Nathan Sturtevant)

- Introduction
- Exponential domains
- Algorithms
- Heuristics

- Polynomial domains
- Algorithms
- Heuristics

- Bidirectional Search
- Theory
- Algorithms

- Case studies
- Constraints
- Any-Angle Search
- MAPF

**Part II: Baseline Algorithms with Examples**[75 minutes] (Nathan Sturtevant, Daniel Harabor and Sven Koenig)

- Exponential Algorithms
- Polynomial Algorithms
- Bidirectional Algorithms
- Exponential Heuristics
- Pattern Databases (Demo)

- Polynomial Heuristics

Coffee Break - 30 min

**Part III: Preprocessing and Constraints**[35 minutes] (Nathan Sturtevant, Daniel Harabor & Sven Koenig)

- Motivation
- Approaches

**Part IV: Any-Angle Search in 2D**[60 minutes] (Sven Koenig and Daniel Harabor)

- Motivation
- Analysis of Path Lengths
- Simple (Suboptimal and Optimal) Approaches
- Field D*
- Theta* and its Variants

- Optimal Approaches
- Anya
- Polyanya

- Generalization from 2D to 3D
- Future work

**Part V: Multi-Agent Path Planning**[25 minutes] (Sven Koenig and Daniel Harabor)

- Motivation
- CBS as problem solving with decomposition
- CBS with heuristics
- CBS with constraints
- Future work