BibTex

A two-phase bidirectional heuristic search algorithm

Francisco Javier Pulido, Lawrence Mandow, and J.L. Pérez de la Cruz.
A two-phase bidirectional heuristic search algorithm.
In Frontiers in Artificial Intelligence and Applications. STAIRS 2012- Proceedings of the Sixth Starting AI Researchers' Symposium, volume 241. 2012.

Abstract

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.

BibTex

@incollection{PUL:2012:C,
  affiliation={Universidad de M{\'a}laga Dpto. Lenguajes y Ciencias de la Computaci{\'o}n 29071 M{\'a}laga Spain},
  url={http: //dx.doi.org/10.3233/978-1-61499-096-3-240},
  author={Pulido, Francisco Javier and Mandow, Lawrence and P{\'e}rez de la Cruz, J.L.},
  title={A two-phase bidirectional heuristic search algorithm},
  booktitle={Frontiers in Artificial Intelligence and Applications. STAIRS 2012- Proceedings of the Sixth Starting AI Researchers' Symposium},
  volume={241},
  year={2012},
}
Redmine Appliance - Powered by TurnKey Linux