A Guide to Budgeted Tree Search

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Long Papers

Budgeted Tree Search (BTS), a variant of Iterative Budgeted Exponential Search, is a new algorithm that has the same performance as IDA* on problems where the state space grows exponentially, but has far better performance than IDA* in other cases where IDA* fails. The goal of this paper is to provide a detailed guide to BTS with worked examples to make the algorithm more accessible to practitioners in heuristic search.

10.1609/socs.v11i1.18537