# Exponential-Binary State-Space Search

arXiv: https://arxiv.org/abs/1906.02912 · HTML: https://mlsanity.com/paper/1906.02912/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [Understanding Sample Generation Strategies for Learning Heuristic Functions in Classical Planning](https://mlsanity.com/paper/2211.13316/) (2022)

## Abstract (arXiv)

Iterative deepening search is used in applications where the best cost bound for state-space search is unknown. The iterative deepening process is used to avoid overshooting the appropriate cost bound and doing too much work as a result. However, iterative deepening search also does too much work if the cost bound grows too slowly. This paper proposes a new framework for iterative deepening search called exponential-binary state-space search. The approach interleaves exponential and binary searches to find the desired cost bound, reducing the worst-case overhead from polynomial to logarithmic. Exponential-binary search can be used with bounded depth-first search to improve the worst-case performance of IDA* and with breadth-first heuristic search to improve the worst-case performance of search with inconsistent heuristics.