AAAI 2020 Tutorial on Heuristic Search
 Tutorial Overview | Materials | About the Presenters
The aim of the tutorial is to give a survey of selected recent directions in search, and by providing three speakers we will ensure a diverse set of topics and viewpoints. The tutorial will have several focus areas, each given by a speaker whose personal research has focused on the given area. In particular, we aim to focus on the following areas:
• 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
Throughout this tutorial, we aim to highlight the different characteristics of different search problems and indicate which search methods are used for explicit (polynomial) domains and implicit (exponential) domains.

Title: Heuristic Search
Date: TBA (likely Friday, February 7)
Time: TBA
Location: TBA
Schedule: TBA

### Tentative Schedule

Part I: Brief Introduction and Overvew [10 minutes]

• 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]
• Exponential Algorithms
• Polynomial Algorithms
• A* (Optimal search) (Demo)
• Weighted A* (Suboptimal Search) (Demo)
• Bidirectional Algorithms
• Bidirectional Theory (Demo)
• NBS (Demo)
• Exponential Heuristics
• Pattern Databases (Demo)
• Polynomial Heuristics
• Differential Heuristics (Demo)
• Euclidean Embeddings
• Fastmap (Demo)
• Compressed Path Databases

Coffee Break - 30 min
Part III: Preprocessing and Constraints [35 minutes]
• Motivation
• Approaches
• JPS + variants (Demo)
• Reach (Demo)
• Bounding Boxes (Demo)
• Compressed Path Databases
• Subgoals
• Contraction Hierarchies and Variants
Part IV: Any-Angle Search in 2D [60 minutes]
• 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]
• Motivation
• CBS as problem solving with decomposition
• CBS with heuristics
• CBS with constraints
• Future work