Evolutionary Heuristic A* Search: Pathfinding Algorithm with Self-Designed and Optimized Heuristic Function

摘要

The performance and efficiency of A* search algorithm heavily depends on the quality of the heuristic function. Therefore, designing an optimal heuristic function becomes the primary goal of developing a search algorithm for specific domains in artificial intelligence. However, it is difficult to design a well-constructed heuristic function without careful consideration and trial-and-error, especially for complex pathfinding problems. The complexity of a heuristic function increases and becomes unmanageable to design when an increasing number of parameters are involved. Existing approaches often avoid complex heuristic function design: they either trade-off the accuracy for faster computation or taking advantage of the parallelism for better performance. The objective of this paper is to reduce the difficulty of complex heuristic function design for A* search algorithm. We aim to design an algorithm that can be automatically optimized to achieve rapid search with high accuracy and low computational cost. In this paper, we present a novel design and optimization method for a Multi-Weighted-Heuristics function (MWH) named Evolutionary Heuristic A* search (EHA*) to: (1) minimize the effort on heuristic function design via Genetic Algorithm (GA), (2) optimize the performance of A* search and its variants including but not limited to WA* and MHA*, and (3) guarantee the completeness and optimality. EHA* algorithm enables high performance searches and significantly simplifies the processing of heuristic design. We apply EHA* to multiple grid-based pathfinding benchmarks to evaluate the performance. Our experiment result shows that EHA* (1) is capable of choosing an accurate heuristic function that provides an optimal solution, (2) can identify and eliminate inefficient heuristics, (3) is able to automatically design multi-heuristics function, and (4) minimizes both the time and space complexity.