# TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers

arXiv: https://arxiv.org/abs/2212.11730 · HTML: https://mlsanity.com/paper/2212.11730/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 22 Dec 2022.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [A Survey on Visual Transformer](https://mlsanity.com/paper/2012.12556/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates](https://mlsanity.com/paper/1708.07120/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Path Planning using Neural A* Search](https://mlsanity.com/paper/2009.07476/) (2020)
- [Learning Heuristic Search via Imitation](https://mlsanity.com/paper/1707.03034/) (2017)
- [Theta*: Any-Angle Path Planning on Grids](https://mlsanity.com/paper/1401.3843/) (2014)
- [Learning Heuristic Selection with Dynamic Algorithm Configuration](https://mlsanity.com/paper/2006.08246/) (2020)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)
- [Fully Convolutional Search Heuristic Learning for Rapid Path Planners](https://mlsanity.com/paper/1908.03343/) (2019)
- [GAN Path Finder: Preliminary results](https://mlsanity.com/paper/1908.01499/) (2019)

## Built on by (most cited first, 13 of 13)

- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs](https://mlsanity.com/paper/2502.18663/) (2025)
- [Neural Potential Field for Obstacle-Aware Local Motion Planning](https://mlsanity.com/paper/2310.16362/) (2023)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [SLOPE: Search with Learned Optimal Pruning-based Expansion](https://mlsanity.com/paper/2406.04935/) (2024)
- [A Training Data Recipe to Accelerate A* Search with Language Models](https://mlsanity.com/paper/2407.09985/) (2024)
- [DAA*: Deep Angular A Star for Image-based Path Planning](https://mlsanity.com/paper/2507.09305/) (2025)
- [CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)](https://mlsanity.com/paper/2509.19162/) (2025)
- [Contrastive Diffusion Guidance for Spatial Inverse Problems](https://mlsanity.com/paper/2509.26489/) (2025)
- [UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding](https://mlsanity.com/paper/2602.23789/) (2026)
- [NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem](https://mlsanity.com/paper/2604.16967/) (2026)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)
- [FlexPath: Adapting Learned Connectivity Guidance to Path Preferences](https://mlsanity.com/paper/2606.10167/) (2026)

## Abstract (arXiv)

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