AAMAS 2019 Tutorial on Heuristic Search

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: 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
  • DFID (Demo)
  • IDA* (Demo)
• 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
  • APSP compression paradigm
  • Differential Heuristics (Demo)
  • Euclidean Embeddings
  • Fastmap (Demo)
  • Compressed Path Databases

---

Coffee Break - 30 min

---

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

• 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] (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