It is a very well-known result that in the presence of a perfect heuristic function (that is, h (n,t) = g^* (n,t)), an admissible single-agent search algorithm expands only nodes that lie within the optimal path. However, these functions are very difficult to obtain, and, in most cases, heuristics are subjected to errors that are known to propagate exponentially. Therefore, in order to obtain optimal solutions, an exponentially increasing number of nodes has to be expanded, according to Korf et al. [1]. In very difficult domains (such as planning [2] and Sokoban [3]), a good approach consists of sacrificing quality in favor of running time, obtaining satisfiable solutions in a moderate amount of time.

It is within this framework that this work deserves attention; readers interested in optimal solutions are not directed to this paper. In this paper, the authors introduce an idea that is as simple and easy to understand as the WA^* algorithm: KBFS(k). “KBFS(k) is a generalization of best-first-search (BFS) in that each expansion cycle of KBFS(k) expands the best k nodes from the open list. Their children are generated and added to the open list, and only then does a new node expansion cycle begin, expanding the k best nodes in the new open list.” This method “adds diversity” to the search, since KBFS(k) can backtrack clearly to any node in the search tree.

The idea is also proven to be effective for some values of k in some domains, including random trees, various sizes of the N-puzzle problem, and number partitioning, when considering the number of expansions. Unfortunately, figures are not provided about the running time. This consideration is especially relevant since any BFS single-agent search algorithm handles the open list in logarithmic time, and it is observed in the empirical results provided by the authors that a very low number of expansions can be obtained for large values of k, which also implies longer times for managing the open list. Nevertheless, this consideration does not affect the general validity of the algorithm, which is shown to outperform BFS.

From a theoretical point of view, no mathematical model is provided for predicting either the behavior of KBFS(k) or the optimal value of k (which is identified as a future work guideline), though, at first glance, it does not seem difficult to generalize the analysis by Pearl [4] or Korf et al. [1].

All in all, the paper is very well written and serves as a basis for further research. A basic understanding of the main principles of single-agent search algorithms is sufficient to grasp the concepts introduced.