Heuristic search algorithms, e.g. A*, are the commonly used tools for pathfinding on grids, i.e. graphs of regular structure that are widely employed to represent environments in robotics, video games etc. Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles into account and, thus, the search led by such heuristics performs poorly in the obstacle-rich environments. To this end, we suggest learning the instance-dependent heuristic proxies that are supposed to notably increase the efficiency of the search. The first heuristic 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 (computed offline at the training phase). Unlike learning the absolute values of the cost-to-go heuristic function, which was known before, when learning the correction factor the knowledge of the instance-independent heuristic is utilized. The second heuristic proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path. This heuristic can be utilized in the Focal Search framework as the secondary heuristic, allowing us to preserve the guarantees on the bounded sub-optimality of the solution. We learn both suggested heuristics in a supervised fashion with the state-of-the-art neural networks containing attention blocks (transformers). We conduct a thorough empirical evaluation on a comprehensive dataset of planning tasks, showing that the suggested techniques i) reduce the computational effort of the A* up to a factor of $4$x while producing the solutions, which costs exceed the costs of the optimal solutions by less than $0.3$% on average; ii) outperform the competitors, which include the conventional techniques from the heuristic search, i.e. weighted A*, as well as the state-of-the-art learnable planners.

基于冲突的搜索（CBS）是一种广泛使用的算法，用于最佳地求解多代理探路（MAPF）问题。 CBS的核心思想是运行层次搜索，当在高级别的解决方案树上探索候选者的树时，在低级别上进行了针对特定代理的个人计划（受某些约束）进行。为了使运行时间的权衡取得最佳性，设计了有限的子最佳CB的不同变体，这改变了CBS的高级和低级搜索程序。此外，CBS的任何时间变体都存在将焦点搜索（FS）应用于CBS的高级搜索 - 任何时间BCB。然而，当我们简单地重新启动cbs的cbs与较低的亚XB绑定时，没有对这种算法的性能的全面分析。这项工作旨在填补这一空白。此外，我们介绍并评估了另一个在CBS上使用FS的CBS的随时随地。从经验上讲，我们证明其行为主要与任何时间BCB所证明的行为不同。最后，我们比较这两种算法从头开始，并表明在两个级别的CBS上使用焦点搜索在广泛的设置中可能是有益的。

通过深度神经网络实现的A*算法的启发式函数的优化通常是通过最大程度地减少正方形根损失的目标成本估计值来完成的。本文认为，这不一定会导致对A*算法的更快搜索，因为其执行依赖于相对值而不是绝对值。作为缓解措施，我们提出了L*损失，该损失是A*搜索中过度扩展状态的数量上限。当用于优化最先进的深度神经网络的L*损失，用于在索科班等迷宫领域的自动化计划和带有传送的迷宫，可显着改善解决问题的比例，基础计划的质量，并降低扩大状态的数量达到约50％

复杂的推理问题包含确定良好行动计划所需的计算成本各不相同的状态。利用此属性，我们提出了自适应亚go搜索（ADASUBS），这是一种适应性地调整计划范围的搜索方法。为此，ADASUBS在不同距离上产生了不同的子目标。采用验证机制来迅速滤除无法到达的子目标，从而使人专注于可行的进一步子目标。通过这种方式，ADASUBS受益于计划的效率更长的子目标，以及对较短的计划的良好控制。我们表明，ADASUB在三个复杂的推理任务上大大超过了层次规划算法：Sokoban，The Rubik的Cube和不平等现象证明了基准INT，为INT设定了新的最先进。

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

这篇简短的评论旨在使读者熟悉与计划，调度和学习有关的最新作品。首先，我们研究最先进的计划算法。我们简要介绍神经网络。然后，我们更详细地探索图形神经网络，这是一种适合处理图形结构输入的神经网络的最新变体。我们简要描述了强化学习算法和迄今为止设计的一些方法的概念。接下来，我们研究了一些成功的方法，结合了用于路径规划的神经网络。最后，我们专注于不确定性的时间计划问题。

蒙特卡洛树搜索（MCT）是设计游戏机器人或解决顺序决策问题的强大方法。该方法依赖于平衡探索和开发的智能树搜索。MCT以模拟的形式进行随机抽样，并存储动作的统计数据，以在每个随后的迭代中做出更有教育的选择。然而，该方法已成为组合游戏的最新技术，但是，在更复杂的游戏（例如那些具有较高的分支因素或实时系列的游戏）以及各种实用领域（例如，运输，日程安排或安全性）有效的MCT应用程序通常需要其与问题有关的修改或与其他技术集成。这种特定领域的修改和混合方法是本调查的主要重点。最后一项主要的MCT调查已于2012年发布。自发布以来出现的贡献特别感兴趣。

