**Title**: Heuristic Search

**Date**: Friday, February 7

**Time**: 8:30-12:30

**Location**: Regent

### Tentative Schedule

**Part I: Brief Introduction and Overvew** [10 minutes]

- Introduction
- Exponential domains
- Algorithms
- Heuristics
- Constraints

- Polynomial domains
- Algorithms
- Heuristics
- Constraints

- Bidirectional Search
- Theory
- Algorithms

- Application: MAPF

**Part II: Baseline Algorithms with Examples**[1hr 35 minutes]

- Exponential Algorithms
- Polynomial Algorithms
- A* (Optimal search) (Demo)
- Inconsistency - IBEX

- Suboptimal Search Algorithms
- Weighted A* (Suboptimal Search) (Demo)
- Focal List Algorithms
- Alternate Priority Funtions (eg XDP)

- Exponential Heuristics
- Pattern Databases (Demo)

- Polynomial Heuristics
- Constraints (Polynomial)
- Representation
- Subgoals
- Contraction Hierarchies and Variants

Coffee Break - 30 min - 10:15 - 10:45

**Part III: Bidirectional Search**[50 minutes]

**Part IV: Any-Angle Search**[20 minutes]

- Search on visibility graphs
- Search on grid graphs
- search on grid graphs with higher-degree vertices
- search with post smoothing
- Theta*
- other any-angle search algorithms

**Part V: Multi-Agent Path Planning**[30 minutes]

- The multi-agent path-finding problem
- An application: automated warehousing
- Complexity of finding (optimal or bounded-suboptimal) solutions
- Multi-agent path finding algorithms
- A*
- conflict-based search
- lifelong multi-agent path finding