PNBA*: A Parallel Bidirectional Heuristic Search Algorithm - Rios, Luis Henrique Oliveira; Chaimowicz, Luiz (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2011: Anais do VIII Encontro Nacional de Inteligência Artificial, 2011)
A* (A-star) is a heuristic search algorithm used in various domains, such as robotics, digital games, DNA alignment, among others. In spite of its large use, A* can be a computationally expensive depending on the characteristics of the state space and heuristics used. Aiming at improving its performance, in this paper we propose a parallel implementation of a bidirectional version of A*. Named PNBA* (Parallel New Bidirectional A*) the proposed algorithm combines the benefits of bidirectional search and parallel execution in the development of an efficient A* based search algorithm. Experiments performed in different domains show that PNBA* is more efficient than the original A* and NBA*, the bidirectional version of A* it is based on.