ICLRApr, 2022

学习 A * 启发式算法

PDF
TL;DR本文利用神经演算法推导出高效的启发式路径搜索算法，结合 Dijkstra 算法和 A * 算法中的一致的启发函数，并将其推广应用于图形中的路径搜索问题，结果表明相较于 Dijkstra 算法，应用基于学习到的 A * 算法中的启发函数的改进搜索在无损质量的情况下，实现了大幅的速度提升。
path findinggraphsneural algorithmic reasoningdijkstra's algorithma* search algorithm
发现论文，激发创造
  • 学习图搜索启发式

    PHIL (Path Heuristic with Imitation Learning) is a neural architecture and training algorithm that uses imitation learning and graph representation learning to discover graph search and navigation heuristics from data, reducing the number of explored nodes by 58.5% compared to state-of-the-art methods on benchmark datasets and allowing for fast planning in time-critical robotics domains.

    Dec, 2022

  • NP 难问题中启发式近似算法的（不）可扩展性

    本文探讨利用神经网络逼近完全信息启发式函数的可行性，发现对于 NP 难问题，其网络规模可能呈指数级上升，并建议研究方向转向寻找其他机器学习与启发式搜索相结合的方法。

    Sep, 2022

  • 优化规划启发式算法，以排序而非估算目标开销

    本论文重新审视了启发式函数在规划中的模仿学习中的必要和充分条件，并针对给定的前向搜索算法的变体提出了一族基于排名的损失函数。另外，从学习理论的角度讨论了为什么优化成本 - 目标 h * 是不必要困难的。实验比较在多样化的问题集上明确地支持了得出的理论。

    Oct, 2023

  • TransPath：通过 Transformer 学习基于网格的路径搜索算法启发式

    本文提出了一种使用神经网络学习实例依赖的启发式代理来提高在障碍物环境下的 A * 算法性能的方法，并针对该算法进行了全面实验评估，结果表明该算法在减少计算量和保证较小的解代价方面具有优异的性能。

    Dec, 2022

  • 使用神经网络学习特定搜索空间启发式算法

    建议并评估了一种系统，该系统学习了一种用于基于正向搜索的满足经典规划的神经网络启发式函数。我们的系统从头开始学习目标估计器，并生成训练数据。通过反向回归搜索或通过反向搜索从给定或猜测的目标状态生成培训数据。

    Jun, 2023

  • 在神经网络中将最优路径搜索与任务相关的学习结合

    使用神经网络表示寻径问题并将路径的成本值转化为神经元的连接权重，结合网络学习机制，在线自适应更新权重以解决具有不同要求的任务。该算法复杂度与 Bellman Ford 算法相同，可用于寻找最优路径和路径增强。

    Jan, 2022

  • 在图上学习组合优化算法

    本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

    Apr, 2017

  • 通过模仿学习启发式搜索

    使用 SaIL 特有的算法，训练启发式策略来遍历搜索树中的节点，以减少搜索次数。实验证明 SaIL 算法在实时规划环境中优于现有算法，这为学习体现 ' 快速找到可行解并随时间增量调整 ' 的启发式方法铺平了道路。

    Jul, 2017

  • 学习使用不确定拓扑地图进行规划

    本文采用一种数据驱动的策略和基于图像的规划，应用于 3D 环境中的导航系统，通过机器学习方法实现了图像哈希表上的最短路径规划，比传统符号算法更优秀。

    Jul, 2020

  • 使用可接受的神经启发式学习可微分程序

    研究解决学习特定领域语言中表达的可微分函数的问题，通过将神经网络的不同类视为对程序空间的松弛，并在一系列分类任务中实例化遗传算法和分支界限搜索来发现自然解释和有竞争力的程序分类器。

    Jul, 2020