A Course on Single-Agent Search: Class Outline

This is an outline for a graduate course on Heuristic Search, including links to lectures and demo material. At the University of Alberta lectures are 90min 2x a week for 13 weeks.

• Lecture 1: Introduction to Search
  
  • Video 1: Intro to Search

Search Algorithms

• Lecture 2: Uninformed Search
  • Video 2: Uniform Cost Trees
  • Demo: DFS, BFS, DFID
  • Video 3: Best-First Search
  • Demo: Dijkstra's Algorithm
• Lecture 3: Heuristics and A*
  • Video 4: Heuristics
  • Video 5: A*
  • Demo: Dijkstra, A* on a graph
  • Demo: Dijkstra, A* on a grid map
• Lecture 4: IDA* and variants (Parallel IDA*, A*+IDA*)
  • Video 6: IDA*
  • Demo: IDA*
  • Video 7: Enhancing IDA*
• Lecture 5: Budgeted Tree Search (IBEX)
  • Video 8: Budgeted Tree Search
  • Demo: BTS Demo
• Lecture 6: Suboptimal Search
  • Video 9: Weighted A*
  • Video 10: Other Suboptimal Algorithms
  • Demo: Suboptimal Algorithms
• Lecture 7: Re-openings in Suboptimal Search; General Priority Functions
  • Video 11: Weighted A* Re-expansions
  • Demo: Weighted A* Re-expansions
  • Video 12: Avoiding Re-expansions in WA*
  • Video 13: General Phi functions
• Lecture 8: Creating General Suboptimal Priority Functions
  • Video 14: Creating Phi Functions
  • Demo: Suboptimal Algorithms
• Lecture 9: Bidirectional Search: Theory
  • Video 15: Necessary Expansions in Bidirectional Search
  • Demo: Can you identify necessary expansions?
  • Video 16: Bidirectional Search as a Minimum Vertex Cover
  • Demo: The Must-Expand Graph
• Lecture 10: Bidirectional Search: Algorithms
  • Video 17: Near-Optimal Bidirectional Search (NBS)
  • Demo: NBS
  • Video 18: Bidirectional Search with a Consistent Heuristic
• Lecture 11: External-Memory Search
  • Video 19: External-Memory Search in Explicit State Spaces
  • Video 20: External-Memory Search in Implicit State Spaces
• Lecture 12: Multi-Agent Pathfinding
  • Video 21: Conflict-Based Search (CBS)

Heuristics

• Lecture 13: Pattern Databases
  • Video 22: Heuristics and Abstraction
  • Video 23: Pattern Databases
  • Demo: Pattern Databases with IDA*
• Lecture 14: Ranking and Unranking Functions
  • Video 24: Ranking Functions
  • Video 25: k-Permutations and Linear-Time Ranking
• Lecture 15: PDB Enhancements
  • Video 26: Additive PDBs
  • Video 27: Compressed PDBs
  • Demo: Compressed PDBs
  • Video 28: Neural Network Compression of PDBs
• Lecture 16: Predicting IDA* Performance
  • Video 29: Asymptotic Branching Factor of a State Space
  • Video 30: IDA* Performance
• Lecture 17: Inconsistent Heuristics
  • Video 31: Inconsistent Heuristics
  • Demo: Inconsistent Heursitics
  • Video 32: Handling Inconsistent Heuristics
• Lecture 18: Budgeted Graph Search
  • Video 33: Breadth-First Heuristic Search
  • Video 34: Budgeted Graph Search
  • Demo: Budgeted Graph Search
• Lecture 19: Heuristics for Polynomial State Spaces
  • Video 35: Heuristics for Polynomial Domains
  • Video 36: Subset Selection of Heuristics
  • Demo: Differential Heuristics
• Lecture 20: Compressed DH, Fastmap
  • Video 37: Compressed Differential Heuristics
  • Video 38: Euclidean Embeddings
  • Demo: FastMap Embdding

Constraints

• Lecture 21: Grid Search
  • Video 39: Canonical Orderings
  • Video 40: Canonical A*, Canonical Dijkstra, Jump Point Search (JPS), Weighted JPS
  • Demo: Canonical Ordering/Algorithms
• Lecture 22: Constraints
  • Video 41: Constraints and Bounding Boxes
  • Demo: Bounding Boxes
  • Video 42: Reach for A*
  • Demo: Reach for A*
  • Video 43: Swamps and Other Constraints
• Lecture 23: Contraction Hierarchies / Transit Routing
  • Video 44: Transit Routing
  • Demo: Transit Routing Pre-Computation
  • Video 45: Contraction Hierarchies
• Lecture 24: Compressed Path Databases
  • Video 46: Compresed Path Databases
• Lecture 25: Abstraction and Refinement
  • Video 47: Abstraction and Refinement
  • Demo: Abstraction for a static Grid Map
  • Demo: Abstraction for Dynamic Maps
• Lecture 26: Conclusion
  • Video 48: Conclusion and Summary