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

Abstract

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