A Course on Single-Agent Search: Interactive Demos

This page lists a broad range of demos for learning about single-agent heuristic search. In addition to each page containing a demo, the demo pages also contain links to lecture videos, and references to relevant papers.

When teaching a course on heuristic search, I use these as part of a flipped classroom. Students watch the videos and then we interact with the demos and discuss the material more deeply together. But, they are available here for anyone to interact and learn from.

Contributions are welcome, and can be sent to nathanst at ualberta.ca including:

• Additional references for any of the pages (included a .bib file)
• Typos or corrections
• Suggested foundational topics for future videos

Demonstrations

• Domains
  • The Sliding Tile Puzzle
  • The Pancake Puzzle
  • The Racetrack Domain
  • Two-Segment Robotic Arm
• Optimal Graph Search
  • DFS, BFS, DFID on an exponential tree
  • Dijkstra's Algorithm on a graph (integer weights)
  • Dijkstra, A* and Weighted A* on a graph
  • A* on a grid map
  • NBS on a grid map
  • JPS on a grid map
  • Find the shortest path to the closest target
• Suboptimal Graph Search
  • Dijkstra, A* and Weighted A* on a graph
  • A*, Weighted A*, A* Epsilon, Optimistic Search and Dynamic Potential Search on a grid map
  • Weighted A* - Overhead of Re-expansions
  • Abstraction and refinment in grid maps
  • Abstraction and refinment on dynamic grid maps with dynamic costs
• Tree Search
  • IDA* on the 3x2 Sliding tile puzzle
  • IBEX/BTS and IDA* on the 3x2 sliding tile puzzle with non-unit costs
• Heuristics
  • IDA* on the 3x2 Sliding tile puzzle with Pattern Databases
  • A* with Differential Heuristics
  • FastMap Heuristic Calculation Demo
• Inconsistent Heuristics
  • IDA* with Min-Compressed Pattern Databases
  • A* and IBEX/BGS with inconsistent heuristics
• Constraints
  • A* with Reach
  • A* with Bounding Boxes
  • Abstraction and refinment in grid maps
  • Abstraction and refinment on dynamic grid maps with dynamic costs
  • Transit Routing Calculation Demo
• Theory
  • Necessary expansions in unidirectional and bidirectional search
  • The Must-Expand graph (GMX) for bidirectional search
  • Fractional meeting points for bidirectional search algorithms
  • Worst-case inconsistent heuristic graphs
  • Weighted A* - Overhead of Re-expansions

The demos here are written in C++ and compiled into javascript using emscripten. Source code for the demos is available in HOG2.