Hierarchical Evolutionary Heuristic A* Search

摘要

A* is an informed pathfinding algorithm that uses a heuristic function to determine the best action to take based on the given information. The performance of A* is heavily dependent on the quality of the heuristic function. The heuristic function determines the search speed, accuracy, and memory consumption. Hence, designing good heuristic functions for specific domains becomes the primary research focus on pathfinding algorithms optimization. However, designing new heuristic functions is a difficult task, especially when they are used to solve complex problems. Moreover, a single heuristic function might not be enough to digest all the provided information and return the best guidance during the search. Previous works suggest that multiple heuristics for complex problems can dramatically speed up the search. However, choosing the appropriate combination of heuristic functions is tricky. Current optimization approaches rely on hand-tuning the parameters via trial and error by the engineers over many iterations. There is a need to reduce the difficulty of designing heuristic functions for search performance maximization. In this paper, we develop a novel heuristic search called Hierarchical Evolutionary Heuristic A* (HEHA*) where multiple heuristics are chosen and evolved using Genetic Algorithm. HEHA* combines the techniques of map abstraction, pattern database, and heuristic improvement. The advantage of HEHA* is twofold: 1) it partitions and reduces the search space based on local features to speed-up the search, and 2) it automatically designs and optimizes heuristics for different local regions to maximize the search performance. We test our algorithm on a widely used grid-based map benchmark to compare with A* variants. Our results show that HEHA* outperforms compared with other pathfinding algorithms in terms of execution time and memory consumption.