publication . Conference object . Article . Preprint . Other literature type . 2019 . Embargo end date: 01 Jan 2019

Iterative Budgeted Exponential Search

Malte Helmert; Tor Lattimore; Levi H. S. Lelis; Laurent Orseau; Nathan R. Sturtevant;
Open Access
  • Published: 01 Jan 2019
  • Publisher: arXiv
  • Country: Switzerland
We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require $\Omega(2^{n})$ expansions, where $n$ is the number of states within the final $f$ bound. Existing algorithms that address this problem like B and B' improve this bound to $\Omega(n^2)$. For tree search, IDA* can also require $\Omega(n^2)$ expansions. We describe a new algorithmic framework that iteratively controls an expansion budget and solution cost limit, giving rise to new graph and tree search algorithms for which the number of expansions is $O(n \log C)$, where $C$ is the optimal solution cost. Our experiments show that the new a...
free text keywords: Data Structures and Algorithms (cs.DS), Artificial Intelligence (cs.AI), FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Computer Science - Artificial Intelligence, Discrete mathematics, Tree (graph theory), Graph (abstract data type), Limit (mathematics), Exponential search, Omega, Computer science, Search algorithm, Overhead (computing)
Funded by
Beyond Distance Estimates: A New Theory of Heuristics for State-Space Search
  • Funder: European Commission (EC)
  • Project Code: 817639
  • Funding stream: H2020 | ERC | ERC-COG
Validated by funder
Related research
Any information missing or wrong?Report an Issue