A Guide to Budgeted Tree Search

Authors

  • Nathan Sturtevant University of Alberta
  • Malte Helmert University of Basel

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.

Downloads

Published

2021-09-01