AAAI 2020 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. 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: 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
  • DFID (Demo)
  • IDA* (Demo)
  • IBEX/BTS (Demo)
• 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
  • APSP compression paradigm
  • Differential Heuristics (Demo)
  • Euclidean Embeddings
  • Fastmap (Demo)
• Constraints (Polynomial)
  • JPS + variants (Demo)
  • Reach (Demo)
  • Bounding Boxes (Demo)
• Representation
  • Subgoals
  • Contraction Hierarchies and Variants

---

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

---

Part III: Bidirectional Search [50 minutes]

• Motivation
• Approaches
  • Theory
  • Bidirectional Theory (Demo)
  • NBS (Demo)
  • DVCBS
  • fMM, GBHS

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