SoCS Conference 2018 Conference Paper
GBFHS: A Generalized Breadth-First Heuristic Search Algorithm
- Mike Barley
- Patricia J. Riddle
- Carlos Linares López
- Sean Dobson
- Ira Pohl
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