In a graph search algorithm, a given environment is represented as a graph comprising a set of feasible system configurations and their neighboring connections. A path is generated by connecting the initial and goal configurations through graph exploration, whereby the path is often desired to be optimal or suboptimal. The computational performance of the optimal path generation depends on the avoidance of unnecessary explorations. Accordingly, heuristic functions have been widely adopted to guide the exploration efficiently by providing estimated costs to the goal configurations. The exploration is efficient when the heuristic functions estimate the optimal cost closely, which remains challenging because it requires a comprehensive understanding of the environment. However, this challenge presents the scope to improve the computational efficiency over the existing methods. Herein, we propose reinforcement learning heuristic A* (RLHA*), which adopts an artificial neural network as a learning heuristic function to closely estimate the optimal cost, while achieving a bounded suboptimal path. Instead of being trained by precomputed paths, the learning heuristic function keeps improving by using self-generated paths. Numerous simulations were performed to demonstrate the consistent and robust performance of RLHA* by comparing it with the existing methods.

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.