This work describes a new best-first bidirectional heuristic search algorithm with two phases. The new algorithm is based on a critical review of the basic search reduction operations in previous algorithms like BS* or Switch-A*. The general guideline is to let search fronts meet as close to midground as possible. In a first phase, search is discontinued at nodes as soon as the opposite frontier is met, terminating when one of the fronts runs out of open nodes. In a second phase, unidirectional search is conducted from the discontinued nodes until an optimal solution can be guaranteed. The new algorithm is tested on random instances of the 15-puzzle and on path-finding problems. A significant improvement in efficiency is observed when compared with other bidirectional algorithms.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com