用一个模型搞定各种地图路径规划，比传统方法快近两倍。
UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding
- 训练一次通用神经网络，适配不同拓扑结构的地图
- 使A*算法计算量减半，平均解接近最优（误差<3%）
- 适合需要跨场景通用的路径规划应用
基于网格的路径搜索算法（如A*）性能高度依赖启发式函数。近期研究发现，可借助深度神经网络近似考虑障碍物位置与形状的有向启发式。但现有学习方法多假设训练与测试地图来自相同分布（如城市图、室内图），在分布外任务上表现不佳，限制了实际应用中对通用求解器的需求。本文提出一种通用启发式预测器：一次训练即可跨多种未见任务实现良好泛化。大量实验表明，该方法使A*计算开销减少高达2.2倍，且在完全不同于训练集的任务上平均解距最优成本仅差3%，首次达成可学习求解器的这一里程碑。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。