Exploração dos paradigmas bidirecional e paralelo em algoritmos de busca heurística

Abstract

A* is a very important heuristic search algorithm in Artificial Intelligence. The use of a heuristic provides a significant reduction in the computational efforts of the search algorithm. However, in many contexts this is not sufficient. In order to better deal with this issue, several extensions of the A* algorithm have been proposed. The goal of this dissertation is to investigate ways of improving the performance of A* through bidirectional and parallel approaches to propose new algorithms. Therefore, the contributions are: a way of organizing the main search algorithms based on A* that have been proposed in the literature and two new parallel bidirectional heuristic search algorithms called PNBA* and BPBNF. We discuss and organize the main extensions of A* in six different classes: bidirectional, incremental, memory-concerned, parallel, anytime and real-time. These classes are not mutually exclusive and represent the main objectives and characteristics of the majority of A* extensions found in the literature. The PNBA* is a parallel implementation of NBA* (a bidirectional heuristic search algorithm) for computational environments with shared memory. Its two search processes are executed in parallel. We show in our experiments that PNBA* is faster than A* and NBA* in three different application domains. The BPBNF algorithm generalizes the idea of PNBA* for more than two processors and also reduces the execution time of PBNF (an algorithm in which it is based on). Our experiments have showed a clear superiority of BPBNF relative to A*. When compared to PBNF in two of the three tested domains, it was also possible to note BPBNF supremacy. Therefore, this dissertation shows the viability and the feasibility of combining the bidirectional and parallel paradigms in order to reduce the run time of A* while keeping its admissibility.