UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding

• URL: http://arxiv.org/abs/2602.23789v1
• Date: Fri, 27 Feb 2026 08:34:56 GMT
• Title: UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding
• Authors: Aleksandr Ananikian, Daniil Drozdov, Konstantin Yakovlev,
• Abstract summary: In this work, we close this gap by designing an universal predictor by designing a model trained once, but capable of generalizing tasks.<n>Our empirical approach shows suggested halves the computational effort of A* by up to a factor of 2.2, while still providing solutions within 3% of average factor of 2.2.
• Score: 43.22339935902436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The performance of search algorithms for grid-based pathfinding, e.g. A*, critically depends on the heuristic function that is used to focus the search. Recent studies have shown that informed heuristics that take the positions/shapes of the obstacles into account can be approximated with the deep neural networks. Unfortunately, the existing learning-based approaches mostly rely on the assumption that training and test grid maps are drawn from the same distribution (e.g., city maps, indoor maps, etc.) and perform poorly on out-of-distribution tasks. This naturally limits their application in practice when often a universal solver is needed that is capable of efficiently handling any problem instance. In this work, we close this gap by designing an universal heuristic predictor: a model trained once, but capable of generalizing across a full spectrum of unseen tasks. Our extensive empirical evaluation shows that the suggested approach halves the computational effort of A* by up to a factor of 2.2, while still providing solutions within 3% of the optimal cost on average altogether on the tasks that are completely different from the ones used for training $\unicode{x2013}$ a milestone reached for the first time by a learnable solver.

Related papers

• Learning Admissible Heuristics for A*: Theory and Practice [8.408138419383747]
  deep learning approaches often disregard admissibility and provide limited guarantees on generalization beyond the training data.<n>This paper addresses both of these limitations. First, we pose learning as a constrained optimization problem and introduce Cross-Entropy Admissibility (CEA), a loss function that enforces admissibility during training.<n>On the Rubik's Cube domain, this method yields near-admissibles with significantly stronger than compressed pattern database (PDB) guidances.
  arXiv  Detail & Related papers  (2025-09-26T17:51:26Z)
• OFA$^2$: A Multi-Objective Perspective for the Once-for-All Neural Architecture Search [79.36688444492405]
  Once-for-All (OFA) is a Neural Architecture Search (NAS) framework designed to address the problem of searching efficient architectures for devices with different resources constraints. We aim to give one step further in the search for efficiency by explicitly conceiving the search stage as a multi-objective optimization problem.
  arXiv  Detail & Related papers  (2023-03-23T21:30:29Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first 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. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Combining Optimal Path Search With Task-Dependent Learning in a Neural Network [4.1712273169097305]
  We show that one can define a neural network representation of path finding problems by transforming cost values into synaptic weights. We show that network learning mechanisms can adapt the weights in the network augmenting the resulting paths according to some task at hand.
  arXiv  Detail & Related papers  (2022-01-26T18:29:00Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Training Binary Neural Networks using the Bayesian Learning Rule [19.01146578435531]
  Neural networks with binary weights are computation-efficient and hardware-friendly, but their training is challenging because it involves a discrete optimization problem. We propose a principled approach for training binary neural networks which justifies and extends existing approaches. Our work provides a principled approach for training binary neural networks which justifies and extends existing approaches.
  arXiv  Detail & Related papers  (2020-02-25T10:20:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.