Predicting A* search algorithm heuristics using neural networks
Ouardi Amine, Mohammed Mestari · 2021 International Conference on Electrical, Computer and Energy Technologies (ICECET) · 2021
At the opposite side of the uninformed search algorithms, performing a systematic search, heuristic search algorithms are based on multiple rules leading it to estimate, in a predictive way, the minimal cost of the path from the current state to the goal. In this sense, A* algorithm is an example of heuristics-based algorithms that can guarantee to find a least-cost path to a goal state if this algorithm is using an “admissible heuristic”. A heuristic is said to be “admissible” if it never overestimates the real path cost from the current state to the goal. Through this article, the main idea consists of developing a Neural Network that can predict those heuristics to further refine the A star algorithm results. During its learning phase, and as inputs, the neural network will have some representative examples in the form of pairs of several problems (graph and destination node) and heuristics$\boldsymbol{(\{\mathrm{P}1,\mathrm{h}1\};\{\mathrm{P}2_{9}\mathrm{h}2\}\ldots\{\text{Pn},\text{hn}\})}$, to finally be able to calculate the best heuristic regardless of the inputs.