Using Lookaheads with Optimal Best-First Search

Authors

  • Roni Stern Ben Gurion University of the Negev
  • Tamar Kulberis Ben Gurion University of the Negev
  • Ariel Felner Ben Gurion University of the Negev
  • Robert Holte University of Alberta

DOI:

https://doi.org/10.1609/aaai.v24i1.7559

Keywords:

Heuristic search, Lookahead, Best-first search

Abstract

We present an algorithm that exploits the complimentary benefits of best-first search (BFS) and depth-first search (DFS) by performing limited DFS lookaheads from the frontier of BFS. We show that this continuum requires significantly less memory than BFS. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. We demonstrate this idea for breadth-first search and for A*. Additionally, we show that when using inconsistent heuristics, Bidirectional Pathmax (BPMX), can be implemented very easily on top of the lookahead phase. Experimental results on several domains demonstrate the benefits of all our ideas.

Downloads

Published

2010-07-03

How to Cite

Stern, R., Kulberis, T., Felner, A., & Holte, R. (2010). Using Lookaheads with Optimal Best-First Search. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 185-190. https://doi.org/10.1609/aaai.v24i1.7559

Issue

Vol. 24 No. 1 (2010): Twenty-Fourth AAAI Conference on Artificial Intelligence

Section

Constraints, Satisfiability, and Search