AAAI Publications, Thirteenth Annual Symposium on Combinatorial Search

Font Size: 
A Guide to Budgeted Tree Search
Nathan Sturtevant, Malte Helmert

Last modified: 2020-05-08

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.


Full Text: PDF