GBFHS: A Generalized Breadth-First Heuristic Search Algorithm

Recently there has been renewed interest in bidirectional heuristic search. New algorithms, e. g. , MM, MMe, and NBS, have been introduced which seem much closer to refuting the accepted wisdom that "any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search". However, MM and MMe can still be dominated by their bidirectional brute-force versions, i. e. , they can show a "hump-in-the-middle". We introduce a novel general breadth-first heuristic search algorithm, GBFHS, that unifies both unidirectional and bidirectional search into a single algorithm. It uses knowledge of the edge cost in unit cost domains to stop on first-collision in unidirectional search and in bidirectional search, unlike MM, MMe, and NBS. With no heuristic it expands fewer nodes bidirectionally than Nicholson

Authors

• Mike Barley
• Patricia J. Riddle
• Carlos Linares López
• Sean Dobson
• Ira Pohl

Keywords

No keywords are indexed for this paper.