Learning to Learn from Search

The effectiveness of heuristic search when solving pathfinding problems often relies on the accuracy of the heuristic function. While it has been shown that heuristic functions can be learned using deep reinforcement learning, it is assumed that learning is only performed once and that the heuristic function remains fixed when attempting to solve a problem instance. However, heuristic search, itself, produces data from which a heuristic function can learn. For example, given the nodes expanded during search, Bellman updates of the states associated with those nodes can be quickly computed. In this paper, we introduce Learning to Learn from Search (L2LFS), an algorithm that trains a sequence of heuristic functions, where each heuristic function in the sequence learns from data obtained when performing heuristic search with the previous heuristic function. We will show that data obtained during search can be encoded into a fixed length encoding and that this data can be used to train a subsequent heuristic function that better estimates Bellman updates when compared to one that does not use this encoding. Future work will refine and repeat this process multiple times in hopes of yielding iteratively improving heuristic functions. computed. This data can be used to improve a subsequent heuristic function that would then be used in a subsequent search. This process can then be repeated with the objective of yielding iteratively improving heuristic functions. In this paper, we introduce learning to learn from search (L2LFS), an algorithm that builds on DeepCubeA (Agostinelli et al. 2019) to train heuristic functions to improve their cost-to-go estimation (i. e. , learn) based on data obtained from search. Data obtained during search that is used to improve a subsequent heuristic function is referred to as the search summary. A heuristic function that also takes a search summary as an input is referred to as a summaryaware heuristic function (SAHF). In this paper, we make the following contributions: • Showing that search summaries can be encoded into a fixed-length representation. • Leveraging this encoding to train SAHFs that learn from search. • Showing that SAHFs better estimate the Bellman updates of states seen during a subsequent search when compared to a heuristic function that is not summary-aware.

Authors

• Forest Agostinelli
• Shahaf S. Shperberg Ben Gurion University

Keywords

No keywords are indexed for this paper.