TransPath: Learning Heuristics for Grid-Based Pathfinding via Transformers

• DOI: 10.1609/aaai.v37i10.26465
• Publication Date: 2023-06-27T18:00:12Z
• Authors: Daniil Kirilenko; Anton Andreychuk; Aleksandr Panov; Konstantin Yakovlev
• Keywords: Heuristics; Consistent heuristic; Null-move heuristic

Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that widely employed to represent environments in robotics, video games, etc. Instance-independent heuristics grid graphs, Manhattan distance, do not take obstacles into account, and thus led by such performs poorly obstacle-rich environments. To this end, we suggest learning instance-dependent heuristic proxies supposed notably increase efficiency search. The first proxy learn is correction factor, ratio between instance-independent cost-to-go estimate perfect one (computed offline at training phase). Unlike absolute values function, which was known before, factor utilizes knowledge heuristic. second path probability, indicates how likely cell lying shortest path. This can be Focal Search framework as secondary heuristic, allowing us preserve guarantees bounded sub-optimality solution. We both suggested a supervised fashion with state-of-the-art neural networks containing attention blocks (transformers). conduct thorough empirical evaluation comprehensive dataset planning tasks, showing techniques i) reduce computational effort A* up 4x while producing solutions, whose costs exceed those optimal solutions less than 0.3% average; ii) outperform competitors, include conventional from search, weighted well learnable planners. project web-page is: https://airi-institute.github.io/TransPath/.