Hosted Pages

Pathfinding Benchmarks

Grid-Based Path Planning Competition

AAAI 2017 Job Fair

AAAI 2017 Workshop on what's next for AI in games

Archived Pages

AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010


IDA* (Korf, 1985) is a commonly used algorithm for heuristic search on exponential domains with unit edge costs. These videos show the search in progress on the 2x3 sliding tile puzzle. The graph of the complete search space is shown on the left. The current search state is shown on the right/bottom. The search control information is on the right/top.

States are colored by their f-cost; all states with the same f-cost are the same color. States that are not marked with a colored box have f-cost greater than the goal.

Interactive code for running this demo is available as part of the HOG2 code repository. Please contact us if you'd like more information about HOG2.

Example #1: Small search tree, accurate heuristic, very slow speed:

Example #2: Small search tree, less accurate heuristic, medium speed:
Example #3: Larger tree, less accurate heuristic, high speed:

The videos are freely available for educational use. Download (96.7 MB) (1600x800 resolution)

© Nathan Sturtevant, All rights reserved.