Speeding Up Heuristic Function Synthesis via Extending the Formula Grammar

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Student Papers

Heuristic search algorithms have long been used in video-game AI for unit navigation and planning. The quality of the solution they produce depends substantially on the quality of the heuristic function they use. Recent work automatically synthesized human-readable heuristic functions for a given pathfinding map. This enables tailoring a heuristic to the map but is expensive since each map requires an independent synthesis run. In this paper we propose and evaluate re-using elements of heuristics synthesized for one map in synthesizing heuristics for another map. We do so by adding parts of a synthesized heuristic back to the grammar that defines the space of heuristic functions for the synthesis.

10.1609/socs.v12i1.18594