Ariel Felner

Best-First Search (BFS) is a classic general search technique. It maintains an open-list of generated nodes and expands the least-cost node from it while adding its unvisited neighbors to the open-list. The main limitation of BFS is that it stores all the states it visits in memory. BFS is composed by a number of primitive steps and can be implemented in many ways. In this paper we deepen into implementation details of BFS by analyzing the standard primitive steps and their execution order. In particular, we study the roles of the duplicate detection and of the goal test primitives. Based on this study we introduce a new BFS variation called BFS with Lookahead (BFSL). The basic idea of BFSL is to to perform limited DFS lookaheads from the frontier of the BSF (open-list). We show that this algorithm requires significantly less memory. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. Experimental results on several domains demonstrate the benefits of all our ideas.