PNBA*: A Parallel Bidirectional Heuristic Search Algorithm

• Luis Henrique Oliveira Rios UFMG
• Luiz Chaimowicz UFMG

Resumo

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.

Referências

Burns, E., Lemons, S., Zhou, R., and Ruml, W. (2009). Best-first heuristic search for multi-core machines. In Proceedings of IJCAI, pages 449–455.

Davis, H. W., Pollack, R. B., and Sudkamp, T. (1984). Towards a better understanding of bidirectional search. In AAAI, pages 68–72.

Dutt, S. and Mahapatra, N. R. (1993). Parallel a* algorithms and their performance on hypercube multiprocessors. In IPPS, pages 797–803.

Grama, A. Y. and Kumar, V. (1993). A survey of parallel search algorithms for discrete optimization problems. ORSA Journal on Computing, 7.

Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on, 4(2):100–107.

Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., and Mitoh, K. (1994). A fast algorithm for finding better routes by ai search techniques. In VNIS, pages 291–296.

Kaindl, H. and Kainz, G. (1997). Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. (JAIR), 7:283–317.

Kishimoto, A., Fukunaga, A. S., and Botea, A. (2009). Scalable, parallel best-first search for optimal sequential planning. In ICAPS. AAAI.

Klunder, G. A. and Post, H. N. (2006). The shortest path problem on large-scale real-road networks. Networks, 48(4):182–194.

Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1):97–109.

Korf, R. E. (1996). Artificial intelligence search algorithms. Technical report, University of California.

Nilsson, N. J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann Publishers, San Francisco.

Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Pijls, W. and Post, H. (2009a). A new bidirectional search algorithm with shortened postprocessing. European Journal of Operational Research, 198(2):363–369.

Pijls, W. and Post, H. (2009b). Yet another bidirectional algorithm for shortest paths. Technical Report EI 2009-10, Erasmus University Rotterdam, Econometric Institute.

Pohl, I. (1969). Bi-directional and heuristic search in path problems. Technical Report 104, SLAC (Stanford Linear Accelerator Center), Stanford, California.

Pohl, I. (1971). Bi-directional search. In Meltzer, B. and Michie, D., editors, Machine Intelligence, volume 6, pages 124–140, Edinburgh. Edinburgh University Press.

Politowski, G. and Pohl, I. (1984). D-node retargeting in bidirectional heuristic search. In AAAI, pages 274–277.

Rios, L. and Chaimowicz, L. (2010). A survey and classification of a* based best-first heuristic search algorithms. In SBIA 2010, volume 6404, pages 253–262. Springer.

Russell, S. J. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Pearson Education.

Sohn, A., Sato, M., Sakai, S., Kodama, Y., and Yamaguchi, Y. (1994). Parallel bidirectional heuristic search on the em-4 multiprocessor. In Proceedings of the 6th Symposium on Parallel and Distributed Processing, pages 100–109.

Whangbo, T. K. (2007). Efficient modified bidirectional a* algorithm for optimal route-finding. In IEA/AIE, volume 4570, pages 344–353. Springer.