\ textit {约束路径发现}的经典问题是一个经过充分研究但充满挑战的主题，在各个领域，例如沟通和运输等各个领域的应用。权重限制了最短路径问题（WCSPP），作为仅具有一个侧面约束的约束路径查找的基本形式，旨在计划成本最佳路径，其权重/资源使用受到限制。鉴于问题的双标准性质（即处理路径的成本和权重），解决WCSPP的方法具有一些带有双目标搜索的共同属性。本文在约束路径查找和双目标搜索中利用了最新的基于A*的最新技术，并为WCSPP提供了两种精确的解决方案方法，两者都可以在非常大的图表上解决硬性问题实例。我们从经验上评估了算法在新的大型和现实的问题实例上的性能，并在时空指标中显示出它们比最新算法的优势。本文还调查了优先级队列在被a*的约束搜索中的重要性。我们通过对逼真的和随机图进行了广泛的实验来展示，基于桶的队列没有打破打盘的方式可以有效地改善详尽的双标准搜索的算法性能。

传统上，启发式搜索一直依赖于手工制作或编程派生的启发式方法。神经网络（NNS）是更新的强大工具，可用于从州学习复杂的映射到成本到启发式方法。但是，他们缓慢的单个推理时间是一个很大的开销，可以在优化的启发式搜索实现中大大减少计划时间。最近的一些作品描述了利用NN的批处理计算的方法，以减少计划中的开销，同时保持（子）最优性的界限。但是，所有这些方法在建立批处理的同时以“阻止”方式使用了NN启发式方法，并且忽略了通常可以使用的快速计算可接受的启发式方法（例如现有的经典启发式启发术）。我们介绍了一种非阻滞批次A*（NBBA*），这是一种有界的次优方法，它懒洋洋地分批计算NN启发式方法，同时允许通过非NN启发式启发术告知扩展。我们展示了与当前的阻止替代方案相比，这种微妙但重要的变化如何导致扩展大幅减少，并看到该性能与计算出的NN和快速非NN启发式的批处理差异有关。

机器学习（ML）管道中的组合优化（CO）层是解决数据驱动决策任务的强大工具，但它们面临两个主要挑战。首先，CO问题的解通常是其客观参数的分段常数函数。鉴于通常使用随机梯度下降对ML管道进行训练，因此缺乏斜率信息是非常有害的。其次，标准ML损失在组合设置中不能很好地工作。越来越多的研究通过各种方法解决了这些挑战。不幸的是，缺乏维护良好的实现会减慢采用CO层的速度。在本文的基础上，我们对CO层介绍了一种概率的观点，该观点自然而然地是近似分化和结构化损失的构建。我们从文献中恢复了许多特殊情况的方法，我们也得出了新方法。基于这个统一的观点，我们提出了inferpopt.jl，一个开源的朱莉娅软件包，1）允许将任何具有线性物镜的Co Oracle转换为可区分的层，以及2）定义足够的损失以训练包含此类层的管道。我们的图书馆使用任意优化算法，并且与朱莉娅的ML生态系统完全兼容。我们使用视频游戏地图上的探索问题来证明其能力。

基于冲突的搜索（CBS）是一种流行的多试路径查找（MAPF）求解器，该求解器采用低级单位代理计划者和高级约束树来解决冲突。绝大多数现代MAPF求解器都专注于通过各种策略减少这棵树的大小来改善CB，几乎没有修改低级计划者的方法。现有CBS方法中的所有低级计划者都使用未加权的启发式启发式方法，次优的CBS方法还使用冲突启发式启发式启发式来帮助高级搜索。与普遍的信念相反，我们表明，通过以特定方式加权冲突，可以更有效地使用启发式成本的启发式。我们介绍了这样做的两个变体，并证明这种变化在某些情况下可以导致2-100倍的加速。此外，据我们所知，我们展示了优先规划和有限的次优的CB的第一个理论关系，并证明我们的方法是它们的自然概括。

This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.

近年来，深入的强化学习（RL）在各种组合搜索领域（例如两人游戏和科学发现）中都取得了成功。但是，直接在计划域中应用深度RL仍然具有挑战性。一个主要的困难是，如果没有人工制作的启发式功能，奖励信号除非学习框架发现任何解决方案计划，否则奖励信号将保持零。随着计划的最小长度的增长，搜索空间变为\ emph {指数更大}，这是计划实例的严重限制，该实例的计划最小计划长度为数百到数千步。以前的学习框架可以增强使用深神经网络和额外生成的子观念的图形搜索在各种具有挑战性的计划域中取得了成功。但是，生成有用的子目标需要广泛的领域知识。我们提出了一种独立于域的方法，该方法可以通过图值迭代来增强图形搜索，以求解针对域特有的求解器无法实现的硬计划实例。特别是，我们的方法还没有仅从发现的计划中获得学习信号，而是从未达到目标状态的失败尝试中学习。图值迭代组件可以利用本地搜索空间的图形结构并提供更有信息的学习信号。我们还展示了如何使用课程策略来平滑学习过程并对图形值迭代量表的完整分析并实现学习。

本文使用基于采样的方法RRT*研究，以在复杂的环境中重新配置一组连接的瓷砖，在这些环境中可能存在多个障碍。由于目标应用程序是自动构建离散的自动构建，因此使用移动机器人进行了蜂窝结构，因此有一些限制可以确定可以拾取哪些图块以及在重新配置期间可以将其放下的块。我们将我们的方法与两种算法作为全球和本地计划者进行了比较，并表明我们能够在具有不同程度的障碍空间的环境中使用合理数量的样本找到更有效的构建序列。

