Learning Heuristic A*: Efficient Graph Search using Neural Network

Abstract

In this paper, we consider the path planning problem on a graph. To reduce computation load by efficiently exploring the graph, we model the heuristic function as a neural network, which is trained by a training set derived from optimal paths to estimate the optimal cost between a pair of vertices on the graph. As such heuristic function cannot be proved to be an admissible heuristic to guarantee the global optimality of the path, we adapt an admissible heuristic function for the terminating criteria. Thus, proposed Learning Heuristic A* (LHA*) guarantees the bounded suboptimality of the path. The performance of LHA* was demonstrated by simulations in a maze-like map and compared with the performance of weighted A* with the same suboptimality bound.