AAAIDec, 2022

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

PDF
TL;DR本文提出了一种使用神经网络学习实例依赖的启发式代理来提高在障碍物环境下的 A * 算法性能的方法，并针对该算法进行了全面实验评估，结果表明该算法在减少计算量和保证较小的解代价方面具有优异的性能。
heuristic search algorithmsinstance-dependent heuristic proxiescorrection factorpath probabilityneural networks
发现论文，激发创造
  • 学习 A * 启发式算法

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

    Apr, 2022

  • 使用有界次优图形转换器加速多智体规划

    该论文提出了一种名为 Graph Transformer 的学习组件，作为加速规划的启发式函数，证明了其完备性和有限次最优性，同时经实验证明，在相对少的代理问题实例中训练的 Graph Transformer 可以很好地推广到更多代理的问题实例中，并且性能优于现有方法。

    Jan, 2023

  • 学习图搜索启发式

    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

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

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

    Oct, 2023

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

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

    Jul, 2020

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

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

    Jan, 2022

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

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

    Sep, 2022

  • 学习基础模型以解决路径规划问题的启发函数

    通过深度强化学习训练启发式函数，该研究提出了一种新型基础模型，能够在不进一步微调的情况下适应各种新领域，从而在复杂路径规划问题中为人工智能驱动的解决方案建立了新的效率和适应性标准。

    Jun, 2024

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

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

    Jun, 2023

  • 使用深度强化学习学习公共交通网络设计和改进的启发式方法

    利用深度强化学习和图神经网络学习低级启发式算法可有效优化公共交通网络设计，在合成和现实城市场景中均取得最佳结果并降低成本。

    Apr, 2024