Explaining and Improving Formula-Represented Heuristic Functions in Grid Pathfinding

Abstract

Heuristic functions substantially influence heuristic search performance. Recent work used program synthesis to produce high-performance formula-based heuristics, offering a promise of human explanability. In this thesis we investigate the promise and present a tool to improve a given heuristic function while visualizing how each subformula computes heuristic values on video-game-style maps. The visualization algorithm decomposes a heuristic formula into subformulae and associates each with a region of the map, aiding a human expert to modify the heuristic formula to improve search performance. We introduce our approach by applying it in three simple problem instances. To expand upon them, we study the approach in two adversarial settings. First, a video-game map is fixed but once the heuristic formula is improved by a human user for a given pathfinding problem, another problem is selected so that the just improved heuristic provides poor guidance on it. The cycle repeats, improving a heuristic for various pathfinding problems on the given map. The second setting generalizes the cycle across video-game maps by selecting a new map on which the user-improved heuristic provides poor guidance. The cycle repeats, improving a heuristic for several maps. We demonstrate from the adversarial case studies that this approach can improve existing heuristics with respect to both guiding performance and explanability for actual video-game maps. Furthermore, we demonstrate that our approach is able to generate an explainable heuristic formula that works well in general across several actual video-game maps in the adversarial setting. Note that our visualization is more effective when subformulae are short, since the user is more likely to readily understand behavior of formulae with shorter subformulae. Thus we make another contribution by modifying an existing algorithm for heuristic synthesis to generate formulae with short subformulae. We empirically show that imposing an upper bound on subformula size does not degrade search performance of synthesized heuristics. To wrap up, we propose a visualization tool to explain synthesized heuristic formulae on video-game maps. We show examples of applying the tool to improve existing heuristic formulae. Furthermore, we show empirical results of synthesizing heuristic formulae with constrained subformula sizes and show that the constraints impose less effect on average for problems with varying goal locations than for problems with a shared goal location, and in general such constraints do not hurt heuristic's guiding performance while improving their explanability.