Searching for a path between two nodes in a graph is one of the most well-studied and fundamental problems in computer science. In numerous domains such as robotics, AI, or biology, practitioners develop search heuristics to accelerate their pathfinding algorithms. However, it is a laborious and complex process to hand-design heuristics based on the problem and the structure of a given use case. Here we present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigation heuristics from data by leveraging recent advances in imitation learning and graph representation learning. At training time, we aggregate datasets of search trajectories and ground-truth shortest path distances, which we use to train a specialized graph neural network-based heuristic function using backpropagation through steps of the pathfinding process. Our heuristic function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5\% on average, can be directly applied in diverse graphs ranging from biological networks to road networks, and allows for fast planning in time-critical robotics domains.

尽管实用的求解器在各种NP完整域中取得了成功，例如SAT和CSP以及使用深度强化学习来解决诸如GO之类的两人游戏，但某些类别的Pspace-Hard计划问题仍然遥不可及。由于硬实例的指数搜索空间，即使是精心设计的域专用求解器也可能会迅速失败。结合了传统搜索方法的最新作品，例如最佳优先搜索和蒙特卡洛树搜索，以及深度神经网络（DNN）的启发式方法，已经显示出有希望的进步，并且可以解决超出专业求解器以外的大量艰苦计划实例。为了更好地理解这些方法为何起作用，我们研究了基于DNN的最佳优先搜索的政策和价值网络的相互作用，并展示了该策略网络的惊人有效性，并通过价值网络进一步增强了价值网络，作为指导启发式的启发式启发式程序。搜索。为了进一步理解现象，我们研究了搜索算法的成本分布，发现索科巴实例可以具有重尾的运行时分布，左侧和右侧都有尾巴。特别是，我们首次展示了\ textit {左尾巴}的存在，并提出了一个抽象的树模型，可以从经验上解释这些尾巴的外观。该实验表明，政策网络是一种强大的启发式指导搜索的关键作用，这可以通过避免探索成倍的尺寸的子树来导致左尾部具有多项式缩放。我们的结果还证明了与传统组合求解器中广泛使用的随机重新启动的重要性，用于避免左和右重尾巴的基于DNN的搜索方法。

我们考虑空间路径规划问题。与从划痕优化新计划的经典解决方案相比，我们以与地面真理障碍物位置访问完整地图，我们以可分散的方式从数据中学到策划员，允许我们利用过去数据的统计规则。我们提出了空间规划变压器（SPT），给出了障碍地图学习通过规划长期空间依赖性来生成动作，与以迭代方式通过卷积结构传播信息的先前数据驱动规划策规范。在地面真理地图对代理人未知的情况下，我们利用预先训练的SPTS在端到端的框架中，该框架具有映射器和计划内置的映射器和规划仪的结构，允许无缝概括到分配外地图和目标。 SPTS以处理和导航任务的所有设置均优于最先进的可分散规划者，导致7-19％的绝对提高。

Steiner树问题（STP）在图中旨在在连接给定的顶点集的图表中找到一个最小权重的树。它是一种经典的NP - 硬组合优化问题，具有许多现实世界应用（例如，VLSI芯片设计，运输网络规划和无线传感器网络）。为STP开发了许多精确和近似算法，但它们分别遭受高计算复杂性和弱案例解决方案保证。还开发了启发式算法。但是，它们中的每一个都需要应用域知识来设计，并且仅适用于特定方案。最近报道的观察结果，同一NP-COLLECLIAL问题的情况可能保持相同或相似的组合结构，但主要在其数据中不同，我们调查将机器学习技术应用于STP的可行性和益处。为此，我们基于新型图形神经网络和深增强学习设计了一种新型模型瓦坎。 Vulcan的核心是一种新颖的紧凑型图形嵌入，将高瞻度图形结构数据（即路径改变信息）转换为低维矢量表示。鉴于STP实例，Vulcan使用此嵌入来对其路径相关的信息进行编码，并基于双层Q网络（DDQN）将编码的图形发送到深度加强学习组件，以找到解决方案。除了STP之外，Vulcan还可以通过将解决方案（例如，SAT，MVC和X3C）来减少到STP来找到解决方案。我们使用现实世界和合成数据集进行广泛的实验，展示了vulcan的原型，并展示了它的功效和效率。

学习一项难以捉摸的问题域的知情启发式功能是一个难以捉摸的问题。虽然有了已知的神经网络架构来代表这种启发式知识，但它不明显地了解了哪些具体信息以及针对理解结构的技术有助于提高启发式的质量。本文介绍了一种网络模型，用于学习一种能够通过使用注意机制通过最佳计划模仿与状态空间的遥远部分相互关联的启发式机制，这大幅提高了一种良好的启发式功能的学习。为了抵消制定难度越来越困难问题的方法的限制，我们展示了课程学习的使用，其中新解决的问题实例被添加到培训集中，反过来有助于解决更高复杂性的问题和远远超出所有现有基线的表演，包括古典规划启发式。我们展示了其对网格型PDDL结构域的有效性。

Monte Carlo Tree Search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarise the results from the key game and non-game domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.