Evolutionary Heuristic A* search: Heuristic Function Optimization via Genetic Algorithm Conference Paper uri icon

abstract

  • 2018 IEEE. The performance and efficiency of A search algorithm heavily depend 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 avoids 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 MHAand 3) guarantee the completeness and optimality. EHA algorithm enables high performance searches and significantly simplifies the processing of heuristic design. We apply EHA to two classic AI search problems: the Blocks World and the Sliding Tile Puzzle. Our experiment result shows that EHA 1) is capable to choose 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) minimize both the time and space complexity.

name of conference

  • 2018 IEEE First International Conference on Artificial Intelligence and Knowledge Engineering (AIKE)

published proceedings

  • 2018 IEEE FIRST INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND KNOWLEDGE ENGINEERING (AIKE)

author list (cited authors)

  • Yiu, Y. F., Du, J., & Mahapatra, R.

citation count

  • 22

complete list of authors

  • Yiu, Ying Fung||Du, Jing||Mahapatra, Rabi

publication date

  • September 2018