IJCAI 2018 Tutorial on Heuristic Search

The aim of the tutorial is to give a survey of selected recent directions in search, and by providing multiple speakers we will ensure a diverse set of topics and viewpoints.

Title: Tutorial on Heuristic Search
Date: Friday, July 13
Time: 2:00-6:00pm
Location: Meeting Room C6
Schedule:

• 14:00-15:30: Part I-IIa
• 15:30-16:00: Coffee break
• 16:00-18:00: Part IIb, III, IV

Part I: Introduction and Overview (75 Minutes, Nathan Sturtevant)

• Introduction
• Exponential domains
  • Algorithms (DFID, IDA*)
  • Heuristics (PDBs)
• Polynomial domains
  • Algorithms (A*, JPS)
  • Heuristics (Differential heuristics)
  • Constraints (Bounding boxes)
• Bidirectional Search
  • Theory (Necessary expansions)
  • Algorithms (NBS, fMM)

Part II: Preprocessing and Heuristics (40 Minutes, Sven Koenig and Daniel Harabor)

• Motivation
• Calculation of Heuristics
  • Differential Heuristics (brief)
  • Fastmap
• Search algorithms
  • Contraction Hierarchies and Variants
  • Compressed Path Databases

Part III: Any-Angle Search in 2D (40 Minutes, Sven Koenig and Daniel Harabor)

• Motivation
• Analysis of Path Lengths
• Simple (Suboptimal and Optimal) Approaches
• Suboptimal Approaches
  • Field D*
  • Theta* and its Variants
• Optimal Approaches
  • Anya
  • Polyanya
• Generalization from 2D to 3D

Part IV: Optimal Search (50 Minutes, Ariel Felner)

• Inconsistent heuristics
• Collapse/restore macros
  • SMA*
  • ILBFS/RBFS
  • EPEA*
  • Lookahead A*