Fast synthesis of algebraic heuristic functions for video-game pathfinding

摘要: Heuristic search is widely used in games for pathfinding and general planning. High-quality heuristic functions are key to finding a low-cost solution quickly. Commonly used heuristic functions for video-game pathfinding are either manually designed and generic or pre-computed for a specific map. The former fail to take advantage of pathfinding specifics while the latter tend to have a large memory footprint, may require substantial pre-computation and are not portable to other maps or easily presentable to humans. In this work we attempt to combine the best of both approaches by automatically synthesizing well performing pathfinding-specific yet compact and human-readable heuristics. We do so by defining a space of algebraic formulae expressing heuristic functions and then conducting an automated search of the space. To make the synthesis tractable we employ a multi-tier evaluation which allows us to …