A Neural Network for Decision Making in Real-Time Heuristic Search

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Short Papers

Most real-time heuristic search algorithms solve search problems by executing a series of episodes. During each episode the algorithm decides an action for execution. Such a decision is usually made using information gathered by running a bounded, heuristic-search algorithm. In this paper we report on a real-time search algorithm that does not use a search algorithm to choose the next action to be applied. Rather, it uses a neural network whose input is local information about the search graph, comparable to the information that would be used by a bounded search algorithm. We describe a supervised learning approach to training such a network. Our three types of maps from the Moving AI benchmarks, shows that our algorithm is, in some cases, substantially superior to algorithms that have access to the same information about the graph. One of our most important conclusions is that our extended set of features important: indeed, using features beyond the heuristic seems key to achieving good performance.

10.1609/socs.v9i1.18468