Jun, 2022

基于深度神经网络的 Sokoban 计划中左重尾的影响及其策略和价值网络的有效性

PDF
TL;DR通过将传统搜索方法与深度神经网络（DNN）相结合，对 Sokoban 进行了研究，发现 DNN 的策略和价值网络对于搜索具有出色的引导启发作用，特别是策略网络能够避免探索指数大小子树以实现左重尾的多项式缩放，因此随机重启在 DNN-based 搜索方法中也至关重要。
planning problemsdeep neural networksbest-first searchsokobanleft heavy tails
发现论文，激发创造
  • 使用课程驱动的深度强化学习解决困难的人工智能计划实例

    本文介绍了一个基于深度强化学习和课程驱动方法的方法，该方法可以自动发现领域结构并解决 AI 计划中的 PSPACE 完全问题，这是其他现代求解器无法解决的。

    Jun, 2020

  • Sokoban 初始状态的程序化生成

    本文提出了一种使用模式数据库启发式和新颖性来改进搜索方法探索的难度指标的 Beta 系统，可以生成比人类专家设计的更难解的 Sokoban 难题初始状态。

    Jul, 2019

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

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

    Jun, 2023

  • BalMCTS: 在 MCTS 中平衡目标函数和搜索节点，用于约束优化问题

    该论文探讨了针对约束优化问题，采用深度优先搜索算法以在前 n 个解中寻找最优或近似最优解，并提出了一种基于 MCTS 的新型启发式神经网络算法，结合编码约束优化问题和利用图神经网络聚合变量和约束信息的方法，实验结果表明该方法能够快速找到初始的 5 个可行解中与最优解间隔小于 17.63% 的解，并在应用于约束满足问题时，与最先进方法相比，搜索节点数减少不到 5%。

    Dec, 2023

  • 用策略梯度学习经典规划策略

    引入一种新的搜索框架来解决规划问题，该框架能够在解决特定规划问题时在几种前向搜索方法之间交替使用，使用可训练的随机策略来选择搜索方法，进而优化搜索策略，实验结果表明该框架优于传统的最佳优先搜索和均匀策略方法。

    Oct, 2018

  • 具有上下文模型的 Levin 树搜索

    本文介绍了一种基于 Levin Tree Search (LTS) 算法的 LTS+CM 算法，使用参数化的上下文模型并在具有凸保证的基础上优化策略。此算法在 Sokoban，The Witness 和 24 滑动方块 (STP) 等多个问题上表现优异，能够解决魔方等问题，且相对于之前的机器学习技术有很大的进步。

    May, 2023

  • 基于可信度的潜在空间经典规划启发式

    LatPlan 通过无标签图像数据学习领域无关的经典计划器模型，提出了基于可信性的启发式方法 PBH，可以显著提高图像拼图和汉诺塔领域的有效解决方案数量。

    Jun, 2023

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

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

    Jul, 2020

  • 非阻塞批处理 A*（技术报告）

    使用神经网络进行启发式搜索的研究中，Non-Blocking Batch A* 提出了一种新的边界次优方法，该方法可以懒惰地以批处理方式计算神经网络启发式搜索结果，同时使用非神经网络启发式搜索算法进行扩展。在实验中发现，相较于当前阻塞式替代方法，这种微妙但重要的变化可以显著减少扩展次数，而性能与批处理计算的神经网络和快速的非神经网络启发式算法之间的信息差有关。

    Aug, 2022

  • 深度学习在组合优化树搜索中的问题

    本研究提出了一个开源基准套件，对最大独立集问题进行了深入分析，结果表明现有的机器学习算法未能学习最优解的结构，算法技术仍是获得有效解决方案的关键。

    Jan, 2022