BIDIRECTIONAL HEURISTIC-SEARCH WITH LIMITED RESOURCES

Heuristic search strategies have useful applications for problem solving in AI. It has been observed that bidirectional heuristic search algorithms can be potentially more efficient than their unidirectional counterparts. However, the problem with bidirectional search in practice is to make the two search fronts (forward and backward) meet in the middle. De Champeaux suggested a front-to-front algorithm [3] that overcomes this problem. But the disadvantage of that algorithm is that it is computationally very expensive. In this paper, we suggest a new front-to-front algorithm that is computationally much less expensive. Our algorithm does not guarantee optimality always, but its solution quality and execution time can be controlled by some external parameters. Finally, we present some experimental results on a generic state space problem, viz. 15-puzzle, showing the effectiveness of our algorithm.