A Guide to Budgeted Tree Search

Abstract

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.