IDA* and IBEX/BTS on 3x2 STP Demo

This web page demonstrates IDA* and Budgeted Tree Search (IBEX with DFS) on the 3x2 sliding tile puzzle.

IBEX is a general framework for search algorithms that is able to improve the performance of A* with inconsistent heuristics and IDA* when the f-cost layers do not grow exponentially. Budgeted Tree Search (BTS) uses the framework of IBEX to improve the worst-case performance of IDA* from O(b^2d) to O(b^d log C*), where C* is the cost of the optimal solution.

In each iteration, IDA* uses the minimum f-cost from the previous iteration as the f-cost for search in the next iteration. This works well when the f-cost layers grow exponentially. (The default in the demo below.) If you toggle weighted edges, the f-cost layers grow more linearly (1-2 new nodes in each iteration instead of 2x growth), and IDA* will exhibit very poor performance.

BTS maintains the default behavior of IDA*, but fixes the worst case. Like IDA* it uses cost-bounded DFS to search the tree. The paper has the full details, but at the high level, the approach works to ensure that the number of node expansions doubles between each stage of the algorithm. But, it also ensures that the node expansions don't grow too fast. So, in each stage it finds the f-cost that causes the search to grow sufficiently fast, but not too fast.
Roughly speaking, it works like this:

1. Run a cost-bounded DFS using the f-cost of the root and record the number of nodes expanded and the f-cost for the next iteration.
2. Until the optimal solution is proven, repeat the following stages:
   1. Run one cost-bounded DFS with the previous f-cost limit
   2. If the number of node expansions grows by at least a factor of two, this stage is complete.
   3. If the number of node expansions grew too slowly, EXPONENTIALLY increase the f-cost
      That is, run with (f+1), (f+2), (f+4), (f+8), (f+16)..., but terminate the search if more than 8x expansions are performed
   4. If the number node expansions is between 2x and 8x, this stage is complete.
   5. At this point, we know that with (f+k) the search does less than 2x the previous node expansions and with (f+2k) more than 8x expansions are performed.
   6. Do a BINARY search between (f+k) and (f+2k) to find the f-cost for which the tree grows sufficiently fast.

The research paper has compact code and suggests reasonable data structures that implement this search. An implementation is also publicly available on github

In the default problem below, if you do not switch to non-unit edge costs, IDA* and BTS will have the same performance.
If you switch to non-unit edge costs IDA* will perform poorly. BTS will complete the first few stages easily. But, in later stages both the exponential and binary portions of the search will be illustrated.

Downloads

• IDA* on tree with non-unit costs (Running at 120 fps)
• BTS on the same tree (Running at 120 fps)
• PDF sequence (54.7MB) showing each step of the BTS search with annotated f-limits and node limits

Instructions

1. Click a state to see the state and heuristic value
2. Step the search to watch IDA* run
3. Optionally change the problem being solved to observe different behavior

Algorithm Controls IDA*/IBEX (BTS):


Problem:

Related Videos

Selected Related Publications